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:2212.03906

Quantum Lower Bounds for Finding Stationary Points of Nonconvex Functions

Zhang, Chenyi, Tongyang Li

Published Dec 7, 2022• 1 citation
arXivHTMLPDF

Abstract

Quantum algorithms for optimization problems are of general interest. Despite recent progress in classical lower bounds for nonconvex optimization under different settings and quantum lower bounds for convex optimization, quantum lower bounds for nonconvex optimization are still widely open. In this paper, we conduct a systematic study of quantum query lower bounds on finding $ε$-approximate stationary points of nonconvex functions, and we consider the following two important settings: 1) having access to $p$-th order derivatives; or 2) having access to stochastic gradients. The classical query lower bounds is $Ω\big(ε^{-\frac{1+p}{p}}\big)$ regarding the first setting, and $Ω(ε^{-4})$ regarding the second setting (or $Ω(ε^{-3})$ if the stochastic gradient function is mean-squared smooth). In this paper, we extend all these classical lower bounds to the quantum setting. They match the classical algorithmic results respectively, demonstrating that there is no quantum speedup for finding $ε$-stationary points of nonconvex functions with $p$-th order derivative inputs or stochastic gradient inputs, whether with or without the mean-squared smoothness assumption. Technically, our quantum lower bounds are obtained by showing that the sequential nature of classical hard instances in all these settings also applies to quantum queries, preventing any quantum speedup other than revealing information of the stationary points sequentially.

DOI
10.48550/arxiv.2212.03906

Related papers

Robustness of Quantum Algorithms for Nonconvex Optimization

Weiyuan Gong, Zhang, Chenyi, Tongyang Li

Recent results suggest that quantum computers possess the potential to speed up nonconvex optimization problems. However, a crucial factor for the implementation of quantum optimization algorithms is their robustness against experimental and statistical noises. In this paper, we systematically study quantum algorithms for finding an $ε$-approximate second-order stationary point ($ε$-SOSP) of a $d$-dimensional nonconvex function, a fundamental problem in nonconvex optimization, with noisy zeroth- or first-order oracles as inputs. We first prove that, up to noise of $O(ε^{10}/d^5)$, accelerated perturbed gradient descent with quantum gradient estimation takes $O(\log d/ε^{1.75})$ quantum queries to find an $ε$-SOSP. We then prove that perturbed gradient descent is robust to the noise of $O(ε^6/d^4)$ and $O(ε/d^{0.5+ζ})$ for $ζ>0$ on the zeroth- and first-order oracles, respectively, which provides a quantum algorithm with poly-logarithmic query complexity. We then propose a stochastic gradient descent algorithm using quantum mean estimation on the Gaussian smoothing of noisy oracles, which is robust to $O(ε^{1.5}/d)$ and $O(ε/\sqrt{d})$ noise on the zeroth- and first-order oracles, respectively. The quantum algorithm takes $O(d^{2.5}/ε^{3.5})$ and $O(d^2/ε^3)$ queries to the two oracles, giving a polynomial speedup over the classical counterparts. Moreover, we characterize the domains where quantum algorithms can find an $ε$-SOSP with poly-logarithmic, polynomial, or exponential number of queries in $d$, or the problem is information-theoretically unsolvable even by an infinite number of queries. In addition, we prove an $Ω(ε^{-12/7})$ lower bound in $ε$ for any randomized classical and quantum algorithm to find an $ε$-SOSP using either noisy zeroth- or first-order oracles.

arXiv:2212.02548•Dec 5, 2022•0 citations

No Quantum Speedup over Gradient Descent for Non-Smooth Convex Optimization

Ankit Garg, Robin Kothari, Praneeth Netrapalli +1 more

