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

Cambridge University Press eBooks

Quantum gradient estimation

Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, Fernando G. S. L. Brandão

Published Apr 24, 2025• 0 citations
Publisher

Abstract

This chapter covers the quantum algorithmic primitive called quantum gradient estimation, where the goal is to output an estimate for the gradient of a multivariate function. This primitive features in other primitives, for example, quantum tomography. It also features in several quantum algorithms for end-to-end problems in continuous optimization, finance, and machine learning, among other areas. The size of the speedup it provides depends on how the algorithm can access the function, and how difficult the gradient is to estimate classically.

DOI
10.1017/9781009639651.022

Related papers

Quantum phase estimation

Alexander M. Dalzell, Sam McArdle, Mario Berta +10 more

This chapter covers the quantum algorithmic primitive called quantum phase estimation. Quantum phase estimation is an essential quantum algorithmic primitive that computes an estimate for the eigenvalue of a unitary operator, given as input an eigenstate of the operator. It features prominently in many end-to-end quantum algorithms, for example, computing ground state energies of physical systems in the areas of condensed matter physics and quantum chemistry. We carefully discuss nuances of quantum phase estimation that appear when it is applied to a superposition of eigenstates with different eigenvalues.

Cambridge University Press eBooks•Apr 24, 2025•0 citations

Chapter 5: Quantum gradient algorithm and vector input/output

Giacomo Nannicini

In this chapter we discuss a quantum algorithm to estimate the gradient of a multivariate function, given access to a quantum circuit to compute the function. The core of the algorithm is a multidimensional version of phase estimation. After introducing the quantum gradient algorithm, we discuss two of its applications: an algorithm to extract the classical description of the vector describing a quantum state, and an algorithm to separate a point from a convex set when we only have an indirect description of the set, via an oracle that determines if a point belongs to it or not. Whereas algorithms discussed in previous chapters always output a scalar, in this chapter they output vectors. We also present an algorithm to create the natural quantum encoding of a given classical vector, which is used as a subroutine in a variety of quantum algorithms, sometimes to encode part of the input data.

Society for Industrial and Applied Mathematics eBooks•Dec 17, 2025•0 citations

Quantum tomography

Alexander M. Dalzell, Sam McArdle, Mario Berta +10 more

This chapter covers quantum tomography, a quantum algorithmic primitive that enables a quantum algorithm to learn a full classical description of a quantum state. Generally, the goal of a quantum tomography procedure is to obtain this description using as few copies of the state as possible. The optimal number of copies may depend on what kind of measurements are allowed and what error metric is being used, and in most cases, quantum tomography procedures have been developed with provably optimal complexity.

Cambridge University Press eBooks•Apr 24, 2025•0 citations

Amplitude amplification and estimation

Alexander M. Dalzell, Sam McArdle, Mario Berta +10 more

This chapter covers the quantum algorithmic primitives of amplitude amplification and amplitude estimation. Amplitude amplification is a generalization of Grover’s quantum algorithm for the unstructured search problem. Amplitude estimation can be understood in a similar framework, where it utilizes quantum phase estimation to estimate the value of the amplitude or probability associated with a quantum state. Both amplitude amplification and amplitude estimation provide a quadratic speedup over their classical counterparts, and feature prominently as an ingredient in many end-to-end algorithms.

Cambridge University Press eBooks•Apr 24, 2025•0 citations

Quantum Algorithms: A Survey of Applications and End-to-end Complexities

Alexander M. Dalzell, Sam McArdle, Mario Berta +10 more

The anticipated applications of quantum computers span across science and industry, ranging from quantum chemistry and many-body physics to optimization, finance, and machine learning. Proposed quantum solutions in these areas typically combine multiple quantum algorithmic primitives into an overall quantum algorithm, which must then incorporate the methods of quantum error correction and fault tolerance to be implemented correctly on quantum hardware. As such, it can be difficult to assess how much a particular application benefits from quantum computing, as the various approaches are often sensitive to intricate technical details about the underlying primitives and their complexities. Here we present a survey of several potential application areas of quantum algorithms and their underlying algorithmic primitives, carefully considering technical caveats and subtleties. We outline the challenges and opportunities in each area in an "end-to-end" fashion by clearly defining the problem being solved alongside the input-output model, instantiating all "oracles," and spelling out all hidden costs. We also compare quantum solutions against state-of-the-art classical methods and complexity-theoretic limitations to evaluate possible quantum speedups. The survey is written in a modular, wiki-like fashion to facilitate navigation of the content. Each primitive and application area is discussed in a standalone section, with its own bibliography of references and embedded hyperlinks that direct to other relevant sections. This structure mirrors that of complex quantum algorithms that involve several layers of abstraction, and it enables rapid evaluation of how end-to-end complexities are impacted when subroutines are altered.

