2026-08-25T11:01:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27305 2026-08-25T07:42:37Z ddc:004 open_access

Quantum Speedups for Sampling and Non-Convex Optimization with Stochastic Oracles Ozgul, Guneykan Li, Xiantao Mahdavi, Mehrdad Wang, Chunhao Quantum algorithms sampling Langevin Monte Carlo Hamiltonian Monte Carlo stochastic oracles non-convex optimization We present quantum speedups for sampling from distributions of the form π∝ e^{-f} on ℝ^d. We consider two stochastic oracle models: a stochastic gradient oracle, where f = 1/n∑_{i = 1}ⁿ f_i and component gradients {∇ f_i}_{i ∈ [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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Guneykan Ozgul and Xiantao Li and Mehrdad Mahdavi and Chunhao Wang 2026 Is Part Of LIPIcs, Volume 389, 21st Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TQC.2026.8 urn:nbn:de:0030-drops-273053 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2026.8 eng https://creativecommons.org/licenses/by/4.0/legalcode