The Quantum Approximate Optimisation Algorithm turns a discrete objective function into a diagonal quantum Hamiltonian, alternates phase evolution under that cost with a noncommuting mixer, then searches the resulting low-dimensional parameter landscape for bit strings with high objective value.
QAOA sits between two earlier Quantum Mathematics owners. Guide 20 develops adiabatic optimisation, where one slowly changes a Hamiltonian and follows low-energy structure. Guide 14 develops general variational eigensolvers. QAOA instead uses a deliberately structured depth-p circuit derived from an optimisation cost Hamiltonian and a mixer Hamiltonian. It is variational, but its alternation has a combinatorial job.
This guide develops MaxCut encodings, Ising cost operators, mixer rotations, the p-layer QAOA state, a complete p=1 one-edge calculation, parameter periodicity, local objective structure, constrained mixers, warm starts, approximation metrics, optimisation difficulty and the boundary between heuristic evidence and proven performance.
Discrete objective → diagonal cost Hamiltonian → noncommuting mixer → alternating phase rotations → expectation landscape → classical parameter search → sample candidate solutions.
1. From a bit-string objective to a Hamiltonian
Suppose a classical optimisation problem has bit string z∈{0,1}n and objective C(z).
Construct a diagonal operator Ĉ satisfying
Ĉ|z⟩=C(z)|z⟩.
The computational basis eigenvalue is exactly the classical objective value.
Maximising C(z) is therefore equivalent to finding a high-eigenvalue computational basis state of Ĉ.
2. MaxCut
Given graph G=(V,E), assign each vertex to one of two sides.
An edge (u,v) contributes 1 when its endpoints lie on different sides and 0 when they lie on the same side.
Encode side assignment by qubit Z eigenvalues. Under the convention |0⟩ has Z=+1 and |1⟩ has Z=−1, one edge cost is
C_{uv}=(I−Z_uZ_v)/2.
If the endpoint bits agree, ZuZv=+1 and the cost is zero. If they differ, the product is −1 and the cost is one.
3. MaxCut cost Hamiltonian
Sum over edges:
C=Σ_{(u,v)∈E}(I−Z_uZ_v)/2.
Every term commutes because each is diagonal in the Z basis.
The maximum eigenvalue of C equals the maximum cut size.
Weighted MaxCut replaces each edge term by weight wuvCuv.
4. Initial state
Standard QAOA begins with the uniform superposition
|s⟩=|+⟩^{⊗n}.
Every bit string starts with equal probability 1/2n.
This is the highest-energy eigenstate of the conventional mixer B=ΣXj with eigenvalue n, or the ground state if the mixer sign is chosen as −ΣX. QAOA sign conventions vary; the state and implemented rotations must be interpreted together.
5. Cost unitary
For angle γ, define
U_C(γ)=e^{-iγC}.
Because C is diagonal, this applies an objective-dependent phase:
U_C(γ)|z⟩=e^{-iγC(z)}|z⟩.
No bit-string probability changes during this unitary alone. The cost information is encoded into relative phase.
6. Mixer unitary
The standard unconstrained mixer is
B=Σ_{j=1}^n X_j.
Since X terms on different qubits commute,
U_B(β)=e^{-iβB}=⊗_j e^{-iβX_j}.
The mixer changes computational-basis amplitudes and converts the phase pattern created by UC into constructive/destructive interference among candidate bit strings.
7. p-layer QAOA state
At depth p, choose parameter vectors γ=(γ₁,…,γp) and β=(β₁,…,βp).
The QAOA state is
|γ,β⟩=U_B(β_p)U_C(γ_p)…U_B(β_1)U_C(γ_1)|s⟩.
The objective supplied to the classical optimiser is
F_p(γ,β)=⟨γ,β|C|γ,β⟩.
After parameters are chosen, measure in the computational basis and evaluate sampled cuts classically.
8. Why phase separation and mixing must alternate
UC alone only changes phases, so computational-basis probabilities remain uniform.
UB alone begins from an eigenstate of B, so it contributes only a global phase to |+⟩⊗n.
The algorithm works because the two Hamiltonians do not commute. Cost phases become amplitude differences after the mixer, then later cost layers phase those new amplitudes again.
9. Complete p=1 calculation for one edge
Take two qubits with one MaxCut edge. The cost is
C=(I−Z_1Z_2)/2.
At p=1,
|γ,β⟩=e^{-iβ(X_1+X_2)}e^{-iγC}|++⟩.
A direct Pauli conjugation calculation gives
⟨C⟩=(1+sin(4β)sinγ)/2.
This formula is convention specific: reversing signs in UC or UB changes the corresponding parameter signs but not the reachable probabilities after reparameterisation.
10. Optimise the one-edge example
Choose
β=π/8
so sin4β=1, and
γ=π/2
so sinγ=1.
Then
⟨C⟩=1.
One QAOA layer solves the one-edge MaxCut perfectly. The measured state is supported on the two optimal cuts 01 and 10, up to phases.
11. Locality of p=1 expectations
At fixed shallow p, the expectation of a local edge term depends only on a bounded neighbourhood around that edge because conjugating local Paulis through p layers expands operator support only a finite graph distance.
This allows analytic formulas for regular or locally tree-like graph families at low p.
For example, on triangle-free D-regular graphs, the p=1 expected cut fraction has a closed form depending on β,γ and D. The formula shows how local degree enters performance before any global graph structure appears.
12. Approximation ratio
For a maximisation problem with optimum Cmax>0, define the expectation approximation ratio
r=F_p/C_max.
0≤r≤1 for nonnegative objectives.
This is an expected objective ratio, not the probability of sampling the exact optimum.
A state can have high expected cut value while spreading probability across many near-optimal strings and very little probability on the exact optimum.
13. Expected value versus best-of-samples
Hardware typically produces samples z1,…,zM.
Possible evaluation metrics include:
- mean objective E[C(z)];
- probability of sampling an optimum;
- expected best value after M shots;
- tail probability P(C(z)≥threshold);
- time-to-solution at a target confidence.
Two algorithms with identical expectation can behave very differently under best-of-samples metrics.
14. Parameter periodicity
For integer-valued MaxCut C,
e^{-i(γ+2π)C}=e^{-iγC}.
Thus γ is 2π-periodic in this normalisation.
Because e^{-i(β+π)X}=−e^{-iβX} for one qubit and global signs can cancel physically, β domains can often be reduced further using symmetries.
Exact fundamental parameter domains depend on graph parity and Hamiltonian normalisation; optimisation code should exploit only proven symmetries.
15. Classical parameter optimisation
Each objective evaluation requires quantum expectation estimation or samples.
A classical optimiser then updates 2p parameters.
Methods include:
- grid search at very low p;
- gradient methods;
- SPSA/noisy stochastic optimisation;
- Bayesian optimisation;
- Fourier/interpolated parameter schedules;
- layerwise training.
The best choice depends on shot noise, p, parameter smoothness and hardware drift.
16. Parameter transfer
Optimal QAOA angles often vary smoothly across graph instances from the same ensemble or across neighbouring depth p values.
This motivates transferring parameters from small instances, lower depth or similar graphs rather than random initialisation.
Transfer is empirical structure, not a universal theorem. Adversarial or structurally different instances can break the pattern.
17. QAOA and digitised adiabatic evolution
QAOA resembles a bang-bang or digitised interpolation between mixer and cost Hamiltonians.
At large p, suitable angle schedules can approximate discretised adiabatic paths.
But low-depth QAOA is not simply “adiabatic computing with too few Trotter steps”. Its parameters are freely optimised and can exploit interference patterns far from a monotone adiabatic schedule.
18. Constrained optimisation
Standard X mixers connect every bit string by single-bit flips. That is inconvenient when only a constrained subset of strings is feasible.
One strategy adds penalty terms to the cost Hamiltonian.
Another designs a mixer that preserves feasibility exactly.
Hadfield and collaborators formalised the Quantum Alternating Operator Ansatz for such structured mixers. [2]
19. XY mixer for fixed Hamming weight
Suppose feasible strings must contain exactly k ones.
An XY-type mixer
B_XY=Σ_{(i,j)}(X_iX_j+Y_iY_j)
moves excitations between qubits while preserving total Z excitation/Hamming weight.
If the initial state lies in the feasible weight-k sector, ideal evolution remains there.
This can be more efficient than wasting amplitude on infeasible strings and penalising them.
20. Mixer connectivity matters
A feasibility-preserving mixer must also connect the feasible solution space sufficiently.
If the mixer breaks feasible configurations into disconnected components, starting in one component can make the global optimum unreachable.
Constraint preservation is therefore necessary but not sufficient; ergodicity/connectivity inside the feasible set matters.
21. Warm-start QAOA
Classical relaxations can supply approximate continuous solutions that initialise a biased quantum state or modified mixer.
The intention is to begin near a promising region rather than from uniform |+⟩⊗n.
A warm start can improve finite-depth performance on some problems but may also reduce exploration if the classical seed lies in a poor basin.
22. Shot noise
If C(z) is estimated from M independent bit-string samples,
Var(C̄)=Var(C)/M.
For a graph with many edges, raw objective variance can scale with problem size.
Noisy objective evaluations can confuse a classical optimiser, especially when parameter updates change expectation by less than shot uncertainty.
23. Hardware noise
QAOA’s shallow repeated structure is attractive for near-term hardware, but two-qubit cost gates can still dominate error.
Coherent over-rotation changes the effective γ. Decoherence reduces interference. Readout noise biases cut statistics.
Error mitigation from Guide 55 can help selected observables but adds shot/calibration overhead and does not restore arbitrarily deep computation.
24. Barren plateaus are not one universal QAOA law
Generic deep random variational circuits can exhibit exponentially vanishing gradients.
QAOA has stronger locality and problem structure, so gradient concentration depends on depth, graph family, objective locality and parameter initialisation.
One should not claim either that QAOA is immune to trainability problems or that every QAOA landscape has an exponential barren plateau.
25. Classical competitors
Combinatorial optimisation has strong classical baselines:
- semidefinite relaxations;
- local search;
- simulated annealing;
- branch-and-bound;
- message passing;
- specialised approximation algorithms;
- tensor/network simulation of shallow quantum circuits.
A credible QAOA advantage claim must compare against the best relevant classical method at matched solution quality and total resource cost—not against brute force by default.
26. Proven versus heuristic performance
For selected graph families and fixed p, analytic approximation guarantees can be derived.
For general instances, low-depth QAOA is primarily a heuristic algorithm family.
As p→∞, QAOA can in principle approximate adiabatic schedules under suitable controllability assumptions, but this does not imply a practical finite-depth speedup or efficient classical parameter optimisation.
27. Common misconception: QAOA outputs the optimal bit string directly
QAOA prepares a probability distribution. One must sample it, evaluate candidate strings, and usually repeat many times. High expected value need not mean high exact-optimum probability.
28. Common misconception: increasing p always improves hardware performance
The ideal variational family is nested when parameters can effectively reproduce lower depth, so ideal optimum expectation need not worsen with p. On hardware, extra depth adds noise and harder classical optimisation, so observed performance can decrease.
29. Common misconception: every constraint should be a penalty
Penalty Hamiltonians are simple but can distort energy scales and demand large coefficients. Constraint-preserving mixers can keep the state entirely inside the feasible subspace when a suitable connected mixer is available.
30. Worked synthesis problem
A graph consists of one edge between two vertices.
Step 1: Cost. C=(I−Z₁Z₂)/2.
Step 2: p=1 expectation. F_1=(1+sin4β sinγ)/2.
Step 3: Choose β=π/8. Then sin4β=1.
Step 4: Choose γ=π/2. Then sinγ=1 and F₁=1.
Step 5: Interpret. The optimum cost is 1, so this parameter choice gives approximation ratio 1 and supports only optimal cut outcomes ideally. This exact success is a special two-vertex case, not evidence that p=1 solves arbitrary MaxCut instances exactly.
31. Practice set
- How is a classical objective C(z) encoded quantumly?
- Write one MaxCut edge Hamiltonian.
- What is the standard QAOA initial state?
- What does U_C change before any mixer is applied?
- What is the standard X mixer?
- Write the depth-p QAOA state.
- What objective does the classical optimiser maximise?
- Why are cost and mixer both needed?
- For one edge at p=1, state the expected cost formula used here.
- What is the difference between expected approximation ratio and optimum-sampling probability?
- Why can a feasibility-preserving mixer still fail?
- Why does a QAOA advantage claim require strong classical baselines?
Answers
- As a diagonal operator satisfying
Ĉ|z⟩=C(z)|z⟩. (I−Z_uZ_v)/2.|+⟩^{⊗n}.- Relative phases indexed by objective value, not computational-basis probabilities.
B=Σ_jX_jandU_B=e^{-iβB}.U_B(β_p)U_C(γ_p)…U_B(β_1)U_C(γ_1)|s⟩.⟨C⟩or a chosen sample-based surrogate.- Neither alone changes the relevant distribution from the standard starting point; noncommuting alternation converts cost phase into amplitude interference.
(1+sin4β sinγ)/2.- The first is mean objective divided by optimum; the second is the probability mass exactly on optimal strings.
- Its transition graph inside the feasible subspace may be disconnected, making some solutions unreachable.
- Classical combinatorial optimisation already has specialised heuristics, relaxations and approximation algorithms; brute force is rarely the right comparator.
Sources and further study
[1] Edward Farhi, Jeffrey Goldstone and Sam Gutmann, A Quantum Approximate Optimization Algorithm. The foundational QAOA proposal and MaxCut analysis.
[2] Stuart Hadfield and colleagues, From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz. Extends QAOA to constraint-preserving mixers and broader discrete optimisation structures.
[3] Zhihui Wang and colleagues, Quantum approximate optimization algorithm for MaxCut: A fermionic view. Analytic QAOA structure and parameter behaviour for MaxCut families.
[4] Leo Zhou and colleagues, Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices. Numerical/experimental perspective on parameter structure and finite-depth performance.
Continue through Quantum Mathematics
Guide 62: Quantum Machine Learning, Feature Maps, Quantum Kernels and Variational Classifiers develops another hybrid variational/data-processing lane. Guide 63: Quantum Differential Equations, Linear ODEs, PDEs, Spectral Methods and Solution States develops state-encoded numerical solution methods. Guide 64: Quantum Simulation of Lattice Gauge Theories, Gauge Constraints, Wilson Loops and Kogut–Susskind Hamiltonians develops a structured quantum-simulation application.