Quantum Walks Can Find a Marked Element on Any Graph

• Published in: Algorithmica 2016-02, Vol.74 (2), p.851-907
• Main Authors: Krovi, Hari, Magniez, Frédéric, Ozols, Maris, Roland, Jérémie
• Format: Article
• Language: English
• Subjects: Algorithm Analysis and Problem Complexity; Algorithms; Computer Science; Computer Systems Organization and Communication Networks; Data Structures and Information Theory; Mathematics of Computing; Theory of Computation
• ISSN: 0178-4617; 1432-0541
• DOI: 10.1007/s00453-015-9979-8

We solve an open problem by constructing quantum walks that not only detect but also find marked vertices in a graph. In the case when the marked set M consists of a single vertex, the number of steps of the quantum walk is quadratically smaller than the classical hitting time HT ( P , M ) of any reversible random walk P on the graph. In the case of multiple marked elements, the number of steps is given in terms of a related quantity HT + ( P , M ) which we call extended hitting time. Our approach is new, simpler and more general than previous ones. We introduce a notion of interpolation between the random walk P and the absorbing walk P ′ , whose marked states are absorbing. Then our quantum walk is simply the quantum analogue of this interpolation. Contrary to previous approaches, our results remain valid when the random walk P is not state-transitive. We also provide algorithms in the cases when only approximations or bounds on parameters p M (the probability of picking a marked vertex from the stationary distribution) and HT + ( P , M ) are known.