We study the first-order convex optimization problem, where we have black-box access to a (not necessarily smooth) function $f:\mathbb{R}^n \to \mathbb{R}$ and its (sub)gradient. Our goal is to find an $ε$-approximate minimum of $f$ starting from a point that is distance at most $R$ from the true minimum. If $f$ is $G$-Lipschitz, then the classic gradient descent algorithm solves this problem with $O((GR/ε)^{2})$ queries. Importantly, the number of queries is independent of the dimension $n$ and gradient descent is optimal in this regard: No deterministic or randomized algorithm can achieve better complexity that is still independent of the dimension $n$. In this paper we reprove the randomized lower bound of $Ω((GR/ε)^{2})$ using a simpler argument than previous lower bounds. We then show that although the function family used in the lower bound is hard for randomized algorithms, it can be solved using $O(GR/ε)$ quantum queries. We then show an improved lower bound against quantum algorithms using a different set of instances and establish our main result that in general even quantum algorithms need $Ω((GR/ε)^2)$ queries to solve the problem. Hence there is no quantum speedup over gradient descent for black-box first-order convex optimization without further assumptions on the function family.

arXiv:2010.01801•Leibniz international proceedings in informatics•Oct 5, 2020•1 citation

No Quantum Speedup over Gradient Descent for Non-Smooth Convex Optimization

Ankit Garg, Robin Kothari, Praneeth Netrapalli +1 more

We study the first-order convex optimization problem, where we have black-box access to a (not necessarily smooth) function f:ℝⁿ → ℝ and its (sub)gradient. Our goal is to find an ε-approximate minimum of f starting from a point that is distance at most R from the true minimum. If f is G-Lipschitz, then the classic gradient descent algorithm solves this problem with O((GR/ε)²) queries. Importantly, the number of queries is independent of the dimension n and gradient descent is optimal in this regard: No deterministic or randomized algorithm can achieve better complexity that is still independent of the dimension n. In this paper we reprove the randomized lower bound of Ω((GR/ε)²) using a simpler argument than previous lower bounds. We then show that although the function family used in the lower bound is hard for randomized algorithms, it can be solved using O(GR/ε) quantum queries. We then show an improved lower bound against quantum algorithms using a different set of instances and establish our main result that in general even quantum algorithms need Ω((GR/ε)²) queries to solve the problem. Hence there is no quantum speedup over gradient descent for black-box first-order convex optimization without further assumptions on the function family.

