Quantum Gradient Descent

Overview

Gradient descent is the workhorse of machine learning: to train a model, you compute the gradient of a loss function and take a small step downhill, repeating many times. Quantum gradient descent aims to speed up pieces of this loop using quantum subroutines, for example by estimating the gradient of a function with far fewer queries or by performing the descent steps on quantum states.

The topic covers several different results. Jordan's 2005 algorithm computes a numerical gradient with a single quantum query. Rebentrost and coauthors showed how to run gradient descent and Newton's method for certain polynomial optimization problems with logarithmic dependence on dimension. And a separate line of work uses the parameter-shift rule to compute gradients of quantum circuits on quantum hardware for variational algorithms.

The problem it solves

Efficiently finding the minimum of a cost function — the core operation repeated millions of times when training classical machine learning models.

History and background

Stephen Jordan published a quantum algorithm for numerical gradient estimation in Physical Review Letters in 2005. For a smooth function of d variables, a classical computer needs about d plus 1 evaluations to estimate the gradient by finite differences, while Jordan's algorithm needs one evaluation of the function in superposition, using the quantum Fourier transform to read out all partial derivatives at once.

In 2016 Rebentrost, Schuld, Wossnig, Petruccione, and Lloyd posted a paper on quantum gradient descent and Newton's method for constrained polynomial optimization, published in 2019 in the New Journal of Physics. Gilyén, Arunachalam, and Wiebe extended Jordan's work in 2019 to non-smooth functions and optimized the dependence on dimension, and Kerenidis and Prakash gave quantum gradient descent for linear systems and least squares in 2020. Meanwhile, Mitarai, Negoro, Kitagawa, and Fujii in 2018 and Schuld and coauthors in 2019 described the parameter-shift rule for gradients of variational quantum circuits.

How it works

Encodes gradient computations into quantum states using techniques related to the HHL algorithm, exploiting quantum linear algebra subroutines to estimate gradients faster under certain sparsity and conditioning assumptions.

Jordan's algorithm works because a smooth function is approximately linear near a point. A linear function f of x equal to g dot x has phases that depend linearly on x. If you evaluate f in superposition over a grid of small displacements and store the value in the phase, the grid state carries a phase pattern with slope g. A quantum Fourier transform converts that slope into a measurable string, so one query yields all components of the gradient.

The polynomial optimization algorithms take a different route. They encode the data as quantum states and apply quantum linear algebra, such as HHL-style matrix inversion, to perform a gradient or Newton step in time logarithmic in the dimension. The result is a quantum state encoding the new point, which is then used for the next step, so the whole iteration can stay quantum.

For variational quantum circuits, the gradient with respect to a gate angle can be obtained exactly by running the circuit twice with the angle shifted by plus and minus a fixed amount, then subtracting the expectation values. This costs two runs per parameter, so a circuit with many parameters needs many runs, and noise limits accuracy.

Step by step

1. Define a cost function f of x over d parameters and choose a starting point x0.
2. In Jordan's version, prepare a superposition over a small grid of displacements, evaluate f once into the phase, and apply an inverse quantum Fourier transform.
3. Measure the result to read off the gradient estimate, with an accuracy that depends on the grid spacing and the smoothness of f.
4. Update the parameters by a step against the gradient, scaled by a learning rate.
5. For a parameterized quantum circuit, instead run two circuits per parameter with shifted angles and compute the gradient from the difference of expectation values.
6. Repeat until the gradient is small or the cost stops improving.

A worked example

Suppose f has d = 1,000 parameters and each evaluation of f is expensive. Finite differences need 1,001 evaluations for one gradient. Jordan's algorithm needs one coherent evaluation, plus a quantum Fourier transform over the grid, and returns all 1,000 partial derivatives to a given precision at once.

For a variational circuit with 100 parameters, the parameter-shift rule needs 200 circuit executions per gradient, and each is repeated thousands of times to estimate expectation values. That is why training variational circuits is slow in practice, even though there is no proven quantum speedup for the descent itself.

Complexity and resources

What hardware it needs

• Fault-tolerant hardware and efficient coherent function evaluation for Jordan-style gradients.
• Quantum memory for data in polynomial optimization algorithms.
• For variational circuits, current noisy devices suffice, but gradients are noisy and expensive.

Applications

• Training machine learning models, if efficient quantum data access can be provided.
• Optimization of variational quantum eigensolvers and quantum neural networks.
• Escaping saddle points and finding critical points in non-convex landscapes, which is an active research topic.
• Solving least squares and linear regression problems in a quantum setting.

Limitations and caveats

• The speedups require coherent function evaluations or quantum data access, which are expensive to implement.
• Jordan's algorithm assumes the function is smooth within the grid.
• For deep learning, no quantum algorithm yet gives a practical advantage, and classical training uses automatic differentiation that already computes full gradients at low cost.
• Barren plateaus make gradients vanishingly small for some variational circuits.

Common misconceptions

• Quantum gradient descent does not make training neural networks exponentially faster. Speedups are limited to specific settings.
• Classical backpropagation already computes a full gradient at about the cost of a few function evaluations, so the d plus 1 comparison applies to black-box functions.

How it compares

• HHL and quantum linear algebra provide the core machinery for the polynomial optimization algorithms.
• VQE and QAOA use classical gradient-based optimizers around a quantum circuit instead of quantum gradient descent.
• Quantum natural gradient accounts for the geometry of the parameter space and speeds up variational training.

Real-world impact

Largely theoretical — like other quantum linear algebra speedups, it depends on efficient quantum data loading, which remains a significant unsolved practical bottleneck for real machine learning datasets.

Why it matters

Optimization sits inside almost every machine learning method, so any real quantum speedup here would matter widely. Jordan's gradient algorithm is also a clean example of a quantum speedup from simple Fourier analysis.

The topic is also a useful reminder to compare against the right classical baseline. Backpropagation makes gradients cheap for explicit models, and quantum advantage must be assessed against it.

Frequently asked questions

Keep learning

• Related algorithm: Quantum Natural Gradient Descent
• Related algorithm: HHL Algorithm
• Related algorithm: Variational Quantum Eigensolver (VQE)
• Related algorithm: Quantum Approximate Optimization Algorithm (QAOA)

This page is written for educational purposes. Complexity statements describe the best known results at the time of review (September 30, 2026), and research in this area moves quickly, so check recent papers before relying on a specific bound.

← Back to Algorithms Database