The memory of a classical computer is a string of 0s and 1s, and a classical computer can do calculations on only one set of numbers at once. The memory of a quantum computer is a quantum state which can be in a superposition of many different numbers at once. A classical computer is made up of bits, and a quantum computer is made up of quantum bits, or qubits. A quantum computer can do an arbitrary reversible classical computation on all the numbers simultaneously, and also has some ability to produce interference, constructive or destructive, between various different numbers. By doing a computation on many different numbers at once, then interfering the results to get a single answer, a quantum computer has the potential to be much more powerful than a classical computer of the same size.
The most famous example of the extra power of a quantum computer is Peter Shor's algorithm for factoring large numbers. Factoring is an important problem in cryptography; for instance, the security of RSA public key cryptography depends on factoring being a hard problem. Despite much research, no efficient classical factoring algorithm is known.
Shor actually solved a related problem, the discrete log. Suppose we take a number x to the power r and reduce the answer modulo n (i.e., find the remainder r after dividing xr by n). This is straightforward to calculate. It is much more difficult to find the inverse - given x, n, and y, find r such that xr = y (mod n). For factoring, all we need to do is consider y=1 and find the smallest positive r such that xr = 1 (mod n). Shor's quantum algorithm to do this calculates xr for all r at once. Since xl+r = xl (mod n), this is a periodic function with period r. Then when we take the Fourier transform, we will get something that is peaked at multiples of 1/r. Luckily, there is an efficient quantum algorithm for the Fourier transform, so we can then find r.
There are many proposals for how to build a quantum computer, with more being made all the time. The 0 and 1 of a qubit might be the ground and excited states of an atom in a linear ion trap; they might be polarizations of photons that interact in an optical cavity; they might even be the excess of one nuclear spin state over another in a liquid sample in an NMR machine. As long as there is a way to put the system in a quantum superposition and there is a way to interact multiple qubits, a system can potentially be used as a quantum computer. In order for a system to be a good choice, it is also important that we can do many operations before losing quantum coherence. It may not ultimately be possible to make a quantum computer that can do a useful calculation before decohering, but if we can get the error rate low enough, we can use a quantum error-correcting code to protect the data even when the individual qubits in the computer decohere.
Back to Daniel Gottesman's home page
October 29, 1997