•Jan 1, 2021•4 citations

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

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

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 algorithms for optimization problems are of general interest. Despite recent progress in classical lower bounds for nonconvex optimization under different settings and quantum lower bounds for convex optimization, quantum lower bounds for nonconvex optimization are still widely open. In this paper, we conduct a systematic study of quantum query lower bounds on finding εεε-approximate stationary points of nonconvex functions, and we consider the following two important settings: 1) having access to ppp-th order derivatives; or 2) having access to stochastic gradients. The classical query lower bounds is Ω(ε−1+pp)Ω\big(ε^{-\frac{1+p}{p}}\big)Ω(ε−p1+p​) regarding the first setting, and Ω(ε−4)Ω(ε^{-4})Ω(ε−4) regarding the second setting (or Ω(ε−3)Ω(ε^{-3})Ω(ε−3) if the stochastic gradient function is mean-squared smooth). In this paper, we extend all these classical lower bounds to the quantum setting. They match the classical algorithmic results respectively, demonstrating that there is no quantum speedup for finding εεε-stationary points of nonconvex functions with ppp-th order derivative inputs or stochastic gradient inputs, whether with or without the mean-squared smoothness assumption. Technically, our quantum lower bounds are obtained by showing that the sequential nature of classical hard instances in all these settings also applies to quantum queries, preventing any quantum speedup other than revealing information of the stationary points sequentially.
Recent results suggest that quantum computers possess the potential to speed up nonconvex optimization problems. However, a crucial factor for the implementation of quantum optimization algorithms is their robustness against experimental and statistical noises. In this paper, we systematically study quantum algorithms for finding an εεε-approximate second-order stationary point (εεε-SOSP) of a ddd-dimensional nonconvex function, a fundamental problem in nonconvex optimization, with noisy zeroth- or first-order oracles as inputs. We first prove that, up to noise of O(ε10/d5)O(ε^{10}/d^5)O(ε10/d5), accelerated perturbed gradient descent with quantum gradient estimation takes O(log⁡d/ε1.75)O(\log d/ε^{1.75})O(logd/ε1.75) quantum queries to find an εεε-SOSP. We then prove that perturbed gradient descent is robust to the noise of O(ε6/d4)O(ε^6/d^4)O(ε6/d4) and O(ε/d0.5+ζ)O(ε/d^{0.5+ζ})O(ε/d0.5+ζ) for ζ>0ζ>0ζ>0 on the zeroth- and first-order oracles, respectively, which provides a quantum algorithm with poly-logarithmic query complexity. We then propose a stochastic gradient descent algorithm using quantum mean estimation on the Gaussian smoothing of noisy oracles, which is robust to O(ε1.5/d)O(ε^{1.5}/d)O(ε1.5/d) and O(ε/d)O(ε/\sqrt{d})O(ε/d​) noise on the zeroth- and first-order oracles, respectively. The quantum algorithm takes O(d2.5/ε3.5)O(d^{2.5}/ε^{3.5})O(d2.5/ε3.5) and O(d2/ε3)O(d^2/ε^3)O(d2/ε3) queries to the two oracles, giving a polynomial speedup over the classical counterparts. Moreover, we characterize the domains where quantum algorithms can find an εεε-SOSP with poly-logarithmic, polynomial, or exponential number of queries in ddd, or the problem is information-theoretically unsolvable even by an infinite number of queries. In addition, we prove an Ω(ε−12/7)Ω(ε^{-12/7})Ω(ε−12/7) lower bound in εεε for any randomized classical and quantum algorithm to find an εεε-SOSP using either noisy zeroth- or first-order oracles.
We study the first-order convex optimization problem, where we have black-box access to a (not necessarily smooth) function f:Rn→Rf:\mathbb{R}^n \to \mathbb{R}f:Rn→R and its (sub)gradient. Our goal is to find an εεε-approximate minimum of fff starting from a point that is distance at most RRR from the true minimum. If fff is GGG-Lipschitz, then the classic gradient descent algorithm solves this problem with O((GR/ε)2)O((GR/ε)^{2})O((GR/ε)2) queries. Importantly, the number of queries is independent of the dimension nnn and gradient descent is optimal in this regard: No deterministic or randomized algorithm can achieve better complexity that is still independent of the dimension nnn. In this paper we reprove the randomized lower bound of Ω((GR/ε)2)Ω((GR/ε)^{2})Ω((GR/ε)2) using a simpler argument than previous lower bounds. We then show that although the function family used in the lower bound is hard for randomized algorithms, it can be solved using O(GR/ε)O(GR/ε)O(GR/ε) quantum queries. We then show an improved lower bound against quantum algorithms using a different set of instances and establish our main result that in general even quantum algorithms need Ω((GR/ε)2)Ω((GR/ε)^2)Ω((GR/ε)2) queries to solve the problem. Hence there is no quantum speedup over gradient descent for black-box first-order convex optimization without further assumptions on the function family.
We study the first-order convex optimization problem, where we have black-box access to a (not necessarily smooth) function f:ℝⁿ → ℝ and its (sub)gradient. Our goal is to find an ε-approximate minimum of f starting from a point that is distance at most R from the true minimum. If f is G-Lipschitz, then the classic gradient descent algorithm solves this problem with O((GR/ε)²) queries. Importantly, the number of queries is independent of the dimension n and gradient descent is optimal in this regard: No deterministic or randomized algorithm can achieve better complexity that is still independent of the dimension n. In this paper we reprove the randomized lower bound of Ω((GR/ε)²) using a simpler argument than previous lower bounds. We then show that although the function family used in the lower bound is hard for randomized algorithms, it can be solved using O(GR/ε) quantum queries. We then show an improved lower bound against quantum algorithms using a different set of instances and establish our main result that in general even quantum algorithms need Ω((GR/ε)²) queries to solve the problem. Hence there is no quantum speedup over gradient descent for black-box first-order convex optimization without further assumptions on the function family.
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.
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.
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.