/ quantum courseBack to lab
PATHWAY PROGRESS0/27 passed

09 / Scientific applications · LESSON 21 / 27 · 25 MIN

QAOA and combinatorial optimization.

Translate a graph cost into a hybrid optimization objective.

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

1. For a single edge, bit string 01 has cut value…
2. Increasing QAOA depth guarantees real-world advantage?

Checking your account…