QAOA on a small graph

Cost and mixer layers for MaxCut, read off the cut from the histogram, and understand the depth p.

You will learn to

Write the MaxCut cost Hamiltonian for a triangle.
Identify cost (rzz) and mixer (rx) layers in a circuit.
Interpret the histogram as candidate cuts.

C = (i, j) \in E \sum \frac{1}{2} (1 - Z_{i} Z_{j}), ∣ γ, β ⟩ = ℓ = 1 \prod p e^{- i β_{ℓ} \sum_{i} X_{i}} e^{- i γ_{ℓ} C} ∣ + ⟩^{\otimes n}

Each edge contributes 1 when its endpoints are on different sides of the cut. The cost layer is one rzz(2γ) per edge, the mixer one rx(2β) per qubit; p layers alternate.

Try it

MaxCut on a triangle, p = 1

Simulate: the six strings with one vertex alone (001, 010, 100 and their complements) carry most of the weight; each cuts two of the three edges, which is the maximum. 000 and 111 cut nothing and are suppressed.

OPENQASM 3.0;
include "stdgates.inc";
qubit[3] q;
bit[3] c;
h q[0];
h q[1];
h q[2];
rzz(1.2) q[0], q[1];
rzz(1.2) q[1], q[2];
rzz(1.2) q[0], q[2];
rx(0.8) q[0];
rx(0.8) q[1];
rx(0.8) q[2];
c = measure q;

Open in the IDE Open in the Playground

QAOA does not output the answer; it outputs a distribution that favours good answers. You sample, evaluate the cut of each string classically, and keep the best. Increasing p improves the distribution but doubles the two-qubit gate count each time, so on hardware p stays at 1–3.

Quiz 1 · 10 XP

In QAOA for MaxCut, the cost layer is built from…

Quiz 2 · 10 XP

Why is a triangle's MaxCut at most 2?

Key takeaway

QAOA alternates a cost layer of rzz gates with a mixer of rx gates and samples good cuts with high probability. Depth p trades quality against two-qubit gate count.

Docs: Hamiltonians and expectation values

OPENQASM 3.0; include "stdgates.inc"; qubit[3] q; bit[3] c; h q[0]; h q[1]; h q[2]; rzz(1.2) q[0], q[1]; rzz(1.2) q[1], q[2]; rzz(1.2) q[0], q[2]; rx(0.8) q[0]; rx(0.8) q[1]; rx(0.8) q[2]; c = measure q;