Chapter 23: Quantum Approximate Optimization (QAOA)

23.1 Combinatorial Optimization

A combinatorial optimization problem asks: given a finite set of candidate solutions, each with an associated cost (or objective value), find the solution that maximizes or minimizes that cost. The challenge is that the number of candidates grows exponentially with the problem size, making exhaustive search impractical.

MaxCut: The Canonical Example

Given an undirected graph $G = (V, E)$ with $n$ vertices and $m$ edges, the MaxCut problem asks: partition the vertices into two groups (call them $S$ and $\bar{S}$) so that the number of edges crossing between the two groups is maximized. An edge $(i, j)$ is "cut" if vertex $i$ is in one group and vertex $j$ is in the other.

We encode the partition using binary variables $z_i \in \{0, 1\}$ for each vertex $i$. Vertex $i$ goes into group $S$ if $z_i = 0$ and into $\bar{S}$ if $z_i = 1$. An edge $(i,j)$ is cut whenever $z_i \neq z_j$, which we can express mathematically as $z_i + z_j - 2 z_i z_j$ (this equals 1 when the bits differ and 0 when they match). The total number of cut edges is:

For a graph with $n$ vertices, there are $2^n$ possible partitions. A graph with just 50 vertices has over $10^{15}$ possible cuts - far too many to check one by one. MaxCut is NP-hard: no known classical algorithm solves it exactly in polynomial time for all graphs.

From Classical Bits to Quantum Spins

To bring MaxCut into the quantum world, we replace each classical bit $z_i \in \{0, 1\}$ with a qubit and use the Pauli-Z operator to encode the partition. Recall that $Z|0\rangle = +|0\rangle$ and $Z|1\rangle = -|1\rangle$, so the eigenvalue of $Z_i$ tells us which group vertex $i$ belongs to. The classical cost function translates to a quantum operator called the cost Hamiltonian:

When qubits $i$ and $j$ are in different computational basis states (one $|0\rangle$, one $|1\rangle$), the term $Z_i Z_j$ evaluates to $-1$, so $(I - Z_i Z_j)/2 = 1$ - the edge contributes to the cut. When they are in the same state, $Z_i Z_j = +1$ and the term vanishes. The eigenvalues of $H_C$ are exactly the cut values $C(z)$ for each bitstring $z$. Maximizing the cut is equivalent to finding the highest eigenvalue of $H_C$.

Beyond MaxCut: SAT and Scheduling

The QAOA framework extends far beyond MaxCut. Any combinatorial optimization problem whose objective function can be written as a sum of terms involving a bounded number of variables can be encoded as a cost Hamiltonian:

• Satisfiability (SAT): Given a Boolean formula in conjunctive normal form (a conjunction of clauses, each a disjunction of literals), find an assignment that satisfies the maximum number of clauses. Each clause becomes a term in $H_C$ using products of $Z$ operators and identity shifts.
• Graph coloring: Assign colors to vertices so that no two adjacent vertices share a color, using the minimum number of colors. The penalty for adjacent same-color vertices becomes the cost Hamiltonian.
• Scheduling: Assign jobs to time slots and machines to minimize total completion time or conflicts. Constraints become penalty terms in the Hamiltonian; the objective becomes the cost to minimize.
• Portfolio optimization: Select a subset of financial assets to maximize expected return while minimizing risk, subject to budget constraints. The quadratic risk-return trade-off maps naturally to a QUBO (Quadratic Unconstrained Binary Optimization) formulation.

The general pattern is always the same: encode the problem as a cost Hamiltonian $H_C$ whose ground state (or highest eigenstate) encodes the optimal solution, then use QAOA to prepare a quantum state with high overlap on that optimal state.

23.2 The QAOA Circuit

The QAOA circuit has an elegant, layered structure. It alternates between two types of unitary operations - the problem unitary (which encodes the cost function) and the mixing unitary (which explores the solution space) - applied $p$ times, where $p$ is the number of layers (also called the circuit depth). Each layer is parameterized by two angles, $\gamma_k$ and $\beta_k$, which are optimized classically.

Step 1: Initial State

QAOA begins by preparing an equal superposition over all $2^n$ computational basis states. This is achieved by applying a Hadamard gate to each of the $n$ qubits:

This initial state gives every possible solution an equal amplitude. The subsequent QAOA layers will reshape these amplitudes, concentrating probability on high-quality solutions.

Step 2: The Problem Unitary $U(H_C, \gamma)$

The problem unitary applies the cost Hamiltonian as a phase rotation:

For MaxCut, the cost Hamiltonian is a sum of commuting $Z_i Z_j$ terms (diagonal operators commute with each other), so the exponential factors cleanly:

up to a global phase. Each factor $e^{-i \gamma Z_i Z_j / 2}$ is implemented by an $R_{ZZ}(\gamma)$ gate - a two-qubit gate that applies a relative phase depending on whether qubits $i$ and $j$ agree or disagree. In QASM, this is written as rzz(gamma) q[i], q[j];. The problem unitary stamps the cost function into the phases of the quantum state: bitstrings with higher cut values accumulate different phases than those with lower cut values.

