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