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

Quantum gradient estimation and its application to quantum reinforcement learning

Arjan Cornelissen

Published Jan 1, 2018• 9 citations
OpenAlex

Abstract

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.

Related papers

Quantum gradient estimation of Gevrey functions

Arjan Cornelissen

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.

arXiv:1909.13528•Sep 30, 2019•4 citations

Improved Quantum Algorithms for Reinforcement Learning Under a Generative Model

Joao F. Doriguello

Reinforcement learning is a subfield of machine learning that studies how an agent interacts with an environment in order to extract as large a reward as possible. A standard approach to study such interaction is through Markov Decision Processes (MDPs) and the task of choosing an optimal policy --- a function that tells the agent which action to take. In this work, we study two types of MDPs --- finite-horizon and infinite-horizon discounted --- and propose new quantum algorithms for computing approximate optimal policies. Our quantum algorithms are based on a new combination of standard value iteration and quantum subroutines like quantum mean estimation and quantum maximum finding, overall enhanced with techniques from sample-optimal classical algorithms. Our resulting query complexities improve upon previous works, thus approaching already established quantum lower bounds.

quant-pharXiv:2608.02826•Aug 5, 2026•0 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 Algorithms for Reinforcement Learning with a Generative Model

Daochen Wang, Aarthi Sundaram, Robin Kothari +2 more

Reinforcement learning studies how an agent should interact with an environment to maximize its cumulative reward. A standard way to study this question abstractly is to ask how many samples an agent needs from the environment to learn an optimal policy for a $γ$-discounted Markov decision process (MDP). For such an MDP, we design quantum algorithms that approximate an optimal policy ($π^*$), the optimal value function ($v^*$), and the optimal $Q$-function ($q^*$), assuming the algorithms can access samples from the environment in quantum superposition. This assumption is justified whenever there exists a simulator for the environment; for example, if the environment is a video game or some other program. Our quantum algorithms, inspired by value iteration, achieve quadratic speedups over the best-possible classical sample complexities in the approximation accuracy ($ε$) and two main parameters of the MDP: the effective time horizon ($\frac{1}{1-γ}$) and the size of the action space ($A$). Moreover, we show that our quantum algorithm for computing $q^*$ is optimal by proving a matching quantum lower bound.

arXiv:2112.08451•Dec 15, 2021•14 citations

Quantum Policy Iteration via Amplitude Estimation and Grover Search -- Towards Quantum Advantage for Reinforcement Learning

Simon M. Wiedemann, Daniel M. Hein, Steffen Udluft +1 more

We present a full implementation and simulation of a novel quantum reinforcement learning method. Our work is a detailed and formal proof of concept for how quantum algorithms can be used to solve reinforcement learning problems and shows that, given access to error-free, efficient quantum realizations of the agent and environment, quantum methods can yield provable improvements over classical Monte-Carlo based methods in terms of sample complexity. Our approach shows in detail how to combine amplitude estimation and Grover search into a policy evaluation and improvement scheme. We first develop quantum policy evaluation (QPE) which is quadratically more efficient compared to an analogous classical Monte Carlo estimation and is based on a quantum mechanical realization of a finite Markov decision process (MDP). Building on QPE, we derive a quantum policy iteration that repeatedly improves an initial policy using Grover search until the optimum is reached. Finally, we present an implementation of our algorithm for a two-armed bandit MDP which we then simulate.

arXiv:2206.04741•Jun 9, 2022•10 citations
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.
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.
Reinforcement learning is a subfield of machine learning that studies how an agent interacts with an environment in order to extract as large a reward as possible. A standard approach to study such interaction is through Markov Decision Processes (MDPs) and the task of choosing an optimal policy --- a function that tells the agent which action to take. In this work, we study two types of MDPs --- finite-horizon and infinite-horizon discounted --- and propose new quantum algorithms for computing approximate optimal policies. Our quantum algorithms are based on a new combination of standard value iteration and quantum subroutines like quantum mean estimation and quantum maximum finding, overall enhanced with techniques from sample-optimal classical algorithms. Our resulting query complexities improve upon previous works, thus approaching already established quantum lower bounds.
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).
Reinforcement learning studies how an agent should interact with an environment to maximize its cumulative reward. A standard way to study this question abstractly is to ask how many samples an agent needs from the environment to learn an optimal policy for a γγγ-discounted Markov decision process (MDP). For such an MDP, we design quantum algorithms that approximate an optimal policy (π∗π^*π∗), the optimal value function (v∗v^*v∗), and the optimal QQQ-function (q∗q^*q∗), assuming the algorithms can access samples from the environment in quantum superposition. This assumption is justified whenever there exists a simulator for the environment; for example, if the environment is a video game or some other program. Our quantum algorithms, inspired by value iteration, achieve quadratic speedups over the best-possible classical sample complexities in the approximation accuracy (εεε) and two main parameters of the MDP: the effective time horizon (11−γ\frac{1}{1-γ}1−γ1​) and the size of the action space (AAA). Moreover, we show that our quantum algorithm for computing q∗q^*q∗ is optimal by proving a matching quantum lower bound.
We present a full implementation and simulation of a novel quantum reinforcement learning method. Our work is a detailed and formal proof of concept for how quantum algorithms can be used to solve reinforcement learning problems and shows that, given access to error-free, efficient quantum realizations of the agent and environment, quantum methods can yield provable improvements over classical Monte-Carlo based methods in terms of sample complexity. Our approach shows in detail how to combine amplitude estimation and Grover search into a policy evaluation and improvement scheme. We first develop quantum policy evaluation (QPE) which is quadratically more efficient compared to an analogous classical Monte Carlo estimation and is based on a quantum mechanical realization of a finite Markov decision process (MDP). Building on QPE, we derive a quantum policy iteration that repeatedly improves an initial policy using Grover search until the optimum is reached. Finally, we present an implementation of our algorithm for a two-armed bandit MDP which we then simulate.