Step 3: The Mixing Unitary $U(H_B, \beta)$

The mixing unitary is generated by a "mixer" Hamiltonian $H_B$ that does not commute with $H_C$. The standard choice is the transverse-field mixer:

which gives the mixing unitary:

Since the individual $X_i$ operators commute with each other (they act on different qubits), the product factorizes into single-qubit $R_X$ rotations. The mixer's role is to create transitions between computational basis states - it "mixes" the amplitudes, allowing the algorithm to explore the solution space. Without the mixer, the problem unitary would only modify phases, never moving amplitude between different bitstrings.

Step 4: Layer the Unitaries

A depth-$p$ QAOA circuit applies $p$ alternating layers of problem and mixing unitaries:

The full parameter set is $(\gamma_1, \ldots, \gamma_p, \beta_1, \ldots, \beta_p)$ - a total of $2p$ real numbers. The quantum state $|\gamma, \beta\rangle$ depends on these parameters, and the goal is to choose them so that measuring the final state yields high-quality solutions with high probability.

Step 5: Measure and Optimize

After preparing $|\gamma, \beta\rangle$, we measure all qubits in the computational basis. Each measurement outcome is a bitstring $z$ representing a candidate partition. We evaluate the classical cost $C(z)$ for this bitstring. Repeating many times, we estimate the expected cost:

A classical optimizer (such as COBYLA, Nelder-Mead, or gradient-based methods) then adjusts the $2p$ parameters to maximize $\langle C \rangle$. This classical-quantum feedback loop continues until the parameters converge. The best bitstring observed during the entire optimization process is returned as the approximate solution.

The sandbox below implements a single-layer ($p = 1$) QAOA circuit for MaxCut on a triangle graph (3 vertices, 3 edges). Each edge contributes an rzz gate for the problem unitary, and each qubit gets an rx gate for the mixer. Try varying the angles to see how the output distribution changes.

For the triangle graph, the optimal MaxCut partitions cut exactly 2 out of 3 edges (you cannot cut all three edges of a triangle). The optimal bitstrings are 001, 010, 100, 110, 101, and 011 - any partition where the groups are not trivially all-zero or all-one. A well-tuned QAOA circuit should concentrate probability on these six bitstrings while suppressing 000 and 111.

23.3 From QAOA to the Adiabatic Theorem

QAOA is not just a clever heuristic - it has deep roots in one of quantum mechanics' most powerful results: the adiabatic theorem. Understanding this connection explains why QAOA works, when it fails, and how to improve it.

The Adiabatic Theorem

The adiabatic theorem, first formulated by Max Born and Vladimir Fock in 1928, states: if a quantum system starts in the ground state of a Hamiltonian $H(0)$, and the Hamiltonian is changed slowly enough to a final Hamiltonian $H(T)$, then the system will remain in the ground state of the instantaneous Hamiltonian throughout the evolution. "Slowly enough" means the evolution time $T$ must be large compared to the inverse of the minimum energy gap squared between the ground state and the first excited state:

where $\Delta_{\min} = \min_{0 \leq t \leq T} \left( E_1(t) - E_0(t) \right)$ is the minimum spectral gap along the entire evolution path.

Adiabatic Quantum Computation

Adiabatic quantum computation (AQC) exploits this theorem directly. The idea: start with a simple Hamiltonian $H_B$ whose ground state is easy to prepare (the equal superposition $|s\rangle$ is the ground state of $H_B = -\sum_i X_i$), and slowly interpolate to the problem Hamiltonian $H_C$ whose ground state encodes the solution:

If the interpolation is slow enough, the adiabatic theorem guarantees that the system ends in the ground state of $H_C$ - the optimal solution. The required evolution time depends on the minimum gap, which is problem-dependent and can be exponentially small for hard instances.

QAOA as Trotterized Adiabatic Evolution

Here is the key insight: QAOA can be viewed as a Trotterized (discretized) version of adiabatic evolution. In the Trotterization of the continuous-time evolution under $H(t)$, we break the evolution into $p$ discrete steps. At step $k$, the system evolves under $H_C$ for a short time $\gamma_k$ and then under $H_B$ for a short time $\beta_k$. This is exactly the QAOA circuit structure:

If we choose $\gamma_k$ and $\beta_k$ to mimic a linear adiabatic schedule - small at the beginning (mostly mixer) and large at the end (mostly problem) - the QAOA circuit approximates the continuous adiabatic evolution. As $p \to \infty$ with an appropriate choice of parameters, QAOA converges to exact adiabatic evolution and finds the optimal solution.

Why Variational Freedom Helps

A crucial advantage of QAOA over a fixed Trotter schedule: the parameters $\gamma_k$ and $\beta_k$ are variationally optimized, not fixed by a predetermined schedule. This means QAOA can compensate for the discretization error inherent in using only $p$ layers. Research has shown that the "Trotter errors" in QAOA can actually be beneficial - they act like counterdiabatic driving terms that suppress transitions out of the ground state, allowing QAOA to achieve better performance than a naive discretization of adiabatic evolution at the same circuit depth.

