Further Reading: Variational Algorithms

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

The primary sources

• Peruzzo et al., "A variational eigenvalue solver on a photonic quantum processor" (2014), Nature Communications 5, 4213. VQE's introduction, on hardware, with a small molecule. Worth reading for how carefully the original paper frames what it did — a contrast with much of what followed. Tier 1.
• Farhi, Goldstone, and Gutmann, "A Quantum Approximate Optimization Algorithm" (2014), arXiv:1411.4028. QAOA's introduction. Note the paper is careful that the algorithm is approximate and that its guarantees are limited — §24.5's honest framing is the authors' own. Tier 1.
• Cerezo et al., "Variational Quantum Algorithms" (2021), Nature Reviews Physics 3, 625. The comprehensive survey: ansatz design, optimizers, cost functions, and the obstacles. The single best orientation, and it is candid about the barriers. Tier 1.
• The PennyLane demos on VQE and QAOA. Genuinely good worked implementations, and the closest thing to a reference for the code in this chapter. Tier 1.

On the shot budget

This is the section to read if you read only one, because §24.3's constraint is under-discussed.

• Wecker, Hastings, and Troyer, "Progress towards practical quantum variational algorithms" (2015), Physical Review A 92, 042303. The paper that first took the measurement cost seriously and computed what chemical accuracy actually requires. The origin of the "VQE needs an enormous number of measurements" result, and still the clearest statement of it. Tier 1.
• Gonthier et al., "Measurements as a roadblock to near-term practical quantum advantage in chemistry" (2022), Physical Review Research 4, 033154. Exactly §24.3's argument, worked out for realistic molecules. Read this before believing any VQE advantage claim. Tier 1.
• Huang, Kueng, and Preskill, "Predicting many properties of a quantum system from very few measurements" (2020), Nature Physics 16, 1050. Classical shadows — the most important shot-efficiency technique, and an honest look at what it does and does not improve. Tier 1.
• Literature on Pauli grouping and commuting-set measurement. The practical constant-factor savings. Exercise 24.15's subject. Tier 2.

On ansatz design

• Grimsley et al., "An adaptive variational algorithm for exact molecular simulations on a quantum computer" (2019), Nature Communications 10, 3007. ADAPT-VQE: grow the ansatz by adding the operator with the largest gradient. The best-motivated answer to "how do I choose an ansatz," and Exercise 24.29's subject. Tier 1.
• Any treatment of the unitary coupled-cluster (UCCSD) ansatz. The chemistry-derived ansatz — problem-informed in the strong sense, expensive, and the standard against which hardware-efficient ansätze are compared. Tier 1.
• Chapter 16's barren-plateau reading list, especially McClean et al. and Cerezo et al. on local cost functions. Ansatz design and barren plateaus are the same subject. Tier 1.

On QAOA and its classical competition

• Goemans and Williamson, "Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming" (1995), Journal of the ACM 42, 1115. The 0.87856 algorithm. Read it to understand what a proven approximation guarantee is, which is the distinction §24.5 turns on. Tier 1.
• Any current work on QAOA performance guarantees and limitations at low depth. There are results showing $p=1$ QAOA cannot beat classical algorithms on certain instance families — the concrete form of §24.5's "no guarantee." Exercise 24.23's subject. Tier 2 — active.
• Literature comparing QAOA against classical heuristics on realistic instances. The comparisons that actually decide whether QAOA is useful, and the ones most often omitted from QAOA papers. Tier 2.
• Chapter 21's further reading on Grover, for the same pattern: a quantum algorithm compared against a strawman classical baseline rather than the best available method.

On where the classical crossover is

• Any recent survey of classical quantum-chemistry methods — full configuration interaction, coupled cluster (CCSD(T)), DMRG, and quantum Monte Carlo. You cannot argue for quantum advantage in chemistry without knowing what these do, and they are extremely good. Tier 1.
• Estimates of the classically-intractable frontier for correlated systems. The "50+ orbitals" figure §24.7 quotes is a moving target and worth checking against current work. Tier 2.
• Chapter 15's resource estimator, applied to phase-estimation chemistry. The fault-tolerant route to the same problem, for comparison — Exercise 24.30's subject. Tier 1.

Forward references

• Chapter 25 — the thing that changes all of this, and Part IV's close.
• Chapter 32 — Part VI is this chapter with a different cost function, and the same shot budget.
• Chapter 36 — VQE applied to chemistry properly, with the ansatz question taken seriously.
• Chapter 37 — QAOA on real optimization problems, and the classical baselines.

Where to go next. If one thing: Gonthier et al. on measurements as a roadblock. It is §24.3's argument done properly for realistic systems, and it will change how you read every VQE result that quotes iterations instead of shots.

If two: add Goemans and Williamson, not for the algorithm but for what a proven approximation guarantee looks like — the standard §24.5 holds QAOA to, and the reason the comparison is a matter of kind rather than degree.

Then Chapter 25 — error correction, which is what has to work before any of Chapter 23's or this chapter's ambitions become engineering rather than research.