Quantum computing is a technology that’s often discussed vaguely. This is partly due to the technology’s complexity, but also because the world was waiting for real-world applications.
It would appear that in some capacity, this wait is over.
Quantum approaches are already becoming valuable resources in the computing field, and even the pursuit of valuable quantum machines has caused us to extend our grasp into the unknown.
This development within quantum computing is a central point of Matthias Troyer’s keynote speech at ISC 2021. A distinguished scientist at Microsoft, Troyer is on the cutting edge of quantum. We sat down with him to discuss what quantum is, what it can bring to our current traditional computing architectures, and even what quantum’s limitations are.
What kind of problems will quantum machines be able to solve? And why can quantum computing solve these problems better than traditional architectures?
Those are good questions. When we look deep down to the level of atoms and electrons, nature behaves quantum mechanically, which is described by the laws of quantum mechanics. These are different from what we are used to in the classical world.
When you have a classical object — like my phone here or a ball — it is like a particle that sits at one location. When you have an electron, however, it can be a particle, — such as when it hits an object. But when it moves, it behaves like a wave. This duality of the particles and waves is described by the laws of quantum physics.
Now imagine, what if bits in a computer could be waves? That they have a certain wave amplitude for being zero and one, and thus can be in both states. We can then think of computations, where registers are not fixed to one value, but they can be in a wavelike superposition of exponentially many different values. We can use that to compute exponentially faster and solve problems that are classically intractable.
Any classical problem can, in principle, also be solved on quantum hardware. One could always use a quantum register just like a classical one. But one would not do that because qubits are much more expensive than classical bits and operations are much slower on quantum computers because quantum computers are so much more complex. However, if one puts the quantum registers into this wave-like superposition of many values, you might have to do far fewer operations. And that's how the quantum computer can win.
There are problems that you will be able to solve on future quantum hardware in days for which a classical computer — even one the size of the planet — would take a billion years to solve.
How can we implement quantum approaches on traditional HPC architecture? What challenges arise?
That question takes us into an interesting direction. We sometimes find that an algorithm we have developed for quantum computers gives us ideas for how to run them also on a classical computer. This does not work for all algorithms. If I want to naively simulate a quantum algorithm on classic hardware, then I have to apply the algorithm to all the values in the superposition. And that takes exponential time.
But if I don't just simulate the quantum algorithm at the microscopic level of the qubits, but view them more abstractly, then we've had cases where the same algorithmic idea can also be implemented as a probabilistic classical algorithm. Thus, we have invented new classical algorithms, which capture the same idea as the quantum algorithm almost as well on classic hardware.
Initially quantum researchers may have found a quantum algorithm that is exponentially better than the best-known classical algorithm, and celebrate it as a success. But then they may look deeper and say, "Oh… I can do this almost as well on classical hardware, that is not as exciting”. But that's when I would come and say "Actually, you have now made exponential progress on classic hardware."
And since our goal is actually solving problems, that's an even bigger success. We don’t need to wait for quantum computers to realize the value of this algorithm, we can run it today. We can solve problems with quantum ideas today on classical hardware!
We would not have had those ideas if we had not thought about quantum computing. When people assume that a certain problem is intractable, they don't even think about new solutions. But then they come to us and say, "I have this really important problem that is totally intractable. I can't solve it classically. Could quantum help me?" And we then jointly think about this problem. And once you start to think of radically new ways of solving problems, there's a big potential for disruption. Just the idea of quantum computing can already unlock a mindset of disruption.
Will building a quantum computer help us better understand quantum mechanics?
Oh, yes, definitely. It will because there will always be open questions in quantum physics. For example, there is the famous Schrödinger’s cat paradox that you may have you heard of.
Imagine a radioactive atom that may decay. You place that atom in a room with a cat. And in the room there is a hellish contraption: a vial with poison gas and a hammer. If the atom decays, the hammer falls, hits the vial, the gas escapes, and the cat dies.
But now, as time progresses, the equations of quantum mechanics tell us that the atom is in a wave-quantum superposition of having decayed and not decayed. The hammer is then also in a wave-like quantum state: it has fallen or not. The vial then is in a similar quantum state of being broken and not. And you end up with a cat that is in a quantum state of being both dead and alive at the same time. This is Schrodinger’s cat.
Have you seen Schrödinger’s cats running around? No. And the reason is that, as we scale up a quantum system, something will always interact with the system. When that happens it will go from a wave-like state to a particle-like state, a well defined single state in a fixed location. Just looking at Schrödinger’s cat will turn it into a cat that is either dead or alive.
Building the quantum computer, we now want to avoid this process that we call “decoherence” . We need to find a way to protect the quantum state in a macroscopic computer, to keep the wave-like state alive for the duration of the computation. And to do that, we have to understand all of the mechanisms that turn a wave-like quantum state into a classical one. Building a quantum computer will thus give us deep insight into how the crossover from the quantum world to the classic one happens.
Shall we move onto quantum applications?
Yes! There is a big disruptive potential here, since quantum algorithms can solve certain problems much better than the classic ones. There are many problems, from climate prediction to protein folding, where people say quantum can help. But we are up against two challenges.
First of all, as mentioned before, quantum operations are much slower than classical ones. With a classic computer being able to process 10 billion times more operations per second than a quantum computer, we need to look at problems where the quantum computer needs to perform significantly fewer operations than the classical one.
In principle, when the problem size gets large, quantum computers will always win, because of a scaling advantage called quantum speedup. But, unless there is significant, exponential, quantum speedup, the crossover point — where the slow quantum computer will beat the fast classic one because it has to do far less work — may be a millennium or a billion years or more.
One main point of my keynote is such guidelines that we have determined for what is needed for a quantum computer to beat a classic one in a short time of days or weeks. A second point we see immediately is that the I/O bandwidth of the quantum computer is far less than that of a classical computer, because we have fewer qubits and the qubit operations are slower. That means quantum computers will not be useful for big data; they have an even bigger big data problem than classical computers. Quanrtum computers are useful for small data problems — for big compute problems on small data with exponential quantum speedup.
One of the applications of quantum computers is the well-known application to cryptanalysis with Shor’s algorithm. But that is not an opportunity but a a threat. And the community counters that threat by developing new cryptography schemes, so-called post-quantum cryptography that are resistant to quantum attacks.
The real impactful application of quantum will be for solving quantum science problems. Quantum science problems can be exponentially hard to solve classically, but will map perfectly to quantum hardware. These can be problems like designing novel materials, with switchable properties, or chemicals. We can use quantum computers to design new catalysts, for clean combustion, efficient fertilizer production, for carbon fixation, and many other applications.
This is the first time in millennia that we have a totally new technology. The way our laptops work, the way HPC machines work, it is all digital logic. The same logic behind an abacus., We have computed in essentially the same way for the klast four thousand years. Quantum computing, however, is a totally new way of computing... in ways that we've never done before, and that alone is exciting.
