Every now and then we see a flurry of news about quantum computing. But one recent piece rather focused the mind: a company claimed to have an encryption algorithm you will soon need, when quantum computers render today’s encryption algorithms useless.
Now to the skeptic, such a claim raises questions. Right away there is curiosity. What is quantum computing (Figure 1)? Is it real? If so, how does it work? And what does it have to do with cryptography? Then there are more personal questions. Is quantum computing going to force me to change my design practices? Am I going to have to learn this stuff?
It turns out these are not easy questions to explore. The literature is mostly in one of two genres. The first form is aimed at general readers, and treats quantum mechanics rather like a satanic cult: dark, possibly dangerous, and you wouldn’t understand anyway. This makes it rather tricky to draw conclusions.
The second genre is entirely different but equally helpful, written by experts to impress other experts. This form is easily identified by several touchstones: Turing machines, Richard Feynman’s name, Hilbert space, and Hadamard gates, all mentioned within about 75 words, followed by a blizzard of equations with unfamiliar and unexplained nomenclature. Of course you remember what |0> means!
Three Parallel Universes
One reason this gets so complicated is that important contributions to quantum computing have come from three disciplines with very different vocabularies and interests. The idea began with theoretical physicists. Notably in 1980, physicist Paul Benioff of Argonne National Laboratory described how some quantum-mechanical effects could be used to implement a Turing machine. Two years later, iconic physicist Richard Feynman also raised the question of a computer using quantum behavior.
The thread was picked up by an entirely different group: computer scientists and mathematicians. Taking the basic ideas of a quantum bit (a qbit) and of reversible unitary transforms (which they called quantum gates, or qgates) from physics, computer scientists explored what kinds of computing you might be able to do if ideal qbits and qgates actually existed. They found cases where such theoretical computers could be far faster than conventional digital computers.
This result prompted experimental physicists—a third group entirely—to begin trying to build physical devices that could approximate ideal qbits and qgates. That has been a long, resource-eating pursuit that still has not proved that a useful quantum computer is physically possible. But it has offered tantalizing hints.
So what is this theoretical computer that we should be interested? For clarity, let’s first eliminate some things that it is not. A quantum computer is not a conventional computer simulating quantum-mechanical phenomena. Nor is it a conventional digital computer build from some post-Moore’s-Law transistors so tiny that they store or switch individual quanta of energy.
Instead, quantum computers are machines based on unique behaviors predicted by quantum mechanics and utterly like the behavior of classical systems. One is the ability to constrain a particle or group of particles so that some aspect of it has only two discrete quantum base states—call them 0 and 1. (We will dispense with the funny-looking brackets here.) The aspect might be the spin on an electron, the polarization of a photon, or the charge on a quantum dot, for example.
Second, quantum computing depends on superposition—the counterintuitive ability of a quantity to be in a combination of both 0 and 1 base states simultaneously, until you measure it. Once you measure it, the state reverts to either 0 or 1, and all the rest of the information disappears. Quantum mechanics properly expresses the superimposed state as a sum of the two base states, each multiplied by a complex coefficient and always with a total magnitude of 1. This can also be imagined as a unit vector starting at the origin and ending somewhere on a sphere called the Bloch Sphere (Figure 2). A key here is that the square of the complex coefficient on the 0 base states represents the probability that you will measure the qbit to be in the 0 base state, and likewise for the 1 base state. And when you make a measurement, you will always come up with either exactly a 0 state or exactly a 1 state.
This is important because it allows a qbit to be, conceptually, both a 0 and a 1 simultaneously. And hence a register made up of n qbits can simultaneously “contain” all the possible binary numbers n bits long. This allows a quantum computer to perform a single operation not on just one n-bit integer, but on all possible n-bit integers at once—very substantial parallelism as n gets large.
Third, quantum computing depends on the ability of a qgate to change those coefficients—and hence your probability of measuring any particular number—in predictable ways. If you start out with all the coefficients in all the qbits equal, and then measure all the qbits in the register, you are equally likely to come up with any string of bits between all zeros and all ones, inclusive. But by running this initial state through a carefully designed sequence of qgates, the quantum computer can manipulate the coefficients so that the pattern you are most likely to measure at the output qbits represents the result of a computation—for instance, it might be highly probable that you will measure the bits of a number that is a perfect square.
A Computer on Paper
But what does all this have to do with real computing? To answer that, we have to turn our attention from the theoretical physicists to the computer scientists and mathematicians. To do useful work, we would have to be able to place a register of qbits into a known superposition of states. We would need qgates, maybe wires, and some kind of output.
All this is easy for computer scientists—they can just assume that these ideas exist in real life. They do have to make concessions to quantum mechanics, though. In order not to violate the laws of quantum physics, computer scientists must require that qgates be reversible—you can put a result into the output and get the correct input values at the input. And they must insist that the qgates be unitary transforms. Sparing the matrix algebra, this roughly means that when you put the state of a qbit through a qgate, the state you get out will certainly measure as either a 0 or a 1: the sum of the probabilities from the squares of those coefficients still has to add to exactly one.
Notice that these qgates, even in theory, are very unlike normal Boolean logic gates. Most Boolean functions aren’t reversible, for instance. There is no way to infer the inputs to a NAND gate from its output unless the output happens to be 0. And of course logic gates only work with 1s and 0s, while the qgates work by rotating the vector inside the Bloch sphere. There really is no close analogy beyond the names.
The computer scientists worked out that a very small set of qgates is sufficient for emulating a Turing machine—just the set of one-input qgates and a single two-input qgate. The most often used example of the two-input qgate is the controlled NOT (CNOT) gate. This reversible function either flips the vector state of a qbit or leaves it unchanged, depending on the state of a second qbit. It is rather like the quantum analogy to an XOR gate.
We still haven’t really answered the question of how you would use one of these things. The answer is that if you string enough qgates together in the right pattern, you can prepare the input qbits to represent all possible numbers in your domain of inputs, and at the output of the qgate array you can, in theory, measure the bits that represent values of some useful function.
An example might help. In 1994, mathematician Peter Shor, then at Bell Labs, developed an algorithm for factoring very large numbers using quantum subroutines. This factoring is a vital problem in applied math because there is no analytical solution: the only way is trial and error, and you can only make the algorithm faster by choosing more cleverly the numbers to try. So when you make the input number very large, the amount of trial and error becomes enormous. This is the basis of RSA-like cryptography algorithms, not at all incidentally. RSA and elliptic-curve cyphers are hard to crack specifically because it is so hard to factor huge numbers.
Shor’s algorithm combined some traditional computing with two quantum functions that directly accelerate the trial-and-error part by, in effect, trying all possible numbers at the same time (Figure 3). One of these quantum functions performs modular exponentiation, and the other does a quantum version of a fast Fourier transform. For reasons only a mathematician could love, if we put in a set of n qbits prepared so that together they represent all the possible binary numbers up to length n, then in the qgates various superimposed states cancel each other—much like interference between two coherent light beams—and we are left with a distinct pattern of states in the output register.
This pattern isn’t a prime factor—it is only an intermediate step that allows us to calculate a possible prime factor. That calculation is done by measuring the qbits—remembering that we are only likely, not certain, to measure the most probably state of each qbit—and then to apply a lot of conventional computing in an ordinary CPU to produce the possible factor, and then to test to see if it is really a factor or a false result.
All of this may sound hopelessly complex and infeasible. But the ability of the quantum exponentiation and FFT algorithms to work on all possible powers of 2 simultaneously to find the largest prime factor makes Shor’s algorithm faster than conventional computing for large numbers using even rather slow theoretical quantum subroutines.
Shor’s algorithm makes a dramatic example because it is both bafflingly unlike conventional computing and potentially enormously important. But it is not alone. The US National Institute of Standards and Technology (NIST) maintains a large library of quantum computing algorithms in its Quantum Algorithm Zoo, at math.nist.gov/quantum/zoo/.
Are these algorithms just math exercises? It is too early to tell for sure. But in practice, researchers have actually built laboratory quantum calculators with a few working qbits. These machines have successfully factored the number 15 (at IBM in 2001), unsurprisingly finding 3 and 5, and the current world’s record, 21 (done by a cross-institutional team in 2012). So for small numbers the idea works. Usefully large numbers will have to wait for machines with many more qbits. And that brings up the question of practicality.
The Path to Realization
In order to construct workable quantum computing devices, we have to achieve a number of implementation milestones. We have to build working qbits—not just five, but thousands. We have to figure out the quantum gates, and the equivalent of wires—unless we can make the gates act directly on the state in the input quantum register. All of these are huge undertakings, and the schedule for their achievement is unpredictable.
The challenges, unfortunately, come not so much from the novelty of the problems as from the laws of quantum mechanics and classical physics. Perhaps the foremost, and least familiar, is called decoherence. The job of a qbit is to hold a physical thing—an ion, a packet of photons, or an electron, perhaps–in place so that we can manipulate and eventually measure a quantized quantity like charge or spin. For that quantity to behave in a quantum way instead of a classical-physics way, we have to be able to restrict it to a superposition of the two pure base states we’ve been calling 0 and 1.
But the nature of quantum systems is to couple to things around them, vastly increasing the number of possible base states. Physicists call that blurring away from the pure states decoherence. An analogy might be a coherent laser beam in a waveguide striking an impurity and blurring from a superposition of two modes into completely incoherent light. The job of the physical qbit design is to stave off decoherence for as long as possible.
This means, in effect, that even a single qbit is a demanding laboratory apparatus, possibly involving lasers or RF transmitters, closely controlled electric and magnetic fields, exact dimensions, special materials, and maybe cryogenic cooling. Using it is essentially performing an elaborate experimental procedure. Even with all this work, today “as long as possible” is measured in tens of microseconds. So you have very little time to perform quantum computations before your qbits have lost their coherence. It is as if the information leaks out.
Today these limitations preclude large quantum registers or computations that require more than a few microseconds. But research is underway to implement far more extensive arrays of qbits and qgates using microelectronic fabrication techniques.
The work is itself somewhat incoherent, though, because there is no agreement on what physical phenomenon to use to hold the quantum state. There are qbit designs that quantize the polarization of photons, the charge on electrons trapped in quantum dots, the net spin of super-cooled trapped ions, the charge in a device called a transmon, and various other approaches.
The kind of qbit you choose will naturally determine how you implement quantum gates. For instance you might use the interaction of RF pulses with internal spins in trapped molecules, or the interaction of beam splitters with photon modes in waveguides. Clearly the subject lies deep within the boundaries of experimental physics. And as mentioned, implementation of qbits or qgates requires considerable external equipment, from digital logic to lasers or RF transmitters and antennas to cryogenic coolers.
Qbit implementation will also dictate how you measure the state of the qbit. You may need a super-sensitive photometer or bolometer, a resistance bridge, or some other incredibly sensitive device to measure the qbits and resolve the superposition state into a base state. And this process of measuring the qbit state brings up another issue unfamiliar to conventional computing: getting the wrong answer.
There are two main kinds of problems with extracting a base state from a qbit. The first is that you are measuring a quantum superposition, not a classical quantity. Assuming the qbit has remained coherent, you will get one or the other of the base states, but you can’t be sure which: you can only be sure that the probability of your getting a particular state will be the square of the coefficient of that state in the superposition. If you measure a qbit in exactly the same state a hundred times, you should expect to get a distribution of 0s and 1s that converges toward the squares of the coefficients.
So you don’t know that the base state you measured on any give try is the one that had the highest probability. After you have read out a quantum output register by measuring the bits—thereby setting them all to base states—you have three choices. You can bet that you have the correct answer and go ahead. You can check through conventional computing, as Shor’s algorithm does, to see if the number you read is in fact a valid solution. Or you can repeat the computation a large number of times, either sequentially or in parallel, and take the most frequent result. It is also possible to design your computation so that the answer you want is the probability distribution of the base states rather than a particular binary number. In that case too, repetition is in order.
That is true even in a theoretical perfect quantum computer. But in a real implementation, there is another issue: good old classical noise. Even if everything goes well, there are no decoherent qbits, and the computation is designed to resolve the answer you want with very high probability, you are still observing the qbits by attempting to measure very, very small physical quantities. Noise happens. Once again, the only solution is either to detect an error by further calculation, or to perform the computation so many times that you are willing to accept any remaining uncertainty in the result. The concept of a guaranteed right answer is rather foreign to quantum computing.
If this is not painting a rosy picture of the future of quantum computing, take heart. Discovery is under way to find the best choice for qbits—though the answer may turn out to be algorithm-dependent. Microelectronics folk are working on miniaturization of quantum components through new materials and structures—allowing very large arrays of quantum computing devices that could be mass-produced like CPU chips. Computer scientists are developing the equivalent of assemblers and compilers that can convert an algorithm into an arrangement of quantum registers and qgates in a particular technology.
Is it worth it? Here is one data point. Shor estimated that a modest hybrid quantum/conventional computer could crack a powerful RSA cypher faster than a conventional computer could encrypt it. There have been similar results projected for tasks like sorting, and untangling other similarly hard math-based problems. So yes, there is enough promise here that researchers will keep working. But it might not be good to hold your breath.
For Further Reading
For comparison purposes, explore an FFT IP block for FPGAs.