Computing With Quantum Physics

Dr. Dobb's Special Report December 2000

Quantum computing offers great promise for very powerful systems

By David Cory and Raymond Laflamme

All of today's computers obey the laws of classical mechanics -- the laws ruling the macroscopic world. With these rules, you can classify the difficulty of solving mathematical problems and discover that some of them are essentially intractable. These hard to solve problems can be put to use. For example, RSA encryption, used in most secure Internet transactions, relies on the fact that the code cannot be broken without great difficulty using classical computers. But can you change the rules of computing? Quantum mechanics is the theory that reigns at the microscopic level and it might allow much more efficient algorithms. Indeed, for selective problems, quantum computing has been shown to be exponentially more powerful than known classical algorithms. Over the last few years, small prototype quantum computers have even been built, and we are slowly learning how to program them.

Bits and Qubits

All information on a classical computer is translated into strings of bits. They are physically implemented by the presence or absence of charges in capacitors and can be represented by strings of 0 and 1. In today's computer, the storage of each bit of information requires roughly 1 million electrons. In a quantum computer, each bit is replaced by a qubit (quantum bit): a two-level state of a single particle that obeys the rules of quantum mechanics such as in the magnetic state of a single electron. One of the characteristic rules of quantum mechanics is that the state can exist in a superposition (see Figure 1), where the particle simultaneously exists in both computational states; that is, 0 and 1. In many respects, it then acts as though there were two copies, and a type of computational parallelism unique to quantum mechanics results.

As in Figure 1, a qubit can be represented by an arrow from the origin to the surface of a unit sphere. There are two angular degrees of freedom for a qubit corresponding to the longitude or superposition () and the latitude or quantum phase, (). The two extreme states (oriented along the vertical z-axis) may be compared to classical states, and the superposition states are those where the vector is positioned in between these and can be represented by the equation cos|0>+eⁱ sin|1>.

Simultaneous Computational States

Part of the reason that a quantum computer would be so powerful is the way quantum parallelism scales with the number of qubits. There are 2ⁿ distinct computational states for n classical bits, and, as in Figure 2, all of these can be created simultaneously with only n qubits. To classically run through all 2ⁿ possible values of n bits requires a straightforward set of 2ⁿ trials; but with a quantum processor, a superposition state that simultaneously contains all 2ⁿ states can be created through only n rotations, and using only n qubits.

The magnitude of this exponential scaling is seen most easily through a comparison between the resources necessary to create all possible computational states of an n-bit classical system and an n-qubit quantum system. Figure 3 compares the ability of classical and quantum processors to manipulate information for very large systems. As the size of quantum processors increases, the size of their computational space increases exponentially. The result is that quantum computers of only a few tens of qubits cannot be simulated on even the most powerful classical computers. The horizontal axis is the number of qubits in the quantum computer, and the vertical axis is the required size for a classical computer that could contain the same amount of information. The Earth example is of course a fiction; the assumed sample is a volume of water the size of the Earth from which the two protons in each molecule are used as classical bits.

A surprising point is that for certain problems, the largest classical computers are unable to simulate the dynamics of quantum computers containing only tens of qubits. Indeed, a general simulation of a 100-qubit quantum computer will probably always remain out of reach for classical computers. The ability of a quantum system to simultaneously span an exponentially large number of states following a linear number of manipulations is one important component of the power of quantum computers.

Probability and Interference

A second characteristic of quantum mechanics is the probabilistic nature of measurement. A measurement of a qubit (described in Figure 1, for instance) would give a random answer of either up or down. The probability of each result is dependent on the angle describing the superposition (q). For our n-qubit superposition of Figure 2, the probabilistic result is one number from the classical list, each element of the list having probability 1/2ⁿ. The design of quantum algorithms not only takes advantage of quantum parallelism, but also requires making the desired information available with high probability. Thus, a critical part is to ensure that the answer will be in a classical state at the end of the computation. This is achieved through a third characteristic of quantum mechanics -- quantum interference. This permits the manipulation not only of strings of qubits, but also of the sum of strings of qubits, and, therefore, allows the simultaneous calculation of many classical problems at once. Superposition of states can contain a large amount of information, but only a small part of this information can be extracted in a single experiment. Quantum interference is used to give high probability to measure the desired information corresponding to the computational result.

Parallelism and Interference

The interplay of quantum parallelism and quantum interference for efficient computations is best seen through an example. In the accompanying text box entitled "The Magic of Quantum Computers," we describe how factoring large integers can be accomplished on a quantum computer by finding the periodicity of the function ya ^{mod n}. Although each number ya ^{mod n} is present in the superposition, they can be known only through a measurement that would destroy this superposition. The periodicity can, however, be determined by a Fourier transform without an intermediate step of observing any of these numbers. This transform generates constructive interference of the correct value of the periodicity and destructive interference for others. This also shows another puzzling feature of a quantum computer: You cannot look at intermediate computations without destroying the delicate quantum superpositions that so efficiently contain the computation.

Toffoli Gates

We can understand all classical algorithms through a set of universal gates -- fundamental building blocks generating any desired logic operation. Indeed, the NAND gate by itself is universal for classical computation. It turns out that NAND gates are irreversible: Knowledge of the output state is not sufficient to know the input. This seems to create an incompatibility with the rules of quantum mechanics, which are reversible. However, classical logic can be embedded in reversible gates. For example, Toffoli gates, which keep track of all the information (see Figure 4), can be used to implement the actions of more common logic operations. On a quantum computer, these gates act on quantum superpositions as well as classical states. Toffoli gates and rotations of single qubits are universal for quantum computation.

Challenges Ahead

Although a quantum processor is potentially exponentially more efficient at manipulating information, a quantum computer does not speed up every computation, and it has been proven not to improve algorithms of certain problems. To date, there are three general areas where a quantum computer would be significantly more powerful than a classical computer:

• Factoring large numbers.
• Unordered searches.
• Efficient simulation of quantum dynamics.

Peter Shor's integer factorization algorithm is justifiably the most famous of these, both because it solves an important problem (breaking RSA encryption) and because it offers an exponential speedup. This is the algorithm that is explained in "The Magic of Quantum Computers."

Unfortunately, even though we know some of the areas where a quantum computer is more powerful than a classical computer, we still do not have one. To date, there has been a variety of small quantum processors made in research laboratories with complexities reaching 7 qubits. The challenge is that we do not yet have sufficient control over quantum systems to keep them from losing the quantum correlations and reverting back to classical systems. Initially, there was a great deal of doubt as to whether the fragility of quantum systems would permit quantum computation. Fortunately, progress in understanding how to make quantum information robust through quantum error correcting codes has given hope that we might scale up devices superseding their classical counterparts. It has even been shown that an accuracy threshold exists (approximately one error per 10,000 gates), so there is a reasonable expectation that the quantum processing of information can be made robust. Today, there are many laboratories pursuing a wide range of quantum transducers that with improved engineering, may yet become quantum computers. This is still a long road, but the first steps have been taken.

More Information

Brown, Julian. Mind, Machine and Multiverse: The Quest for the Quantum Computer, Simon & Schuster, 1999.

Bennett, Charles H. and David P. DiVincenzo. Nature, 404, 247-255, 2000.

Cory, D., et al., "NMR-based Quantum Information Processing: Achievements and Prospects." http://xxx.lanl.gov/abs/quantph0004104/.

Lloyd, S. "Quantum Mechanical Computers." Scientific American, April, 1995.

Steane, A. "Quantum Computing," Progress in Physics, 61, 117-173, 1998.

Also, for an extensive list of publications in the field, see Quantum Physics archives on the Web at http://xxx.lanl.gov/.

DDJ