Quantum Speed-up of Markov Chain Based Algorithms

Please contact Yaoyun Shi (shiyy@eecs, 764-3308) if you would like to meet
with Professor Szegedy
We develop a generic method for quantizing classical algorithms
based on random walks. We show that under certain conditions,
the quantum version gives rise to a quadratic speed-up. This is
the case, in particular, when the Markov chain is ergodic and
its transition matrix is symmetric. This generalizes the celebrated
result of Grover and a number of more recent results, including
the element distinctnesss result of Ambainis and the result of
Ambainis, Kempe and Rivosh that computes properties of quantum walks
on the $d$-dimensional torus. Among the consequences is a faster
search for multiple marked items. We show that the quantum escape
time, just like its classical version, depends on the spectral
properties of the transition matrix with the marked rows and
columns deleted.

Mario Szegedy received an M.A. in mathematics from the University of
Budapest, Hungary, in 1985, and a Ph.D. in Computer Science from the
University of Chicago in 1989. After spending seven years at Bell
Laboratories, he conducted research at the Institute for Advanced Study
in Princeton. In 2000, Szegedy joined Rutgers University, New
Brunswick, USA, as an associate professor in the Faculty of Arts and
Sciences. In 2001 he was the recipient of the prestigious Godel Prize
for his pioneering works in the area of probabilistically checkable
proofs, which has played instrumental role in the resolution of many
longstanding questions in combinatorial optimization. Since 2002
Szegedy is a professor of Computer Science at Rutgers University. His
wide-ranging research interests include complexity theory,
computational geometry and quantum computing.