2006/09/30 by Peter C. Richter
Physics and Astronomy · #quant-ph
paper · pdf · doi:10.1103/physreva.76.042306
published as Phys. Rev. A 76, 042306 (2007) · 13 pages; v2 revised several parts
arxiv created 2007/04/05 · arxiv updated 2011/11/09
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 π over a large set §. This problem is solved using the \em Markov chain Monte Carlo method: a sparse, reversible Markov chain P on § with stationary distribution π is run to near equilibrium. The running time of this random walk algorithm, the so-called \em mixing time of P, is O(δ-1 log 1/π_*) as shown by Aldous, where δ is the spectral gap of P and π_* is the minimum value of π. A natural question is whether a speedup of this classical method to O(√δ-1 log 1/π_*), 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 \Znd is O(n d log d), which is indeed O(√δ-1 log 1/π_*) and is asymptotically no worse than the diameter of \Znd (the obvious lower bound) up to at most a logarithmic factor.