Search via quantum walk

Abstract

We propose a new method for designing quantum search algorithms forfinding a "marked" element in the state space of a classical Markovchain. The algorithm is based on a quantum walk à la Szegedy [25] that is defined in terms of the Markov chain. The main new idea is to apply quantum phase estimation to the quantumwalk in order to implement an approximate reflection operator. Thisoperatoris then used in an amplitude amplification scheme. As a result weconsiderably expand the scope of the previous approaches ofAmbainis [6] and Szegedy [25]. Our algorithm combines the benefits of these approaches in terms of beingable to find marked elements, incurring the smaller cost of the two,and being applicable to a larger class of Markov chain. In addition,it is conceptually simple, avoids several technical difficulties in the previous analyses, and leads to improvements in various aspects of several algorithms based on quantum walk.