Motivated by the immense success of random walk and Markov
chain methods in the design of classical
algorithms, we consider {\em quantum\/} walks on graphs.
We analyse in detail the behaviour of unbiased quantum walk on the line,
with the example of a typical walk, the ``Hadamard walk''. In
particular, we show that
after~$t$ time steps, the probability distribution on the line induced
by the Hadamard walk is almost uniformly distributed over the
interval~$[-t/\sqrt{2},\;t/\sqrt{2}]$. This implies that the same walk
defined on the circle mixes in {\em linear\/} time.
This is in direct contrast with the quadratic mixing time for the
corresponding classical walk.
We conclude by indicating
how our techniques may be applied to more general graphs.
DIMACS Home Page