Checkpoint: Solve Max-Cut

This checkpoint asks you to assemble a complete QAOA circuit for a new graph — from blank starter code — and verify that the output distribution concentrates on the optimal cuts. No scaffolding is provided: you apply every gate yourself.

The problem graph

Three nodes connected in a line (a path graph $P_3$ ):

0 - 1 - 2

Edge set $E = \{(0,1),\,(1,2)\}$ . Each qubit represents a vertex; $|0\rangle$ places a vertex in partition $S$ and $|1\rangle$ places it in $\bar{S}$ . An edge contributes 1 to the cut value when its endpoints are in opposite partitions.

Optimal cuts

The maximum cut value for $P_3$ is 2 (both edges are cut). The two bitstrings that achieve this are $010$ (vertex 1 alone in $\bar{S}$ ) and $101$ (vertices 0 and 2 alone in $\bar{S}$ ). Every other assignment cuts at most one edge.

QAOA $p = 1$ recipe

The $p = 1$ QAOA ansatz is

|\gamma, \beta\rangle = U_B(\beta)\,U_C(\gamma)\,H^{\otimes 3}\,|000\rangle,

where

U_C(\gamma) = e^{-i\gamma H_C}, \qquad H_C = \sum_{(i,j)\in E} \tfrac{1}{2}(I - Z_i Z_j),

and the transverse-field mixer is

U_B(\beta) = e^{-i\beta H_B}, \qquad H_B = X_0 + X_1 + X_2.

Compiling the cost unitary

The $ZZ$ rotation for one edge $(i,j)$ decomposes as

e^{-i(\gamma/2)Z_i Z_j} = \mathrm{CX}_{ij}\;\cdot\;R_z(\gamma)_j\;\cdot\;\mathrm{CX}_{ij}.

Because $H_C$ contains a factor of $\tfrac{1}{2}$ and $R_z(\theta) = e^{-i(\theta/2)Z}$ , the angle you pass to $R_z$ is $2\gamma$ .

Apply the CNOT-RZ-CNOT block for edge $(0,1)$ and then for edge $(1,2)$ .

Compiling the mixer

Each term $e^{-i\beta X_q}$ is a single rotation:

e^{-i\beta X_q} = R_x(2\beta)_q.

The factor of $2$ arises from the convention $R_x(\theta) = e^{-i(\theta/2)X}$ .

Decoding the result

After measurement, the most frequent bitstrings tell you the best cut found. Bitstring $b_0 b_1 b_2$ encodes the partition: vertex $q$ goes to $\bar{S}$ if $b_q = 1$ . For $010$ the partition is $\{0,2\} \mid \{1\}$ ; for $101$ it is $\{1\} \mid \{0,2\}$ — the same cut by symmetry.

The approximation ratio $\alpha$ for a single run is $C_\text{best} / C_\text{max}$ . Here $C_\text{max} = 2$ , and if the QAOA output is one of the optimal strings then $\alpha = 1$ .

Try it

Build the complete QAOA circuit for $P_3$ with the fixed angles $\gamma = 3\pi/4$ , $\beta = \pi/8$ . The grader checks the output distribution, so an empty or incomplete circuit will fail — the angles must actually shift probability onto $|010\rangle$ and $|101\rangle$ .

Run your code to see the quantum state.