have a profound consequence, we must next describe how to update our description of a system as it changes in time. One can think about this as analyzing an algorithm where information in our computing device changes with time according to a set of specific recipe of changes.

For a classical probabilistic computing device we can describe how it changes in time by describing the conditional probability that the system changed into a new configuration given that it was in an old configuration. Such a set of conditional probabilities means that we can describe a probabilistic computing action by a stochastic matrix (a matrix whose entries are positive and whose columns sum to unity). A classical probabilistic algorithm can then be viewed as just a set of stochastic matrices describing how probabilities propagate through the computing device. If the classical probabilistic algorithm starts with n bits and ends with m bits, then the stochastic matrix describing the algorithm will be a 2m by 2n matrix.

What is the analogous procedure for a quantum system? Well instead of specifying conditional probabilities of a new configuration given an old configuration, in a quantum system you need to specify the conditional amplitude of a new configuration given an old configuration. In the quantum world, the matrix of conditional amplitudes has two major differences from the classical probabilistic setting. The first is that quantum systems evolve reversibly and thus the matrix is 2n by 2n (corresponding to the amplitude of every configuration to change into any other configuration). The second is that, in order to preserve the sum of the squares of those amplitudes, which should be 1 throughout, this matrix is a unitary matrix, meaning the entries of the matrix are complex numbers, and that the rows (and columns) of this matrix are orthonormal. Thus a quantum algorithm for a quantum system is given by a unitary matrix of conditional amplitudes.

What consequence does this change
from probabilities to amplitudes
and from stochastic matrices to uni-
tary matrices have for the notion of
an algorithm? This is, of course, the
essential question at hand when con-
sidering quantum algorithms. In
this survey we single out three major
differences—quantum interference,
the deep relationship between sym-
metries and quantum mechanics, and
quantum entanglement—and show
how they are related to recent prog-
ress in quantum algorithms.

interference and the Quantum
Drunkard’s Walk

The first of our claimed differences between quantum computers and classical computers was that the former led to effects of quantum interference. What is interference and how can it lead to new efficient algorithms?

To illustrate the ideas of interference, consider a random walk on a line. The standard, classical drunkard’s walk on a line refers to situation where the walker is allowed to step either forward or backward with equal probability every unit time step. When starting at position 0 at time zero, then after one time step there is an equal probability to be at locations + 1 and − 1. After the next time step, there is a one-fourth probability of being at positions − 2 and 2 and one half probability of being at position 0. Notice here that the probability of reaching zero was the sum of two probabilities: the probability that the drunkard got to 0 via 1 and the probability that it got to 0 via − 1. Random walks on structures more complicated than a line are a well-known tool in classical algorithms.

Suppose that we want to construct
a quantum version of this drunkard’s
walk. To specify a quantum walk, we
need, instead of a probability for tak-
ing a step forward or backward, an
amplitude for doing this. However we
also need to make sure that the unitary
nature of quantum theory is respected.
For example, you might think that the
quantum analogy of a classical walk is to
take a step forward and a step backward
with amplitude one over the square root
of two (since squaring this gives a prob-
ability of one half). If we start at 0, then
after one step this prescription works:
we have equal amplitude of one over
square root of two of being at either
1 or − 1. If we measure the walker after
this first step, the probability of being
at 1 or − 1 is both one half. But if we run
this for another time step, we see that
we have an amplitude of ½ to be at
− 2 or 2 and an amplitude 1 to be at 0.
Unfortunately if we square these num-
bers and add them up, we get a num-
ber greater than unity, indicating that
the evolution we have described is not
unitary.

 

If we follow this prescription for a quantum random walk with the drunkard initially positioned at zero, one quickly sees that something strange happens. Consider, for instance, the probability distribution formed by the quantum walk had we measured the walker’s position after three time steps (see Figure 2). Then the probability of getting to + 1 for the drunkard is 18. For a classical walk the similar number would be 38. What is going on here? Well if you trace back how he could have gotten to + 1 in three steps, you’ll see that there are three paths it could have used to get to this position. In the classical world each of these is traversed with equal probability, adding a contribution of 18 for each step.