A0248
Title: Quantum speedups for multi-proposal MCMC
Authors: Andrew Holbrook - UCLA (United States) [presenting]
Abstract: Multi-proposal Markov chain Monte Carlo (MCMC) algorithms choose from multiple proposals at each iteration in order to sample from challenging target distributions more efficiently. Recent work demonstrates the possibility of quadratic quantum speedups for one such multi-proposal MCMC algorithm. Using P proposals, this quantum parallel MCMC QPMCMC algorithm requires only $O(\sqrt{P})$ target evaluations at each step. A fast new quantum multi-proposal MCMC strategy is presented, QPMCMC2, that only requires O(1) target evaluations and O(log P) qubits. Unlike its slower predecessor, the QPMCMC2 Markov kernel (1) maintains a detailed balance exactly, and (2) is fully explicit for a large class of graphical models. This flexibility is demonstrated by applying QPMCMC2 to novel Ising-type models built on bacterial evolutionary networks, and significant speedups are obtained for Bayesian ancestral trait reconstruction for 248 observed salmonella bacteria.
