Quantum computing

A quantum computer is a device that computes using superpositions of quantum states. Small quantum computers have recently been built, and progress is continuing. It is widely suspected that if large-scale quantum computers can be built, they will be able to solve certain problems faster than any classical computer. Quantum computers are different from classical computers such as quantum dot computers, DNA computers, and computers based on transistors, even though all of these use quantum mechanical effects other than state superpositions.

The Structure of Quantum Computers

In quantum mechanics, it is possible for a particle to be in two places at once, or in two states at once. This is like Schrödinger's cat: it is both alive and dead at the same time. This ability to be in multiple states simultaneously is called superposition.

A classical computer has a memory made up of bits. Each bit holds either a one or a zero. The device computes by manipulating those bits. A quantum computer maintains a set of qubits. A qubit can hold a one, or a zero, or a superposition of one and zero. In other words, it can hold both a one and a zero at the same time. The quantum computer computes by manipulating those qubits.

A quantum computer can be implemented using any small particle that can have two states. Quantum computers might be built from atoms that are both excited and not excited at the same time. They might be built from photons of light that are in two places at the same time. They might be built from protons and neutrons that have a spin of "up" and "down" at the same time.

A microscopic molecule can contain many thousands of protons and neutrons. It might be used as a quantum computer with many thousands of qubits.

The Power of Quantum Computers

It can be very difficult to take a large number and find all its prime factors. A quantum computer could solve this problem very quickly. If a number has n bits (is n digits long when written in binary), then a quantum computer with just over 2n qubits can find its factors. It can also solve a related problem called the discrete log problem. This ability would allow a quantum computer to break many of the cryptographic systems in use today. Most of the popular public key ciphers could be quickly broken, including forms of RSA, ElGammal and Diffie-Helman. These are used to protect secure Web pages, encrypted email, and many other types of data. Breaking these would be significant. The only way to make an algorithm like RSA secure would be to make the key size larger than the largest quantum computer that can be built. It seems likely that it will always be possible to build classical computers that have more bits than the number of qubits in the largest quantum computer. If that's true, then algorithms like RSA could be made secure.

If a quantum computer were based on the protons and neutrons in a molecule, it might be too small to see, but could factor integers with many thousands of bits. A classical computer running known algorithms could also factor those integers. But to do it before the sun burns out, it would have to be larger than the known universe. That would be somewhat inconvenient to build.

Not surprisingly, quantum computers could also be useful for running simulations of quantum mechanics. The speedup could be just as large as for factoring. This could be of great practical benefit to many physicists.

This dramatic advantage of quantum computers is currently known to exist for only those three problems: factoring, discrete log, and quantum physics simulations. There is one other problem where quantum computers have a smaller, though significant advantage. It is quantum database search, and is sometimes referred to as the square root speedup.

Suppose there is a problem, such as finding the password that decrypts a file. The problem has these four properties:

The only way to solve it is to guess answers repeatedly and check them

There are n possible answers to check

Every possible answer takes the same amount of time to check

There are no clues about which answers might be better. Generating possibilities randomly is just as good as checking them in some special order

For problems with all four properties, it will take an average of n/2 guesses to find the answer using a classical computer. The time for a quantum computer to solve this will be proportional to the square root of n. That can be a very large speedup, reducing some problems from years to seconds. It can be used to attack symmetric ciphers such as 3DES and AES. But it is also easy to defend against. Just double the size of the key for the cipher. There are also more complicated methods for secure communication, such as using quantum cryptography.

There are currently no other practical problems known where quantum computers give a large speedup over classical computers. Research is continuing, and more problems may yet be found.

The History of Quantum Computers

1981 - Richard Feynman gave the first proposal for using quantum phenomena to perform computations. It was in a talk he gave at the First Conference on the Physics of Computation at MIT. He pointed out that it would probably take a classical computer an extremely long time to simulate a simple experiment in quantum physics. If so, then simple quantum systems are essentially performing huge calculations all the time. It might even be possible to harness that for something useful.

1985 - David Deutsch, at the University of Oxford, described the first universal quantum computer. Just as a universal Turing machine can simulate any other Turing machine efficiently, so the universal quantum computer is able to simulate any other quantum computer with at most a polynomial slowdown. This raised the hope that a simple device might be able to perform many different quantum algorithms.

1994 - Peter Shor, at AT&T's Bell Labs in New Jersey, discovered a remarkable algorithm. It allowed a quantum computer to factor large integers quickly. It solved both the factoring problem and the discrete log problem. Shor's algorithm could theoretically break many of the cryptosystems in use today. It's invention sparked a tremendous interest in quantum computers, even outside the physics community.

