QAOA for Traveling Salesman Problem

Overview

The Traveling Salesman Problem (TSP) asks: given a list of cities and distances between them, what is the shortest route that visits each city exactly once and returns to the start?

This circuit demonstrates QAOA for a simplified TSP instance.

The Problem

CODE
City 0 ←──5──→ City 1
   ↑            ↑
   └─────10─────┘
         ↓
      City 2

Find: Shortest route visiting all cities once.

Encoding

For n cities, we need n² qubits in the position encoding:

Qubit (i,t) = 1 means city i is visited at time t

For 2 cities:

Qubit	Meaning
q₀	City 0 at time 0
q₁	City 1 at time 0
q₂	City 0 at time 1
q₃	City 1 at time 1

Constraints

Each city visited exactly once
Exactly one city per timestep

These are encoded as penalty terms in the Hamiltonian.

Running the Circuit

PYTHON
from circuit import run_circuit
import numpy as np

# Custom distance matrix
distances = np.array([
    [0, 5, 10],
    [5, 0, 3],
    [10, 3, 0]
])

result = run_circuit(distances=distances)
print(f"Best route: {result['best_route']}")

Expected Output

For 2 cities:

Valid routes: [0,1] or [1,0]
Optimal tour length: 10 (5 + 5)

Scaling Challenge

Cities	Qubits needed	Classical solutions
2	4	2
3	9	6
4	16	24
5	25	120
n	n²	(n-1)!/2

Limitations

Qubit overhead: n² qubits for n cities
Constraint satisfaction: Hard to enforce exactly
Approximate solutions: QAOA gives probabilistic results

Alternative Encodings

Binary encoding: O(n log n) qubits
Mixer-preserving: Maintains feasible subspace
Grover-mixer: Better constraint handling

Applications

Logistics: Delivery route optimization
Manufacturing: Tool path planning
PCB design: Minimize drilling distance

QAOA for TSP