Eric Bach(UW-Madison):
Combinatorial Analysis of Quantum Random Walks
Random walks have many applications in the analysis
of algorithms and elsewhere. We investigate quantum analogs of
random walks, which may play a role in future applications
of quantum computing. The behavior of these processes is
strikingly different from their classical cousins. The following
example is typical. Unlike the classical random walk, which
is likely to be O(sqrt(t)) away from its starting place after
t steps, the quantum walk spreads out much more quickly, and
is nearly uniformly distributed over O(t) places. We will also
discuss the behavior of quantum walks on finite lattices.
Joint work with Andris Ambianis, John Watrous, Ashvin Nayak,
and Ashwin Vishwanath.