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

Quantum gradient estimation of Gevrey functions

Arjan Cornelissen

Published Sep 30, 2019• 4 citations
arXivHTMLPDF

Abstract

Gradient-based numerical methods are ubiquitous in optimization techniques frequently applied in industry to solve practical problems. Often times, evaluating the objective function is a complicated process, so estimating the gradient of a function with as few function evaluations as possible is a natural problem. We investigate whether quantum computers can perform $\ell^{\infty}$-approximate gradient estimation of multivariate functions $f : \mathbb{R}^d \to \mathbb{R}$ with fewer function evaluations than classically. Following previous work by Jordan [Jor05] and Gilyén et al. [GAW18], we prove that one can calculate an $\ell^{\infty}$-approximation of the gradient of $f$ with a query complexity that scales sublinearly with $d$ under weaker smoothness conditions than previously considered. Furthermore, for a particular subset of smoothness conditions, we prove a new lower bound on the query complexity of the gradient estimation problem, proving essential optimality of Gilyén et al.'s gradient estimation algorithm in a broader range of parameter values, and affirming the validity of their conjecture [GAW18]. Moreover, we improve their lower bound qualitatively by showing that their algorithm is also optimal for functions that satisfy the imposed smoothness conditions globally instead of locally. Finally, we introduce new ideas to prove lower bounds on the query complexity of the $\ell^p$-approximate gradient estimation problem where $p \in [1,\infty)$, and prove that lifting Gilyén et al.'s algorithm to this domain in the canonical manner is essentially optimal.

DOI
10.48550/arxiv.1909.13528

Related papers

Quantum gradient estimation and its application to quantum reinforcement learning

Arjan Cornelissen

In 2005, Jordan showed how to estimate the gradient of a real-valued function with a high-dimensional domain on a quantum computer. Subsequently, in 2017, it was shown by Gilyén et al. how to do this with a different input model. They also proved optimality of their algorithm for \\ell^\\infty -approximations of functions satisfying some smoothness conditions. In this text, we expand the ideas of Gilyén et al., and extend their algorithm such that functions with fewer regularity constraints can be used as input. Moreover, we show that their algorithm is essentially optimal in the query complexity to the phase oracle even for classes of functions that have more stringent smoothness conditions. Finally, we also prove that their algorithm is optimal for approximating gradients with respect to general \\ell^p -norms, where p \\in [1,\\infty]. Furthermore, we investigate how Gilyén et al.’s algorithm can be used to do reinforcement learning on a quantum computer. We elaborate on Montanaro’s ideas for quantum Monte-Carlo simulation, and show how they can be used to implement quantum value estimation of Markov reward processes. We also show essential optimality of this algorithm in the query complexity of all its oracles. Next, we show how we can construct a quantum policy evaluation algorithm, and how we can use these algorithms as subroutines in Gilyén et al.’s quantum gradient estimation algorithm to perform quantum policy optimization. The most important open questions remain whether it is possible to improve the query complexity of the extension of Gilyén et al.’s algorithm, when function classes containing functions of Gevrey-type 1 are used as input, as at the moment for this specific parameter setting the algorithm is not better than a very simple classical gradient estimation procedure. Improvement of this result would automatically improve the quantum policy optimization routine as well.

•Jan 1, 2018•9 citations

Optimizing quantum optimization algorithms via faster quantum gradient computation

András Gilyén, Srinivasan Arunachalam, Nathan Wiebe

We consider a generic framework of optimization algorithms based on gradient descent. We develop a quantum algorithm that computes the gradient of a multi-variate real-valued function f : Rd → R by evaluating it at only a logarithmic number of times in superposition. Our algorithm is an improved version of Jordan's gradient computation algorithm [28], providing an approximation of the gradient ▽f with quadratically better dependence on the evaluation accuracy of f, for an important class of smooth functions. Furthermore, we show that objective functions arising from variational quantum circuits usually satisfy the necessary smoothness conditions, hence our algorithm provides a quadratic improvement in the complexity of computing their gradient. We also show that in a continuous phase-query model, our gradient computation algorithm has optimal query complexity up to poly-logarithmic factors, for a particular class of smooth functions. Moreover, we show that for low-degree multivariate polynomials our algorithm can provide exponential speedups compared to Jordan's algorithm in terms of the dimension d.One of the technical challenges in applying our gradient computation procedure for quantum optimization problems is the need to convert between a probability oracle (which is common in quantum optimization procedures) and a phase oracle (which is common in quantum algorithms) of the objective function f. We provide efficient subroutines to perform this delicate interconversion between the two types of oracles incurring only a logarithmic overhead, which might be of independent interest. Finally, using these tools we improve the runtime of prior approaches for training quantum auto-encoders, variational quantum eigensolvers (VQE), and quantum approximate optimization algorithms (QAOA).

