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 (15)

• Quantum random walks - an introductory overview
• Quantum Computation and Decision Trees
• A Quantum Random Walk Search Algorithm
• Exponential algorithmic speedup by quantum walk
• Spatial search by quantum walk
• From quantum cellular automata to quantum lattice gases
• Quantum measurements and the Abelian Stabilizer Problem
• An example of the difference between quantum and classical random walks
• Decoherence can be useful in quantum walks
• Spatial search and the Dirac equation
• Quantum Random Walks Hit Exponentially Faster
• Quantum speedup of classical mixing processes
• Quantum Complexity of Testing Group Commutativity
• Optimal computation with non-unitary quantum walks
• Quantum algorithms for subset finding

Cited by in corpus (26)

• Quantum walks: a comprehensive review
• Search via Quantum Walk
• Decoherence in quantum walks - a review
• Speed-up via Quantum Sampling
• Quantum speedup of classical mixing processes
• Decoherence vs entanglement in coined quantum walks
• Hitting time for the continuous quantum walk
• How fast do quantum walks mix?
• The Limiting Distribution of Decoherent Quantum Random Walks
• Quantum walk based search algorithms
• Quantum random walks on the $N$-cycle subject to decoherence on the coin degree of freedom
• Faster quantum mixing for slowly evolving sequences of Markov chains
• Analog quantum algorithms for the mixing of Markov chains
• Optimal computation with non-unitary quantum walks
• Simulation of Quantum Walks and Fast Mixing with Classical Processes
• Decoherence in quantum walks and quantum computers
• Quantum scattering theory on graphs with tails
• Small quantum computers and large classical data sets
• Quantum algorithm for estimating volumes of convex bodies
• Study of Quantum Walk over a Square Lattice
• Transient temperature and mixing times of quantum walks on cycles
• Two-level Quantum Walkers on Directed Graphs I: Universal Quantum Computing
• One-dimensional discrete-time quantum walks on random environments
• Quantum walk mixing is faster than classical on periodic lattices
• Quantum walks advantage on the dihedral group for uniform sampling problem
• Solving Markov Chains with Analog Quantum Computing: The Fine Print