Peter Høyer

Abstract We consider the problem of sampling from a target distribution in a Markov chain P. The random walk starts in a state drawn from the stationary distribution of P, walks according to P, and eventually stops once some predefined conditions are satisfied, generating a desired target distribution tau. We present a quantum algorithm that generates the target distribution tau using quadratically fewer steps than the optimal random walk. Our algorithm uses a generalization of controlled quantum walks. We introduce a quantum analogue of the exit frequencies of a random walk and use it to prove a relationship between sampling in random and quantum walks. Our framework yields simple and natural proofs. Applications of the framework include: A quantum rejection sampling algorithm achieving a quadratic speedup. A proof that controlled quantum walks can emulate generalized quantum interpolated walks. A proof that the extended hitting time is a measure of the complexity of a sampling problem. Efficient sampling is an important computational task used in e.g. simulations based stochastic processes. This is the first quantum algorithm that achieves a quadratic speed-up for sampling from general probability distributions over states of a Markov chain starting from the stationary distribution.

The success probability of a classical randomized algorithm can be boosted by repetition: If the algorithm succeeds with probability a, then by repeating the algorithm k times, we can increase the probability of success to roughly ka, assuming ka << 1. Intuitively, we can think of this basic strategy as each additional run of the given algorithm boosting the probability of success by an additive amount of roughly a.