1996 - Lov Grover, at Bell Labs, discovered the quantum database search algorithm. The quadratic speedup isn't as dramatic as the speedup for factoring, discrete logs, or physics simulations. However, the algorithm can be applied to a much wider variety of problems. Any problem that had to be solved by random, brute-force search, could now have a quadratic speedup.

1995 - Peter Shor proposed the first scheme for quantum error correction. This is an approach to making quantum computers that can compute with large numbers of qubits for long periods of time. Errors are always introduced by the environment, but quantum error correction might be able to overcome those errors. This could be a key technology for building large-scale quantum computers that work. These early proposals had a number of limitations. They could correct for some errors, but not errors that occur during the correction process itself. A number of improvements have been suggested, and active research on this continues.

1997 - Neil Gershenfeld and Isaac Chuang at MIT published the first paper on quantum computers based on bulk spin resonance, or thermal ensembles. The computer is actually a single, small molecule, which stores qubits in the spin of its protons and neutrons. Trillions of trillions of these can float in a cup of water. That cup is placed in a nuclear magnetic resonance machine, similar to the the magnetic resonance imaging machines used in hospitals. This room-temperature (thermal) collection of molecules (ensemble) has massive amounts of redundancy, which allows it to maintain coherence for thousands of seconds, much better than many other proposed systems.

The largest quantum computer built to date, as of mid 2001, is 7 qubits.

How They Work

A classical computer with three bits of memory can only store three digital ones and zeros. At a given time, it might contain the bits "101". A quantum computer with 3 qubits can actually store 16 analog values, paired up to form 8 complex numbers. At a given time, it might contain this:

    State        Amplitude    Probability

                  (a+ib)        (a²+b²)

     000       0.37 + i 0.04      0.14

     001       0.11 + i 0.18      0.04

     010       0.09 + i 0.31      0.10

     011       0.30 + i 0.30      0.18

     100       0.35 + i 0.43      0.31

     101       0.40 + i 0.01      0.16

     110       0.09 + i 0.12      0.02

     111       0.15 + i 0.16      0.05

If there had been n qubits, then this table would have had 2ⁿ rows. For an n in the hundreds, that is more rows than there are atoms in the known universe.

The first column shows all possible states for three bits. A classical computer can hold only one of those patterns at a time. A quantum computer can be in a superposition of all 8 states at the same time. The second column shows the "amplitude" for each of the 8 states. These 8 complex numbers are a snapshot of the contents of a quantum computer at a given time. During computation, these 8 numbers will change and interact with each other. In this sense, a 3-qubit quantum computer has far more memory than a 3-bit classical computer.

However, there is no way to directly see these 8 numbers. When the algorithm is finished, a single measurement is made. The measurement returns a simple 3-bit string, and erases all 8 of the complex numbers. The returned string is generated randomly. The third column of the table gives the probability for each possible string. In this example, there is a 14% chance that the returned string will be "000", a 4% chance it will be "001", and so on. Each probability is found by squaring the complex number. The square of (a+ib) is (a²+b²). The 8 probabilities add up to 1.

Typically, an algorithm for a quantum computer will initialize all the complex numbers to equal values, so all the states will have equal probabilities. The list of complex numbers can be thought of as an 8-element vector. On each step of the algorithm, that vector is modified by multiplying it by a matrix. The matrix comes from the physics of the actual machine, and will always be invertible, and will ensure that the probabilities continue to sum to 1.

For a thermal ensemble machine, the operation is performed by shooting a short pulse of radiation at the container of molecules. Different types of pulses result in different matrices. The algorithm for the quantum computer consists of which pulses to use, and in what order. The sequence is usually chosen so that all the probabilities will go to zero except for one. That probability is the one corresponding to the string that is the right answer. Then, when the measurement is made, that answer is the most likely one to be returned. For a given algorithm, the operations will always be done in exactly the same order. There is no "IF THEN" statement to vary the order, since there is no way to read memory before the measurement at the end.

For more details on the sequences of operations used for various algorithms, see universal quantum computer, Shor's algorithm, quantum database search, and quantum error correction.

The quantum computer in the above example could be thought of as a black box containing 8 complex numbers. Or, it could be thought of as 8 black boxes, each containing 1 complex number, each sitting in a different alternate universe, and all communicating with each other. These two interpretations correspond to the Copenhagen interpretation and many worlds interpretation, respectively, of quantum mechanics. The choice of interpretation has no effect on the math, or on the behavior of the quantum computer. Either way, it's an 8-element vector that is modified by matrix multiplication.