•Jan 6, 2019•33 citations

Optimizing quantum optimization algorithms via faster quantum gradient computation

András Gilyén, Srinivasan Arunachalam, Nathan Wiebe

We consider a generic framework of optimization algorithms based on gradient descent. We develop a quantum algorithm that computes the gradient of a multi-variate realvalued function f : ℝd → ℝ by evaluating it at only a logarithmic number of times in superposition. Our algorithm is an improved version of Jordan's gradient computation algorithm [28], providing an approximation of the gradient ▽f with quadratically better dependence on the evaluation accuracy of f, for an important class of smooth functions. Furthermore, we show that objective functions arising from variational quantum circuits usually satisfy the necessary smoothness conditions, hence our algorithm provides a quadratic improvement in the complexity of computing their gradient. We also show that in a continuous phase-query model, our gradient computation algorithm has optimal query complexity up to poly-logarithmic factors, for a particular class of smooth functions. Moreover, we show that for low-degree multivariate polynomials our algorithm can provide exponential speedups compared to Jordan's algorithm in terms of the dimension d. One of the technical challenges in applying our gradient computation procedure for quantum optimization problems is the need to convert between a probability oracle (which is common in quantum optimization procedures) and a phase oracle (which is common in quantum algorithms) of the objective function f. We provide efficient subroutines to perform this delicate interconversion between the two types of oracles incurring only a logarithmic overhead, which might be of independent interest. Finally, using these tools we improve the runtime of prior approaches for training quantum auto-encoders, variational quantum eigensolvers (VQE), and quantum approximate optimization algorithms (QAOA).

arXiv:1711.00465•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2019•103 citations

Quantum Lower Bounds for Finding Stationary Points of Nonconvex Functions

Zhang, Chenyi, Tongyang Li

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.

