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.
Categories: quant-ph