Exercises: Quantum Optimization with QAOA

Difficulty: ★ warm-up · ★★ standard · ★★★ extended · ★★★★ open-ended.

[measure] — run something and report a number. [refuse] — identify a claim that should not be made. [reseed] — the exercise is specifically about not trusting one draw.

These need pip install cvxpy networkx in addition to the book's usual environment.

MaxCut and the baselines (§37.1–37.2)

37.1 ★ A graph has 15 edges and an optimum cut of 13. A random assignment achieves 7.5 in expectation. Give both approximation ratios and say which one a paper should report.

37.2 ★ Why is ratio_denominator(7.5, 15, 13, against="whatever") an error rather than a warning? Answer in one sentence.

37.3 ★★ Write out the Ising Hamiltonian for a triangle graph. What is its optimum, and how many assignments achieve it?

37.4 ★★ §37.2 calls the MaxCut mapping "exact and free." Contrast with Chapter 36 §36.4 in two sentences, and say what that difference lets this chapter claim that Chapter 36 could not.

37.5 ★★ [measure] Build the SDP for a 6-vertex graph by hand in cvxpy and confirm the bound is at least the brute-force optimum. Why must it be?

37.6 ★★★ [refuse] A vendor's chart shows QAOA beating "the classical baseline" by 1.6× on MaxCut. What is the single question that determines whether the chart means anything?

The ansatz and $p$ (§37.3)

37.7 ★ How many parameters does QAOA use at $p=5$? Compare to a hardware-efficient ansatz on 12 qubits with 5 layers.

37.8 ★★ Explain why $p \to \infty$ QAOA finds the exact optimum. Then explain in one sentence why that guarantee is not useful.

37.9 ★★ [measure] Reproduce §37.3's table on a different 12-node 3-regular graph. Do the means still rise monotonically? Does $p=1$ still have std 0.000?

37.10 ★★ $P(\text{optimal})$ at $p=5$ is 0.388 against 0.0005 for the uniform superposition. What does that factor of 795 mean operationally — how many shots do you need to see an optimal cut with 99% confidence, in each case?

37.11 ★★★ [measure] Extend to $p=6,7,8$. Does the mean keep rising? Does the variance? Report the wall-clock cost, and say where you would stop.

37.12 ★★★ QAOA's angles are known to transfer between instances of the same family. Test it: optimize on one 3-regular graph, apply the angles unchanged to five others, and report the ratios. What does a positive result do to §37.8's shot budget?

The regression that was not there (§37.4)

37.13 ★ State precisely why a measured $p=4 < p=3$ cannot be a property of the ansatz.

37.14 ★★ [reseed] Take the $p=3$ and $p=4$ per-seed lists from §37.3. Draw one value from each at random, 1,000 times, and report how often $p=4$ appears worse. That number is the probability the book's original table was going to mislead.

37.15 ★★ MIN_SEEDS = 8 is admitted to be arbitrary. Derive a defensible value from the measured standard deviations and an effect size you choose. State the effect size first.

37.16 ★★ [refuse] Write the claim the single-seed data does support, in a form you would defend in review.

37.17 ★★★ [reseed] The variance grows from 0.000 at $p=1$ to 0.021 at $p=4$, then falls to 0.014 at $p=5$. Is that fall real? Design the measurement that would settle it, then run it if you can.

37.18 ★★★ Chapter 27, 28, 33, 34 and now 37 all made the same error. Write the checklist item that would have caught all five, in one sentence, and say what it costs to follow.

The comparison (§37.5–37.6)

37.19 ★ Why does the chapter give GW one rounding rather than 100?

37.20 ★★ [measure] Reproduce §37.6's ten-instance table. Do you get 0/10?

37.21 ★★ QAOA's mean ratio was 0.891, above the 0.87856 guarantee, and it won 0 of 10. Explain how both are true.

37.22 ★★ [refuse] "QAOA achieved a 0.891 approximation ratio, exceeding the Goemans–Williamson guarantee." Everything in that sentence is arithmetically correct. What is wrong with it?

37.23 ★★★ [measure] Give QAOA 1,000 samples and GW 1,000 roundings on the same ten instances. Does QAOA win any? At what sample count do they converge, and what does that tell you?

37.24 ★★★ [measure] Find an instance family where GW's single rounding does not find the optimum most of the time. (Try weighted graphs, or graphs with large odd cycles.) Then re-run the comparison there. Report honestly whether QAOA does better.

37.25 ★★★★ [open] §37.9 says no instance family has been demonstrated on hardware where GW's 0.878 is tight and QAOA does better. Search the literature and report what you find, including "none" if that is the answer.

The certificate (§37.7)

37.26 ★ What does UncertifiedResult.certified_ratio return, and why is that better than 1.0?

37.27 ★★ [measure] For each of the ten instances, compute the certified ratio and compare it to the true ratio. How tight is the SDP bound?

37.28 ★★ Construct two UncertifiedResult objects that a user cannot distinguish but that differ by 30% in quality. Then do the same with CertifiedResult and explain why you cannot.

37.29 ★★★ Is there any way to get a bound out of QAOA? Consider: the variational principle, sampling statistics, and running the classical relaxation alongside. Evaluate each honestly.

37.30 ★★★ §37.7 claims the certificate gap "does not close when devices improve." Attack that claim — find the strongest counterargument you can — then say whether it survives.

The shot budget and integration (§37.8–37.9)

37.31 ★★ [measure] Price a 20-node QAOA at $p=3$ and $\epsilon=0.01$. Then price it at $\epsilon=0.05$ and say whether 5% precision is defensible for MaxCut.

37.32 ★★ Warm-starting from GW removes the classical optimization loop. Estimate what that saves from §37.8's budget, and state what it concedes.

37.33 ★★★ [measure] Run QAOA with a finite shot budget (qml.device("default.qubit", shots=N)) at $N = 100, 1000, 10000$. At what $N$ does the optimizer stop converging, and how does that compare to §37.8's estimate?

37.34 ★★★ Case Study 37.1's analyst won the argument with a solver log line. Find the equivalent line in a solver you have access to, and say what it certifies.

37.35 ★★★★ [open] §37.9 lists four things that would have to change. Rank them by how likely each is to happen in five years, and defend the ranking with evidence rather than intuition.