[Colloquium] Today's talk by Mario Szegedy, Rutgers University

[Margery Ishmael]

DEPARTMENT OF COMPUTER SCIENCE

Date: Wednesday, June 16
Time: 2:00 p.m.
Place: Ryerson 251

-------------------------------------------

Speaker: MARIO SZEGEDY (Rutgers University)

Title: Quantum Speed-up of Markov Chain Based Algorithms

Abstract:
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 (1996) and a number of more recent
results, including Ambainis (2003) and Ambainis, Kempe
and Rivosh (2004). 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.

Visitor's host:  Laci Babai

Speaker's website: http://www.cs.rutgers.edu/~szegedy/

***Refreshments will follow the talk in Ryerson 255***