QAOA for Max-Cut

The Quantum Approximate Optimization Algorithm (QAOA) finds good cuts of a graph by alternating a problem (cost) layer with a mixer layer and classically tuning the per-layer angles. It is the canonical example of a variational quantum algorithm applied to combinatorial optimization.

The problem it solves

Given a graph, partition its vertices into two sets so that as many edges as possible cross the partition — this is Max-Cut. It is NP-hard: known exact classical algorithms grow exponentially with the number of vertices in the worst case. Max-Cut looks abstract, but it is the kernel of many practical tasks such as clustering, circuit layout, and network partitioning.

In QAOA each vertex maps to a qubit. Whether each bit of the string is 0 or 1 decides which side that vertex falls on; the cut is read directly from the measured bitstring. Our goal is to make the quantum circuit concentrate high probability on the bitstrings that correspond to high-quality cuts.

Encoding the problem into a Hamiltonian

The first step of QAOA is to translate "maximize the number of cut edges" into "minimize an energy". For each edge (i, j) we introduce a term 0.5·(ZiZj − 1). The Pauli Z operator gives +1 on bit 0 and −1 on bit 1, so:

• When both endpoints are on the same side (both 0 or both 1), ZiZj = +1 and the term is 0 — this edge is not cut and contributes nothing.
• When the endpoints are on opposite sides, ZiZj = −1 and the term is −1 — this edge is cut.

Summing over all edges gives the cost Hamiltonian HC. Its ground-state energy equals −(maximum number of cut edges). So "maximize the cut" turns into "minimize ⟨H_C⟩" — a clear target a quantum computer can aim at.

The variational ansatz — two alternating unitaries

QAOA starts from a uniform superposition of all bitstrings (one layer of Hadamards), then alternately applies two kinds of unitary, for p layers total:

One "cost + mixer" layer is parameterized by a pair of angles (γ, β). p layers thus have 2p parameters. A classical optimizer repeatedly tunes these angles to make the measured ⟨H_C⟩ as low as possible. This is what variational means: the quantum circuit prepares and measures the trial state, while the classical loop searches for better angles.

Why it works — the connection to adiabatic evolution

Why does this alternating structure approach the answer? With a suitable angle sequence and a large enough number of layers p, QAOA can be understood as a discretized approximation of the adiabatic evolution path: prepare the system in the easy-to-make ground state of the mixer Hamiltonian (the uniform superposition), then gradually hand the Hamiltonian over from the mixer term to the cost term, so the system tends to stay near its instantaneous ground state and approach the ground state of HC — the optimal cut. The QAOA angle sequence (γ₁, β₁, …, γ_p, β_p) can be seen as one discretized sampling of this adiabatic path. This connection offers intuition, but performance at small p still depends mainly on angle optimization and the structure of the problem.

The key point is that QAOA does not require slowness. Even for small p, optimized angles often achieve approximation ratios far better than random guessing. Because the circuit is shallow at small p, QAOA has been regarded as a candidate algorithm suited to NISQ hardware; in practice, however, its performance still depends strongly on noise, connectivity, compilation overhead, and the sampling budget.

What it is good at — and what it isn't

• It gives an approximate solution, not a proven optimum. QAOA outputs a "good" cut with no guarantee of global optimality and usually no certificate of optimality.
• Shallow depth limits expressive power. At a fixed small p there is a provable upper bound on the achievable approximation ratio; approaching the optimum often needs larger p, and deeper circuits accumulate more noise. There is a real tension between depth and quality.
• The classical competition is strong. For Max-Cut, classical approximation algorithms like the Goemans–Williamson semidefinite program perform excellently and are well battle-tested. Demonstrating a clear quantum advantage for QAOA at practical scale remains an open problem.
• The optimization itself can be hard. The angle landscape has barren plateaus and many local minima that the outer classical optimizer can get stuck in — a shared pain point of variational algorithms.

The algorithm, step by step

1. Encode the target problem (here, Max-Cut) into a cost Hamiltonian HC.
2. Prepare a uniform superposition of all bitstrings with Hadamard gates.
3. Alternately apply the cost unitary (angle γ_l) and the mixer unitary (angle β_l), for p layers.
4. Measure and estimate ⟨H_C⟩; hand it to the classical optimizer.
5. The optimizer updates all 2p angles, repeating the above until convergence.
6. Sample the circuit repeatedly at the optimal angles and read off the most probable bitstring as the recommended cut.

Seeing it in code

First encode the graph into the cost Hamiltonian. Note that 0.5 * (spin.z(i) * spin.z(j) - 1.0) is exactly the term above: it is −1 when the endpoints are on opposite sides, counting one cut edge.

import qalgora
from qalgora import spin

# square graph: 4 nodes, 4 edges
edges = [(0, 1), (1, 2), (2, 3), (3, 0)]
n_qubits = 4

# cost Hamiltonian: sum over edges of 0.5*(Z_i Z_j - 1)
cost = 0
for i, j in edges:
    cost += 0.5 * (spin.z(i) * spin.z(j) - 1.0)

The circuit ansatz carries the structure above directly into code: a Hadamard on every qubit prepares the uniform superposition; the inner x.ctrl … rz(γ) … x.ctrl sandwich is the cost unitary applied edge by edge (engraving a cost-dependent phase on each edge); the closing rx(2·β) on each qubit is the mixer unitary. layers is exactly the number of layers p.

Angle conventions. We take Rz(θ) = exp(−iθZ/2) and Rx(θ) = exp(−iθX/2). Under the per-edge cost term 0.5·(ZiZj − 1), the CNOT–Rz–CNOT sandwich realizes exp(−iγ·0.5·ZiZj) with the cost-layer rotation rz(γ) (not rz(2γ)), while the mixer is rx(2β) because exp(−iβX) = rx(2β).

@qalgora.kernel
def qaoa(gammas: list[float], betas: list[float], layers: int):
    q = qalgora.qvector(4)
    for i in range(4):
        h(q[i])                           # uniform superposition
    for l in range(layers):
        for i, j in [(0, 1), (1, 2), (2, 3), (3, 0)]:
            x.ctrl(q[i], q[j])
            rz(gammas[l], q[j])           # cost layer: Rz(gamma) for 0.5(Z_iZ_j-1)
            x.ctrl(q[i], q[j])
        for i in range(4):
            rx(2.0 * betas[l], q[i])       # mixer layer

Finally the outer classical optimization. objective sends the current angles into the circuit and returns the expectation value of cost — that is, the ⟨H_C⟩ we want to minimize; COBYLA is a gradient-free optimizer that searches for better (γ, β). After convergence we sample once more and read off the most probable cut.

layers = 2
optimizer = qalgora.optimizers.COBYLA()

def objective(params):
    gammas, betas = params[:layers], params[layers:]
    return qalgora.observe(qaoa, cost, gammas, betas, layers).expectation()

energy, params = optimizer.optimize(dimensions=2 * layers, function=objective)
print("best cut value:", -energy)

# sample the optimized circuit to read out the partition
counts = qalgora.sample(qaoa, params[:layers], params[layers:], layers)
print("most probable cut:", counts.most_probable())

References

• E. Farhi, J. Goldstone, S. Gutmann, "A quantum approximate optimization algorithm," (2014). arXiv:1411.4028