Quantum walks can find a marked element on any graph

Hari Krovi; Frédéric Magniez; Maris Ozols; Jérémie Roland

doi:10.1007/s00453-015-9979-8

paper

Quantum walks can find a marked element on any graph

arXiv:1002.2419 · doi:10.1007/s00453-015-9979-8

Abstract

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 $H T (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 $H T^{+} (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 $H T^{+} (P, M)$ are known.

50 pages

Quantum walks can find a marked element on any graph

Abstract

References in corpus (6)

Cited by in corpus (47)