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.