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:quant-ph/0507109

Quantum computational gradient estimation

David W. Bulger

Published Jul 12, 2005• 4 citations
arXivHTMLPDF

Abstract

Classically, determining the gradient of a black-box function f:R^p->R requires p+1 evaluations. Using the quantum Fourier transform, two evaluations suffice. This is based on the approximate local periodicity of exp(2*pi*i*f(x)). It is shown that sufficiently precise machine arithmetic results in gradient estimates of any required accuracy.

DOI
10.48550/arxiv.quant-ph/0507109

Related papers

Fast Quantum Algorithm for Numerical Gradient Estimation

Stephen P. Jordan

Given a black box for f, a smooth real scalar function of d real variables, one wants to estimate [symbol: see text]f at a given point with n bits of precision. On a classical computer this requires a minimum of d + 1 black box queries, whereas on a quantum computer it requires only one query regardless of d. The number of bits of precision to which f must be evaluated matches the classical requirement in the limit of large n.

arXiv:quant-ph/0405146•Physical Review Letters•Jul 28, 2005•150 citations

Efficient quantum algorithm for numerical gradient estimation

Stephen P. Jordan

Given a blackbox for f, a smooth real scalar function of d real variables, one wants to estimate the gradient of f at a given point with n bits of precision. On a classical computer this requires a minimum of d+1 blackbox queries, whereas on a quantum computer it requires only two queries regardless of d. The number of bits of precision to which f must be evaluated differs between the quantum and classical cases. In the limit of large n the quantum algorithm requires twice as many bits.

•May 25, 2004•0 citations

Quantum algorithm for finding periodicities in the spectrum of a black-box Hamiltonian or unitary transformation

Dominik Janzing, Thomas Beth

Estimating the eigenvalues of a unitary transformation U by standard phase estimation requires the implementation of controlled-U-gates which are not available if U is only given as a black box. We show that a simple trick allows to measure eigenvalues of U\otimes U^\dagger even in this case. Running the algorithm several times allows therefore to estimate the autocorrelation function of the density of eigenstates of U. This can be applied to find periodicities in the energy spectrum of a quantum system with unknown Hamiltonian if it can be coupled to a quantum computer.

arXiv:quant-ph/0108053•Aug 10, 2001•6 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•8 citations

Quantum Fourier transform computational accuracy analysis

Marina O. Lisnichenko, O. M. Kiselëv

In this work, we present a rigorous accuracy analysis of the quantum Fourier transform (QFT), that identifies three natural sources of accuracy degeneracy: (i) discretization accuracy inherited from classical sampling theory, (ii) accuracy degeneracy due to limited resolution in eigenvalue (phase) estimation, and (iii) accuracy degeneracy resulting from finite quantum resources. We formalize these accuracy degradation sources by proving two theorems that relate the minimal amplitude and eigenvalue resolution to the number of qubits. In addition, we describe a gate-level implementation of the QFT and present simulation results on small-scale quantum systems that illustrate our theoretical findings. Our results clarify the interplay between classical signal discretization limits and quantum hardware limitations, and they provide guidelines for the resource requirements needed to achieve a desired precision.

arXiv:2502.10840•Feb 15, 2025•1 citation

Evaluating analytic gradients on quantum hardware

Maria Schuld, Ville Bergholm, Christian Gogolin +2 more

An important application for near-term quantum computing lies in optimization tasks, with applications ranging from quantum chemistry and drug discovery to machine learning. In many settings, most prominently in so-called parametrized or variational algorithms, the objective function is a result of hybrid quantum-classical processing. To optimize the objective, it is useful to have access to exact gradients of quantum circuits with respect to gate parameters. This paper shows how gradients of expectation values of quantum measurements can be estimated using the same, or almost the same, architecture that executes the original circuit. It generalizes previous results for qubit-based platforms, and proposes recipes for the computation of gradients of continuous-variable circuits. Interestingly, in many important instances it is sufficient to run the original quantum circuit twice while shifting a single gate parameter to obtain the corresponding component of the gradient. More general cases can be solved by conditioning a single gate on an ancilla.

arXiv:1811.11184•Physical Review A•Mar 21, 2019•1,281 citations
Classically, determining the gradient of a black-box function f:R^p->R requires p+1 evaluations. Using the quantum Fourier transform, two evaluations suffice. This is based on the approximate local periodicity of exp(2pii*f(x)). It is shown that sufficiently precise machine arithmetic results in gradient estimates of any required accuracy.
Estimating the eigenvalues of a unitary transformation U by standard phase estimation requires the implementation of controlled-U-gates which are not available if U is only given as a black box. We show that a simple trick allows to measure eigenvalues of U\otimes U^\dagger even in this case. Running the algorithm several times allows therefore to estimate the autocorrelation function of the density of eigenstates of U. This can be applied to find periodicities in the energy spectrum of a quantum system with unknown Hamiltonian if it can be coupled to a quantum computer.
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 this work, we present a rigorous accuracy analysis of the quantum Fourier transform (QFT), that identifies three natural sources of accuracy degeneracy: (i) discretization accuracy inherited from classical sampling theory, (ii) accuracy degeneracy due to limited resolution in eigenvalue (phase) estimation, and (iii) accuracy degeneracy resulting from finite quantum resources. We formalize these accuracy degradation sources by proving two theorems that relate the minimal amplitude and eigenvalue resolution to the number of qubits. In addition, we describe a gate-level implementation of the QFT and present simulation results on small-scale quantum systems that illustrate our theoretical findings. Our results clarify the interplay between classical signal discretization limits and quantum hardware limitations, and they provide guidelines for the resource requirements needed to achieve a desired precision.
An important application for near-term quantum computing lies in optimization tasks, with applications ranging from quantum chemistry and drug discovery to machine learning. In many settings, most prominently in so-called parametrized or variational algorithms, the objective function is a result of hybrid quantum-classical processing. To optimize the objective, it is useful to have access to exact gradients of quantum circuits with respect to gate parameters. This paper shows how gradients of expectation values of quantum measurements can be estimated using the same, or almost the same, architecture that executes the original circuit. It generalizes previous results for qubit-based platforms, and proposes recipes for the computation of gradients of continuous-variable circuits. Interestingly, in many important instances it is sufficient to run the original quantum circuit twice while shifting a single gate parameter to obtain the corresponding component of the gradient. More general cases can be solved by conditioning a single gate on an ancilla.