The QAOA Circuit

The Quantum Approximate Optimization Algorithm (QAOA) is a variational hybrid algorithm for combinatorial optimization. Its quantum circuit alternates between two parameterized layers: a cost unitary that encodes the objective function and a mixer unitary that explores the solution space. Even a single layer ( $p = 1$ ) can capture a non-trivial approximation ratio for problems like Max-Cut.

The QAOA structure

Given a cost function $C(z)$ over bit strings $z \in \{0,1\}^n$ , the corresponding cost Hamiltonian is diagonal in the computational basis with eigenvalues $C(z)$ . QAOA with $p$ layers prepares the state

|\gamma, \beta\rangle = \prod_{j=1}^{p} e^{-i\beta_j B}\, e^{-i\gamma_j C} \,|+\rangle^{\otimes n},

starting from the uniform superposition $|+\rangle^{\otimes n}$ . Measuring this state and averaging many outcomes gives an estimate of $\langle C \rangle$ ; a classical outer loop optimizes $(\gamma, \beta)$ to maximize that estimate.

Max-Cut on a two-node graph

The simplest non-trivial example is Max-Cut on a graph with two nodes connected by a single edge. The cut value for a bit string $z_0 z_1$ is

C(z_0, z_1) = \tfrac{1}{2}\bigl(1 - (-1)^{z_0 \oplus z_1}\bigr),

which equals $1$ when the nodes are on opposite sides ( $z_0 \neq z_1$ ) and $0$ otherwise. In Pauli language,

C = \tfrac{1}{2}(I - Z_0 Z_1).

The cost unitary

The phase separation operator is

U_C(\gamma) = e^{-i\gamma C} = e^{-i\gamma/2}\, e^{i\gamma Z_0 Z_1/2}.

The global phase $e^{-i\gamma/2}$ is unobservable. The $Z_0 Z_1$ coupling is implemented with a standard entangling gadget:

e^{i\theta Z_0 Z_1} = \mathrm{CX}_{01}\;\cdot\; R_z(-2\theta)_1 \;\cdot\; \mathrm{CX}_{01}.

Setting $\theta = \gamma/2$ gives the sequence $\mathrm{CX}(0,1)$ , $R_z(-\gamma)$ on qubit 1, $\mathrm{CX}(0,1)$ .

The mixer unitary

The standard mixer is the transverse-field Hamiltonian $B = \sum_j X_j$ . Its unitary factorizes as

U_B(\beta) = e^{-i\beta B} = \bigotimes_{j} e^{-i\beta X_j} = \bigotimes_{j} R_x(2\beta)_j.

Each qubit receives an independent $R_x(2\beta)$ rotation.

Full one-layer circuit

Putting it together the $p = 1$ QAOA circuit for this graph is:

|\gamma,\beta\rangle = U_B(\beta)\,U_C(\gamma)\,H^{\otimes 2}\,|00\rangle.

Written gate by gate:

$H$ on qubit 0, $H$ on qubit 1.
$\mathrm{CX}(0,1)$ , $R_z(-\gamma)$ on qubit 1, $\mathrm{CX}(0,1)$ .
$R_x(2\beta)$ on qubit 0, $R_x(2\beta)$ on qubit 1.

Try it

Complete the circuit for fixed angles $\gamma = \pi/4$ and $\beta = \pi/4$ . The grader checks the full statevector, so both the cost and mixer layers must be correct.

Run your code to see the quantum state.

After a correct run the statevector will have equal-magnitude amplitudes on all four basis states, but the phases differ: the cut states $|01\rangle$ and $|10\rangle$ accumulate a different relative phase from the cost unitary than $|00\rangle$ and $|11\rangle$ do. At these angles all four probabilities are $0.25$ ; tuning $\gamma$ and $\beta$ with a classical optimizer (the outer QAOA loop) would tilt the balance toward the optimal cut states.