arXiv:2212.03906•Dec 7, 2022•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

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
Gradient-based numerical methods are ubiquitous in optimization techniques frequently applied in industry to solve practical problems. Often times, evaluating the objective function is a complicated process, so estimating the gradient of a function with as few function evaluations as possible is a natural problem. We investigate whether quantum computers can perform ℓ∞\ell^{\infty}ℓ∞-approximate gradient estimation of multivariate functions f:Rd→Rf : \mathbb{R}^d \to \mathbb{R}f:Rd→R with fewer function evaluations than classically. Following previous work by Jordan [Jor05] and Gilyén et al. [GAW18], we prove that one can calculate an ℓ∞\ell^{\infty}ℓ∞-approximation of the gradient of fff with a query complexity that scales sublinearly with ddd under weaker smoothness conditions than previously considered. Furthermore, for a particular subset of smoothness conditions, we prove a new lower bound on the query complexity of the gradient estimation problem, proving essential optimality of Gilyén et al.'s gradient estimation algorithm in a broader range of parameter values, and affirming the validity of their conjecture [GAW18]. Moreover, we improve their lower bound qualitatively by showing that their algorithm is also optimal for functions that satisfy the imposed smoothness conditions globally instead of locally. Finally, we introduce new ideas to prove lower bounds on the query complexity of the ℓp\ell^pℓp-approximate gradient estimation problem where p∈[1,∞)p \in [1,\infty)p∈[1,∞), and prove that lifting Gilyén et al.'s algorithm to this domain in the canonical manner is essentially optimal.
In 2005, Jordan showed how to estimate the gradient of a real-valued function with a high-dimensional domain on a quantum computer. Subsequently, in 2017, it was shown by Gilyén et al. how to do this with a different input model. They also proved optimality of their algorithm for \\ell^\\infty -approximations of functions satisfying some smoothness conditions. In this text, we expand the ideas of Gilyén et al., and extend their algorithm such that functions with fewer regularity constraints can be used as input. Moreover, we show that their algorithm is essentially optimal in the query complexity to the phase oracle even for classes of functions that have more stringent smoothness conditions. Finally, we also prove that their algorithm is optimal for approximating gradients with respect to general \\ell^p -norms, where p \\in [1,\\infty]. Furthermore, we investigate how Gilyén et al.’s algorithm can be used to do reinforcement learning on a quantum computer. We elaborate on Montanaro’s ideas for quantum Monte-Carlo simulation, and show how they can be used to implement quantum value estimation of Markov reward processes. We also show essential optimality of this algorithm in the query complexity of all its oracles. Next, we show how we can construct a quantum policy evaluation algorithm, and how we can use these algorithms as subroutines in Gilyén et al.’s quantum gradient estimation algorithm to perform quantum policy optimization. The most important open questions remain whether it is possible to improve the query complexity of the extension of Gilyén et al.’s algorithm, when function classes containing functions of Gevrey-type 1 are used as input, as at the moment for this specific parameter setting the algorithm is not better than a very simple classical gradient estimation procedure. Improvement of this result would automatically improve the quantum policy optimization routine as well.
We consider a generic framework of optimization algorithms based on gradient descent. We develop a quantum algorithm that computes the gradient of a multi-variate real-valued function f : Rd → R by evaluating it at only a logarithmic number of times in superposition. Our algorithm is an improved version of Jordan's gradient computation algorithm [28], providing an approximation of the gradient ▽f with quadratically better dependence on the evaluation accuracy of f, for an important class of smooth functions. Furthermore, we show that objective functions arising from variational quantum circuits usually satisfy the necessary smoothness conditions, hence our algorithm provides a quadratic improvement in the complexity of computing their gradient. We also show that in a continuous phase-query model, our gradient computation algorithm has optimal query complexity up to poly-logarithmic factors, for a particular class of smooth functions. Moreover, we show that for low-degree multivariate polynomials our algorithm can provide exponential speedups compared to Jordan's algorithm in terms of the dimension d.One of the technical challenges in applying our gradient computation procedure for quantum optimization problems is the need to convert between a probability oracle (which is common in quantum optimization procedures) and a phase oracle (which is common in quantum algorithms) of the objective function f. We provide efficient subroutines to perform this delicate interconversion between the two types of oracles incurring only a logarithmic overhead, which might be of independent interest. Finally, using these tools we improve the runtime of prior approaches for training quantum auto-encoders, variational quantum eigensolvers (VQE), and quantum approximate optimization algorithms (QAOA).
We consider a generic framework of optimization algorithms based on gradient descent. We develop a quantum algorithm that computes the gradient of a multi-variate realvalued function f : ℝd → ℝ by evaluating it at only a logarithmic number of times in superposition. Our algorithm is an improved version of Jordan's gradient computation algorithm [28], providing an approximation of the gradient ▽f with quadratically better dependence on the evaluation accuracy of f, for an important class of smooth functions. Furthermore, we show that objective functions arising from variational quantum circuits usually satisfy the necessary smoothness conditions, hence our algorithm provides a quadratic improvement in the complexity of computing their gradient. We also show that in a continuous phase-query model, our gradient computation algorithm has optimal query complexity up to poly-logarithmic factors, for a particular class of smooth functions. Moreover, we show that for low-degree multivariate polynomials our algorithm can provide exponential speedups compared to Jordan's algorithm in terms of the dimension d. One of the technical challenges in applying our gradient computation procedure for quantum optimization problems is the need to convert between a probability oracle (which is common in quantum optimization procedures) and a phase oracle (which is common in quantum algorithms) of the objective function f. We provide efficient subroutines to perform this delicate interconversion between the two types of oracles incurring only a logarithmic overhead, which might be of independent interest. Finally, using these tools we improve the runtime of prior approaches for training quantum auto-encoders, variational quantum eigensolvers (VQE), and quantum approximate optimization algorithms (QAOA).
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.
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.
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.