Quantum speedup of classical mixing processes
Preprint
Abstract
Most approximation algorithms for #P-complete problems (e.g., evaluating the permanent of a matrix or the volume of a polytope) work by reduction to the problem of approximate sampling from a distribution $\pi$ over a large set $\S$. This problem is solved using the {\em Markov chain Monte Carlo} method: a sparse, reversible Markov chain $P$ on $\S$ with stationary distribution $\pi$ is run to near equilibrium. The running time of this random walk algorithm, the so-called {\em mixing time} of $P$, is $O(\delta^{-1} \log 1/\pi_*)$ as shown by Aldous, where $\delta$ is the spectral gap of $P$ and $\pi_*$ is the minimum value of $\pi$. A natural question is whether a speedup of this classical method to $O(\sqrt{\delta^{-1}} \log 1/\pi_*)$, the diameter of the graph underlying $P$, is possible using {\em quantum walks}. We provide evidence for this possibility using quantum walks that {\em decohere} under repeated randomized measurements. We show: (a) decoherent quantum walks always mix, just like their classical counterparts, (b) the mixing time is a robust quantity, essentially invariant under any smooth form of decoherence, and (c) the mixing time of the decoherent quantum walk on a periodic lattice $\Z_n^d$ is $O(n d \log d)$, which is indeed $O(\sqrt{\delta^{-1}} \log 1/\pi_*)$ and is asymptotically no worse than the diameter of $\Z_n^d$ (the obvious lower bound) up to at most a logarithmic factor.
Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Decoherence in quantum walks – a reviewMathematical Structures in Computer Science, 2007
- Almost uniform sampling via quantum walksNew Journal of Physics, 2007
- Decoherence in quantum walks on the hypercubePhysical Review A, 2005
- Localization of two-dimensional quantum walksPhysical Review A, 2004
- Controlling discrete quantum walks: coins and initial statesNew Journal of Physics, 2003
- Quantum random walks: An introductory overviewContemporary Physics, 2003
- Decoherence can be useful in quantum walksPhysical Review A, 2003
- Quantum walks in higher dimensionsJournal of Physics A: General Physics, 2002
- Quantum computation and decision treesPhysical Review A, 1998
- Eigenvalues and expandersCombinatorica, 1986