The probability of reaching a particular point in space and time, given that we measure the position at that time, is listed on the vertices.

– 5 – 4 – 3 – 2 – 1 0 1

0 1 2 3 4 5

1

1/2 1/2

1/4 1/2 1/4

1/8

1/16 1/4 3/8 1/4 1/16

1/32 5/32 5/16 5/16 5/32 1/32

3/8 3/8 1/8

2 34 5

Space – 5 – 4 – 3 – 2 – 1 0 1

Space
Time
Time

 

But in the quantum world, two of these paths contribute equal but oppositely to the amplitude to get to this position. In other words these two paths interfere with each other. Because amplitudes, unlike probabilities, don’t have to be positive numbers, they can add up in ways that cancel out. This is the effect known as quantum interference. It is the same interference idea which you see when two water waves collide with each other. But note an important difference here: amplitudes squared are probabilities. In water waves, the heights interfere, not anything related to the probabilities of the waves. This is the peculiar effect of quantum interference.

Quantum random walks were actu-
ally first described by physicists in
1993, 2 but only with the rise of interest
in quantum computers was it asked
whether these walks could be used as
a computational tool. An alternative,
continuous time version of these algo-
rithms (tacking more closely to ideas
in physics) has also been developed
by Farhi and Gutmann. 9 Given these
quantum random walks, a natural
question is what does this have to do
with algorithms? Well, the first obser-
vation is that quantum random walks
behave in strange ways. For instance a
well-known property of classical ran-
dom walks on a line is that the expected
standard deviation of a random walk
as a function of the number of steps
taken, T, scales like the square root
of T. However, for a quantum random
walk the standard deviation can actu-
ally spread linearly with T. Remarkably,
this difference has been well known
to physicists for a long time: it turns
out that the quantum random walk
defined above is closely related to the
Dirac equation for a one-dimensional
electron (the Dirac equation is a way
to get quantum mechanics to play
nicely with the special theory of rela-
tivity, and is a basic equation used in
modern quantum field theory). This
discovery that quantum algorithms
seem to explore space quadratically
faster than classical random walks has
recently been shown to lead to quan-
tum algorithms that polynomially out-
perform their classical cousins.

figure 3. An example of a graph arising in the quantum random walk problem considered by childs et al. 8

In this problem one is given access to a function that takes as input a vertex and returns a list of the vertex’s neighbors. The goal of the problem considered by Childs et al. is, by querying the function as few times as possible, traverse from the start vertex to the end vertex. The graphs considered are two full binary trees pasted together with a random cycle (in the example, the cycle resides inside the dashed box) whose roots are the start and end vertices. The quantum algorithm starts at the start vertex and then performs a quantum diffusion to the end vertex. The random cycle in the middle does not destroy this diffusion, since all paths contribute equally to this diffusion. For a graph of depth d, the quantum walk will find the end vertex by querying the local vertex function a polynomial number of times in d. The best classical algorithm can be shown to require querying the function for local vertex information exponentially many times in d.

Start
End