Further Reading: Quantum Optimization with QAOA

Tagged Tier 1 (confident it exists and recommended) and Tier 2 (real and worth seeking, but verify the current version or URL).

Optimization has the best-documented classical baseline of any application in this book, so this list leans harder on the classical literature than the others. That is deliberate: §37.6's result came from a 1994 algorithm, and you cannot evaluate a quantum optimization claim without knowing what it is being compared against.

QAOA itself

• Farhi, Goldstone, and Gutmann, "A Quantum Approximate Optimization Algorithm" (2014), arXiv:1411.4028. The original. Read it for the $p \to \infty$ argument and for how carefully it states what it does and does not claim — the paper is considerably more modest than most of what followed it. Tier 1.
• Farhi, Goldstone, and Gutmann on QAOA applied to bounded-degree MaxCut. Contains the $p=1$ performance guarantee on 3-regular graphs (0.6924), which is the number §37.3's measured 0.751 should be read against. Tier 1.
• Hadfield et al., "From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz" (2019), Algorithms 12, 34. Generalizes the mixer to handle hard constraints — the extension you need for any real scheduling or routing problem. Tier 1.
• Zhou, Wang, Choi, Pichler, and Lukin, "Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices" (2020), PRX 10, 021067. The best single paper on why QAOA angles transfer between instances, which is Exercise 37.12's subject and the most credible route around §37.8's shot budget. Tier 1.

The classical baseline — read at least one before claiming anything

• Goemans and Williamson, "Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming" (1995), JACM 42, 1115. The 0.87856. Read it for the rounding analysis — the geometry of the random hyperplane argument is genuinely beautiful, and understanding it is what makes §37.7's certificate obvious rather than surprising. Tier 1.
• Khot, Kindler, Mossel, and O'Donnell on the optimality of the GW bound under the Unique Games Conjecture. If UGC holds, 0.87856 is the best any polynomial-time algorithm can do — which sharpens §37.9's first requirement considerably. Tier 1.
• The Burer–Monteiro approach to large-scale SDP, and modern MaxCut heuristics. What people actually run when the graph is big. Tier 2.
• Documentation for Gurobi, CPLEX, or HiGHS on optimality gaps. Not glamorous, and it is what Case Study 37.1 turns on: serious optimization software has reported certificates for decades, and the reliance on them is invisible until something proposes to remove it. Tier 1.

The critical literature on quantum optimization

This is a healthy and unusually candid subfield.

• Stilck França and García-Patrón, "Limitations of optimization algorithms on noisy quantum devices" (2021), Nature Physics 17, 1221. Noise limits on variational optimization, rigorously. The single most important critical paper for this chapter. Tier 1.
• Barak et al. and related work on classical algorithms that match QAOA at fixed $p$. For several instance families, a classical algorithm reproduces QAOA's performance directly — the dequantization story from Chapter 34, in optimization. Tier 2 — active, and moving.
• Bravyi, Kliesch, Koenig, and Tang, "Obstacles to Variational Quantum Optimization from Symmetry Protection" (2020), PRL 125, 260505. Symmetry arguments that bound low-depth QAOA on certain graphs. Tier 1.
• Literature on quantum annealing benchmarks, particularly the sequence of papers examining D-Wave's claimed speedups. Read it as a case study in how advantage claims are made and unmade — it is the most thoroughly litigated advantage question in the field, and the methodology developed there is what §37.6 borrows. Tier 1.

On benchmarking, which is the real subject

• Chapter 21 §21.7 ("Grover Does Not Search a Database") and Chapter 36 §36.6. The book's own earlier statements of the baseline problem. §37.6 is the third instance and the cleanest, because the mapping is exact. Tier 1.
• Chapter 27 §27.4, Chapter 28 §28.5, Chapter 33 §33.6, Chapter 34 §34.7. The four earlier single-sample errors that §37.4 joins. Worth re-reading together — the pattern is more visible in aggregate than in any one instance. Tier 1.
• Literature on statistical practice in machine learning benchmarking (seed variance, reporting standards, the reproducibility discussion). Not quantum at all, and directly applicable — the field has already had the argument §37.4 is having. Tier 2.

Software

• PennyLane's qml.qaoa module — what this chapter's examples use. Tier 1.
• cvxpy with SCS or Clarabel — the SDP solver behind §37.5. Note that cvxpy is an extra install for this chapter. Tier 1.
• networkx — graph construction and the instance families. Tier 1.
• Qiskit Optimization — IBM's QUBO/Ising stack, including converters from higher-level problem types. Tier 2 — it has been restructured; check the version your tutorial targets.

Backward references

• Chapter 21 §21.7 — the baseline problem, and another asymptotic guarantee that the machine does not reach.
• Chapter 24 §24.3 — the $1/\epsilon^2$ shot budget that §37.8 rediscovers.
• Chapter 30 §30.5 — quoting a number without naming its statistic.
• Chapter 36 — the same accounting on chemistry, where an approximation stood between the problem and the Hamiltonian.

Forward references

• Chapter 38 — the one deployed application, and a different kind of gap between what a technology guarantees and what a system needs.

Where to go next. If one thing: Goemans and Williamson (1995). It is the algorithm that won §37.6, the rounding analysis is a pleasure to read, and understanding where the SDP bound comes from is what turns §37.7's certificate finding from a surprise into an obvious consequence.

If two: add Stilck França and García-Patrón on noise limitations. §37.8's shot budget is the optimistic term, and that paper prices the pessimistic one.

Then Chapter 38, where for the first time in this book the technology under examination is commercially deployed and provably secure — and the chapter is about why that turns out not to settle anything.