Almost uniform sampling via quantum walks

Abstract

Many classical randomized algorithms (e.g., approximation algorithms for #P-complete problems) utilize the following random walk algorithm for {\em almost uniform sampling} from a state space $S$ of cardinality $N$: run a symmetric ergodic Markov chain $P$ on $S$ for long enough to obtain a random state from within $\epsilon$ total variation distance of the uniform distribution over $S$. The running time of this algorithm, the so-called {\em mixing time} of $P$, is $O({\delta }^{-1}(\log N+\log {\epsilon }^{-1}))$, where $\delta$ is the spectral gap of $P$. We present a natural quantum version of this algorithm based on repeated measurements of the {\em quantum walk} $U_t=e^{-iPt}$. We show that it samples almost uniformly from $S$ with logarithmic dependence on ${\epsilon }^{-1}$ just as the classical walk $P$ does; previously, no such quantum walk algorithm was known. We then outline a framework for analyzing its running time and formulate two plausible conjectures which together would imply that it runs in time $O({\delta }^{-1/2}\log N\log {\epsilon }^{-1})$ when $P$ is the standard transition matrix of a constant-degree graph. We prove each conjecture for a subclass of Cayley graphs.

13 pages; v2 added NSF grant info; v3 incorporated feedback

References in corpus (5)

• Exponential algorithmic speedup by quantum walk
• Spatial search by quantum walk
• Spatial search and the Dirac equation
• Quantum Random Walks Hit Exponentially Faster
• Optimal computation with non-unitary quantum walks

Cited by in corpus (7)

• Decoherence in quantum walks - a review
• Speed-up via Quantum Sampling
• Decoherence vs entanglement in coined quantum walks
• The Limiting Distribution of Decoherent Quantum Random Walks
• Quantum walk based search algorithms
• Optimal computation with non-unitary quantum walks
• Decoherence in quantum walks and quantum computers