Quantum Computing

Quantum computing exploits the fact that small systems such as atoms or elementary particles can be in a superposition of different states. As an example, suppose we have an atom with an electron that can be in two different orbits around the kernel. While everyday common sense tells us that the electron must be in either one orbit or in the other, quantum mechanics allows it to be in a superposition of the two, which loosely speaking means that it is in both orbits at the same time.

Using such an atom, we can build a one-bit register for a quantum computer, by saying that the atom stores a 0 if the electron is in one orbit and a 1 if it is in the other. By what we just said, this register can store both a 0 and a 1 at the same time, contrary to classical registers. By having many such registers, we can store an enormous, exponential number of different values simultaneously. Hence a computation carried out on such a register in fact performs many computations for the price of one.

By designing carefully the operations done, one can avoid the situation where one ends up with a random mix of useful and useless results. By using a phenomenon known as interference, one can make useful computation paths reinforce each other while unwanted paths cancel eachother out. In this way, quantum computers can be shown to be able to solve specific computing problems much faster than classical ones.

Actually building a quantum computer is a huge technical challenge, and no one can today predict if we will ever be able to build quantum computers big enough to outperform classical computers.

A nice introduction to quantum computing from Barenco, Ekert, Sanpera and Machiavello that appeared in La Recherche, Nov 1996 is available here (in english). Also accessible is a bibliography containing nice introduction papers.

Samuel L. Braunstein's tutorial on quantum computation is available here.