Abstract
Most approximation algorithms for #-complete problems (e.g., evaluating the partition function of a monomer-dimer or ferromagnetic Ising system) work by reduction to the problem of approximate sampling from a distribution over a large set . This problem is solved using the Markov chain Monte Carlo method: a sparse, reversible Markov chain on with stationary distribution is run to near equilibrium. The running time of this random walk algorithm, the so-called mixing time of , is as shown by Aldous, where is the spectral gap of and is the minimum value of . A natural question is whether a speedup of this classical method to is possible using quantum walks. We provide evidence for this possibility using quantum walks that decohere under repeated randomized measurements. We show that (i) decoherent quantum walks always mix, just like their classical counterparts, (ii) the mixing time is a robust quantity, essentially invariant under any smooth form of decoherence, and (iii) the mixing time of the decoherent quantum walk on a periodic lattice is , which is indeed and is asymptotically no worse than the diameter of (the obvious lower bound) up to at most a logarithmic factor.
- Received 5 April 2007
DOI:https://doi.org/10.1103/PhysRevA.76.042306
©2007 American Physical Society