2025/04/04 by Guneykan Ozgul, Xiantao Li, Ozgul, Guneykan +5
Computer Science · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Machine Learning (cs.LG) #Markov Chains and Monte Carlo Methods #Optimization and Control (math.OC) #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2504.03626
openalex publication_date 2025/04/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 π∝ 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.