Quantum computer

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 some quantum dot computers[?], DNA computers[?], and computers based on transistors, even though all of these use quantum mechanical effects other than state superpositions.

Table of contents 1 The Structure of Quantum Computers 2 The Power of Quantum Computers 3 How They Work 4 Practical quantum computers 5 Complexity Theory 6 See also 7 Further Information

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. 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:

• 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.

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 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 complex number (a+bi) is called an amplitude, and each probability (a²+b²) is called the squared amplitude, because it equals |a+bi|². 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:

• scalable physically to increase the number of qubits
• qubits can be initialized to arbitrary values
• quantum gates faster than decoherence
• Turing-complete gate set
• qubits can be read easily

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.

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.

See also

• Timeline of quantum computing

---

Further Information

• Quantum computing is part of quantum information processing.

• Good general reference:
  • Centre for Quantum Computation, University of Oxford http://www.qubit.org (http://www.qubit.org)

• Thermal Ensembles
  • Overview (http://www.media.mit.edu/physics/projects/spins/home) of early developments, with links
  • The first two papers ever written on this topic: D.G Cory, A.F. Fahmy, T.F. Havel, Proc. Nat. Acad. of Science, 94, 1634 (1997), and N. Gershenfeld and I. Chuang, Science, 275, pp. 350-356, 1997. (download (http://www.media.mit.edu/physics/publications/papers/97.01.science.pdf))

• 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 (http://www.cs.mcgill.ca/~crepeau/CRYPTO/Biblio-QC)

• 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 (http://eprint.iacr.org/2000/036/))
  • IBM's announcement (http://www.research.ibm.com/resources/news/20011219_quantum.shtml) of the first actual execution of the algorithm, which also gives the history of the first quantum computers with 2, 3, 5, and 7 qubits. Published in the December 19, 2001 issue of Nature.

• 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 computer simulators:
  • libquantum (http://www.enyo.de/libquantum/) - A library for quantum computer simulation
  • QCL (http://tph.tuwien.ac.at/~oemer/qcl) - Simulation of quantum computing with a quantum computing language
  • Quantum::Entanglement (http://search.cpan.org/search?dist=Quantum-Entanglement) - Quantum computation module for Perl.

• 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.

• Quantum error avoidance:
  • D. A. Lidar, I.L. Chuang, K.B. Whaley, "Decoherence free subspaces for quantum computation", Phys. Rev. Lett 81, (1998) pp. 2594-2587

• 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 (http://arxiv.org/abs/quant-ph/9801041))
  • Phil Gossett, 1988, "NP in BQP with Nonlinearity", (download (http://arxiv.org/abs/quant-ph/9804025))
  • Yu Shi, 2001, "Entanglement Between Bose-Einstein Condensates", Int. J. Mod. Phys. B, Vol. 15 (Sept 10, 2001) 3007-3030. (download here (http://xxx.lanl.gov/abs/quant-ph/9910073) or here (http://www.worldscinet.com/journals/ijmpb/15/1522/S0217979201007154))

• For the interested non-expert:
  • West, J.(2000). The Quantum Computer - An Introduction. (Easy to understand explanation of quantum computing. (http://www.cs.caltech.edu/~westside/quantum-intro))