arXiv:2310.03011•Oct 4, 2023•49 citations

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
This chapter covers the quantum algorithmic primitive called quantum gradient estimation, where the goal is to output an estimate for the gradient of a multivariate function. This primitive features in other primitives, for example, quantum tomography. It also features in several quantum algorithms for end-to-end problems in continuous optimization, finance, and machine learning, among other areas. The size of the speedup it provides depends on how the algorithm can access the function, and how difficult the gradient is to estimate classically.
This chapter covers the quantum algorithmic primitive called quantum phase estimation. Quantum phase estimation is an essential quantum algorithmic primitive that computes an estimate for the eigenvalue of a unitary operator, given as input an eigenstate of the operator. It features prominently in many end-to-end quantum algorithms, for example, computing ground state energies of physical systems in the areas of condensed matter physics and quantum chemistry. We carefully discuss nuances of quantum phase estimation that appear when it is applied to a superposition of eigenstates with different eigenvalues.
In this chapter we discuss a quantum algorithm to estimate the gradient of a multivariate function, given access to a quantum circuit to compute the function. The core of the algorithm is a multidimensional version of phase estimation. After introducing the quantum gradient algorithm, we discuss two of its applications: an algorithm to extract the classical description of the vector describing a quantum state, and an algorithm to separate a point from a convex set when we only have an indirect description of the set, via an oracle that determines if a point belongs to it or not. Whereas algorithms discussed in previous chapters always output a scalar, in this chapter they output vectors. We also present an algorithm to create the natural quantum encoding of a given classical vector, which is used as a subroutine in a variety of quantum algorithms, sometimes to encode part of the input data.
This chapter covers quantum tomography, a quantum algorithmic primitive that enables a quantum algorithm to learn a full classical description of a quantum state. Generally, the goal of a quantum tomography procedure is to obtain this description using as few copies of the state as possible. The optimal number of copies may depend on what kind of measurements are allowed and what error metric is being used, and in most cases, quantum tomography procedures have been developed with provably optimal complexity.
This chapter covers the quantum algorithmic primitives of amplitude amplification and amplitude estimation. Amplitude amplification is a generalization of Grover’s quantum algorithm for the unstructured search problem. Amplitude estimation can be understood in a similar framework, where it utilizes quantum phase estimation to estimate the value of the amplitude or probability associated with a quantum state. Both amplitude amplification and amplitude estimation provide a quadratic speedup over their classical counterparts, and feature prominently as an ingredient in many end-to-end algorithms.
The anticipated applications of quantum computers span across science and industry, ranging from quantum chemistry and many-body physics to optimization, finance, and machine learning. Proposed quantum solutions in these areas typically combine multiple quantum algorithmic primitives into an overall quantum algorithm, which must then incorporate the methods of quantum error correction and fault tolerance to be implemented correctly on quantum hardware. As such, it can be difficult to assess how much a particular application benefits from quantum computing, as the various approaches are often sensitive to intricate technical details about the underlying primitives and their complexities. Here we present a survey of several potential application areas of quantum algorithms and their underlying algorithmic primitives, carefully considering technical caveats and subtleties. We outline the challenges and opportunities in each area in an "end-to-end" fashion by clearly defining the problem being solved alongside the input-output model, instantiating all "oracles," and spelling out all hidden costs. We also compare quantum solutions against state-of-the-art classical methods and complexity-theoretic limitations to evaluate possible quantum speedups. The survey is written in a modular, wiki-like fashion to facilitate navigation of the content. Each primitive and application area is discussed in a standalone section, with its own bibliography of references and embedded hyperlinks that direct to other relevant sections. This structure mirrors that of complex quantum algorithms that involve several layers of abstraction, and it enables rapid evaluation of how end-to-end complexities are impacted when subroutines are altered.
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.