  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.
