09 / Scientific applications · LESSON 21 / 27 · 25 MIN
QAOA and combinatorial optimization.
Translate a graph cost into a hybrid optimization objective.
C = Σ(i,j) (I−ZᵢZⱼ)/2 |γ,β⟩ = U_B(β)U_C(γ)|+…+⟩
Encode MaxCut
For an edge (i,j), (I−ZᵢZⱼ)/2 is one when its bits differ and zero otherwise. Summing over edges counts a cut. MaxCut commonly maximizes ⟨C⟩; minimization conventions may negate the cost, so specify the sign.
Alternate two evolutions
Cost evolution exp(−iγC) introduces phase and a mixer exp(−iβΣXᵢ) changes amplitudes. Repeat p layers, measure candidate bit strings and tune parameters classically. More layers increase expressivity and depth.
Benchmark fairly
QAOA does not guarantee practical speedup or the optimum for every graph. Compare with strong classical solvers, report wall-clock resources, distribution of solution quality and noisy-device constraints.
CHECK YOUR UNDERSTANDING
Lesson quiz
Answer all 2 questions correctly. Unlimited retries.
0/2 answered
Checking your account…
