Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2510.20745 · neural information processing systems

Isotropic Noise in Stochastic and Quantum Convex Optimization

Annie Marsden, Liam O’Carroll, Aaron Sidford, Chenyi Zhang

Published Jan 1, 2025• 0 citations
arXivHTMLPDF

Abstract

We consider the problem of minimizing a $d$-dimensional Lipschitz convex function using a stochastic gradient oracle. We introduce and motivate a setting where the noise of the stochastic gradient is isotropic in that it is bounded in every direction with high probability. We then develop an algorithm for this setting which improves upon prior results by a factor of $d$ in certain regimes, and as a corollary, achieves a new state-of-the-art complexity for sub-exponential noise. We give matching lower bounds (up to polylogarithmic factors) for both results. Additionally, we develop an efficient quantum isotropifier, a quantum algorithm which converts a variance-bounded quantum sampling oracle into one that outputs an unbiased estimate with isotropic error. Combining our results, we obtain improved dimension-dependent rates for quantum stochastic convex optimization.

DOI
10.52202/085713-3722

Related papers

Quantum speedups for stochastic optimization

Aaron Sidford, Chenyi Zhang

We consider the problem of minimizing a continuous function given quantum access to a stochastic gradient oracle. We provide two new methods for the special case of minimizing a Lipschitz convex function. Each method obtains a dimension versus accuracy trade-off which is provably unachievable classically and we prove that one method is asymptotically optimal in low-dimensional settings. Additionally, we provide quantum algorithms for computing a critical point of a smooth non-convex function at rates not known to be achievable classically. To obtain these results we build upon the quantum multivariate mean estimation result of Cornelissen et al. 2022 and provide a general quantum-variance reduction technique of independent interest.

arXiv:2308.01582•neural information processing systems•Jan 1, 2023•1 citation

Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise

Bin Luo, Chengchang Liu, Jonathan Allcock +2 more

We study stochastic optimization with heavy-tailed gradient noise. We first propose a novel quantum mean estimator for multivariate heavy-tailed random variables that achieves lower query complexity than optimal classical estimators in the low-dimensional regime. We further develop an unbiased quantum mean estimator by applying a generalized multi-level Monte Carlo technique. We prove quantum lower bounds showing that, when the dimension $d$ of the random vector is small and can be viewed as a constant, our quantum estimators are optimal up to logarithmic factors. We further derive stronger dimension-dependent lower bounds for tail index $p>4/3$, showing that a nontrivial dependence on the dimension is unavoidable in the low-dimensional regime. Based on these estimators, we propose a quantum normalized stochastic gradient descent method ($\texttt{QNSGD}$), which finds an $ε$-stationary point using $\tilde{\mathcal{O}}\big(\sqrt d\,ε^{-\frac{5p-4}{2p-2}}\big)$ queries to the quantum stochastic gradient oracle. For a convex objective function, we propose a quantum projected stochastic gradient descent method ($\texttt{QPSGD}$), which computes a solution with $ε$-optimal solution using $\tilde{\mathcal{O}}\big(\sqrt d\,ε^{-\frac{3p-2}{2p-2}}+ε^{-2}\big)$ queries in expectation. These sharper bounds improve upon the classical lower bounds $Ω\big(ε^{-\frac{3p-2}{p-1}}\big)$ for nonconvex problems and $Ω\big(ε^{-\frac{p}{p-1}}\big)$ for convex problems in the low-dimensional regimes $d\lesssimε^{-\frac{p}{p-1}}$ and $d\lesssimε^{-\frac{2-p}{p-1}}$, respectively.

arXiv:2607.25492•Jul 28, 2026•0 citations

Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss

Hao Wang, Zhang, Chenyi, Tongyang Li

