Quantum Algorithms Database
Quantum Max-Cut Algorithms
Quantum approaches to the Max-Cut problem — partitioning a network's nodes into two groups to maximize the number of connections between the groups — the original benchmark problem for QAOA.
Year
2014 (QAOA's original demonstration problem)
Inventor(s)
Farhi, Goldstone & Gutmann (via QAOA)
Speedup Type
Heuristic (No Proven Speedup)
Difficulty
★★★☆☆
The Problem
Dividing a network into two groups such that the number of connections crossing between the groups is as large as possible.
How It Works
Encodes possible partitions as quantum states, using QAOA's alternating optimization structure to search for partitions with a high cut value.
Real-World Impact
The most commonly used benchmark for testing and comparing QAOA implementations across different quantum hardware platforms, due to its simple, well-understood classical structure.