QAOA for MaxCut
The Quantum Approximate Optimization Algorithm applied to graph MaxCut, its canonical benchmark problem.
MaxCut
Given an undirected graph with vertex set V and edge set E, a cut partitions V into two sets. The cut value is the number of edges crossing the partition. MaxCut asks for the partition of maximum cut value; it is NP-hard in general. Assigning each vertex a spin z_i in {-1,+1}, the cut value is C = sum over edges (i,j) of (1 - z_i z_j)/2.
The QAOA construction
Encode each vertex as a qubit. The cost Hamiltonian is H_C = sum over edges (1 - Z_i Z_j)/2, diagonal in the computational basis with eigenvalue equal to the cut value. The mixing Hamiltonian is H_B = sum_i X_i. QAOA of depth p prepares:
|gamma, beta> = exp(-i beta_p H_B) exp(-i gamma_p H_C) ... exp(-i beta_1 H_B) exp(-i gamma_1 H_C) H^{on all} |0...0>, starting from the uniform superposition. The 2p angles gamma and beta are variational parameters.
The loop
- Prepare |gamma,beta> on hardware.
- Measure in the Z basis and evaluate the average cut value
. - A classical optimizer updates the angles to raise
. - Repeat until convergence; sample the final state for high-cut bitstrings.
Circuit primitives
Each cost term exp(-i gamma (1 - Z_i Z_j)/2) is a two-qubit ZZ rotation implemented with two CNOTs and an RZ gate. Each mixer term is a single-qubit RX(2 beta). Depth-p QAOA therefore uses O(p |E|) two-qubit gates, matching the graph structure.
Performance and limits
At p = 1 on 3-regular graphs, QAOA guarantees a known approximation ratio; increasing p provably converges to the optimum as p grows, since QAOA can approximate adiabatic evolution. In practice noise, barren-plateau-like flatness, and classical optimizer difficulty cap achievable p. Warm starts and structured angle schedules improve results; see QAOA parameter optimization.