Skip to content

Lesson 34: The Quantum Approximate Optimization Algorithm (QAOA)

34.1 Learning Outcomes

By the end of this hour a student will be able to:

  1. Convert a combinatorial problem to QUBO and then to an Ising Hamiltonian.
  2. Construct the QAOA cost and mixer unitaries and the full \(p\)-layer ansatz.
  3. Derive the QAOA circuit for Max-Cut and compute the \(p=1\) expectation analytically.
  4. State the approximation ratio results and the \(p\to\infty\) limit.
  5. 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

\[ \min_{\vec x\in\{0,1\}^{n}} \ \vec x^{T}Q\vec x = \min_{\vec x}\ \sum_{i}Q_{ii}x_i + \sum_{i<j}Q_{ij}x_ix_j \]

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\}\):

\[ \boxed{\ x_i \in\{0,1\} \ \longleftrightarrow\ z_i = 1-2x_i \in\{+1,-1\}\ } \]

The objective becomes the Ising energy

\[ H_{C} = \sum_{i}h_i\,Z_i + \sum_{i<j}J_{ij}\,Z_iZ_j + \text{const} \]

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

\[ \text{cut value} = \sum_{(i,j)\in E}\frac{1 - z_iz_j}{2} \]
\[ \boxed{\ H_{C} = \sum_{(i,j)\in E}\frac{1}{2}\big(I - Z_iZ_j\big), \qquad \langle H_C\rangle = \text{expected number of cut edges}\ } \]

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

\[ H_{B} = \sum_{i=1}^{n} X_i \]

— 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\):

\[ |s\rangle = |+\rangle^{\otimes n} = \frac{1}{\sqrt{2^{n}}}\sum_{\vec z}|\vec z\rangle \]

Alternate \(p\) times:

\[ \boxed{\ |\vec\gamma,\vec\beta\rangle = e^{-i\beta_p H_B}e^{-i\gamma_p H_C}\cdots e^{-i\beta_1H_B}e^{-i\gamma_1H_C}\,|s\rangle\ } \]

\(2p\) parameters: \(\vec\gamma = (\gamma_1,\dots,\gamma_p)\), \(\vec\beta = (\beta_1,\dots,\beta_p)\).

Objective:

\[ F_p(\vec\gamma,\vec\beta) = \big\langle\vec\gamma,\vec\beta\big|H_C\big|\vec\gamma,\vec\beta\big\rangle \ \longrightarrow\ \text{maximise over } (\vec\gamma,\vec\beta) \]

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:

\[ e^{-i\gamma H_C} = \prod_{(i,j)\in E} e^{-i\gamma Z_iZ_j/2}\cdot(\text{global phase}) \]

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

\[ e^{-i\beta H_B} = \prod_{i=1}^{n} R_x(2\beta_i) \]

— 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

\[ H(t) = \Big(1 - \tfrac{t}{T}\Big)H_B + \tfrac{t}{T}H_C \]

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:

\[ \boxed{\ \lim_{p\to\infty}\max_{\vec\gamma,\vec\beta}F_p = C_{\max}\ } \]

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.

\[ H_C = \frac12\big[(I - Z_0Z_1) + (I - Z_1Z_2) + (I - Z_0Z_2)\big] = \frac32 I - \frac12\big(Z_0Z_1 + Z_1Z_2 + Z_0Z_2\big) \]

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
\[ C_{\max} = \mathbf{2} \]

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.

\[ H_C = \frac12\big(I - Z_0Z_1\big) \]

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\}\):

\[ \frac12\Big(|00\rangle + e^{-i\gamma}|01\rangle + e^{-i\gamma}|10\rangle + |11\rangle\Big) \]

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:

\[ \langle Z_0Z_1\rangle = \big\langle s\big| U_C^{\dagger}U_B^{\dagger}\,Z_0Z_1\,U_BU_C\big|s\big\rangle \]

Conjugate by the mixer. \(U_B = e^{-i\beta(X_0+X_1)}\) rotates \(Z\) about the \(x\)-axis:

\[ U_B^{\dagger}Z_iU_B = \cos(2\beta)\,Z_i - \sin(2\beta)\,Y_i \]

so that

