CS 298-2
Theory Seminar

Mario Szegedy
Rutgers University

Quantization of walk based classical algorithms and a new spectral theorem

Monday, April 19, 2004
4pm-5pm
306 Soda Hall

We develop a mathematical machinery for quantizing classical
algorithms that are based on walks and show that in many cases
the quantum version gives rise to a quadratic speed-up. We develop
a new spectral theorem from which earlier results
of Ambainis [A] and Ambainis, Kempe and Rivosh [AKR] easily follow.
Our results imply that for any Cayley graph of a finite
Abelian group the hitting time of the quantized walk is
at most square root of the classical. This yieds an improvement
over [AKR] for the two dimensional torus.