QAOA: Quantum Approximate Optimization

QAOA: Quantum Approximate Optimization Algorithm

The Quantum Approximate Optimization Algorithm (QAOA), introduced by Farhi, Goldstone, and Gutmann (2014), is a leading candidate for demonstrating quantum advantage on combinatorial optimization problems.

The MaxCut Problem

Given a graph $G = (V, E)$, MaxCut asks for a partition of vertices into two sets $S$ and $\bar{S}$ that maximizes the number of edges crossing between them.

MaxCut is NP-hard in general, but QAOA provides a systematic quantum approximation scheme that improves with the number of layers $p$.

Cost Hamiltonian

For each edge $(u, v)$, the cost Hamiltonian encodes a +1 energy whenever the edge is cut:

$C = \sum_{(u,v) \in E} \frac{1 - Z_u Z_v}{2}$

When qubits $u$ and $v$ are in different states ($Z_u Z_v = -1$), this contributes 1; when in the same state ($Z_u Z_v = +1$), it contributes 0. So $\langle C \rangle$ is exactly the expected number of cut edges.

The QAOA Circuit

Starting from the uniform superposition $|+\rangle^{\otimes n}$ (all vertices equally in both sets), QAOA applies $p$ alternating layers:

$|\gamma, \beta\rangle = e^{-i\beta_p B}\, e^{-i\gamma_p C} \cdots e^{-i\beta_1 B}\, e^{-i\gamma_1 C}\, |+\rangle^{\otimes n}$

• Phase separator $e^{-i\gamma C}$: applies phase $e^{-i\gamma}$ to basis states where edge $(u,v)$ is cut
• Mixer $e^{-i\beta B}$ where $B = \sum_u X_u$: applies $R_x(2\beta)$ independently to each qubit, exploring the superposition

As $p \to \infty$ with optimal parameters, QAOA converges to the exact MaxCut solution.

2-Node Example (p=1)

For the simplest graph with one edge $(0, 1)$, the MaxCut optimum is 1 (the edge is always cut when the two nodes are in opposite sets).

The QAOA state-vector evolution for basis states $|00\rangle, |01\rangle, |10\rangle, |11\rangle$:

Initial: $\tfrac{1}{2}(|00\rangle + |01\rangle + |10\rangle + |11\rangle)$

After phase separator (cost = 1 for $|01\rangle$ and $|10\rangle$, cost = 0 for $|00\rangle$ and $|11\rangle$):

$\tfrac{1}{2}\bigl(|00\rangle + e^{-i\gamma}|01\rangle + e^{-i\gamma}|10\rangle + |11\rangle\bigr)$

After mixer $R_x(2\beta) \otimes R_x(2\beta)$: each qubit independently mixed via:

$R_x(2\beta) = \begin{pmatrix}\cos\beta & -i\sin\beta \\ -i\sin\beta & \cos\beta\end{pmatrix}$

Optimal parameters: $\gamma = \pi/2$, $\beta = \pi/8$ achieve $\langle C \rangle = 1$ — the exact maximum cut!

Why QAOA Finds the Optimum Here

At $\gamma = \pi/2$ the phase separator applies $e^{-i\pi/2} = -i$ to the cut states, creating destructive interference for the non-cut states $|00\rangle$ and $|11\rangle$ after the mixer. At $\beta = \pi/8$ the mixer balances the interference precisely so that all probability flows into $|01\rangle$ and $|10\rangle$.

Your Task

Implement:

1. qaoa_maxcut(gamma, beta) — simulate the p=1 QAOA circuit on a 2-node graph with edge (0,1), returning the expected cut value $\langle C \rangle = P(|01\rangle) + P(|10\rangle)$
2. qaoa_optimize() — grid-search over $\gamma \in [0, \pi)$ and $\beta \in [0, \pi/2)$ (20 steps each) to find the maximum $\langle C \rangle$, returned rounded to 4 decimal places