Quantum Speed-Up of Markov Chain Based Algorithms

We develop a generic method for quantizing classical algorithms based on random walks. We show that under certain conditions, the quantum version gives rise to a quadratic speed-up. This is the case, in particular, when the Markov chain is ergodic and its transition matrix is symmetric. This generalizes the celebrated result of L. K. Grover (1996)and a number of more recent results, including the element distinctness result of Ambainis and the result of Ambainis, Kempe and Rivosh that computes properties of quantum walks on the d-dimensional torus. Among the consequences is a faster search for multiple marked items. We show that the quantum escape time, just like its classical version, depends on the spectral…