Ashwin Nayak, DIMACS and AT&T Research
Thursday, December 7, 4:30 PM, Rutgers Univ. Hill CORE building, Room 431
NOTE NON-STANDARD DAY
Abstract.
Motivated by the immense success of random walk and Markov
chain methods in the design of classical algorithms, we
consider _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 _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.
Joint work with Ashvin Vishwanath (Princeton University).