Quantum Algorithms Database
Quantum Algorithms for Semidefinite Programming
Quantum algorithms for solving semidefinite programs — a powerful and widely used class of optimization problems — offering polynomial speedups under certain conditions.
Year
2017 (Brandão & Svore)
Inventor(s)
Brandão & Svore
Speedup Type
Polynomial Speedup
Difficulty
★★★★★
The Problem
Solving semidefinite programs, a generalization of linear programming used throughout combinatorial optimization, control theory, and machine learning.
How It Works
Uses quantum Gibbs sampling and amplitude estimation techniques to approximate solutions to the underlying optimization problem faster than the best known classical algorithms in certain regimes.
Real-World Impact
Primarily theoretical at this stage, but semidefinite programming itself is so broadly used across optimization and machine learning that even modest practical speedups could have wide-reaching effects.