Quantum Algorithms Database
Quantum Approximate Optimization Algorithm (QAOA)
A hybrid algorithm for finding approximate solutions to combinatorial optimization problems on near-term quantum hardware.
Year
2014
Inventor(s)
Farhi, Goldstone & Gutmann
Speedup Type
Heuristic (No Proven Speedup)
Difficulty
★★★☆☆
The Problem
Approximately solving optimization problems like Max-Cut, scheduling, or routing — problems with many possible solutions and no easy way to find the best one.
How It Works
Alternates between quantum operations that explore the solution space and classical optimization that tunes parameters, gradually converging on better solutions.
Real-World Impact
Explored for portfolio optimization, logistics routing, and scheduling problems; whether it offers genuine advantage over the best classical heuristics remains an active research question.