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.
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:
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.
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 square root speedup wasn't as dramatic as the speedup for factoring, discrete logs, or physics simulations. But the algorithm could 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 square root 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.
19?? - ???? at MIT built the first quantum computers based on [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? much better than many other proposed systems.
The largest quantum computer built to date, as of mid 2001, is 7 (????) qubits.
![[Home]](wikipedia.png)
State Amplitude Probability
(a+ib) (a2+b2)
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 2n 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 (a2+b2). 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.
This section surveys what is currently known mathematically about the power of quantum computers. It describes the known results from 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.