\[ U_B^\dagger Z_0Z_1U_B = \big(\cos2\beta\,Z_0 - \sin2\beta\,Y_0\big)\big(\cos2\beta\,Z_1 - \sin2\beta\,Y_1\big) . \]

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

\[ \langle Z_0Z_1\rangle = -\sin(4\beta)\sin(\gamma) \]

and therefore

\[ \boxed{\ F_1(\gamma,\beta) = \frac{1}{2}\Big(1 + \sin(4\beta)\sin(\gamma)\Big)\ } \]

(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

\[ \sin(4\beta) = 1 \Rightarrow \beta = \frac{\pi}{8}, \qquad \sin\gamma = 1 \Rightarrow \gamma = \frac{\pi}{2} \]
\[ F_1^{\max} = \frac{1}{2}(1+1) = \mathbf{1} = C_{\max} \]

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}\).

\[ \text{minimise}\quad f(\vec x) = -\sum_{i=1}^{4}v_ix_i + \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):

\[ \Big(\sum_ix_i - 2\Big)^{2} = \sum_ix_i^2 + 2\sum_{i<j}x_ix_j - 4\sum_ix_i + 4 = 2\sum_{i<j}x_ix_j - 3\sum_ix_i + 4 \]
\[ f(\vec x) = \sum_i(-v_i - 30)x_i + 20\sum_{i<j}x_ix_j + 40 \]

QUBO matrix (with \(\lambda = 10\)):

\[ Q_{ii} = -v_i - 30 = (-33,\ -35,\ -32,\ -37), \qquad Q_{ij} = 20 \ (i<j) \]

Verify the optimum. The best pair is items 2 and 4 (\(v = 5+7 = 12\)):

\[ f = (-35) + (-37) + 20 + 40 = \mathbf{-12} \ \checkmark \]

Check a 3-item selection \(\{1,2,4\}\) (\(v = 15\)):

\[ f = -33-35-37 + 20\times3 + 40 = -105 + 60 + 40 = \mathbf{-5} \]

\(-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}\):

\[ \sum_i Q_{ii}x_i = \sum_i Q_{ii}\frac{1-z_i}{2} = \frac12\sum_iQ_{ii} - \frac12\sum_iQ_{ii}z_i \]
\[ \sum_{i<j}Q_{ij}x_ix_j = \sum_{i<j}\frac{Q_{ij}}{4}\big(1 - z_i - z_j + z_iz_j\big) \]

Collecting terms gives

\[ h_i = -\frac{Q_{ii}}{2} - \frac{1}{4}\sum_{j\ne i}Q_{ij}, \qquad J_{ij} = \frac{Q_{ij}}{4} = 5 . \]

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)\).

\[ H_C = \sum_i h_iZ_i + 5\sum_{i<j}Z_iZ_j + \text{const} \]

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:

\[ |E| = \frac{3\times100}{2} = \mathbf{150} \]

Gates per layer.

\[ \underbrace{2\times150}_{\text{CNOTs}} + \underbrace{150}_{R_z} + \underbrace{100}_{R_x} = \mathbf{550\ \text{gates}} \]

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
\[ \boxed{\ \text{To \emph{match} GW, QAOA needs } p=11, \text{ at which point noise destroys the state.}\ } \]

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.

\[ \text{Saving} \approx \mathbf{400\times} \]

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.

\[ \boxed{\ \text{Warm-starting turns QAOA from a competitor into an \emph{improver} of classical methods.}\ } \]

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

  1. Write \(H_C\) for a 4-cycle graph \(C_4\) and give \(C_{\max}\). [Ans: \(C_{\max}=4\); bipartite]
  2. Convert \(\min\ 3x_1 + 2x_2 - 4x_1x_2\) to Ising form.
  3. How many gates per QAOA layer for a complete graph \(K_6\)? [Ans: \(2\times15+15+6 = 51\)]
  4. For \(F_1 = \frac12(1+\sin4\beta\sin\gamma)\), find all optima in \([0,\pi]^2\).
  5. Compute the random-guess approximation ratio for Max-Cut on any graph. [Ans: 0.5]
  6. Why must \(\lambda\) exceed the maximum objective gain in a penalty formulation?
  7. 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.