QAOA for MaxCut: Solving Real Optimization Problems on Qubits

Optimization is where quantum computing meets the day job: routing delivery vans, scheduling shifts, balancing loads, laying out chips. The Quantum Approximate Optimization Algorithm, QAOA, is the leading near-term approach, and MaxCut is its model problem. This walkthrough runs a real QAOA circuit and watches it concentrate on the best answer, and it is a one-click template in the ZKSF console.

The problem: MaxCut, and why it is everywhere

MaxCut asks a simple question with hard consequences. Given a network of nodes connected by links, split the nodes into two groups so that the number of links running between the groups is as large as possible. That abstract question is a stand-in for a whole family of real ones: partitioning a circuit to minimise wires that cross, splitting a workload across two machines, clustering data, finding the ground state of a magnet. MaxCut is NP-hard, so as the network grows, checking every split becomes hopeless.

Our example is a four-node ring, nodes 0-1-2-3 joined in a loop. The best cut alternates around the ring, group A on the even nodes and group B on the odd ones, which cuts all four links. As bitstrings, the two optimal answers are 0101 and 1010.

The circuit: cost and mixer layers

QAOA builds a circuit from two alternating layers. The cost layer encodes the problem: for every link it applies a ZZ rotation that rewards cutting that link. The mixer layer, a rotation on every qubit, lets the amplitudes explore. Two angles control how hard each layer pushes, and tuning them steers probability towards good cuts. We tuned the two angles for this ring so the optimal partitions stand out clearly.

OPENQASM 2.0;
include "qelib1.inc";
qreg q[4];
creg c[4];
h q[0]; h q[1]; h q[2]; h q[3];
// cost layer: a ZZ rotation on each of the four ring edges
cx q[0],q[1]; rz(2.3) q[1]; cx q[0],q[1];
cx q[1],q[2]; rz(2.3) q[2]; cx q[1],q[2];
cx q[2],q[3]; rz(2.3) q[3]; cx q[2],q[3];
cx q[3],q[0]; rz(2.3) q[0]; cx q[3],q[0];
// mixer layer: an Rx rotation on every qubit
rx(0.86) q[0]; rx(0.86) q[1]; rx(0.86) q[2]; rx(0.86) q[3];
measure q -> c;

In the diagram, the leading Hadamards put the register into an equal superposition of all sixteen possible partitions. Each cost-layer edge shows as a pair of CNOTs around a blue Rz rotation, the standard way to write a ZZ interaction. The row of blue Rx boxes near the end is the mixer.

Running it live: the optimal partitions win

We ran the circuit on ZKSF at 1,000 shots on the exact statevector engine. The two optimal cuts took the lion's share of the outcomes:

counts (top): {"1010": 300, "0101": 259,
               "0011": 81, "1100": 75,
               "0110": 74, "1001": 61,
               "0000": 16, "1111": 29}
error_info:   {"method": "exact statevector",
               "truncation_error": 0.0, "shots": 1000}

Read the tiers. The two optimal alternating partitions, 1010 and 0101, together took 559 of the 1,000 shots, about 56 percent. The four next-best cuts, which separate the ring into unequal pieces, split most of the rest. The two worst answers, 0000 and 1111, which cut nothing at all, drew fewer than 5 percent between them. A single shallow QAOA layer has pushed the measurement onto the good cuts. The run carries a public ZCC-v0.1 certificate.

From four nodes to a hundred

Four qubits fit an exact simulator, so here QAOA is a demonstration rather than a necessity. The point is that the same circuit shape scales. On a hundred-node problem the state no longer fits any classical statevector, and this is where ZKSF earns its keep: the router sends a structured, low-entanglement QAOA circuit to a tensor-network engine that reaches past a hundred qubits, and every approximate answer comes with a certified error bound. See our 100-qubit QAOA benchmark for a run at that scale.

Try it yourself

Choose QAOA MaxCut in the console and run it. Then sweep the two angles, the Rz cost angle and the Rx mixer angle, and watch the balance between good and bad cuts shift: this is the tuning loop at the heart of every variational quantum algorithm. For chemistry's version of the same idea, see the VQE hydrogen walkthrough.