Complexity Theory

This section surveys what is currently known mathematically about the power of quantum computers. It describes the known results from Computational complexity theory and the theory of computation dealing with quantum computers.

The class of problems that can be efficiently solved by quantum computers is called BQP, for "bounded error, quantum, polynomial time". Quantum computers only run randomized algorithms, so BQP on quantum computers is the counterpart of BPP on classical computers. It is defined as the set of problems solvable with a polynomial-time algorithm, whose probability of error is bounded away from one half. A quantum computer is said to "solve" a problem if, for every instance, its answer will be right with high probability. If that solution runs in polynomial time, then that problem is in BQP.

BQP is suspected to be disjoint from NP-Complete and a strict superset of P, but that is not known. Both integer factorization and discrete log are in BQP. Both of these problems are NP problems suspected to be outside P. Both are suspected to not be NP-Complete. There is a common misconception that quantum computers can solve NP-Complete problems in polynomial time. That is not known to be true, and is generally suspected to be false.

It has been shown that if a quantum computer could be designed with nonlinear operators, then it could solve NP-Complete problems in polynomial time. It could even do so for #P-Complete problems. No such designs have yet passed peer review.

Although quantum computers are sometimes faster than classical computers, they can't solve any problems that classical computers can't solve, given enough time and memory. A Turing machine can simulate a quantum computer, so a quantum computer could never solve an undecidable problem like the Halting problem. The existence of quantum computers does not disprove the Church-Turing thesis.

Further Information

Quantum computing is part of quantum information processing.

Good general reference:

- Centre for Quantum Computation, University of Oxford http://www.qubit.org

Thermal Ensembles

- Overview of early developments, with links

- The first paper ever written on this topic: N. Gershenfeld and I. Chuang, Science, 275, pp. 350-356, 1997. download

Using quantum computers to simulation quantum systems:

- Feynman, R. P. "Simulating Physics with Computers" International Journal of Theoretical Physics, Vol. 21 (1982) pp. 467-488.

Quantum cryptography:

- The first paper ever written on this: Wiesner, S. "Conjugate Coding" SIGACT News, Vol. 15, 1983, pp. 78-88; Brassard, G. and Bennett, C.H., Proceedings of the IEEE International Conference on Computer Systems and Signal Processing, 1984, p. 175 Ekert, A. "Quantum Cryptography Based on Bell's Theorem" Physical Review Letters, Vol. 67 1991 pp. 661-663.

- The first paper ever published on this: Bennett, C. H., Brassard, G., Breidbart, S. and Wiesner, S., "Quantum cryptography, or unforgeable subway tokens", Advances in Cryptology: Proceedings of Crypto 82, August 1982, Plenum Press, pp. 267 - 275.

- A listing of a huge number of quantum cryptography papers, with some discussion of them, is at http://www.cs.mcgill.ca/~crepeau/CRYPTO/Biblio-QC.html

Universal quantum computer and the Church-Turing thesis:

- Deutsch, D. "Quantum Theory, the Church-Turing Principle, and the Universal Quantum Computer" Proc. Roy. Soc. Lond. A400 (1985) pp. 97-117.

Shor's factoring algorithm:

- Shor, P. "Algorithms for quantum computation: discrete logarithms and factoring" Proceedings 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, USA, 20-22 Nov. 1994, IEEE Comput. Soc. Press (1994) pp. 124-134.

- John-Pierre Seifert, "Using fewer Qubits in Shor's Factorization Algorithm via Simultaneous Diophantine Approximation," download

Quantum database search:

- Grover, L. K. "A Fast Quantum Mechanical Algorithm for Database Search" Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, Philadelphia, (1996) pp. 212-219.

Quantum error correction:

- Shor, P. W. "Scheme for reducing decoherence in quantum computer memory" Phys. Rev. A 52,(1995) pp. 2493-2496.

- Calderbank, A. R. and Shor, P.W. "Good quantum error-correcting codes exist" Phys. Rev. A 54, (1996) pp. 1098-1106.

- Shor. P. W. "Fault-tolerant quantum computation" Proc. 37nd Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, (1996) pp. 56-65.

Solving NP-Complete and #P-Complete problems:

- Daniel S. Abrams (1), Seth Lloyd (2) ( (1) Dept. of Physics, MIT, (2) Dept. of Mechanical Engineering, MIT), 1988, "Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems"download

- Phil Gossett, 1988, "NP in BQP with Nonlinearity", [download

- Not peer reviewed: Yu Shi, 1999, "Entanglement Between Bose-Einstein Condensates" download

/Talk