Quiz: Quantum Optimization with QAOA

DataField.Dev

Quiz: Quantum Optimization with QAOA

20 questions. Answers with explanations follow.

1. A uniformly random assignment on a MaxCut instance achieves, in expectation:

(a) half the edges
(b) half the optimum
(c) 0.878 of the optimum
(d) nothing — it is not an algorithm

2. The Goemans–Williamson approximation guarantee is:

(a) 0.5
(b) 0.87856 of the optimum, proven, in polynomial time
(c) 0.87856 on average across instances
(d) 1.0 — it is exact

3. On a graph with 15 edges and optimum 13, a random assignment scores:

(a) 0.5 of the edges and 0.577 of the optimum
(b) 0.5 of both
(c) 0.577 of both
(d) it depends on the graph

4. ratio_denominator(cut, edges, opt, against=...) refuses an unrecognized against because:

(a) the parameter is misspelled
(b) the same assignment has different ratios under different denominators, so the denominator is not a detail
(c) it makes the API simpler
(d) ratios must be against the optimum

5. The MaxCut → Ising mapping is:

(a) approximate, like Chapter 36's active space
(b) exact — one qubit per vertex, one term per edge, no modelling error
(c) only valid for regular graphs
(d) exponentially expensive to construct

6. QAOA uses how many parameters at depth $p$?

(a) $p$
(b) $2p$
(c) $np$
(d) $2^p$

7. As $p \to \infty$, QAOA:

(a) diverges
(b) becomes adiabatic evolution and finds the exact optimum
(c) converges to random guessing
(d) reaches exactly 0.878

8. ★ Measured mean approximation ratios across 8 seeds, $p=1$ to $p=5$:

(a) 0.751, 0.812, 0.852, 0.873, 0.907
(b) 0.5, 0.6, 0.7, 0.8, 0.9
(c) all approximately 0.878
(d) they decrease with $p$

9. ★★ QAOA at $p=1$ scores 0.751. Relative to the classical guarantee, that is:

(a) above it
(b) below it — beaten by a proof from 1994
(c) exactly equal
(d) not comparable

10. ★ At $p=5$, QAOA puts what fraction of its probability on the 2 optimal states out of 4,096?

(a) 0.0005, the same as uniform
(b) 0.388 — a factor of 795 over uniform
(c) 1.0
(d) 0.878

11. ★★ The book's first version of the $p$ table showed $p=4$ worse than $p=3$. That was:

(a) a real effect caused by barren plateaus
(b) an artifact of using one seed — $p=4$ beat $p=3$ in 7 of 8
(c) a bug in PennyLane
(d) correct but unimportant

12. ★★★ A measured $p=4 < p=3$ cannot be a property of the ansatz because:

(a) more parameters always help
(b) $p=4$ contains $p=3$ — set the extra angles to zero and you recover it exactly
(c) the ansatz is linear in $p$
(d) it can be; the claim is wrong

13. ★★ What did survive the re-run:

(a) nothing
(b) the variance across initializations grows with $p$ — std 0.000 at $p=1$ to 0.021 at $p=4$
(c) $p=4$ is still worse on some graphs
(d) barren plateaus at $p=2$

14. ★★★ Across ten instances, one seed and one sample each, the head-to-head result was:

(a) QAOA 6, GW 0, ties 4
(b) QAOA 0, GW 6, ties 4
(c) QAOA 5, GW 5
(d) QAOA 10, GW 0

15. ★★ GW's single random rounding found the exact optimum on:

(a) 8 of 10 instances
(b) 1 of 10
(c) 10 of 10
(d) 0 of 10

16. ★★ QAOA's mean $E[\text{cut}]/\text{OPT}$ was 0.891 — above the guarantee — yet it won nothing. Because:

(a) the mean was computed wrong
(b) the mean describes the state prepared, not the answer a user receives; single samples returned 9 and 11 against an optimum of 13
(c) GW cheated
(d) 0.891 is below 0.87856

17. ★★★ The SDP relaxation returns, in addition to a cut:

(a) nothing
(b) an upper bound on the optimum, so GW certifies its answer without knowing the optimum
(c) a lower bound
(d) the exact optimum, always

18. ★★★ QAOA's output, by contrast:

