QAOA for MaxCut Problem

What You'll Learn:

• How QAOA encodes combinatorial optimization problems into quantum circuits
• How the cost and mixer Hamiltonians alternate to explore solution spaces
• How to optimize QAOA parameters (γ, β) with classical optimizers
• What approximation ratios mean and why QAOA provides guarantees

Level: Intermediate | Time: 25 minutes | Qubits: 4 | Framework: Qiskit

Prerequisites

• Bell State — entanglement basics
• Grover's Search — quantum search over bitstrings

The Idea

Imagine you have a social network and want to split people into two teams for a debate. You want to maximize the number of connections (friendships) that cross team boundaries — so friends argue with friends, not with strangers. That's MaxCut: given a graph, partition its vertices into two sets to maximize the edges between them.

MaxCut is NP-hard for general graphs, meaning no classical algorithm can solve it efficiently for all instances. QAOA offers a quantum approach: encode the graph into a quantum circuit, let interference amplify good partitions, and measure to sample near-optimal solutions.

The key insight: QAOA doesn't solve MaxCut exactly. Instead, it provides an approximation — a partition that cuts at least some guaranteed fraction of the optimal number of edges. With p=1 layer, QAOA guarantees at least 69.2% of optimal. More layers improve this ratio, approaching 100% as p → ∞.

How It Works

The Problem

Given a graph G = (V, E), find a partition {S, S̄} that maximizes cut edges:

CODECopy
4-node cycle graph:           Optimal partition:
   0 ─── 1                    S = {0, 2}  (team 0)
   │     │                    S̄ = {1, 3}  (team 1)
   3 ─── 2                    Cut = 4 edges (all!)

The QAOA Circuit

CODECopy
     ┌───┐ ┌──────────────┐ ┌─────────┐
q_0: ┤ H ├─┤ RZZ(2γ, 0-1)├─┤ RX(2β) ├── measure
     ├───┤ ├──────────────┤ ├─────────┤
q_1: ┤ H ├─┤ RZZ(2γ, 1-2)├─┤ RX(2β) ├── measure
     ├───┤ ├──────────────┤ ├─────────┤
q_2: ┤ H ├─┤ RZZ(2γ, 2-3)├─┤ RX(2β) ├── measure
     ├───┤ ├──────────────┤ ├─────────┤
q_3: ┤ H ├─┤ RZZ(2γ, 3-0)├─┤ RX(2β) ├── measure
     └───┘ └──────────────┘ └─────────┘
           ├─ Cost ────────┤├─ Mixer ─┤

Step 1: Uniform Superposition

All qubits start in |+⟩ — equal probability over all 2⁴ = 16 possible partitions.

Step 2: Cost Operator

For each edge (i,j), apply RZZ(2γ):

• When qubits i and j are in the same set (same bit value): adds phase +γ
• When they're in different sets (edge is cut): adds phase -γ

This creates constructive interference for partitions with many cut edges.

Step 3: Mixer Operator

Apply RX(2β) on each qubit. This "mixes" between partition assignments, allowing the state to explore neighboring solutions. Without the mixer, the cost operator alone would just add phases without changing probabilities.

Step 4: Measure and Optimize

Measure all qubits → get a partition → compute its cut value. Repeat many times. Then classically optimize γ and β to maximize the expected cut.

PYTHONCopy
from circuit import run_circuit, optimize_qaoa

# Default parameters (near-optimal for cycle graph)
result = run_circuit()
print(f"Approximation ratio: {result['approximation_ratio']:.1%}")

# Optimize parameters
opt = optimize_qaoa(p=1, max_iterations=50, seed=42)
print(f"Optimized ratio: {opt['approximation_ratio']:.1%}")

The Math

Cost Hamiltonian

The MaxCut cost function as a quantum operator:

C = Σ_{(i,j) ∈ E} (1 - Z_i Z_j) / 2

For each edge: Z_i Z_j = +1 when both qubits agree (same set), -1 when they disagree (edge cut). So (1 - Z_i Z_j)/2 equals 1 for cut edges, 0 otherwise.

Mixer Hamiltonian

B = Σ_i X_i

The transverse field mixer drives transitions between partitions, enabling exploration.

QAOA State

After p layers:

|γ, β⟩ = exp(-iβ_p B) exp(-iγ_p C) ... exp(-iβ_1 B) exp(-iγ_1 C) |+⟩^n

The expected cut value ⟨γ,β|C|γ,β⟩ is maximized over the 2p parameters.

Approximation Guarantees

For the 4-node cycle (3-regular bipartite), p=1 achieves ~75%.

Expected Output

Running the Circuit

PYTHONCopy
from circuit import run_circuit, optimize_qaoa, verify_qaoa, compute_exact_solution

# Exact solution
exact = compute_exact_solution()
print(f"Optimal: {exact['optimal_cut']}, solutions: {exact['optimal_bitstrings']}")

# QAOA with defaults
result = run_circuit(shots=2048)
print(f"Expected cut: {result['expected_cut']:.2f}")
print(f"Ratio: {result['approximation_ratio']:.1%}")

# Optimize
opt = optimize_qaoa(p=1, shots=2048, seed=42)
print(f"Optimized ratio: {opt['approximation_ratio']:.1%}")

# Custom graph (triangle)
result = run_circuit(edges=[(0,1), (1,2), (0,2)], gamma=[0.5], beta=[1.0])

# Verification
v = verify_qaoa()
for check in v["checks"]:
    print(f"[{'PASS' if check['passed'] else 'FAIL'}] {check['name']}")

Try It Yourself

1. Increase p: Run with p=2 (optimize_qaoa(p=2)). Does the approximation ratio improve beyond 75%? How many more iterations does the optimizer need?

2. Try a triangle graph: Use edges=[(0,1), (1,2), (0,2)]. The optimal cut is 2 (can't cut all 3 edges of a triangle). What ratio does QAOA achieve?

3. Scale up: Create a random 8-vertex graph and run QAOA. How does the approximation ratio change with graph size?

4. Compare with random: Generate 1000 random partitions and compute the average cut. How does QAOA p=1 compare?

5. Visualize the landscape: Plot expected cut as a function of γ ∈ [0, π] and β ∈ [0, π/2] for p=1. Is the landscape smooth or rugged?

What's Next

• TSP — QAOA for the Traveling Salesman Problem (constraint optimization)
• Portfolio Optimization — QAOA for financial portfolio selection
• VQE H2 Ground State — Another variational algorithm, for quantum chemistry

Applications

References

• Farhi, E., Goldstone, J., Gutmann, S. (2014). "A Quantum Approximate Optimization Algorithm." arXiv: 1411.4028
• Guerreschi, G., Matsuura, A. (2019). "QAOA for Max-Cut requires hundreds of qubits for quantum speed-up." Scientific Reports 9, 6903. DOI: 10.1038/s41598-019-43176-9
• Zhou, L. et al. (2020). "Quantum approximate optimization algorithm: performance, mechanism, and implementation on near-term devices." Physical Review X 10, 021067. DOI: 10.1103/PhysRevX.10.021067