What is QAOA and what is it for (and not for)?

Status as of: August 1, 2026. QAOA is the most-cited algorithm in quantum optimization marketing and the most-benchmarked algorithm in quantum optimization research. Those two facts point in opposite directions. Here is the definition, what it is actually good for today, and what the measured record says.

What exactly is QAOA?

The Quantum Approximate Optimization Algorithm (Farhi, Goldstone & Gutmann, arXiv:1411.4028, Nov 2014) is a hybrid quantum-classical recipe for combinatorial optimization — problems like MaxCut, scheduling, or portfolio selection, where you pick the best configuration out of exponentially many.

The mechanics, without mystique: encode the cost function as a Hamiltonian; prepare a uniform superposition over all bitstrings; then alternate two operations p times — a cost layer (angle γ) that phases states by how good they are, and a mixer layer (angle β) that moves amplitude between states. Measure, get a candidate bitstring. A classical optimizer outside the chip tunes the 2p angles to push the average cost down, then you sample the tuned circuit and keep the best draw.

Two properties made it famous: it runs on shallow circuits (NISQ-friendly), and it has a provable floor — at p=1 on 3-regular MaxCut it guarantees at least 0.6924× the optimal cut, and as p→∞ it converges to the exact optimum. The catch: the guarantee that impresses is asymptotic in a depth nobody can run, and the depth people can run has a guarantee a classical algorithm beat decades ago.

What is it legitimately used for today?

Three real uses, none of them "solving your logistics":

1. Algorithm research. QAOA is the standard testbed for questions about variational circuits: parameter setting, landscapes, noise response. Most of what the field knows about shallow-circuit optimization was learned on it.
2. Hardware benchmarking. A QAOA circuit is a structured, scalable workload with a scoreable output, which makes it a common stress test for new devices — a use closer to "dynamometer" than "delivery truck".
3. A candidate for future advantage. If (and only if) its empirical scaling holds and fault-tolerant hardware arrives, some problem families could eventually favor it. That is a research bet, not a capability.

What it is not used for, as of August 2026: production optimization. We found no published head-to-head where QAOA beats a strong, tuned classical solver on the same instance at practical scale — in portfolios, routing, or scheduling. A 2025 benchmark of quantum portfolio optimization (arXiv:2509.17876) found QAOA variants and annealing failing to match Gurobi, and on several instances performing close to random sampling.

What does the strongest evidence in its favor say?

The best published pro-QAOA result is Shaydulin et al., Science Advances (2024): the LABS problem (low-autocorrelation binary sequences — genuinely hard, with merit-factor stakes in radar engineering). In noiseless simulation up to 40 qubits with fixed parameters, time-to-solution scaled as:

Read the table twice. In the strongest published evidence for QAOA, bare QAOA scales worse than the best classical heuristic. The advantage only appears after bolting on quantum minimum finding — a subroutine that requires error-corrected hardware nobody has. The authors are explicit about all of this in the paper; read those caveats before citing the headline.

Why doesn't it win yet?

Four independent walls, stacked:

1. Structure. Constant-depth QAOA is local — each qubit only "sees" a neighborhood. Bravyi, Kliesch, König & Tang (PRL 2020) proved that the classical Goemans-Williamson algorithm outperforms QAOA at any constant depth on certain MaxCut instances, because locality plus symmetry caps what shallow circuits can reach.
2. Trainability. Tuning the angles is itself hard. At useful depths the landscape fills with superpolynomially many low-quality local minima; random initialization "is doomed to fail beyond small n" (arXiv:2402.10188, 2024). You need good parameter guesses to even start.
3. Throughput. Even where solution quality could compete, the clock matters. For MaxCut on 3-regular graphs, Lykov et al. (npj QI 2023) estimate QAOA needs p>11 and roughly 10 kHz sampling to edge classical heuristics that already return high-quality solutions in linear time — while typical devices sample at lower rates, and the required rate grows with problem size.
4. The measured record. Where someone runs the head-to-head on the same instances, classical wins — see the portfolio benchmark above, and our routing verdict.

What do our own runs show?

Our sealed verdict V-0012 (portfolio selection): QAOA at p=2 against Google's CP-SAT, 20 runs at n=12/16/20 assets, same instances, same budget rules. CP-SAT returned the proven optimum 20/20; QAOA landed 25–48% away from optimum, with no improvement trend as n grew. Honesty note that cuts against us: our quantum runs were noiseless simulations — a setting that favors the quantum side — and it still lost every run. This is one small problem class at toy scale; it is a data point, not a universal verdict. It is, however, measured — which is more than most QAOA claims offer. Method: why a weak classical baseline ruins a quantum benchmark.

What we don't know

• Whether the LABS scaling (1.21^N with QMF) survives noise, error-correction overhead, and larger N — it was measured in noiseless simulation up to 40 qubits with fixed parameters.
• Whether better parameter-transfer schemes or non-local QAOA variants materially change the trainability picture at scale.
• Where the crossover point N* would sit for any QAOA use case — nobody has published one with evidence, us included.
• Whether p can be pushed high enough on real hardware for the p→∞ guarantee to ever matter in practice.

Rosetta Q publishes verdicts with reproducible raw data. This is educational content, not a product claim.