Max-Cut with QAOA

Previous lessons built the cost unitary and the mixing unitary in isolation. This lesson assembles them into a working p = 1 QAOA circuit and runs it on a concrete example: a three-node triangle graph.

The triangle instance

Let the graph have vertices $\{0, 1, 2\}$ and edges $E = \{(0,1),\,(1,2),\,(0,2)\}$ . Each vertex becomes one qubit: $|0\rangle$ places a vertex in partition $S$ and $|1\rangle$ places it in $\bar{S}$ . An edge $(i,j)$ contributes $+1$ to the cut value when the two endpoints land in different partitions, i.e. when $z_i \neq z_j$ .

The cost function for a bitstring $\mathbf{z} \in \{0,1\}^3$ is

C(\mathbf{z}) = \sum_{(i,j)\in E} \frac{1 - (-1)^{z_i + z_j}}{2}.

For the triangle, the maximum cut value is 2 (any single vertex alone on one side, the other two on the other side). The six optimal bitstrings are $001, 010, 011, 100, 101, 110$ . The two all-same strings $000$ and $111$ give cut value 0.

QAOA p = 1 structure

A single QAOA layer has three stages.

Stage 1: Initialisation. Apply $H$ to every qubit to create the uniform superposition over all $2^3 = 8$ bitstrings:

|\psi_0\rangle = H^{\otimes 3}|000\rangle = \frac{1}{2\sqrt{2}}\sum_{\mathbf{z}\in\{0,1\}^3}|\mathbf{z}\rangle.

Stage 2: Cost unitary. For each edge $(i,j)$ apply the two-qubit entangling block that implements $e^{i\gamma Z_i Z_j}$ (up to a global phase from the full $e^{-i\gamma H_C}$ ):

\text{CNOT}(i,j) \;\; R_z(-2\gamma,\, j) \;\; \text{CNOT}(i,j).

The derivation uses the conjugation identity $\text{CNOT}(i,j)\, Z_j\, \text{CNOT}(i,j) = Z_i Z_j$ and the fact that $e^{i\gamma Z} = R_z(-2\gamma)$ (since $R_z(\theta) = e^{-i\theta Z/2}$ , so $R_z(-2\gamma) = e^{i\gamma Z}$ ). Applying this block for every edge implements $e^{-i\gamma H_C}$ (up to global phase) where

H_C = \sum_{(i,j)\in E} \frac{1 - Z_i Z_j}{2}.

The eigenvalue of $H_C$ on bitstring $|\mathbf{z}\rangle$ is exactly $C(\mathbf{z})$ , so states with more cut edges acquire a larger phase rotation — this is how QAOA encodes the objective.

Stage 3: Mixer. Apply $R_x(2\beta)$ to each qubit:

e^{-i\beta H_M} = \bigotimes_{i=0}^{2} R_x(2\beta,\, i), \qquad H_M = \sum_i X_i.

The mixer moves amplitude between bitstrings in a controlled way, amplifying the high-cut states through interference.

What to expect from the output

With the angles above the simulator produces a distribution where all six bitstrings with cut value 2 share the probability mass equally (by the symmetry of the triangle), and the zero-cut strings $|000\rangle$ and $|111\rangle$ are strongly suppressed. A classical random partition achieves only 75% probability of a near-optimal assignment in the same setup, so QAOA already does better with a single layer.

Try it

Complete the cost-unitary block by adding the CNOT-RZ-CNOT pattern for each of the three edges. The mixer and measurement are already in place. The grader checks the output distribution, so leaving the cost-unitary lines empty will fail — the circuit must actually phase-encode the cut objective before the mixer can do its job.

Run your code to see the quantum state.