This also explains a practical observation: optimal QAOA parameters often follow a smooth, monotonic pattern. The $\gamma$ values tend to increase across layers (the problem Hamiltonian gets stronger) while the $\beta$ values tend to decrease (the mixer gets weaker) - precisely mimicking an adiabatic ramp. This pattern has been exploited to develop parameter initialization strategies that reduce the classical optimization burden.

The Gap Sets the Difficulty

The adiabatic perspective reveals why some optimization problems are harder than others for QAOA. The minimum spectral gap $\Delta_{\min}$ along the interpolation path determines how many QAOA layers are needed. Problems with exponentially small gaps require exponentially many layers - and thus exponentially long circuits - to solve exactly. This is consistent with computational complexity theory: if QAOA could efficiently solve NP-hard problems with polynomial-depth circuits, it would imply P = NP.

23.4 Solving MaxCut with QAOA on a Simulator

Let us now put QAOA into practice. We will solve MaxCut on a small graph, exploring how the parameters $\gamma$ and $\beta$ affect the quality of the solution. The simulation below implements a depth-1 QAOA circuit for MaxCut on a 4-vertex path graph with edges $(0,1)$, $(1,2)$, and $(2,3)$. The optimal MaxCut for this graph cuts all 3 edges, achieved by the bitstrings 0101 and 1010.

Interactive Parameter Exploration

Use the sliders below to adjust the QAOA parameters $\gamma$ and $\beta$. Watch how the measurement distribution changes as you sweep through different parameter values. The goal is to find parameters that concentrate probability on the optimal bitstrings.

As you explore the parameter landscape, notice several features. When $\gamma = 0$, the problem unitary is the identity and you get a uniform distribution over all 16 bitstrings. When $\beta = 0$, the mixer is the identity and the problem unitary only adds phases (which do not affect measurement probabilities after a single layer). The interesting behavior emerges when both parameters are nonzero. Try values near $\gamma \approx 0.6$ and $\beta \approx 1.0$ - you should see the optimal bitstrings 0101 and 1010 begin to dominate the distribution.

The Optimization Landscape

The function $\langle C \rangle(\gamma, \beta)$ defines a two-dimensional landscape for depth-1 QAOA. This landscape has the following properties:

• It is periodic in both $\gamma$ (period $2\pi$) and $\beta$ (period $\pi$), because the $R_{ZZ}$ and $R_X$ gates are periodic in their angles.
• It can have multiple local maxima, making the classical optimization non-trivial. However, for small graphs, the landscape is smooth and the global optimum is easy to find.
• For depth-1 QAOA on MaxCut, analytical formulas exist for the expected cost as a function of $\gamma$ and $\beta$, enabling exact optimization without sampling noise.

Exercise: Build a QAOA Circuit for a Square Graph

Now it is your turn. Construct a depth-1 QAOA circuit for MaxCut on a 4-vertex cycle (square) graph with edges $(0,1)$, $(1,2)$, $(2,3)$, and $(3,0)$. The optimal MaxCut for a square cuts all 4 edges, achieved by the bitstrings 0101 and 1010. Use $\gamma = \pi/4$ and $\beta = \pi/4$ as starting parameters.

Scaling Up: Deeper Circuits

Depth-1 QAOA provides a limited approximation. For 3-regular graphs (a class that includes the triangle), Farhi et al. proved that depth-1 QAOA achieves a worst-case approximation ratio (ratio of expected cut to optimal cut) of at least 0.6924 - provably above the trivial 0.5 ratio of random guessing, but below the 0.878 ratio guaranteed by the best known classical algorithm (the Goemans-Williamson semidefinite programming relaxation) on general graphs.

Increasing $p$ improves the approximation ratio. At depth $p = 2$, the QAOA state depends on 4 parameters ($\gamma_1, \gamma_2, \beta_1, \beta_2$), and the circuit applies two rounds of problem and mixing unitaries. Each additional layer adds more parameters and more expressive power, but also increases the circuit depth and the difficulty of classical parameter optimization. In practice, QAOA circuits with $p = 5$ to $p = 20$ are explored on near-term devices, with parameter initialization strategies (such as linear ramp schedules inspired by the adiabatic connection) helping the classical optimizer converge.

23.5 Quantum Annealing: D-Wave's Alternative

While QAOA runs on gate-based quantum computers, there is an entirely different approach to quantum optimization: quantum annealing. The Canadian company D-Wave Systems has built a series of special-purpose quantum processors based on this principle, with their latest systems containing over 5,000 qubits - far more than any gate-based quantum computer, though with a much more restricted set of operations.

How Quantum Annealing Works

Quantum annealing is a physical implementation of adiabatic quantum computation (the same principle that inspired QAOA). The processor implements a time-dependent Hamiltonian: