VQE chased the lowest energy of a molecule. QAOA chases the best answer to a combinatorial puzzle — the best schedule, the best route, the best way to split a network. The trick is identical: encode “best” as the ground state of a cost Hamiltonian, then use the hybrid loop to hunt for it.
↩ before you start · keep these handy
·From QC 10: the hybrid loop tunes circuit angles to minimize a measured cost.
·From QC 11: minimizing ⟨H⟩ finds the ground state — here that ground state IS the answer.
·From QC 09: e−iHt “evolves” under H — QAOA alternates two such evolutions.
🔑 symbol decoder · every new mark, in plain words
MaxCutsplit a graph’s nodes into two groups to cut as many edges as possible — a classic hard problem.cost Hᶜa Hamiltonian whose lowest energy sits on the best bitstring — the optimum encoded as a ground state.mixer Hᶫthe “stirring” term ΣX that lets amplitude flow between candidate bitstrings.γ, β (angles)how long to apply the cost and mixer in each layer — the variational knobs.p (layers)how many cost-then-mixer rounds you stack; bigger p, better answers (and deeper circuit).bitstringone candidate solution — which side of the cut each node is on, e.g. 01101.
feel
Make the good answers loud
Start in an even mix of every possible answer at once. The cost step quietly stamps a phase on each candidate according to how good it is; the mixer step turns those phases into shifts of amplitude — nudging weight toward the better answers. Repeat, and the good bitstrings grow loud while the bad ones fade. Measure, and you most likely read out a great solution.
🏛️ everyday picture
Imagine seating guests at two tables so that feuding pairs end up apart. You can’t try every seating by hand, so instead you keep all arrangements faintly in mind and repeatedly do two things: mark which seatings keep enemies separated, then shuffle a little toward those. After a few rounds, the “everyone’s happy” seatings dominate your attention. That marking-then-shuffling is the cost step and the mixer step.
recapCost step marks good bitstrings with a phase; mixer step turns those phases into amplitude toward better answers.
play
Solve a MaxCut by hand
This is the objective QAOA optimizes. Click a node to flip which side of the cut it’s on (teal or amber). Edges that cross between the two sides light up green — those are cut. Try to cut as many as possible, then reveal the true maximum.
▸ MaxCut benchcut = edges crossing sides
edges cut
{{ cut }}/ {{ total }} edges
assignment {{ bitstring }}
{{ status }}
recapMaxCut asks for the two-way split with the most crossing edges; QAOA hunts for that best bitstring.
math
Cost, mixer, repeat
Encode MaxCut as a Hamiltonian whose energy counts cut edges — one term per edge:
Hᶜ = Σ(i,j)∈E ½(1 − Zᵢ Zⱼ)
A term scores 1 when the two endpoints differ (edge cut) and 0 when they match. QAOA prepares its trial state by alternating the cost evolution and the mixer, p times, starting from the equal superposition:
tune (γ,β) to maximize ⟨Hᶜ⟩ · p → ∞ recovers the exact optimum
✎ worked example · MaxCut of a triangle
1.3 nodes, 3 edges, all connected. Try to put all into two groups
2.any 2-vs-1 split (e.g. 0,0,1) cuts the two edges touching the lone node
3.the third edge joins the two same-side nodes — uncut
4.max cut = 2 of 3 — an odd cycle can never cut them all. ✓
recapEncode the objective in Hᶜ, alternate cost & mixer p times, tune (γ,β) to maximize ⟨Hᶜ⟩.
⚠ common misconceptions
“QAOA returns the guaranteed optimal answer.” The “A” is for Approximate. At finite p it returns a good bitstring with high probability, not a certificate of optimality. Only p → ∞ guarantees the exact optimum.
“The circuit hands you the answer directly.” You measure the final state and get a bitstring sampled from the distribution. You typically run it many times and keep the best cut you see.
“QAOA is proven to beat classical optimizers.” For MaxCut, strong classical algorithms already do very well. Whether QAOA gives a real advantage — and at what depth p — is an active, unsettled research question.
✓ you can now
✓state MaxCut and compute the cut value of any node assignment
✓encode the objective as a cost Hamiltonian Hᶜ = Σ ½(1 − ZᵢZⱼ)
✓describe the QAOA ansatz: alternate cost and mixer p times, tune (γ,β)
✓explain why it’s approximate and why you sample many shots