Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Fast quantum algorithm for numerical gradient estimation.

Stephen P Jordan1

  • 1Physics Department, MIT, 77 Massachusetts Avenue, Cambridge, Massachusetts 02139, USA. sjordan@mit.edu

Physical Review Letters
|August 11, 2005
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Optimization by decoded quantum interferometry.

Nature·2025
Same author

Automated design of pulse sequences for magnetic resonance fingerprinting using physics-inspired optimization.

Proceedings of the National Academy of Sciences of the United States of America·2021
Same author

Grover Search and the No-Signaling Principle.

Physical review letters·2016
Same author

Quantum algorithms for quantum field theories.

Science (New York, N.Y.)·2012
Same author

Polynomial-time quantum algorithm for the simulation of chemical dynamics.

Proceedings of the National Academy of Sciences of the United States of America·2008
Same author

Theory of carbon nanocones: mechanical chiral inversion of a micron-scale three-dimensional object.

Physical review letters·2005
Same journal

Erratum: Bacterial Turbulence at Compressible Fluid Interfaces [Phys. Rev. Lett. 136, 138301 (2026)].

Physical review letters·2026
Same journal

Unveiling Light-Quark Yukawa Flavor Structure via Dihadron Fragmentation at Lepton Colliders.

Physical review letters·2026
Same journal

Adaptable Route to Fast Coherent State Transport via Bang-Bang-Bang Protocols.

Physical review letters·2026
Same journal

Topological Transition and Emergence of Elasticity of Dislocation in Skyrmion Lattice: Beyond Kittel's Magnetic-Polar Analogy.

Physical review letters·2026
Same journal

Pound-Drever-Hall Method for Superconducting-Qubit Readout.

Physical review letters·2026
Same journal

Coupling a ^{73}Ge Nuclear Spin to an Electrostatically Defined Quantum Dot in Silicon.

Physical review letters·2026
See all related articles

Estimating the gradient of a smooth function using a quantum computer requires only one query, significantly outperforming classical methods that need d+1 queries. This quantum advantage holds regardless of the number of variables, offering substantial computational savings.

Area of Science:

  • Quantum Computing
  • Numerical Analysis
  • Computational Complexity

Background:

  • Estimating function gradients is crucial in various scientific and engineering fields.
  • Classical algorithms for gradient estimation typically require multiple function evaluations (queries).
  • The computational cost often scales with the number of variables (d) and desired precision (n).

Purpose of the Study:

  • To investigate the potential of quantum computing for accelerating gradient estimation.
  • To compare the query complexity of quantum versus classical algorithms for this task.
  • To analyze the impact of precision on quantum gradient estimation.

Main Methods:

  • Utilizing a quantum black-box model for function evaluation.
  • Developing a quantum algorithm for estimating the gradient of a smooth scalar function.

Related Experiment Videos

  • Analyzing the query complexity of the proposed quantum algorithm.

    • Main Results:

    • A quantum computer can estimate the gradient of a smooth function using only one query, irrespective of the number of variables (d).
    • Classical computation requires a minimum of d+1 queries for the same task.
    • The required precision (n bits) for the quantum method aligns with classical requirements for large n.

    Conclusions:

    • Quantum computers offer a significant speedup in gradient estimation compared to classical computers.
    • The quantum approach provides a d-independent query complexity, a major advantage for high-dimensional problems.
    • This research highlights the potential of quantum algorithms for enhancing numerical analysis tasks.