[Rule] TravelingSalesman to QUBO

[zazabap]

Source: TravelingSalesman
Target: QUBO
Motivation: Enables solving TSP on quantum annealers and Ising machines, one of the most studied quantum computing applications.
Reference: Lucas, A. (2014). "Ising formulations of many NP problems." Frontiers in Physics, 2, 5.

Reduction Algorithm

Given a TravelingSalesman instance on graph $G = (V, E)$ with $n = |V|$ vertices and edge weights $w_{uv}$:

Notation:

• $n$ = number of vertices (cities), $m = |E|$
• $w_{uv}$ = weight of edge $(u, v)$
• $A$ = penalty coefficient, chosen as $A > \sum w_{uv}$ (ensures constraint violations dominate)

Variable mapping:
Introduce $n^2$ binary variables $x_{v,p}$ for $v \in {0, \ldots, n-1}$ and $p \in {0, \ldots, n-1}$, where $x_{v,p} = 1$ means city $v$ is visited at position $p$ in the tour.

QUBO variable index: variable $x_{v,p}$ maps to QUBO variable index $v \cdot n + p$.

Constraint/objective transformation:

The QUBO matrix $Q$ encodes three terms: $H = H_A + H_B + H_C$.

$H_A$ — Each city visited exactly once (row constraint):

$$H_A = A \sum_{v=0}^{n-1} \left(1 - \sum_{p=0}^{n-1} x_{v,p}\right)^2$$

• Diagonal: $Q[v \cdot n + p,; v \cdot n + p] \mathrel{+}= -A$
• Off-diagonal: $Q[v \cdot n + p,; v \cdot n + p'] \mathrel{+}= 2A$ for $p < p'$

$H_B$ — Each position occupied by exactly one city (column constraint):

$$H_B = A \sum_{p=0}^{n-1} \left(1 - \sum_{v=0}^{n-1} x_{v,p}\right)^2$$

• Diagonal: $Q[v \cdot n + p,; v \cdot n + p] \mathrel{+}= -A$
• Off-diagonal: $Q[v \cdot n + p,; v' \cdot n + p] \mathrel{+}= 2A$ for $v < v'$

$H_C$ — Distance objective (consecutive positions):

$$H_C = \sum_{(u,v) \in E} w_{uv} \sum_{p=0}^{n-1} \left(x_{u,p} \cdot x_{v,(p+1) \bmod n} + x_{v,p} \cdot x_{u,(p+1) \bmod n}\right)$$

Solution extraction: From QUBO solution $x^$, read the permutation: for each position $p$, find the unique $v$ with $x^_{v \cdot n + p} = 1$. Map the tour back to the TSP solution.

Size Overhead

Target metric (code name)	Polynomial (using symbols above)
num_vars	$n^2$

The $Q$ matrix is $n^2 \times n^2$ with $O(n^3)$ non-zero entries.

Validation Method

• Create small TravelingSalesman instances (complete graphs, $n=3,4$), encode as QUBO, solve both with BruteForce, verify that the QUBO ground state corresponds to the optimal tour.
• Check that invalid permutations (violating row/column constraints) have higher QUBO energy than any valid tour.
• Cross-check with the existing TravelingSalesman → ILP reduction for consistency of optimal values.

Example

Source: TravelingSalesman on $K_3$ (complete graph, 3 vertices) with edge weights $w_{01}=1$, $w_{02}=2$, $w_{12}=3$.

Reduction: $n=3$, so $9$ binary variables $x_{v,p}$. Let $A = 7$ (since $> 1+2+3=6$).

Variables: $x_{0,0}, x_{0,1}, x_{0,2}, x_{1,0}, x_{1,1}, x_{1,2}, x_{2,0}, x_{2,1}, x_{2,2}$.

• $H_A$ penalizes rows: e.g., $x_{0,0} + x_{0,1} + x_{0,2} \neq 1$.
• $H_B$ penalizes columns: e.g., $x_{0,0} + x_{1,0} + x_{2,0} \neq 1$.
• $H_C$ adds distance: e.g., $w_{01}(x_{0,p} \cdot x_{1,p+1} + x_{1,p} \cdot x_{0,p+1})$ for each $p$.

Target: $9 \times 9$ QUBO matrix $Q$ with penalty and distance terms.

Solution: Optimal tour is $0 \to 1 \to 2 \to 0$ with cost $1+3+2=6$. The QUBO ground state is $x_{0,0}=1, x_{1,1}=1, x_{2,2}=1$ (or any cyclic rotation), yielding minimum QUBO value $= 6$ (no penalty).