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

arXiv:2504.03626 · quant-ph, cs.LG, math.OC · Submitted 2025-04-04 · Read on arXiv

quant-ph, cs.LG, math.OC

Submitted: 2025-04-04

Updated: 2026-09-02

Comments: 38 pages. Minor changes. To appear in the proceedings of TQC 2026

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

Query Complexity — 20× in this paper · explained in 2 episodes
Hamiltonian Monte Carlo — 15× in this paper
Accuracy — 7× in this paper · explained in 1 episode
Langevin Monte Carlo — 7× in this paper
Langevin Dynamics — 6× in this paper · explained in 2 episodes
Stochastic Gradient Langevin Dynamics — 5× in this paper
Wasserstein Distance — 5× in this paper · explained in 4 episodes
Bayesian Inference — 3× in this paper · explained in 5 episodes
Markov Chain Monte Carlo — 3× in this paper
Control Variates — 2× in this paper
Convergence Guarantees — 2× in this paper · explained in 3 episodes
Combinatorial Optimization — 1× in this paper · explained in 2 episodes
Fisher Information — 1× in this paper · explained in 3 episodes
Generalization — 1× in this paper · explained in 13 episodes
Generative Model — 1× in this paper · explained in 2 episodes
Generative Models — 1× in this paper · explained in 2 episodes
Higher-order derivatives — 1× in this paper · explained in 2 episodes
Loss Function — 1× in this paper · explained in 2 episodes
Regret — 1× in this paper · explained in 3 episodes
Robustness — 1× in this paper · explained in 5 episodes
Score Function — 1× in this paper · explained in 4 episodes
Spectral Gap — 1× in this paper · explained in 5 episodes
Stochastic Gradient Descent (SGD) — 1× in this paper · explained in 5 episodes

Related papers