The MaxCut Problem

Divide a graph's nodes into two groups to maximize edges between groups. This is NP-hard - classical computers struggle as problem size grows.

    0
   / \
  /   \
 1─────2

Triangle graph: find the cut that maximizes crossed edges

The Code

qaoa.ql

# QAOA - MaxCut on Triangle Graph
QUBIT q0, q1, q2
c0 = 0
c1 = 0
c2 = 0
 
# Superposition
H(q0)
H(q1)
H(q2)
 
# Cost layer (edges)
CNOT(q0, q1)
RZ(q1, 0.8)
CNOT(q0, q1)
 
CNOT(q1, q2)
RZ(q2, 0.8)
CNOT(q1, q2)
 
CNOT(q0, q2)
RZ(q2, 0.8)
CNOT(q0, q2)
 
# Mixer layer
RX(q0, 1.2)
RX(q1, 1.2)
RX(q2, 1.2)
 
# Measure
MEASURE q0 -> c0
MEASURE q1 -> c1
MEASURE q2 -> c2

How QAOA Works

1. Cost Layer

Encodes the problem. For each edge, applies a phase based on whether connected nodes are in the same or different groups.

2. Mixer Layer

RX rotations allow transitions between solutions, exploring the search space.

3. Parameter Optimization

A classical optimizer tunes γ (cost) and β (mixer) angles to maximize the cut value.

Solution Table

State	Partition	Edges Cut	Optimal?
000	{0,1,2} vs {}	0	❌
001	{0,1} vs {2}	2	✓
010	{0,2} vs {1}	2	✓
100	{1,2} vs {0}	2	✓
111	{} vs {0,1,2}	0	❌

Real-World Applications

• Logistics - Vehicle routing, delivery optimization
• Finance - Portfolio optimization, risk management
• Manufacturing - Job scheduling, resource allocation
• Telecom - Network design, frequency assignment

Try It Yourself

python qubitlang_cli.py run qaoa.ql --shots 10000Request Files

QAOA: Quantum Optimization