Fast quantum algorithm for numerical gradient estimation
arXiv:quant-ph/0405146 · doi:10.1103/PhysRevLett.95.050501
Abstract
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 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.
additional references and minor clarifications and corrections to version 1
Cited by in corpus (50)
- Simulating chemistry using quantum computers
- Quantum algorithm and circuit design solving the Poisson equation
- Quantum gradient descent for linear systems and least squares
- On the impact of quantum computing technology on future developments in high-performance scientific computing
- Low-depth gradient measurements can improve convergence in variational hybrid quantum-classical algorithms
- Calculating energy derivatives for quantum chemistry on a quantum computer
- Quantum Hamiltonian Learning Using Imperfect Quantum Resources
- Advances in Quantum Reinforcement Learning
- Quantum Algorithm for Molecular Properties and Geometry Optimization
- Prospects of Quantum Computing for Molecular Sciences
- Quantum Fourier Transform in Computational Basis
- Efficient quantum computation of molecular forces and other energy gradients
- Nearly Optimal Quantum Algorithm for Estimating Multiple Expectation Values
- Quantum information processing using strongly-dipolar coupled nuclear spins
- Quantum algorithms and lower bounds for convex optimization
- Towards Quantum Advantage in Financial Market Risk using Quantum Gradient Algorithms
- Quantum Computation Beyond the Circuit Model
- Convex optimization using quantum oracles
- Ab Initio Molecular Dynamics on Quantum Computers
- Lanczos recursion on a quantum computer for the Green's function and ground state
- Quantum simulation of real-space dynamics
- Optimizing a Polynomial Function on a Quantum Simulator
- Near-Optimal Quantum Algorithms for Multivariate Mean Estimation
- Quantum Gradient Algorithm for General Polynomials
- Evolution Operators for Linearly Polarized Two-Killing Cosmological Models
- Rotating Electric Classical Solutions of 2+1 D U(1) Einstein Maxwell Chern-Simons
- Density functionals and Kohn-Sham potentials with minimal wavefunction preparations on a quantum computer
- Quantum algorithms for escaping from saddle points
- Functional evolution of quantum cylindrical waves
- Random coordinate descent: a simple alternative for optimizing parameterized quantum circuits
- Quantum basin hopping with gradient-based local optimisation
- Everything You Always Wanted to Know About Quantum Circuits
- Simulated Quantum Computation of Global Minima
- Quantum algorithms for multivariate Monte Carlo estimation
- Probing Quantized Einstein-Rosen Waves with Massless Scalar Matter
- Average-Case Verification of the Quantum Fourier Transform Enables Worst-Case Phase Estimation
- Heisenberg-limited adaptive gradient estimation for multiple observables
- Quantum and Classical Algorithms for Approximate Submodular Function Minimization
- Quantum gradient estimation of Gevrey functions
- A quantum algorithm for solving systems of nonlinear algebraic equations
- Quantum Algorithm for Online Convex Optimization
- Classical Simulation of Quantum Adiabatic Algorithms using Mathematica on GPUs
- Physics and computer science: quantum computation and other approaches
- Quantum Algorithms Using the Curvelet Transform
- Comprehensive Study on Heisenberg-limited Quantum Algorithms for Multiple Observables Estimation
- Quantum query complexity with matrix-vector products
- Quantum Enhanced Pattern Search Optimization
- Faster Quantum Algorithm for Multiple Observables Estimation in Fermionic Problems
- Quantum algorithmic differentiation
- A Spectral Quantum Algorithm for Numerical Differentiation and Integration