Quantum Algorithms Database
Quantum Gradient Descent
A quantum approach to the gradient descent optimization technique that underlies most classical machine learning training, offering speedups under specific structural assumptions.
Year
2017 (Rebentrost, Schuld, Wossnig et al.)
Inventor(s)
Rebentrost, Schuld, Wossnig and others
Speedup Type
Polynomial Speedup
Difficulty
★★★★★
The Problem
Efficiently finding the minimum of a cost function — the core operation repeated millions of times when training classical machine learning models.
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.
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.