QAOA for Max-Cut: Turn a Graph into a Quantum Circuit

Take a triangle: three vertices, with an edge between every pair. Split its vertices into two groups, and count edges whose endpoints land in different groups. No matter how you split it, at most two of the three edges cross. This tiny puzzle is a useful way to see how the Quantum Approximate Optimization Algorithm, or QAOA, turns a graph problem into a sequence of quantum gates, then uses measurements to hunt for a good answer.

From a graph to a cost Hamiltonian

Represent each vertex with one qubit. Measuring it gives a bit, either 0 or 1, which says which side of the cut that vertex belongs to. For an edge between vertices u and v, the edge contributes one to the cut if their bits differ, and zero if they match.

Quantum circuits use Pauli-Z operators to express this test. Since a qubit's Z value is +1 for bit 0 and -1 for bit 1, the edge's cut contribution is (1 - ZᵤZᵥ) / 2. Equal bits give a product of +1 and a contribution of zero; different bits give -1 and a contribution of one.

For the triangle, add one term per edge:

C = (1 - Z₀Z₁)/2 + (1 - Z₁Z₂)/2 + (1 - Z₀Z₂)/2

This operator, called the cost Hamiltonian, assigns each measured bitstring its cut score. In code, the same idea is simply to loop over edges and count how many endpoint bits differ. The Hamiltonian is the bridge between that familiar scoring rule and quantum operations.

Alternating cost and mixer layers

QAOA prepares a trial state, then alternates two kinds of operations. First, the cost unitary applies a phase based on the score encoded by C: U_C(γ) = exp(-i γ C). The parameter γ controls how strongly those score-dependent phases affect the state. For a graph cost made of pairwise Z terms, this operation can be built from gates acting on the qubits at each edge.

Next comes the mixer, U_B(β) = exp(-i β B), where B = X₀ + X₁ + ... and each X acts on one qubit. The mixer rotates qubits between the two bit values, helping the circuit explore different assignments. Start with every qubit in an equal superposition using Hadamard gates, then apply a cost layer and a mixer layer. Repeat this pair p times. The integer p is the circuit depth parameter: more layers can represent richer patterns, but also mean a deeper circuit.

For our triangle, a single layer uses three qubits, three edge interactions in the cost operation, and one mixer rotation per qubit. The angles γ and β are not chosen by the quantum circuit itself. A classical optimizer proposes them; the quantum processor samples the resulting circuit; and the measured scores guide the next proposal. This loop is a hybrid algorithm.

Optimize, measure, and score

After choosing angles, measure the qubits many times. Each shot produces a bitstring such as 010, which assigns vertices 0 and 2 to one side and vertex 1 to the other. Its score is two: edges 0-1 and 1-2 cross, while 0-2 does not. The triangle's maximum is known to be two, so this sample happens to be optimal.

In a real run, the optimizer usually maximizes the average score observed across shots. It may use a derivative-free method or another classical optimization routine. Once the angles look promising, inspect the distribution of bitstrings and calculate each one's score directly from the original edge list. Return the highest-scoring observed assignment, not just the average objective value.

Here is the classical scoring step, which is useful whether samples came from a simulator or hardware:

def cut_score(bitstring, edges):
    bits = [int(bit) for bit in bitstring]
    return sum(bits[u] != bits[v] for u, v in edges)

edges = [(0, 1), (1, 2), (0, 2)]
print(cut_score("010", edges))  # 2

Keep the bit ordering consistent with the framework that produced the measured string. Some tools display multi-qubit outcomes in an order that differs from the order used to label circuit qubits, so verify the mapping before scoring.

What QAOA can and cannot promise

QAOA gives programmers a concrete workflow: encode a score, build parameterized layers, sample, and evaluate candidates. It does not guarantee that a shallow circuit will find the optimum, or that a quantum device will beat a classical Max-Cut solver. Parameter tuning can be difficult, and shot noise makes objective estimates imperfect. Hardware noise and limited connectivity can add errors or require extra gates.

The triangle is small enough to solve by inspection, not a quantum advantage demonstration. Its value is that every piece of the workflow is visible. On larger graphs, the same encoding applies, but useful performance depends on graph structure, circuit depth, optimizer behavior, measurement budget, and hardware quality. Treat QAOA as a practical way to explore quantum optimization, then benchmark it against strong classical methods on the same instances.