QAOA for MaxCut

Implement QAOA for the MaxCut combinatorial optimization problem and analyze solution quality vs circuit depth.

QAOA for MaxCut

The Quantum Approximate Optimization Algorithm (QAOA) tackles combinatorial optimization. MaxCut, partition vertices into two sets to maximize crossing edges, is the canonical benchmark.

MaxCut: An NP-Hard Problem

Given a graph G = (V, E), partition V into sets S and S̄ to maximize |{(u,v) ∈ E : u ∈ S, v ∈ S̄}|. For a triangle graph (3 vertices, 3 edges), the optimal cut is 2 (any single vertex vs the other two).

MaxCut is NP-hard in general. The best classical approximation algorithm (Goemans-Williamson, 1995) achieves 0.878 × OPT using semidefinite programming. QAOA with p layers achieves at least 0.6924 for p=1, with guarantees improving with p.

QAOA Circuit Structure

QAOA prepares the state:

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

where:

• $∣ + ⟩^{\otimes n}$ : uniform superposition, H applied to all n qubits
• $U_{C} (γ)$ : cost unitary, encodes the MaxCut objective
• $U_{B} (β)$ : mixer unitary, explores the solution space

Parameters (γ₁,...,γₚ, β₁,...,βₚ) are optimized classically to maximize the expected cut value.

Cost Unitary: Encoding MaxCut

For each edge (i,j) in the graph, the contribution to the Hamiltonian is:

H_{C} = (i, j) \in E \sum (I - Z_{i} \otimes Z_{j}) /2

The unitary $U_{C} (γ) = e^{- iγ H_{C}}$ decomposes per edge as $R Z Z (γ)$ :

•CX(i,j) → RZ(γ, j) → CX(i,j)

This implements $e^{- iγ Z_{i} \otimes Z_{j} /2}$ per edge.

Mixer Unitary: Exploring Solutions

The mixer $U_{B} (β) = e^{- i β \sum_{j} X_{j}} = ⨂_{j} R X (2 β, j)$ simply applies $R X (2 β)$ to every qubit. This drives transitions between different cut assignments, ensuring the optimization explores the full space.

Classical Optimization

After the quantum circuit measures the expected cut value, a classical optimizer (grid search for p=1, COBYLA or gradient descent for p>1) finds the optimal parameters. For p=1 on the triangle graph, an exhaustive grid search over (γ, β) ∈ [0,2π]² works well.

QAOA Depth vs Quality Tradeoff

QAOA with p=1 layer offers weak approximation guarantees (~0.692 for MaxCut). With p→∞, QAOA converges to the exact optimum. But each layer adds ~3 two-qubit gates per edge: a 10-edge graph with p=3 requires 90 CX gates. On current NISQ devices with T2~100μs and CX~300ns, this circuit accumulates substantial noise before completing. The sweet spot is currently p=1 or p=2.

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 hands-on coding challenge. You write Qiskit-compatible Python in the browser editor, run it instantly via WebAssembly, watch the circuit and Bloch sphere react, and pass automatic output checks. The AI tutor Qubitus gives Socratic hints if you get stuck.

Part of: Real-World Quantum Python

Write production-quality quantum Python, circuit optimization, hybrid algorithms, cloud backends, noise modeling, and software engineering patterns.

Previous lessonQuantum Chemistry on Quantum Computers Next lessonGrover's Algorithm Implementation

This lesson is part of Pro

Unlock Real-World Quantum Python 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