Almost uniform sampling via quantum walks

Abstract

Many classical randomized algorithms (e.g., approximation algorithms for #P-complete problems) utilize the following random walk algorithm for 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 ǫ total variation distance of the uniform distribution over S. The running time of this algorithm, the so-called mixing time of P, is O(δ −1 (log N+log ǫ −1)), where δ is the spectral gap of P. We present a natural quantum version of this algorithm based on repeated measurements of the quantum walk Ut = e −iPt. We show that it samples almost uniformly from S with logarithmic dependence on ǫ −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(δ −1/2 log N log ǫ −1). We prove each of the conjectures for the standard walk on a restricted class of graphs: the torus Z d p, p prime, and the hypercube Z n 2. 1