A0770
Title: A quantum parallel Markov chain Monte Carlo
Authors: Andrew Holbrook - UCLA (United States) [presenting]
Abstract: A novel quantum computing strategy is proposed for parallel MCMC algorithms that generate multiple proposals at each step. This strategy makes parallel MCMC amenable to quantum parallelization by using the Gumbel-max trick to turn the generalized accept-reject step into a discrete optimization problem. This allows us to embed target density evaluations within a well-known extension of Grover's quantum search algorithm. Letting $P$ denote the number of proposals in a single MCMC iteration, the combined strategy reduces the number of target evaluations required from $O(P)$ to $O(P^1/2)$. We review both the rudiments of quantum computing and the Gumbel-max trick in order to elucidate their combination for as wide an audience as possible.
