quantum computer could be built.
While there currently appear to be no
fundamental obstacles toward building a large scale quantum computer
(and even more importantly, a
result known as the “threshold
theorem” 1, 16–18, 25 shows that quantum computers can be made resilient against small amounts of noise,
thereby confirming that these are
not analog machines), the engineering challenges posed to build an RSA
breaking quantum computer are
severe and the largest quantum computers built to date have less than
10 quantum bits (qubits). 13, 19 But
regardless of the progress in building a quantum computer, if we are to
seriously consider our understanding
of computation as being based upon
experimental evidence, we will have
to investigate the power of quantum
algorithms. Christos Papadimitriou
said in a recent interview26 that the
theory of computational complexity is
such a difficult field because it is nearly
impossible to prove what everyone
knows from experience. How, then,
can we even begin to gain an understanding of the power of quantum
computers if we don’t have one from
which to gain such an experience?
Further, and perhaps even more challenging, quantum algorithms seem to
be exploiting the very effects that make
quantum theory so uniquely counterintuitive. 6 Designing algorithms for
a quantum computer is like building
a car without having a road or gas to
take it for a test drive.
In spite of these difficulties, a
group of intrepid multidisciplinary
researchers have been tackling the
question of the power of quantum
algorithms in the decades since Shor’s
discoveries. Here we review recent
progress on the upper bounding side
of this problem: what new quantum
algorithms have been discovered
that outperform classical algorithms
and what can we learn from these
discoveries? Indeed, while Shor’s
factoring algorithm is a tough act to
follow, significant progress in quantum algorithms has been achieved.
We concentrate on reviewing the
more recent progress on this problem, skipping the discussion of early
(but still important) quantum algorithms such as Grover’s algorithm12
for searching (a quantum algorithm
that can search an unstructured space
quadratically faster than the best classical algorithm), but explaining some
older algorithms in order to set context. For a good reference for learning about such early, now “classic”
algorithms (like Grover’s algorithm
and Shor’s algorithm) we refer the
reader to the textbook by Nielsen and
Chuang. 21 Our discussion is largely
ahistoric and motivated by attempting to give the reader intuition as to
what motivated these new quantum
algorithms. Astonishingly, we will see
that progress in quantum algorithms
has brought into the algorithmic fold
basic ideas that have long been foundational in physics: interference,
scattering, and group representation
theory. Today’s quantum algorithm
designers plunder ideas from physics,
mathematics, and chemistry, weld
them with the tried and true methods
of classical computer science, in order
to build a new generation of quantum
contraptions which can outperform
their classical counterparts.
Quantum theory in a nutshell
Quantum theory has acquired a reputation as an impenetrable theory accessible only after acquiring a significant
theoretical physics background. One
of the lessons of quantum computing is that this is not necessarily true:
quantum computing can be learned
without mastering vast amounts of
physics, but instead by learning a few
simple differences between quantum
and classical information. Before discussing quantum algorithms we first
give a brief overview of why this is true
and point out the distinguishing features that separate quantum information from classical information.
To describe a deterministic n-bit
system it is sufficient to write down its
configuration, which is simply a binary
string of length n. If, however, we have
n-bits that can change according to pro-
babilistic rules (we allow randomness
into how we manipulate these bits), we
will instead have to specify the prob-
ability distribution of the n-bits. This
means to specify the system we require
2n positive real numbers describing
the probability of the system being in a
given configuration. These 2 n numbers
must sum to unity since they are, after
all, probabilities. When we observe
a classical system, we will always find it
to exist in one particular configuration
(i.e. one particular binary string) with
the probability given by the 2n num-
bers in our probability distribution.
figure 1. classical versus
quantum information.
On the left, the classical bit is described by two
nonnegative real numbers for its probabilities
Pr(0) = 1/3 and Pr( 1) = 2/3. The quantum bit
on the right, instead, has two complex valued
amplitudes that give the (same) probabilities by
taking the absolute value-squared of its entries.
When a quantum system has such a description
with nonzero amplitudes, one says that the
system is in a superposition of the 0 and 1
configurations.
1
3
− 1
3Ö
Classical bit:
Quantum bit:
2
3
1+i
3Ö