Abstract:
Although the original problem may not be formulated in terms of graph search, computational problems can often be recast as the problem of searching for a special kind of vertex in a graph.  This turns out to be a particularly useful view to take for designing efficient algorithms---quantum particles exploring a graph may detect special (or ``marked'') vertices quadratically faster than classical particles, as illustrated by Ambainis (2004) and Szegedy (2004).

In this talk, we will see a quantum walk based algorithm that may be defined for an arbitrary ergodic Markov Chain.  It combines the benefits of two previous approaches while guaranteeing the better form of run time.  The algorithm is both conceptually simple and avoids several technical difficulties in the analysis of earlier approaches.  It thus seems to demystify the role of quantum walks in search algorithms.

We will begin with example search problems and algorithms based on random walk, describe amplitude amplification and phase estimation (two useful building blocks for quantum algorithms), and sketch how their confluence gives our search algorithm.

This is joint work with Fr'ed'eric Magniez (CNRS--LRI), J'er'emie Roland (UC Berkeley), and Miklos Santha (CNRS--LRI).