(a) includes a variational bound
(b) is a bitstring with no certificate — a bad answer is indistinguishable from a good one
(c) includes a confidence interval
(d) includes the optimum

19. ★★★ The certificate gap is important because:

(a) it makes QAOA slower
(b) it is a difference in what the algorithms produce, and does not close when devices improve
(c) it only matters for MaxCut
(d) it will be fixed by error correction

20. ★★ QAOA at $p=3$ and $\epsilon = 0.01$ on a 12-node graph needs:

(a) 13,000,000 shots = 22 minutes of device time, against GW's 8 milliseconds
(b) 1,300 shots
(c) no shots — expectation values are free
(d) 13,000 shots

Answers

1. (a) half the edges. Each edge is cut with probability $\tfrac{1}{2}$ independent of the graph. Note this is half the edges, not half the optimum — see question 3.

2. (b). A theorem, not a heuristic: for every graph, in polynomial time, with a certificate. Any MaxCut result below 0.878 is beaten by a classical algorithm from 1994.

3. (a). 7.5/15 = 0.5 of the edges; 7.5/13 = 0.577 of the optimum. Same cut, same graph, two ratios, because the optimum is less than every edge. §37.1.

4. (b). "QAOA achieves 0.9" means nothing until you say 0.9 of what, and the two denominators get swapped constantly. The module raises rather than picking a default.

5. (b) exact. One qubit per vertex, one two-qubit term per edge. Contrast Chapter 36, where the active space introduced an error $10^7$ times larger than the method being demonstrated. That is why optimization is the cleaner test — everything measured here is a property of the algorithm.

6. (b) $2p$ — one $\gamma$ and one $\beta$ per layer. Far fewer than any Part VI ansatz, which is the design's real virtue.

7. (b). QAOA is a Trotterized adiabatic evolution. The algorithm is guaranteed correct in a limit nobody can reach, which is exactly Chapter 21's situation with Grover.

8. (a). Monotone, and the improvement is real.

9. (b) below it. It takes $p=5$ to clear 0.87856 on this instance — in expectation, on a simulator, with no shot noise and no hardware error.

10. (b) 0.388, a factor of 795. Worth stating plainly: QAOA is doing real work. It is not a failed algorithm; it is an algorithm that works and loses anyway.

11. (b). The single-seed $p=3$ range (0.818–0.877) and $p=4$ range (0.834–0.897) overlap across almost their entire width. The book drew badly and stopped. This was the fourth time — Chapters 27, 28, 33, and 34 made the same error.

12. (b). Set $\gamma_4 = \beta_4 = 0$ and the fourth layer is the identity. So the $p=4$ optimum is at least the $p=3$ optimum, always. A measured regression is therefore a statement about the optimizer, not the ansatz — which is a different claim needing different evidence. The structural argument is what made the error catchable, and it was available before any measurement.

13. (b). The mechanism the original story described was real; it was attached to the wrong observable. At $p=1$ all eight starts converge to exactly the same ratio — two parameters, one basin.

14. (b) QAOA 0, GW 6, ties 4.

15. (a) 8 of 10 — from a single rounding, in 5.9 ms.

16. (b). An optimization user receives an answer, not a mean. Chapter 30 §30.5 refused to let a fidelity be quoted without naming its statistic; this is the same refusal with a graph attached.

17. (b) an upper bound. On instance 0 it proved the cut of 13 was within 0.9975 of optimal — without brute force and without being told the optimum.

18. (b). Instance 9 returned a cut of 9 against an optimum of 13, and nothing in the output distinguishes it from instance 5's optimal 13. To find out you must run something else — and if that something else is GW, you have already solved the problem.

19. (b). This is the finding that outlasts the scorecard. Better hardware makes QAOA faster; it does not make QAOA produce a bound. A faster QAOA is a faster uncertified answer. Case Study 37.1 shows what that costs in practice — the incumbent solver was printing a 0.046% optimality gap every day and nobody had read it.

20. (a). And that is the optimistic term: it assumes the optimizer converges in 100 iterations, that simulator angles transfer to hardware, and that noise does not flatten the landscape below the resolution the shots buy. Every number in this chapter came from exact simulation, where expectation values are free — that is what the simulator was hiding.