# Quantum Speedups for Sampling and Non-convex Optimization with Stochastic Oracles

arXiv: https://arxiv.org/abs/2504.03626 · HTML: https://mlsanity.com/paper/2504.03626/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 52 references that are in the map.
- First posted on arXiv 4 Apr 2025.

## Builds on (most cited first, 26 of 26)

- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Stochastic Gradient Hamiltonian Monte Carlo](https://mlsanity.com/paper/1402.4102/) (2014)
- [Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices](https://mlsanity.com/paper/1903.08568/) (2019)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [High-dimensional Bayesian inference via the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1605.01559/) (2016)
- [Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimization](https://mlsanity.com/paper/1707.06618/) (2017)
- [A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/1702.05575/) (2017)
- [Sampling Can Be Faster Than Optimization](https://mlsanity.com/paper/1811.08413/) (2018)
- [Privacy for Free: Posterior Sampling and Stochastic Gradient Monte Carlo](https://mlsanity.com/paper/1502.07645/) (2015)
- [Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling](https://mlsanity.com/paper/2010.09597/) (2020)
- [Control Variates for Stochastic Gradient MCMC](https://mlsanity.com/paper/1706.05439/) (2017)
- [On the Theory of Variance Reduction for Stochastic Gradient Monte Carlo](https://mlsanity.com/paper/1802.05431/) (2018)
- [Convex optimization using quantum oracles](https://mlsanity.com/paper/1809.00643/) (2018)
- [Near-Optimal Quantum Algorithms for Multivariate Mean Estimation](https://mlsanity.com/paper/2111.09787/) (2021)
- [Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization](https://mlsanity.com/paper/2203.16217/) (2022)
- [Quantum algorithms and lower bounds for convex optimization](https://mlsanity.com/paper/1809.01731/) (2018)
- [On Stationary-Point Hitting Time and Ergodicity of Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/1904.13016/) (2019)
- [Quantum speedups for stochastic optimization](https://mlsanity.com/paper/2308.01582/) (2023)
- [Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Bandits](https://mlsanity.com/paper/2209.12897/) (2022)
- [Escaping the Local Minima via Simulated Annealing: Optimization of Approximately Convex Functions](https://mlsanity.com/paper/1501.07242/) (2015)
- [Quantum algorithm for estimating volumes of convex bodies](https://mlsanity.com/paper/1908.03903/) (2019)
- [Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants](https://mlsanity.com/paper/2210.06539/) (2022)
- [Utilising the CLT Structure in Stochastic Gradient based Sampling : Improved Analysis and Faster Algorithms](https://mlsanity.com/paper/2206.03792/) (2022)
- [Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functions](https://mlsanity.com/paper/2310.11445/) (2023)
- [Quantum Algorithms for Non-smooth Non-convex Optimization](https://mlsanity.com/paper/2410.16189/) (2024)
- [Generalized Short Path Algorithms: Towards Super-Quadratic Speedup over Markov Chain Search for Combinatorial Optimization](https://mlsanity.com/paper/2410.23270/) (2024)

## Built on by (most cited first, 2 of 2)

- [Operator-Level Quantum Acceleration of Non-Logconcave Sampling](https://mlsanity.com/paper/2505.05301/) (2025)
- [Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2607.25492/) (2026)

## Abstract (arXiv)

We present quantum speedups for sampling from distributions of the form πpropto e-f on ℝd. We consider two stochastic oracle models: a stochastic gradient oracle, where f=frac1nsumi=1n fi  and component gradients nabla fii ∈ [n] are available, and a stochastic evaluation oracle, where only noisy values of f are available. Our framework accelerates classical stochastic Langevin Monte Carlo (LMC) and Hamiltonian Monte Carlo (HMC) algorithms by replacing stochastic gradient estimators with variance-controlled quantum mean estimation and gradient estimation subroutines. Unlike quantum walk based approaches, our algorithms do not require reversibility or exact gradients, and they preserve the structure of the underlying Markov chain. In the finite-sum setting, quantum mean estimation combined with classical variance-reduction techniques improves the stochastic gradient-query complexity for the approximate sampling task. In the stochastic zeroth-order setting, we develop gradient estimators robust to noisy function evaluations, yielding improved evaluation complexity for LMC and HMC. These results apply to strongly log-concave and/or non-log-concave distributions satisfying a log-Sobolev inequality, with convergence guarantees in Wasserstein distance and Kullback--Leibler divergence. We also show that faster sampling methods lead to quantum speedups for optimization, including for non-smooth and approximately convex objectives.