Project: QAOA at Scale

The Quantum Approximate Optimization Algorithm (QAOA) attacks combinatorial problems by interleaving a problem-specific cost Hamiltonian with a generic mixing Hamiltonian, tuning the angles to push amplitude toward high-quality solutions. This capstone builds a full QAOA layer for MaxCut and asks you to assemble the cost gadget, mixer, and measurement correctly — the same template that "scales up" to deeper circuits and larger graphs.

MaxCut and the cost Hamiltonian

Given a graph $G = (V, E)$ , MaxCut partitions the vertices into two sets to maximize the number of edges crossing the partition. Encoding each vertex as a qubit, the cut value of a bitstring $z$ is

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

Promoting $z_k \to Z_k$ gives the cost Hamiltonian $H_C = \sum_{(i,j)\in E} \tfrac{1}{2}(I - Z_iZ_j)$ , whose largest eigenvalue is the maximum cut.

One QAOA layer

A depth- $p$ QAOA applies $p$ alternating layers to the uniform superposition $|+\rangle^{\otimes n}$ :

|\boldsymbol{\gamma}, \boldsymbol{\beta}\rangle = \prod_{k=1}^{p} e^{-i\beta_k H_M}\, e^{-i\gamma_k H_C}\; H^{\otimes n}|0\rangle^{\otimes n},

with mixer $H_M = \sum_q X_q$ . For $p = 1$ there is a single pair $(\gamma, \beta)$ . Each cost term $e^{-i\gamma Z_iZ_j}$ compiles to the gadget

\texttt{CX}(i,j);\ \texttt{RZ}(2\gamma, j);\ \texttt{CX}(i,j),

and each mixer term is $\texttt{RX}(2\beta, q)$ .

The triangle instance

For the triangle $K_3$ every pair of vertices is connected. The best cut isolates one vertex, cutting $2$ of the $3$ edges — the bitstrings $100, 010, 001$ and their complements $011, 101, 110$ are all optimal. A well-tuned single layer concentrates measurement probability on exactly these six strings and away from the two uncut configurations $000$ and $111$ .

Try it

Build the $p = 1$ QAOA circuit for the triangle with $\gamma = \pi/4$ , $\beta = \pi/8$ , and measure. The grader checks the output distribution; you should see the two non-cut strings $000$ and $111$ suppressed relative to the six optimal cuts.

Run your code to see the quantum state.