Quantum Computing

On May 7, 2019, the U.S. Department of Energy announced a contract with Cray Inc. to build the "Frontier" supercomputer at Oak Ridge National Laboratory. Frontier is anticipated to be operational in 2021 and, with a performance of greater than 1.5 exaflops, will then be the world's most powerful computer. One exaflop is a thousand petaflops or a quintillion, (1,000,000,000,000,000,000), double precision floating point (“0” and “1”) operations per second. That's a lot of computing power... a lot of flops! Even at that, there will still be some fairly straightforward mathematical problems that even Frontier will not be able to solve.

For instance, take the fairly simple factoring equation:

M = p * q

where a number M that is the product of the multiplication of two large prime numbers. If Frontier is given M and asked to find the two prime numbers it is derived from, it is a phenomenally difficult problem to solve. There is no other way to find it than to divide by a sequence of prime numbers until you have the solution. This problem is so difficult that it is used as the basis of all sophisticated encryption today. Today's codes of encryption are so unbreakable that it would take billions of years for even Frontier to break down a very large number M. Pretty secure.

The question that begs is “Will we ever have computing power able to solve not only a simple problem such as this, but even more challenging practical conundrums that currently elude us?” And the answer is a likely “yes”, but probably not for a few more years once we progress into quantum computing. The difference between today's classical computers and tomorrow's quantum computers is that while both break the world down into the bits “0” and “1”, quantum computers go one step further with the addition of a factor of “0” and “1” in superpostion to one another - called a Quantum bit or a qubit. In contrast, quantum computing will be able to find a solution to the most difficult M = p * q problem in a matter of seconds rather than billions of years.

Quantum computing is fundamentally different in that it is based on two laws in the quantum mechanical world - superposition and entanglement. A quantum superposition state of two pure states is a linear combination of these states with the coefficients representing the probability distribution of the pure states inherent in their quantum mechanical nature. Quantum entanglement describes the “entangled interaction” of qubits so that you cannot describe the state of two entangled qubits independently; if you measure one qubit, the measurement result of the other qubit is determined on the outset. Measurement results on qubits are still stochastic due to their quantum mechanical nature. These two effects in quantum computing, superposition and entanglement are responsible for the first step in the exponential speed boost provided by quantum computers.

The speed boost of quantum computing, in short, starts with a “spread” of all given pure states into superposition, so that every state is equally likely to appear. The second step is to “translate” the solution of the problem defined by a quantum mechanical algorithm into circuits using a set of qubits and quantum mechanical elementary gates. Additionally, oracles implement a Boolean function on a set of qubits representing the input of the problem. Final measurements on the set of qubits, with a high number of repetitions, provides a probability distribution as an interpretation of the final state being a superposition of all pure states of all involved qubits. The output of the quantum algorithm is a single pure combination of the set of qubits derived from the distribution; for example, one could take the combination with the highest frequency. Thus, quantum computing can only achieve a better performance compared to classical computers if an analysis of the quantum algorithm proves correct results and shows a lower complexity in the expected number of steps a set of gates and oracles needs to be applied. It’s all about the algorithms!

The first prototypes for quantum computers are already here – like the image of the one pictured above. So what are we going to do with them? Quantum computers promise to run calculations far beyond the reach of any conventional supercomputer. They might revolutionize the discovery of new materials by making it possible to simulate the behavior of matter down to the atomic level. Or they could upend cryptography and security by cracking otherwise invincible codes. There is even hope they will supercharge artificial intelligence by crunching through data more efficiently.

But there considerable reason for caution in our expectations too. It isn’t entirely obvious how useful even a perfectly functioning quantum computer would be. It wouldn't simply speed up any task you threw at it; in fact, for many calculations, it may actually be slower than classical machines. Only a handful of algorithms have so far been devised where a quantum computer would clearly have an edge. And even for those, that edge might be short-lived. The most famous quantum algorithm is for finding the prime factors of an integer like the M = p * q example above. Many common cryptographic schemes rely on the fact that this is hard for a conventional computer to do. But cryptography could adapt, creating new kinds of codes that don’t rely on factorization.

So when will we get there? The best and brightest minds in the field believe that the revolution will not really peak until a new generation of students and hackers get to play with some of the early quantum computing prototypes. Quantum computers require not only different programming languages but a fundamentally different way of thinking about what programming is. The first useful machines are still likely several years away, and that’s assuming the problem of managing and manipulating a large collection of qubits won’t ultimately prove intractable. Enthusiasm could sour if the first quantum computers are slow to find a practical use, but those on the leading edge continue to go forward with confidence and the hope that only a discoverer exploring the frontier of the unknown can fully appreciate.