There has been a lot of talk recently about quantum computers
and here I am going to give a brief introduction to this
trendy topic. At the outset I must say that nobody has
yet built a quantum computer and it may be a long time
before anybody builds one. The interest in this subject
is in the fact that if you had a quantum computer it could
do things that a conventional computer could not. A quantum
computer could solve certain problems much faster than
a conventional computer. This is not because the chips
in a quantum computer run extremely fast. It is because
a quantum computer uses a different logic than an ordinary
computer and for certain problems using quantum logic
this allows for tremendous algorithmic speedup.
This means that a quantum computer could execute many
fewer operations to solve certain problems than a conventional
computer would have to execute. This decrease in the required
number of steps necessary to solve problems is what makes
the study of quantum computation exciting.
We can idealize a conventional computer as a device that
acts on strings of bits. Each bit takes the value 0 or
1. A conventional computer takes an input string of bits
and produces an output string that is the answer to a
problem. The computer acts by executing a program. The
program results in a sequence of instructions that tell
the computer how to change the bits. Each step of the
running program changes a few bits. The harder the problem
the more steps are required to go from the input to the
output.
Although you may think that conventional computers are
really very fast, there are problems that require so many
steps that a conventional computer running since the Big
Bang would not have had enough time to solve the problem.
The basic building block of a quantum computer is called
a qubit. We can idealize a qubit as a spin-one-half particle
such as the electron. You can think of a spin-one-half
particle as spinning about an axis much like the earth
spins. This is where, however, the analogy to a macroscopic
spinning object ends.
The spinning electron carries angular momentum. If you
pick any direction and measure the component of the angular
momentum along that direction you get only one of two
possible values +1/2 or -1/2 (in some units.) There is
no classical spinning object that has the property that
the component of its angular momentum along any direction
must take one of two fixed values. This is called quantization
of angular momentum and is a purely quantum effect. Now
the qubit in a quantum computer plays the role of the
bit in an ordinary computer. Spin +1/2 along some ' direction
can be associated with bit value 0 and spin -1/2 can be
associated with bit value 1. So far a qubit sounds like
an ordinary bit. The difference is that an ordinary bit
can have the value 0 or 1 but the qubit can be a quantum
superposition of the two values +1/2 and -1/2. These quantum
superpositions have no classical analogues. A quantum
computer consists of a string of qubits. A quantum algorithm
is a set of instructions for manipulating these qubits
a few at a time. The rules for how the qubits can be controlled
are governed by quantum mechanical law (which is perfectly
well understood) and these rules are completely different
from the rules that govern the behavior of bits in an
ordinary computer. Quantum algorithms take advantage of
quantum superposition and the basic wave like nature of
quantum systems.
In a few key cases it has been shown that the number
of qubit steps required to solve a problem is far fewer
than the number of steps required in an ordinary computer
acting with ordinary bits. The most striking example is
the ability of a quantum computer to factor a large number
with very few steps. Consider a large number, say one
with 200 digits, and the goal is to write this number
as a product of prime factors. It turns out that the fastest
existing computers cannot factor a number this big in
less than a century. The best known algorithm requires
too many steps. If this problem is given to a quantum
computer running carefully written quantum code, however,
the factors could be found with very few steps. This dramatic
speedup is important because it demonstrates that a quantum
computer could do something a conventional computer could
not do in a reasonable amount of time.
Also, factoring is not just an esoteric math problem.
Almost all existing encryption systems are based on the
inability of computers to quickly factor large numbers.
If you had a quantum computer you could break all existing
codes used by the military and financial institutions!
For this reason the government is very interested in knowing
if a functioning quantum computer could ever be built.
On the theoretical side it is important to know if there
are other problems that can be solved quickly on a quantum
computer. We know of examples of problems where quantum
speedup is not available and accordingly there is no advantage
to using a quantum computer. We need to better understand
the class of problems that are amenable to quantum speedup.
On the experimental side, so far only a few-qubit quantum
computers have been built. By few I mean three or four.
Experimentalists are trying hard to see if they could
eventually build a three or four thousand qubit machine,
which is what you would need to solve a difficult problem.
Building a quantum computer is actually very technically
challenging and probably a new idea is needed before a
big one is ever built. But I am hoping that one is built
because I am sure it will have applications beyond what
has already been discovered.
