QAOA on a small graph

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

Advanced12 min read4 sections · 2 questions+45

By the end you will be able to

01Write the MaxCut cost Hamiltonian for a triangle.
02Identify cost (rzz) and mixer (rx) layers in a circuit.
03Interpret 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.

Hands-on

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

OPENQASM 3.0;
include "stdgates.inc";
gate rzz(theta) a, b { cx a, b; rz(theta) b; cx a, b; }
qubit[3] q;
bit[3] c;
h q[0];
h q[1];
h q[2];
rzz(2.5) q[0], q[1];
rzz(2.5) q[1], q[2];
rzz(2.5) q[0], q[2];
rx(0.6) q[0];
rx(0.6) q[1];
rx(0.6) 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.

Knowledge check

2 questions · one try each counts

Question 1

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

Question 2

Why is a triangle's MaxCut at most 2?

OPENQASM 3.0; include "stdgates.inc"; gate rzz(theta) a, b { cx a, b; rz(theta) b; cx a, b; } qubit[3] q; bit[3] c; h q[0]; h q[1]; h q[2]; rzz(2.5) q[0], q[1]; rzz(2.5) q[1], q[2]; rzz(2.5) q[0], q[2]; rx(0.6) q[0]; rx(0.6) q[1]; rx(0.6) q[2]; c = measure q;