What is Quantum Computing?

Quantum computing is a new field in computer science that has been developed with our increased understanding of quantum mechanics. It holds the key to computers that are exponentially faster than conventional computers (for certain problems). A quantum computer is based on the idea of a quantum bit or qubit. In classical computers, the bit has a discrete range and can represent either a zero or a one. A qubit can be in a linear superposition of the two states. A quantum register consists of n qubits. Because of superposition, a phenomenon known as quantum parallelism allows exponentially many such computations to take place simultaneously, thus vastly increasing the speed of computation.

Quantum interference, the analog of Young's double-slit experiment which demonstrated constructive and destructive interference phenomena of light, is one of the most significant characteristics of quantum computing. Quantum interference improves the probability of obtaining a desired result by constructive interference and diminishes the probability of obtaining an erroneous result by destructive interference. Thus, among the exponentially many computations, the correct answer can theoretically be identified with appropriate quantum "algorithms."

It has been proven that a quantum computer will be able to factor (see Question 45) and compute discrete logarithms (see Question 52) in polynomial time. Unfortunately, the development of a practical quantum computer still seems far away because of a phenomenon called quantum decoherence, which is due to the influence of the outside environment on the quantum computer. Brassard has written a number of helpful texts in this field [Bra95a][Bra95b] [Bra95c].

Quantum cryptography (see Question 110) is quite different from, and currently more viable than, quantum computing.

| Question 110 |