QAOA for MaxCut Problem

Overview

The Quantum Approximate Optimization Algorithm (QAOA) is a variational quantum algorithm for solving combinatorial optimization problems. MaxCut is the canonical example: partition a graph's vertices to maximize edges between partitions.

The Problem

Given a graph G = (V, E), find a partition of V into two sets S and S̄ that maximizes the number of edges between S and S̄.

CODE
Example (4-node cycle):
   0 ─── 1
   │     │
   3 ─── 2

Optimal: {0,2} vs {1,3} → Cut = 4 edges

The Algorithm

QAOA alternates between:

Problem Hamiltonian (encodes MaxCut objective)
Mixer Hamiltonian (explores solution space)

CODE
|+⟩⊗n → [exp(-iγC)][exp(-iβB)] → ... → Measure
         ↑_________________________↑
              Repeat p times

The Circuit

For p=1 layer:

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

Running the Circuit

PYTHON
from circuit import run_circuit

# Use default 4-node cycle graph
result = run_circuit()
print(f"Max cut found: {result['max_cut_found']}")
print(f"Approximation ratio: {result['approximation_ratio']:.2%}")

# Custom graph
edges = [(0,1), (0,2), (1,2), (1,3), (2,3)]
result = run_circuit(edges=edges, gamma=[0.6], beta=[0.3])

Expected Output

Metric	Value
Optimal cut	4 (for cycle graph)
QAOA (p=1)	~3.5-4
Approximation ratio	~87-100%

Why QAOA?

Quantum advantage potential: May outperform classical for large instances
NISQ-friendly: Shallow circuits, noise-tolerant
Tunable depth: More layers (p) → better approximation

Approximation Guarantees

Depth p	Worst-case ratio
1	≥ 0.6924
2	≥ 0.7559
∞	→ 1.0

Applications

Network partitioning: Balanced workload distribution
Circuit design: Minimize wire crossings
Social networks: Community detection
VLSI layout: Minimize cut wires