QAOA for Graph Coloring

Overview

Graph coloring assigns colors to vertices such that no two adjacent vertices share the same color. The minimum number of colors needed is the chromatic number. This circuit demonstrates QAOA for 2-coloring.

The Problem

Given graph G = (V, E), assign colors to vertices such that:

No edge connects two vertices of the same color
Use minimum number of colors

CODE
Example (triangle + 1):
    0 ─── 1
    │   / │
    2     3

2-colorable? Check edges:
- (0,1): must be different
- (0,2): must be different
- (1,2): must be different
- (1,3): must be different

Encoding

For 2-coloring, use 1 qubit per vertex:

|0⟩ = Color A (e.g., Red)
|1⟩ = Color B (e.g., Blue)

Qubit	Vertex	Color
q₀	v₀	Red/Blue
q₁	v₁	Red/Blue
q₂	v₂	Red/Blue
q₃	v₃	Red/Blue

Running the Circuit

PYTHON
from circuit import run_circuit

# Triangle graph (not 2-colorable)
edges = [(0,1), (1,2), (0,2)]
result = run_circuit(edges=edges, n_vertices=3)

# Bipartite graph (2-colorable)
edges = [(0,2), (0,3), (1,2), (1,3)]
result = run_circuit(edges=edges, n_vertices=4)

Expected Output

For the default graph:

Metric	Value
Valid colorings	~2-4
Conflicts in best	0-1
Chromatic number	2 (if valid found)

Graph Types

Graph	Vertices	Edges	2-Colorable?
Path	n	n-1	Yes
Cycle (even)	n	n	Yes
Cycle (odd)	n	n	No
Complete	n	n(n-1)/2	No (n>2)
Bipartite	n	m	Yes

Applications

Map coloring: Color regions without same-color borders
Scheduling: Assign time slots without conflicts
Register allocation: Assign variables to registers
Frequency assignment: Avoid interference

Chromatic Number

k	Example	Description
1	Empty graph	No edges
2	Tree, Bipartite	Two-colorable
3	Planar	Four-color theorem
n	Complete K_n	Every vertex different