Adiabatic condition and the quantum hitting time of Markov chains

The paper presents an adiabatic quantum algorithm for spatial search (finding marked vertices in a graph). Given a random walk (or Markov chain) P on a graph with a set of unknown marked vertices, one can define a related absorbing walk P' where outgoing transitions from marked vertices are replaced by self-loops. They build a Hamiltonian H(s) from the interpolated Markov chain P(s)=(1-s)P+sP' and use it in an adiabatic quantum algorithm to drive an initial superposition over all vertices to a superposition over marked vertices. The running time of the adiabatic algorithm is given by the square root of the classical hitting time. This algorithm therefore demonstrates a novel connection between the adiabatic condition and the classical notion of hitting time of a random walk.

Reference: Hari Krovi, Maris Ozols, and Jeremie Roland, Phys. Rev. A 82, 022333 (2010)