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. This integer factorization problem is believed to be difficult for an ordinary computer. A quantum computer could solve this problem very quickly. If a number has n bits (is n digits long when written in the binary numeral system), 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, ElGamal and Diffie-Hellman. 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.
Perhaps not as 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. However, there is no proof that the advantage is real: an equally fast classical algorithm may still be discovered (though this is considered unlikely). There is one other problem where quantum computers have a smaller, though significant (quadratic) advantage. It is quantum database search, and can be solved by Grover's algorithm. In this case the advantage is provable. This establishes beyond doubt that (ideal) quantum computers are superior to classical computers.
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.
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) (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 complex number (a+bi) is called an amplitude, and each probability (a2+b2) is called the squared amplitude, because it equals |a+bi|2. 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, Grover's algorithm, Deutsch-Jozsa algorithm[?] 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 many black boxes, each containing 3 bits, each in a separate universe, and each interacting with the others. The 8 complex numbers would describe the distribution of 3-bit patterns over all the universes. 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.
Practical quantum computers David DiVincenzo, of IBM, listed the following requirements for a practical quantum computer:
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.
An operator for a quantum computer can be thought of as changing a vector by multiplying it with a particular matrix. Multiplication by a matrix is a linear operation. 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. It is not yet known whether such a machine is possible.
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.