  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.
