QAOA for Graph 2-Coloring

What You'll Learn:

• How QAOA encodes constraint satisfaction problems into quantum circuits
• How graph coloring relates to MaxCut (feasibility vs optimization)
• How the cost Hamiltonian penalizes same-color adjacent vertices
• What the chromatic number means and why 2-coloring tests bipartiteness

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

Prerequisites

• QAOA MaxCut — QAOA fundamentals, cost/mixer structure
• Bell State — entanglement basics

The Idea

Imagine you're a compiler assigning variables to CPU registers. Two variables that are used at the same time can't share a register — that's a conflict. You want to use as few registers as possible. This is graph coloring: vertices are variables, edges connect conflicting pairs, and colors are registers.

Graph 2-Coloring is the simplest case: can you color every vertex with one of two colors such that no edge connects same-color vertices? This is possible if and only if the graph is bipartite (contains no odd cycles). If a graph has a triangle, it needs at least 3 colors.

The minimum number of colors needed is the chromatic number (chi). Determining chi is NP-hard for general graphs, making it a natural target for QAOA.

The key insight: 2-coloring is the feasibility version of MaxCut. MaxCut asks "how many edges can we cut?" while 2-coloring asks "can we cut ALL edges?" The QAOA circuit is identical — only the objective differs: minimize conflicts instead of maximize cuts.

How It Works

The Problem

Given a graph G = (V, E), assign each vertex a color from {0, 1} to minimize conflicts:

CODECopy
Default graph (triangle + dangling):     Example coloring:
   0 ─── 1                               0:Red ─── 1:Blue
   │   / │                               │   /     │
   2     3                               2:Blue    3:Red

Edges: (0,1), (0,2), (1,2), (1,3)       Conflicts: 1 (edge 1-2: both Blue)
Triangle {0,1,2} → NOT 2-colorable       Minimum possible: 1 conflict

The QAOA Circuit

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

Step 1: Uniform Superposition

All qubits start in |+> — equal probability over all 2^4 = 16 possible colorings.

Step 2: Cost Operator

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

• When qubits i and j have the same color (same bit value): adds phase +gamma (penalty)
• When they have different colors (valid edge): adds phase -gamma (reward)

This creates destructive interference for colorings with many conflicts.

Step 3: Mixer Operator

Apply RX(2beta) on each qubit. This "flips" colors between 0 and 1, allowing the state to explore neighboring colorings. Without the mixer, the cost operator alone would just add phases without changing probabilities.

Step 4: Measure and Optimize

Measure all qubits to get a coloring, count its conflicts. Repeat many times. Then classically optimize gamma and beta to minimize expected conflicts.

PYTHONCopy
from circuit import run_circuit, optimize_qaoa

# Default parameters
result = run_circuit()
print(f"Quality ratio: {result['quality_ratio']:.1%}")
print(f"Expected conflicts: {result['expected_conflicts']:.2f}")

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

The Math

Cost Hamiltonian

The coloring conflict function as a quantum operator:

C = sum_{(i,j) in E} (1 + Z_i Z_j) / 2

For each edge: Z_i Z_j = +1 when both qubits agree (same color = conflict), -1 when they disagree (different colors = valid). So (1 + Z_i Z_j)/2 equals 1 for conflicts, 0 for valid edges.

Note: This is the complement of MaxCut's cost function. MaxCut uses (1 - Z_i Z_j)/2 to count cut edges. Coloring uses (1 + Z_i Z_j)/2 to count conflicts. Minimizing conflicts is equivalent to maximizing cuts.

Mixer Hamiltonian

B = sum_i X_i

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

QAOA State

After p layers:

|gamma, beta> = exp(-i*beta_p B) exp(-i*gamma_p C) ... exp(-i*beta_1 B) exp(-i*gamma_1 C) |+>^n

The expected conflict count <gamma,beta|C|gamma,beta> is minimized over the 2p parameters.

Quality Ratio

We define the quality ratio as:

quality = 1 - (expected_conflicts / |E|)

Expected Output

Running the Circuit

PYTHONCopy
from circuit import (
    run_circuit, optimize_qaoa, verify_qaoa,
    compute_exact_solution, check_valid_coloring, count_conflicts,
)

# Exact solution
exact = compute_exact_solution()
print(f"Min conflicts: {exact['min_conflicts']}")
print(f"2-colorable: {exact['is_2_colorable']}")
print(f"Best colorings: {exact['optimal_bitstrings']}")

# QAOA with defaults
result = run_circuit(shots=2048)
print(f"Expected conflicts: {result['expected_conflicts']:.2f}")
print(f"Quality ratio: {result['quality_ratio']:.1%}")

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

# Bipartite graph (guaranteed 2-colorable)
result = run_circuit(edges=[(0,2), (0,3), (1,2), (1,3)], gamma=[0.5], beta=[1.0])
print(f"Valid colorings found: {len(result['valid_colorings_found'])}")

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

Try It Yourself

1. Bipartite graph: Try edges=[(0,2), (0,3), (1,2), (1,3)] (K_{2,2}). This IS 2-colorable. Does QAOA find valid colorings with 0 conflicts?

2. Increase p: Run with p=2 (optimize_qaoa(p=2)). Does QAOA get closer to the minimum conflict count? How many more optimizer iterations are needed?

3. Odd cycle: Try a 5-cycle edges=[(0,1), (1,2), (2,3), (3,4), (4,0)]. Odd cycles are NOT 2-colorable. What's the minimum conflict count QAOA finds?

4. Compare with MaxCut: Run the same graph through MaxCut QAOA. Verify that (edges - max_cut) equals the minimum coloring conflicts.

5. Scale up: Create a random 8-vertex graph. How does quality degrade with graph size? Does increasing p compensate?

What's Next

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

Applications

Chromatic Number Reference

References

• Farhi, E., Goldstone, J., Gutmann, S. (2014). "A Quantum Approximate Optimization Algorithm." arXiv: 1411.4028
• Hadfield, S. et al. (2019). "From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz." Algorithms 12(2), 34. DOI: 10.3390/a12020034
• Lucas, A. (2014). "Ising formulations of many NP problems." Frontiers in Physics 2, 5. DOI: 10.3389/fphy.2014.00005