Self-Assessment Quiz: QAOA

Twenty questions on the Quantum Approximate Optimization Algorithm: structure, depth, performance guarantees, and the state of the evidence. Aim for 16+.

Question 1

QAOA alternates between:

A) A cost Hamiltonian $e^{-i\gamma H_C}$ and a mixer $e^{-i\beta H_M}$ B) Measurement and reset C) Two different cost functions D) Classical and quantum bits

Question 2

The standard mixer Hamiltonian is:

A) $\sum_i X_i$ B) $\sum_i Z_i$ C) $\sum_{ij} Z_iZ_j$ D) The identity

Question 3

The parameter $p$ denotes:

A) The number of qubits B) The number of alternating layers C) The success probability D) The problem size

Question 4

As $p \to \infty$, QAOA:

A) Fails B) Approaches the adiabatic limit and the exact optimum C) Stays constant D) Becomes classical

Question 5

For MaxCut on 3-regular graphs, $p=1$ QAOA guarantees an approximation ratio of at least:

A) 0.5 B) 0.6924 C) 0.878 D) 1.0

Question 6

The classical Goemans–Williamson algorithm guarantees:

A) 0.5 B) 0.6924 C) 0.878 D) 1.0

Question 7

Therefore, at $p=1$ on 3-regular MaxCut, QAOA is:

A) Better than the best classical guarantee B) Worse than the best classical guarantee C) Equal D) Incomparable

Question 8

QAOA's parameters are found by:

A) Analytic formula only B) Classical optimization over measured expectation values C) Random guessing D) Quantum search

Question 9

The number of parameters is:

A) $n$ B) $2p$ C) $p^2$ D) $2^n$

Question 10

A key practical difficulty is:

A) Circuit depth grows linearly with $p$, and useful $p$ may be large B) Too few qubits needed C) No classical component D) It cannot be measured

Question 11

QAOA on a graph with limited hardware connectivity requires:

A) Nothing extra B) SWAP networks, multiplying gate count C) Fewer gates D) Error correction

Question 12

"Concentration" of QAOA parameters means:

A) Optimal parameters are similar across problem instances, allowing transfer B) Qubits cluster C) The energy concentrates D) Measurements concentrate

Question 13

QAOA's relationship to adiabatic quantum computing is:

A) Unrelated B) QAOA is a Trotterized, variationally optimized adiabatic path C) QAOA is faster than adiabatic by definition D) They are identical

Question 14

The strongest current evidence about QAOA's advantage is:

A) Proven exponential speedup B) No proven advantage over the best classical heuristics for practical problem sizes C) Proven quadratic speedup D) Proven for all graphs

Question 15

Which classical method is a strong QAOA competitor on MaxCut?

A) Brute force B) Goemans–Williamson SDP, and tuned local search / tabu heuristics C) Random sampling D) None

Question 16

True or false: QAOA is guaranteed to outperform classical heuristics at sufficiently large $p$.

Question 17

True or false: QAOA suffers from barren plateaus like other variational algorithms.

Question 18

True or false: QAOA returns the optimal solution with certainty.

Question 19

Short answer. Explain why QAOA's performance guarantee at $p=1$ being below Goemans–Williamson matters, and what would change the picture.

Question 20

Short answer. A team reports QAOA finding optimal solutions on 20-node graphs. What is the appropriate reaction?

Answer Key

Q Ans Note
1 A The alternating operator structure.
2 A Transverse field; it drives transitions between computational basis states.
3 B Depth parameter — the circuit has $2p$ alternating blocks.
4 B With optimal parameters, QAOA approximates adiabatic evolution and reaches the optimum. The catch is entirely in how large $p$ must be.
5 B Farhi et al.'s original bound, 0.6924.
6 C 0.878, assuming the unique games conjecture makes it essentially optimal for polynomial-time algorithms.
7 B Strictly worse at $p=1$, which is the honest and frequently omitted comparison.
8 B The hybrid variational loop, as in VQE.
9 B One $\gamma$ and one $\beta$ per layer.
10 A Depth grows with $p$, and $p$ must grow with problem size for good approximation ratios — the central tension.
11 B Mapping a dense problem graph onto sparse hardware connectivity costs SWAPs, often dominating the circuit.
12 A An empirically useful phenomenon: parameters transfer between instances, cutting optimization cost.
13 B QAOA is a discretized adiabatic path with parameters optimized rather than fixed by a schedule.
14 B Despite a decade of work, no instance class has a demonstrated practical advantage.
15 B GW gives a guarantee; tuned heuristics routinely beat both in practice on real instances.
16 False Large $p$ approaches the optimum, but the required $p$ and the resulting depth may be prohibitive, and classical heuristics also improve with more time. The comparison must hold time fixed.
17 True Though QAOA's structured ansatz is somewhat more resistant than random hardware-efficient circuits, plateaus still appear at large $p$.
18 False It returns samples; you take the best over many shots. It is a heuristic sampler.
19 — At $p=1$ QAOA has a worse worst-case guarantee than a polynomial-time classical algorithm, so any advantage must come from larger $p$ — which costs depth on hardware that cannot afford it. What would change the picture: a proof of a better ratio at modest $p$; an instance class where QAOA empirically beats tuned heuristics at equal wall-clock; or hardware making large $p$ cheap. None has arrived.
20 — Muted. Twenty-node MaxCut is solved exactly by classical branch-and-bound in milliseconds, and by simple local search almost instantly. Finding optimal solutions there demonstrates that the implementation is correct, not that the approach is advantageous. The meaningful questions: at what size does QAOA still find optima, how does that scale, and how does it compare at equal wall-clock against a tuned classical heuristic on the same instances? Without those, it is a correctness check reported as a result.