Quantum Speedups for Markov Chain Monte Carlo Methods with Application to Optimization
This addresses the computational bottleneck of MCMC methods for researchers and practitioners in machine learning and optimization, offering incremental improvements through quantum techniques.
The paper tackles the problem of slow Markov Chain Monte Carlo (MCMC) sampling from probability distributions, proposing quantum algorithms that provide provable speedups by improving gradient and evaluation complexities compared to classical samplers like Hamiltonian Monte Carlo and Langevin Monte Carlo. The result includes quantum speedups for optimization, particularly for minimizing non-smooth and approximately convex functions in empirical risk minimization.
We propose quantum algorithms that provide provable speedups for Markov Chain Monte Carlo (MCMC) methods commonly used for sampling from probability distributions of the form $π\propto e^{-f}$, where $f$ is a potential function. Our first approach considers Gibbs sampling for finite-sum potentials in the stochastic setting, employing an oracle that provides gradients of individual functions. In the second setting, we consider access only to a stochastic evaluation oracle, allowing simultaneous queries at two points of the potential function under the same stochastic parameter. By introducing novel techniques for stochastic gradient estimation, our algorithms improve the gradient and evaluation complexities of classical samplers, such as Hamiltonian Monte Carlo (HMC) and Langevin Monte Carlo (LMC) in terms of dimension, precision, and other problem-dependent parameters. Furthermore, we achieve quantum speedups in optimization, particularly for minimizing non-smooth and approximately convex functions that commonly appear in empirical risk minimization problems.