Communications - February 2010

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.