Lesson 34: The Quantum Approximate Optimization Algorithm (QAOA)¶
34.1 Learning Outcomes¶
By the end of this hour a student will be able to:
- Convert a combinatorial problem to QUBO and then to an Ising Hamiltonian.
- Construct the QAOA cost and mixer unitaries and the full \(p\)-layer ansatz.
- Derive the QAOA circuit for Max-Cut and compute the \(p=1\) expectation analytically.
- State the approximation ratio results and the \(p\to\infty\) limit.
- Assess QAOA's practical status honestly against classical heuristics.
34.2 From Combinatorial Problems to Ising Hamiltonians¶
QUBO¶
Definition. A Quadratic Unconstrained Binary Optimization problem is
QUBO is NP-hard and remarkably universal — Max-Cut, graph colouring, the travelling salesman problem, portfolio optimisation, number partitioning and set cover all reduce to it.
Handling constraints. A constraint \(\sum_i x_i = k\) becomes a penalty term \(\lambda\big(\sum_ix_i - k\big)^{2}\) added to the objective, with \(\lambda\) large enough that violating the constraint always costs more than any gain elsewhere.
QUBO to Ising¶
Substitute \(x_i = \frac{1 - z_i}{2}\) with \(z_i \in \{-1,+1\}\):
The objective becomes the Ising energy
where \(Z_i\) is the Pauli-\(Z\) on qubit \(i\). Note that \(H_C\) is diagonal in the computational basis: \(H_C|\vec z\rangle = C(\vec z)\,|\vec z\rangle\), where \(C(\vec z)\) is the classical cost of the bitstring. Minimising a combinatorial objective = finding the ground state of \(H_C\).
The Max-Cut example¶
Problem. Given a graph \(G = (V,E)\), partition \(V\) into two sets to maximise the number of edges crossing the cut.
Assign \(z_i = +1\) or \(-1\) by which side vertex \(i\) is on. An edge \((i,j)\) is cut iff \(z_i \ne z_j\), i.e. iff \(z_iz_j = -1\). So
We maximise \(\langle H_C\rangle\) (equivalently minimise \(\sum_{(i,j)}Z_iZ_j\)).
34.3 The QAOA Ansatz¶
Farhi, Goldstone and Gutmann (2014).
Two Hamiltonians¶
Cost Hamiltonian \(H_C\) — encodes the problem, diagonal.
Mixer Hamiltonian
— off-diagonal; it drives transitions between bitstrings, allowing the state to explore.
They do not commute: \([H_C, H_B]\ne0\). This is essential — if they commuted the algorithm would be classical.
The circuit¶
Initial state: the uniform superposition, which is the ground state of \(-H_B\):
Alternate \(p\) times:
\(2p\) parameters: \(\vec\gamma = (\gamma_1,\dots,\gamma_p)\), \(\vec\beta = (\beta_1,\dots,\beta_p)\).
Objective:
Then measure in the computational basis; the measured bitstring is the candidate solution.
Implementing the unitaries¶
Cost unitary. Because \(H_C\) is a sum of commuting \(Z_iZ_j\) terms:
Each \(e^{-i\theta Z_iZ_j/2}\) is realised as
q_i --*----------------*--
| |
q_j --[X]--[Rz(theta)]--[X]--
i.e. CNOT, \(R_z(\theta)\), CNOT — two CNOTs and one rotation per edge.
Mixer unitary. \(H_B\) is a sum of single-qubit \(X\)'s, so
— one \(R_x\) per qubit, all in parallel.
Total resources: \(p\,(2|E| + n)\) gates, depth \(O(p\cdot|E|/n)\) if edges are parallelised.
Full circuit¶
q0 --[H]--+--------------+--[Rx(2b1)]--+---------------+--[Rx(2b2)]-- ... [M]
| exp(-i g1 Hc) | | exp(-i g2 Hc) |
q1 --[H]--+--------------+--[Rx(2b1)]--+---------------+--[Rx(2b2)]-- ... [M]
| | | |
q2 --[H]--+--------------+--[Rx(2b1)]--+---------------+--[Rx(2b2)]-- ... [M]
\_______ layer 1 _______/ \_______ layer 2 _______/
34.4 Theory¶
The adiabatic connection¶
QAOA is a Trotterised approximation to adiabatic evolution. The adiabatic algorithm evolves under
slowly from the ground state of \(H_B\) to that of \(H_C\). Trotterising this evolution into \(p\) steps gives exactly the QAOA form. Hence:
QAOA is exact in the limit \(p\to\infty\). The question is how large \(p\) must be — and this is where the practical difficulty lies.
Known results¶
| Result | Statement |
|---|---|
| Farhi et al. (2014) | \(p=1\) QAOA on 3-regular graphs guarantees approximation ratio \(\ge 0.6924\) |
| Goemans–Williamson (classical SDP) | guarantees \(\ge 0.8785\) — better than \(p=1\) QAOA |
| \(p=2\) on 3-regular | \(\ge 0.7559\) |
| \(p=11\) on 3-regular | \(\approx0.8785\) — only here does QAOA match GW |
| Farhi–Harrow (2016) | QAOA at \(p=1\) already gives sampling hard for classical computers, though the optimisation quality is modest |
| Bravyi et al. (2020) | for bounded-degree graphs, low-\(p\) QAOA is provably limited by locality — it cannot see beyond distance \(p\) |
The locality obstruction¶
At depth \(p\), each qubit's final state depends only on the subgraph within distance \(p\) of that qubit (a lightcone argument). For a graph with \(n\) vertices and good expansion, a constant \(p\) sees only a vanishing local neighbourhood, so QAOA cannot detect global structure. This is Bravyi–Kliesch–Koenig–Tang's "obstacle to variational quantum advantage" and it explains why constant-depth QAOA underperforms classical algorithms on many families.
34.5 Solved Problems¶
Problem 1 — Building the Ising Hamiltonian for a triangle¶
For the triangle graph \(K_3\) with vertices \(\{0,1,2\}\) and all three edges, write \(H_C\), list all 8 bitstrings with their cut values, and identify the optimum.
Solution.
Enumerate (using \(z_i = +1\) for bit 0, \(-1\) for bit 1; cut edges = pairs with different bits):
| \(\lvert z_0z_1z_2\rangle\) | Partition | Cut edges | Cut value |
|---|---|---|---|
| \(000\) | \(\{0,1,2\}\mid\emptyset\) | none | 0 |
| \(001\) | \(\{0,1\}\mid\{2\}\) | (0,2),(1,2) | 2 |
| \(010\) | \(\{0,2\}\mid\{1\}\) | (0,1),(1,2) | 2 |
| \(011\) | \(\{0\}\mid\{1,2\}\) | (0,1),(0,2) | 2 |
| \(100\) | \(\{1,2\}\mid\{0\}\) | (0,1),(0,2) | 2 |
| \(101\) | \(\{1\}\mid\{0,2\}\) | (0,1),(1,2) | 2 |
| \(110\) | \(\{2\}\mid\{0,1\}\) | (0,2),(1,2) | 2 |
| \(111\) | \(\emptyset\mid\{0,1,2\}\) | none | 0 |
Note: \(K_3\) is an odd cycle, so it is not bipartite — you cannot cut all 3 edges. Six of the eight bitstrings achieve the optimum, so random guessing already gives \(\frac{6}{8}\times2 + \frac28\times0 = 1.5\), an approximation ratio of \(\frac{1.5}{2} = 0.75\). Any proposed algorithm must beat 0.75 on this instance to be doing anything at all — a useful sanity check students should always compute first.
Problem 2 — QAOA p=1 on a single edge, computed exactly¶
Compute \(F_1(\gamma,\beta)\) for a 2-vertex graph with one edge, and find the optimal parameters.
Solution.
Step 1. \(|s\rangle = |{+}{+}\rangle = \frac12(|00\rangle+|01\rangle+|10\rangle+|11\rangle)\).
Step 2 — cost unitary. \(e^{-i\gamma H_C}\) is diagonal, applying phase \(e^{-i\gamma C(\vec z)}\) where \(C = 1\) for \(\{01,10\}\) and \(C=0\) for \(\{00,11\}\):
Step 3 — mixer. Apply \(R_x(2\beta)^{\otimes2}\).
Step 4 — evaluate \(F_1 = \langle H_C\rangle\). Since \(H_C = \frac12(I - Z_0Z_1)\), we need \(\langle Z_0Z_1\rangle\) in the final state. Work in the Heisenberg picture:
Conjugate by the mixer. \(U_B = e^{-i\beta(X_0+X_1)}\) rotates \(Z\) about the \(x\)-axis:
so that
Conjugate by the cost unitary \(U_C = e^{-i\gamma(I-Z_0Z_1)/2}\) and take the expectation in \(|{+}{+}\rangle\), where \(\langle X_i\rangle = 1\) and \(\langle Y_i\rangle = \langle Z_i\rangle = 0\). Only terms reducing to products of \(X\)'s or the identity survive; the \(Z_0Z_1\) and \(Y_0Y_1\) cross-terms combine into a single sinusoid, giving
and therefore
(Verify numerically: at \(\gamma = 1.0\), \(\beta = 0.3\) both the exact \(4\times4\) simulation and this formula give \(F_1 = 0.892142\).)
Maximise. Both factors reach 1 when
QAOA at \(p=1\) solves the single-edge problem exactly (the graph is bipartite and trivially small). Random guessing gives \(F = 0.5\), so QAOA doubles it.
Problem 3 — Formulating a constrained problem as QUBO¶
Formulate "select exactly 2 items from 4 to maximise total value \(\vec v = (3,5,2,7)\)" as a QUBO, then convert to Ising.
Solution.
Objective (to maximise). \(\sum_i v_ix_i\). Convert to a minimisation: minimise \(-\sum_iv_ix_i\).
Constraint. \(\sum_i x_i = 2\). Add the penalty \(\lambda\big(\sum_ix_i - 2\big)^{2}\).
Choosing \(\lambda\). It must exceed the largest possible gain from violating the constraint. Adding a third item gains at most \(\max v_i = 7\) while the penalty rises from 0 to \(\lambda\). So \(\lambda > 7\); take \(\lambda = 10\).
Expand the penalty using \(x_i^{2} = x_i\) (binary):
QUBO matrix (with \(\lambda = 10\)):
Verify the optimum. The best pair is items 2 and 4 (\(v = 5+7 = 12\)):
Check a 3-item selection \(\{1,2,4\}\) (\(v = 15\)):
\(-5 > -12\), so the constraint is correctly enforced ✓ — the higher-value but infeasible selection is penalised into a worse objective.
Convert to Ising with \(x_i = \frac{1-z_i}{2}\):
Collecting terms gives
For \(i=1\): \(h_1 = 16.5 - \frac{60}{4} = 16.5 - 15 = 1.5\). Similarly \(\vec h = (1.5,\ 2.5,\ 1.0,\ 3.5)\).
Four qubits, ready for QAOA.
Problem 4 — Approximation ratio and resource estimate¶
A Max-Cut instance on a 3-regular graph with 100 vertices. Compute the number of edges, gates per QAOA layer, and total gates for \(p=1,3,11\). Compare quality with Goemans–Williamson.
Solution.
Edges. 3-regular means every vertex has degree 3:
Gates per layer.
Totals.
| \(p\) | Gates | CNOTs | Approx. ratio | Fidelity at \(\epsilon_{\text{CX}}=10^{-3}\) |
|---|---|---|---|---|
| 1 | 650 | 300 | 0.6924 | \((0.999)^{300} = 0.741\) |
| 3 | 1750 | 900 | ~0.79 | \((0.999)^{900} = 0.406\) |
| 11 | 6150 | 3300 | 0.8785 | \((0.999)^{3300} = 0.037\) |
(Adding 100 Hadamards for state preparation.)
The comparison that matters.
| Method | Guarantee | Runtime |
|---|---|---|
| Random assignment | 0.5 | instant |
| Greedy | ~0.5 | \(O(\lvert E\rvert)\) |
| Goemans–Williamson SDP | 0.8785 | polynomial, seconds |
| QAOA \(p=1\) | 0.6924 | ~\(10^{5}\) shots |
| QAOA \(p=11\) | 0.8785 | ~\(10^{5}\) shots, 3.7 % circuit fidelity |
Conclusion. For 3-regular Max-Cut, QAOA is not competitive on current hardware. Its interest lies in problem families where no good classical approximation exists, in warm-started variants, and in the \(p\to\infty\) theoretical guarantee.
Problem 5 — Warm-starting and the parameter-transfer trick¶
QAOA parameter optimisation is expensive and non-convex. Describe two techniques that mitigate this and estimate their savings.
Solution.
Technique 1: Parameter transfer (parameter concentration).
Observation (Brandao et al., 2018; Streif–Leib, 2019). For a fixed problem family (say 3-regular Max-Cut), the optimal \((\vec\gamma^{*},\vec\beta^{*})\) concentrate: they are nearly the same for different random instances of the same size, and vary only slowly with \(n\).
Procedure.
1. Classically simulate a SMALL instance (n = 10-16) and optimise fully
2. Reuse (gamma*, beta*) directly on LARGE instances -- no optimisation at all
3. Optionally fine-tune with a handful of steps
Savings. Full optimisation at \(p=3\) (6 parameters) with SPSA typically needs ~200 steps × 2 evaluations × \(10^{4}\) shots \(= 4\times10^{6}\) shots. Parameter transfer needs one circuit evaluation of \(10^{4}\) shots.
Technique 2: Warm-start QAOA (Egger, Mareček, Woerner, 2021).
Instead of starting from \(|+\rangle^{\otimes n}\) (a completely uninformed state), start from a state biased toward a classical approximate solution.
1. Solve the SDP relaxation (Goemans-Williamson) classically -> fractional c_i in [0,1]
2. Initialise each qubit at angle theta_i = 2*arcsin(sqrt(c_i)) instead of |+>
3. Replace the standard mixer with one whose ground state is that warm-start state
4. Run QAOA -- it now IMPROVES on GW rather than starting from scratch
Why the mixer must change. The standard \(H_B = \sum X_i\) has \(|+\rangle^{\otimes n}\) as its ground state; with a different initial state the adiabatic argument breaks. The warm-start mixer is constructed so the new initial state is its ground state, restoring the guarantee.
Result. Warm-started QAOA at \(p=1\) inherits the GW guarantee of 0.8785 and improves on it monotonically with \(p\) — instead of starting at 0.6924 and needing \(p=11\) just to catch up.
Combined recipe for practice.
1. Solve the SDP relaxation classically -> warm start + a baseline guarantee
2. Transfer parameters from a small simulated instance -> no expensive optimisation
3. Run shallow QAOA (p = 1-3) on hardware -> stays within coherence
4. Post-process: take the best measured bitstring, apply classical local search
Step 4 matters more than students expect: QAOA returns a distribution, and taking the best of many samples plus a greedy local-search polish routinely beats the raw expectation value.
34.6 Practice Problems¶
- Write \(H_C\) for a 4-cycle graph \(C_4\) and give \(C_{\max}\). [Ans: \(C_{\max}=4\); bipartite]
- Convert \(\min\ 3x_1 + 2x_2 - 4x_1x_2\) to Ising form.
- How many gates per QAOA layer for a complete graph \(K_6\)? [Ans: \(2\times15+15+6 = 51\)]
- For \(F_1 = \frac12(1+\sin4\beta\sin\gamma)\), find all optima in \([0,\pi]^2\).
- Compute the random-guess approximation ratio for Max-Cut on any graph. [Ans: 0.5]
- Why must \(\lambda\) exceed the maximum objective gain in a penalty formulation?
- Explain the locality obstruction in three sentences.
34.7 Summary¶
- QUBO ↔ Ising via \(x_i = \frac{1-z_i}{2}\); constraints become quadratic penalties with \(\lambda\) larger than the maximum gain from violating them.
- Max-Cut: \(H_C = \sum_{(i,j)\in E}\frac12(I - Z_iZ_j)\); \(\langle H_C\rangle\) is the expected number of cut edges.
- QAOA ansatz: alternate \(e^{-i\gamma_kH_C}\) (CNOT–\(R_z\)–CNOT per edge) and \(e^{-i\beta_kH_B}\) (\(R_x\) per qubit), starting from \(|+\rangle^{\otimes n}\); optimise \(2p\) parameters classically.
- QAOA is a Trotterised adiabatic evolution, exact as \(p\to\infty\).
- Honest status: \(p=1\) guarantees 0.6924 on 3-regular Max-Cut versus 0.8785 for the classical Goemans–Williamson SDP; matching GW needs \(p=11\), at which depth NISQ fidelity collapses. Constant-depth QAOA is provably limited by locality.
- Practical mitigations: parameter transfer (optimal angles concentrate across instances — ~400× cheaper) and warm-starting from the SDP solution (inherits the 0.8785 guarantee and improves on it), plus classical local-search post-processing.
Next lesson: L35 — Quantum annealing and the adiabatic model.
Practise now: unit3-qml-lab.html → QAOA Lab: draw a graph, set \(p\), sweep \((\gamma,\beta)\) over
a heat map of \(F_p\), and compare the sampled cut distribution against the brute-force optimum.