The problem of minimizing the maximum of $N$ convex, Lipschitz functions plays significant roles in optimization and machine learning. It has a series of results, with the most recent one requiring $O(Nε^{-2/3} + ε^{-8/3})$ queries to a first-order oracle to compute an $ε$-suboptimal point. On the other hand, quantum algorithms for optimization are rapidly advancing with speedups shown on many important optimization problems. In this paper, we conduct a systematic study for quantum algorithms and lower bounds for minimizing the maximum of $N$ convex, Lipschitz functions. On one hand, we develop quantum algorithms with an improved complexity bound of $\tilde{O}(\sqrt{N}ε^{-5/3} + ε^{-8/3})$. On the other hand, we prove that quantum algorithms must take $\tildeΩ(\sqrt{N}ε^{-2/3})$ queries to a first order quantum oracle, showing that our dependence on $N$ is optimal up to poly-logarithmic factors.

arXiv:2402.12745•Feb 20, 2024•0 citations

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

Guneykan Ozgul, Xiantao Li, Mehrdad Mahdavi +1 more

We present quantum speedups for sampling from distributions of the form $π\propto e^{-f}$ on $\mathbb{R}^d$. We consider two stochastic oracle models: a stochastic gradient oracle, where $f=\frac{1}{n}\sum_{i=1}^n f_i $ and component gradients $\{\nabla f_i\}_{i \in [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.

arXiv:2504.03626•Leibniz international proceedings in informatics•Apr 4, 2025•0 citations

Quantum Algorithms for Non-smooth Non-convex Optimization

Chengchang Liu, Chaowen Guan, Jianhao He +1 more

This paper considers the problem for finding the $(δ,ε)$-Goldstein stationary point of Lipschitz continuous objective, which is a rich function class to cover a great number of important applications. We construct a zeroth-order quantum estimator for the gradient of the smoothed surrogate. Based on such estimator, we propose a novel quantum algorithm that achieves a query complexity of $\tilde{\mathcal{O}}(d^{3/2}δ^{-1}ε^{-3})$ on the stochastic function value oracle, where $d$ is the dimension of the problem. We also enhance the query complexity to $\tilde{\mathcal{O}}(d^{3/2}δ^{-1}ε^{-7/3})$ by introducing a variance reduction variant. Our findings demonstrate the clear advantages of utilizing quantum techniques for non-convex non-smooth optimization, as they outperform the optimal classical methods on the dependency of $ε$ by a factor of $ε^{-2/3}$.

arXiv:2410.16189•neural information processing systems•Jan 1, 2024•0 citations

On Speedups for Convex Optimization via Quantum Dynamics

Shouvanik Chakrabarti, Dylan Herman, Watkins, Jacob +4 more

This work investigates the possibility of quantum speedups for continuous optimization through quantum Hamiltonian simulation. We establish the first rigorous query complexity bounds for unconstrained convex optimization via digital quantum annealing, based on the non-adiabatic Quantum Hamiltonian Descent (QHD) framework. In the process, we derive rigorous resource estimates for digital quantum simulation of Schrödinger operators depending only on input simulation parameters, given black-box evaluation access to separable, Lipschitz continuous potential b(t) f(x). We apply these simulation bounds to assess the complexity of high-dimensional convex optimization. Our annealing schedule achieves arbitrarily fast convergence rates in the evolution time, with computational time determined solely by the cost of discretization. We show that a G-Lipschitz convex function can be optimized to an error of ε with 𝒪̃(d^{1.5} G² R²/ε²) queries, given a starting point that is Euclidean distance R from optimal. Under reasonable assumptions such as the complexity of simulating Schrödinger operators, we show that Ω̃(d/ε²) queries are necessary. This suggests QHD does not offer improvements over classical methods in the noiseless zeroth order setting. However, we show that the QHD algorithm can tolerate 𝒪̃(ε³ /d^{1.5} G² R²) noise in function evaluation, and as a result, provides a super-quadratic query advantage over the best existing noise-tolerant classical algorithms in the high-dimensional setting. We leverage this to design a quantum algorithm for stochastic convex optimization that offers a super-quadratic speedup over all known classical and quantum algorithms in this regime. To our knowledge, these results represent the first rigorous quantum speedups for convex optimization obtained through a dynamical algorithm.

arXiv:2503.24332•Leibniz international proceedings in informatics•Mar 31, 2025•0 citations
We consider the problem of minimizing a ddd-dimensional Lipschitz convex function using a stochastic gradient oracle. We introduce and motivate a setting where the noise of the stochastic gradient is isotropic in that it is bounded in every direction with high probability. We then develop an algorithm for this setting which improves upon prior results by a factor of ddd in certain regimes, and as a corollary, achieves a new state-of-the-art complexity for sub-exponential noise. We give matching lower bounds (up to polylogarithmic factors) for both results. Additionally, we develop an efficient quantum isotropifier, a quantum algorithm which converts a variance-bounded quantum sampling oracle into one that outputs an unbiased estimate with isotropic error. Combining our results, we obtain improved dimension-dependent rates for quantum stochastic convex optimization.
We consider the problem of minimizing a continuous function given quantum access to a stochastic gradient oracle. We provide two new methods for the special case of minimizing a Lipschitz convex function. Each method obtains a dimension versus accuracy trade-off which is provably unachievable classically and we prove that one method is asymptotically optimal in low-dimensional settings. Additionally, we provide quantum algorithms for computing a critical point of a smooth non-convex function at rates not known to be achievable classically. To obtain these results we build upon the quantum multivariate mean estimation result of Cornelissen et al. 2022 and provide a general quantum-variance reduction technique of independent interest.
We study stochastic optimization with heavy-tailed gradient noise. We first propose a novel quantum mean estimator for multivariate heavy-tailed random variables that achieves lower query complexity than optimal classical estimators in the low-dimensional regime. We further develop an unbiased quantum mean estimator by applying a generalized multi-level Monte Carlo technique. We prove quantum lower bounds showing that, when the dimension ddd of the random vector is small and can be viewed as a constant, our quantum estimators are optimal up to logarithmic factors. We further derive stronger dimension-dependent lower bounds for tail index p>4/3p>4/3p>4/3, showing that a nontrivial dependence on the dimension is unavoidable in the low-dimensional regime. Based on these estimators, we propose a quantum normalized stochastic gradient descent method (QNSGD\texttt{QNSGD}QNSGD), which finds an εεε-stationary point using O~(d ε−5p−42p−2)\tilde{\mathcal{O}}\big(\sqrt d\,ε^{-\frac{5p-4}{2p-2}}\big)O~(d​ε−2p−25p−4​) queries to the quantum stochastic gradient oracle. For a convex objective function, we propose a quantum projected stochastic gradient descent method (QPSGD\texttt{QPSGD}QPSGD), which computes a solution with εεε-optimal solution using O~(d ε−3p−22p−2+ε−2)\tilde{\mathcal{O}}\big(\sqrt d\,ε^{-\frac{3p-2}{2p-2}}+ε^{-2}\big)O~(d​ε−2p−23p−2​+ε−2) queries in expectation. These sharper bounds improve upon the classical lower bounds Ω(ε−3p−2p−1)Ω\big(ε^{-\frac{3p-2}{p-1}}\big)Ω(ε−p−13p−2​) for nonconvex problems and Ω(ε−pp−1)Ω\big(ε^{-\frac{p}{p-1}}\big)Ω(ε−p−1p​) for convex problems in the low-dimensional regimes d≲ε−pp−1d\lesssimε^{-\frac{p}{p-1}}d≲ε−p−1p​ and d≲ε−2−pp−1d\lesssimε^{-\frac{2-p}{p-1}}d≲ε−p−12−p​, respectively.
The problem of minimizing the maximum of NNN convex, Lipschitz functions plays significant roles in optimization and machine learning. It has a series of results, with the most recent one requiring O(Nε−2/3+ε−8/3)O(Nε^{-2/3} + ε^{-8/3})O(Nε−2/3+ε−8/3) queries to a first-order oracle to compute an εεε-suboptimal point. On the other hand, quantum algorithms for optimization are rapidly advancing with speedups shown on many important optimization problems. In this paper, we conduct a systematic study for quantum algorithms and lower bounds for minimizing the maximum of NNN convex, Lipschitz functions. On one hand, we develop quantum algorithms with an improved complexity bound of O~(Nε−5/3+ε−8/3)\tilde{O}(\sqrt{N}ε^{-5/3} + ε^{-8/3})O~(N​ε−5/3+ε−8/3). On the other hand, we prove that quantum algorithms must take Ω~(Nε−2/3)\tildeΩ(\sqrt{N}ε^{-2/3})Ω~(N​ε−2/3) queries to a first order quantum oracle, showing that our dependence on NNN is optimal up to poly-logarithmic factors.
We present quantum speedups for sampling from distributions of the form π∝e−fπ\propto e^{-f}π∝e−f on Rd\mathbb{R}^dRd. We consider two stochastic oracle models: a stochastic gradient oracle, where $f=\frac{1}{n}\sum_{i=1}^n f_i $ and component gradients {∇fi}i∈[n]\{\nabla f_i\}_{i \in [n]}{∇fi​}i∈[n]​ are available, and a stochastic evaluation oracle, where only noisy values of fff 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.
This paper considers the problem for finding the (δ,ε)(δ,ε)(δ,ε)-Goldstein stationary point of Lipschitz continuous objective, which is a rich function class to cover a great number of important applications. We construct a zeroth-order quantum estimator for the gradient of the smoothed surrogate. Based on such estimator, we propose a novel quantum algorithm that achieves a query complexity of O~(d3/2δ−1ε−3)\tilde{\mathcal{O}}(d^{3/2}δ^{-1}ε^{-3})O~(d3/2δ−1ε−3) on the stochastic function value oracle, where ddd is the dimension of the problem. We also enhance the query complexity to O~(d3/2δ−1ε−7/3)\tilde{\mathcal{O}}(d^{3/2}δ^{-1}ε^{-7/3})O~(d3/2δ−1ε−7/3) by introducing a variance reduction variant. Our findings demonstrate the clear advantages of utilizing quantum techniques for non-convex non-smooth optimization, as they outperform the optimal classical methods on the dependency of εεε by a factor of ε−2/3ε^{-2/3}ε−2/3.
This work investigates the possibility of quantum speedups for continuous optimization through quantum Hamiltonian simulation. We establish the first rigorous query complexity bounds for unconstrained convex optimization via digital quantum annealing, based on the non-adiabatic Quantum Hamiltonian Descent (QHD) framework. In the process, we derive rigorous resource estimates for digital quantum simulation of Schrödinger operators depending only on input simulation parameters, given black-box evaluation access to separable, Lipschitz continuous potential b(t) f(x). We apply these simulation bounds to assess the complexity of high-dimensional convex optimization. Our annealing schedule achieves arbitrarily fast convergence rates in the evolution time, with computational time determined solely by the cost of discretization. We show that a G-Lipschitz convex function can be optimized to an error of ε with 𝒪̃(d^{1.5} G² R²/ε²) queries, given a starting point that is Euclidean distance R from optimal. Under reasonable assumptions such as the complexity of simulating Schrödinger operators, we show that Ω̃(d/ε²) queries are necessary. This suggests QHD does not offer improvements over classical methods in the noiseless zeroth order setting. However, we show that the QHD algorithm can tolerate 𝒪̃(ε³ /d^{1.5} G² R²) noise in function evaluation, and as a result, provides a super-quadratic query advantage over the best existing noise-tolerant classical algorithms in the high-dimensional setting. We leverage this to design a quantum algorithm for stochastic convex optimization that offers a super-quadratic speedup over all known classical and quantum algorithms in this regime. To our knowledge, these results represent the first rigorous quantum speedups for convex optimization obtained through a dynamical algorithm.