### DIMACS Theoretical Computer Science Seminar

Title: On the hitting times of quantum versus random walks

Speaker: **Peter Richter**, Rutgers University

Date: Wednesday, April 29, 2009 11:00-12:00pm

Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

In this paper we define new Monte Carlo type classical and quantum
hitting times, and we prove several relationships among these and the
already existing Las Vegas type definitions. In particular, we show
that for some marked state the two types of hitting time are of the
same order in both the classical and the quantum case.

Further, we prove that for any reversible ergodic Markov chain $P$, the
quantum hitting time of the quantum analogue of $P$ has the same order
as the square root of the classical hitting time of $P$. We also
investigate the (im)possibility of achieving a gap greater than
quadratic using an alternative quantum walk.

Finally, we present new quantum algorithms for the detection and
finding problems. The complexities of both algorithms are related to
the new, potentially smaller, quantum hitting times. The detection
algorithm is based on phase estimation and is particularly simple. The
finding algorithm combines a similar phase estimation based procedure
with ideas of Tulsi from his recent theorem for the 2D grid. Extending
his result, we show that for any state-transitive Markov chain with
unique marked state, the quantum hitting time is of the same order for
both the detection and finding problems.

(Joint work with Fridiric Magniez, Ashwin Nayak, and Miklos Santha)