The Quantum Approximate Optimization Algorithm turns a combinatorial
optimization problem into a short, tunable quantum circuit.Everything here is built on a plain NumPy statevector — no quantum SDK.
The whole algorithm is four ideas:
Encode the objective as a diagonal cost operator C, so
C∣z⟩=c(z)∣z⟩ for every bitstring z.
Start in the uniform superposition ∣+⟩⊗n —
every candidate solution, equally weighted.
Alternate p times between a cost layere−iγC (phases proportional to how good each answer is)
and a mixer layere−iβ∑qXq (turns those phases
into amplitude).
Tune the 2p angles (γ,β) classically to
maximize ⟨C⟩.
Our objective is MaxCut: split the graph's nodes into two groups so
that as many edges as possible cross between them.
1. The problem
Pick a graph. Every bitstring z∈{0,1}n is a candidate cut:
bit q says which side node q lands on.
8 nodes means 256 possible cuts and a
statevector of 256 complex amplitudes.Brute force is still easy at this size, which is exactly what makes
it a good test bed: we can check QAOA against the true optimum.
2. The cost operator
For MaxCut the objective counts edges whose endpoints disagree:c(z)=(u,v)∈E∑zu⊕zvBecause c depends only on the bitstring, C is diagonal — we never
build a 2n×2n matrix, just a vector of 2n numbers. That is
what makes the cost layer a single elementwise multiply later on.
3. A statevector simulator in three functions
The state is one complex vector of length 2n, indexed by bitstring.
Qubit q is bit q of the index.
what it does
cost
plus_state
∣+⟩⊗n — every bitstring, equal amplitude
O(2n)
cost_layer
e−iγC — a phase per bitstring, proportional to its cut
one elementwise multiply
mixer_layer
e−iβ∑qXq — an RX(2β) on every qubit
n passes
The cost layer is diagonal, so it costs a single multiply — no matrix
ever gets built. The mixer factorizes across qubits, so it is n
independent 2×2 rotations applied via a reshape.
4. The QAOA circuit
Alternate the two layers p times, starting from ∣+⟩⊗n:∣γ,β⟩=k=1∏pe−iβkBe−iγkC∣+⟩⊗nThat is the entire algorithm. Everything below is measurement and tuning.
5. Turn the knobs
Drag the angles and watch the amplitude pile up on good cuts. The state
starts flat — every bitstring equally likely — and the two layers working
together concentrate it on high-cut strings.Try setting every angle to zero: you get the uniform superposition back,
and ⟨C⟩ drops to the random-guess average.
2
cost angles
mixer angles
6. The landscape the optimizer climbs
At p=1 there are only two angles, so we can just plot ⟨C⟩
over the whole (γ,β) plane. The white dot is where your
sliders currently sit.Note the structure: broad, smooth basins rather than noise. That is why a
derivative-free optimizer with a handful of restarts does well here — and
also why the picture gets much harder to reason about once p>1 and the
landscape lives in 2p dimensions.
7. Let a classical optimizer find the angles
This is the "hybrid" half of QAOA: the quantum state supplies
⟨C⟩, and a classical optimizer picks the next angles to try.We use COBYLA — derivative-free, so it needs no gradients, just
repeated evaluations. The landscape has many local optima, so we run
several random restarts and keep the best.
4
0
8. Does more depth actually help?
QAOA's guarantee is asymptotic: as p→∞ the ansatz can express
the exact optimum. The interesting question is what happens at the small
p you could actually run on hardware.This sweep re-optimizes from scratch at each depth and plots two things:
the approximation ratio⟨C⟩/Cmax, and the
probability of actually sampling an optimal cut — which is what you
care about if you plan to measure and keep the best shot.
If the curve dipsMore layers can never make the best possible QAOA state worse — a deeper
circuit can always reproduce a shallower one by setting the extra angles to
zero. So a dip means the classical optimizer lost, not the ansatz: the
search space grew to 2p dimensions and the restarts missed the good
basin. Raise the restarts and watch the dip fill in. That failure mode is
one of the central practical problems with QAOA.
4
3
What this notebook does and does not show
Everything above is an exact statevector simulation on a handful of
qubits, so it isolates the algorithm from every practical difficulty:
No sampling noise.⟨C⟩ is computed exactly. On
hardware you estimate it from finitely many shots, and the optimizer has
to cope with that noise.
No hardware noise. No decoherence, no gate error, no readout error.
Depth is free here; on a real device it is the main cost.
Small n. At 8–12 qubits brute force wins outright. QAOA is only
interesting where brute force fails — which is also where we can no
longer check the answer this way.
Optimization gets harder fast. The restarts matter even at p=2.
As 2p grows the landscape develops many local optima, and for wide
random circuits gradients can vanish exponentially with qubit count
(barren plateaus).
Whether QAOA beats a good classical heuristic on a real instance is still
an open question. What the simulation does show cleanly is the mechanism:
a diagonal phase, a transverse mixer, and 2p numbers to tune.
