The Quantum Approximate Optimization Algorithm (QAOA)
VQE's sibling algorithm, aimed at combinatorial optimization instead of chemistry
By the end of this topic you'll be able to
The Quantum Approximate Optimization Algorithm (QAOA), introduced by Farhi, Goldstone, and Gutmann in 2014, shares VQE's hybrid quantum-classical loop, but is aimed at a different kind of problem entirely: combinatorial optimization, such as Max-Cut, phrased as minimizing a cost function defined over bit strings rather than finding a molecule's energy.
Max-Cut is a useful concrete example: given a graph, partition its vertices into two groups so as to maximize the number of edges that cross between them. Every possible partition corresponds to one bit string (which group each vertex is in), and the quantity being optimized — the cut size — is exactly the kind of cost function over bit strings QAOA is built for.
QAOA's ansatz alternates two kinds of unitary: a problem unitary, built directly from the cost function so that it encodes the specific optimization problem being solved, and a mixer unitary, which spreads amplitude across candidate bit-string solutions so the search doesn't get stuck on just one.
These two unitaries are applied in alternating layers, each with its own tunable angle, repeated some number of times p — hence 'p-layer QAOA.' The circuit is measured at the end, and — exactly as in VQE's hybrid loop — a classical optimizer adjusts all 2p angles across layers to push the expected cost function value in the right direction, then the whole circuit runs again.
More layers generally produce better solution quality: in the mathematical limit of very many layers, QAOA can be shown to converge toward the exact quantum adiabatic algorithm's guarantee of finding the true optimum. But each additional layer also makes the circuit longer and therefore noisier on real hardware, so more layers isn't free.
This depth-versus-noise tradeoff remains a genuinely active area of near-term quantum computing research, without a settled answer for how many layers of QAOA are worth the additional noise they introduce on any particular piece of hardware — the right number of layers depends on the specific problem, the specific chip, and how good the classical optimizer is at navigating that particular cost landscape.
Try It Yourself
A Max-Cut problem has a 4-vertex graph. How many possible bit strings (partitions) does a p-layer QAOA circuit need to search over, and how does that compare to brute-force classical search?
- 1Each of the 4 vertices is independently assigned to one of 2 groups, so there are 2⁴ = 16 possible bit strings (partitions) total.
- 2A classical brute-force search would need to evaluate the cut size for all 16 partitions to guarantee finding the true optimum.
- 3QAOA instead prepares a quantum superposition over all 16 bit strings simultaneously via its ansatz, and the problem/mixer unitaries bias that superposition, layer by layer, toward higher-cost-function (larger cut) bit strings.
- 4A final measurement collapses the circuit to just one bit string, sampled with higher probability for good solutions — so a single run doesn't guarantee the optimum, but repeated runs and classical-optimizer tuning of the angles push the sampled distribution toward better and better cuts.
16 possible partitions for 4 vertices. Classical brute force checks all 16 exhaustively; QAOA instead biases a quantum superposition over all 16 toward good solutions and samples from it, trading a guarantee of optimality for (hopefully) fewer total evaluations on much larger graphs where 2ⁿ brute force is infeasible.
Reference
| QAOA objective | Approximate solutions to combinatorial optimization problems | |
| Problem unitary | Encodes the cost function C being optimized | |
| Mixer unitary | Spreads amplitude across candidate bit-string solutions | |
| Layers | More layers → better solutions, but a longer, noisier circuit |
Quick Check
What kind of problem does QAOA target, in contrast to VQE?
What's the tradeoff involved in choosing the number of QAOA layers, p?