QAOA Circuit Depth

Understand how QAOA circuit depth affects solution quality and runtime.

QAOA: Quantum Approximate Optimization Algorithm

QAOA (Quantum Approximate Optimization Algorithm) is a hybrid quantum-classical algorithm for combinatorial optimization. Unlike exact solvers, QAOA finds approximate solutions to NP-hard problems in a tunable way: trading circuit depth for solution quality.

The core idea:

QAOA approximates the ground state of a classical cost Hamiltonian $H_{C}$ by alternating between two operators:

•Cost unitary $U_{C} (γ) = e^{- iγ H_{C}}$ : applies phase based on the cost function value
•Mixer unitary $U_{B} (β) = e^{- i β H_{B}}$ : creates superposition between states (usually $H_{B} = \sum X_{i}$ )

The circuit of depth p applies these alternately:

$∣ ψ (γ, β)⟩ = U_{B} (β_{p}) U_{C} (γ_{p}) \dots U_{B} (β_{1}) U_{C} (γ_{1}) ∣ + ⟩^{\otimes n}$

Example: MaxCut on a graph:

MaxCut asks: partition vertices into two sets to maximize cut edges. For a 2-vertex graph {0,1} with edge (0,1):

•Cost: $C (z) = (1 - z_{0} z_{1}) /2$ , equals 1 if $z_{0} \neq = z_{1}$ (a cut edge), 0 if equal
• $H_{C} = (1 - Z_{0} Z_{1}) /2$
• $U_{C} (γ)$ applies $e^{- iγ (Z_{0} Z_{1})}$ = a ZZ rotation

Parameters (p=1 layer)	MaxCut variables
γ (cost angle)	controls phase accumulation on high-cost states
β (mixer angle)	controls diffusion / mixing of states
Optimal γ,β	π/4, π/8 for p=1 MaxCut on complete graph

QAOA converges to exact solution as p → ∞

With depth p=1, QAOA gives a worst-case approximation ratio of 0.693 for MaxCut on 3-regular graphs (the Farhi et al. result; better than random, worse than Goemans-Williamson). The guarantee depends on the graph family, there is no single generic p=1 ratio. As p → ∞, the algorithm provably converges to the exact optimal solution: but the circuit depth grows proportionally, erasing the quantum advantage on near-term hardware. The practical sweet spot is finding good solutions at low p with noise-tolerant parameters.

Implementation structure:

For MaxCut on a 4-node ring graph (edges: 0-1, 1-2, 2-3, 3-0) with p=1 QAOA:

This is the opening of the lesson. The full walkthrough, the interactive circuit, and the graded challenge continue inside myqubit.

How this lesson works

A guided reading lesson with interactive knowledge checks. Concepts are explained step by step with circuit diagrams and runnable examples, and you confirm understanding before moving on.

Part of: Quantum Algorithms

Learn the algorithms that make quantum computers powerful.

Previous lessonVariational Eigensolver Basics

This lesson is part of Pro

Unlock Quantum Algorithms and all 10 tracks with Pro: $12.99/month, $79/year, or $97 lifetime. Start with the free track first if you are new.

Create account Try the Playground