Quantum Walk on the Line

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.