[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).

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	Direct reduction improves on existing 2-step path TSP -> ILP -> QUBO
Non-trivial	✅ Pass	Penalty Hamiltonian construction with three constraint/objective terms
Correctness	✅ Pass	Lucas (2014) is verified and already in project bibliography
Well-written	⚠️ Warn	Overhead notation mismatch, trivial example, missing non-edge handling

Overall: 3 passed, 0 failed, 1 warning

---

Usefulness

The existing path from TravelingSalesman to QUBO goes through ILP in 2 steps, with overhead num_vars = num_vertices^2 + 2 * num_vertices * num_edges. The proposed direct reduction achieves num_vars = n^2 (i.e., num_vertices^2), which is strictly lower on the num_vars dimension for any graph with edges. This is a clear improvement.

Non-trivial

The reduction constructs a penalty Hamiltonian with three distinct terms:

• H_A: Row constraints (each city visited exactly once)
• H_B: Column constraints (each position occupied by exactly one city)
• H_C: Distance objective encoding consecutive-position edge weights

This involves introducing n^2 auxiliary binary variables with a non-trivial penalty coefficient and quadratic interaction structure. This is a genuine structural transformation, not a relabeling or coercion.

Correctness

The cited reference — Lucas, A. (2014), "Ising formulations of many NP problems", Frontiers in Physics, 2, 5 — is a real, widely-cited paper (DOI: 10.3389/fphy.2014.00005, arXiv: 1302.5843). It is already present in the project bibliography (docs/paper/references.bib, line 35). The TSP-to-Ising formulation using n^2 position-based binary variables x_{v,p} is a well-established construction confirmed across multiple independent sources (D-Wave documentation, Glover et al. 2019, numerous quantum computing papers).

The formulas for H_A, H_B, and H_C in the issue are consistent with the standard Lucas formulation.

Minor concern (not fatal): The H_C term only sums over edges (u,v) in E. For non-complete graphs, consecutive tour positions assigned to non-adjacent vertices would not be penalized by H_C, potentially allowing infeasible tours to have lower energy than valid ones. The issue should clarify whether the reduction assumes a complete graph or should add a large penalty for non-edges. In practice, TSP is typically defined on complete graphs (with infinite weight for missing edges), so this may just need an explicit note.

Well-written

The issue is generally well-structured with all required sections present. However, several items need attention:

1. Overhead table notation mismatch: The overhead table lists num_vars = n^2, but the code metric should use the source problem's getter names. The correct expression is num_vars = num_vertices^2. The symbol n is defined in the algorithm section but the overhead table should use code-level metric names as required by the template.

2. Trivial example: The K_3 example with weights w_{01}=1, w_{02}=2, w_{12}=3 is problematic because K_3 has only two distinct tours (which are reverses of each other) and both have identical cost 6 in an undirected graph. The example does not differentiate between optimal and suboptimal tours. A K_4 example with asymmetric weights would be more illustrative.

3. QUBO ground-state value claim: The issue states "minimum QUBO value = 6 (no penalty)" but this ignores the constant terms from expanding (1 - sum)^2 in H_A and H_B. The QUBO objective includes constant offsets of nA from each constraint block (total 2nA). The ground state value of the QUBO matrix is not simply the tour cost; the constant terms shift it. This should be clarified or the claim corrected.

4. Non-edge handling: As noted under Correctness, the reduction algorithm does not specify what happens for non-edges. Since the codebase's TravelingSalesman works on general SimpleGraph (not necessarily complete), the algorithm should either (a) explicitly state it requires a complete graph, or (b) add penalty terms W_max * n for non-adjacent vertex pairs in H_C.

5. Solution extraction incompleteness: The solution extraction says "find the unique v with x*_{v*n+p} = 1" but does not address what to do if the QUBO solution is infeasible (no unique v for some position, or multiple v's). A fallback or error condition should be noted.

Recommendations

• Change the overhead table entry to num_vars = num_vertices^2 to match code metric names.
• Replace the K_3 example with a K_4 instance where the optimal tour is unique and distinguishable from suboptimal tours.
• Add a note about complete-graph assumption or explicitly handle non-edges with large penalty weights.
• Correct or clarify the QUBO ground-state energy claim to account for constant offsets from constraint terms.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	Direct reduction with num_vars = n² vs existing 2-step path (TSP → ILP → QUBO) with ~O(n⁴) overhead
Non-trivial	✅ Pass	Constructs QUBO matrix with penalty terms for row/column constraints and distance objective
Correctness	✅ Pass	Lucas (2014) verified — paper exists, is in project bibliography, and covers TSP-to-Ising formulation
Well-written	⚠️ Warn	Minor notation and example completeness issues (see details below)

Overall: 3 passed, 0 failed, 1 warning

---

Usefulness

An existing 2-step path exists: TravelingSalesman → ILP → QUBO. The composite overhead for num_vars expands to roughly O(n⁴) or worse (the ILP step produces num_vars = num_vertices² + 2 * num_vertices * num_edges variables with O(n³) constraints, and the ILP→QUBO step then multiplies num_vars * num_constraints). The proposed direct reduction achieves num_vars = n², which is a significant improvement on all dimensions. Clear pass.

Non-trivial

The reduction constructs a QUBO matrix encoding three distinct Hamiltonian terms:

• Row constraints ($H_A$): each city visited exactly once
• Column constraints ($H_B$): each position occupied by exactly one city
• Distance objective ($H_C$): edge weights for consecutive tour positions

This involves penalty coefficient selection, quadratic interaction terms, and non-trivial variable indexing. Clearly not a variable substitution or subtype coercion.

Correctness

The reference is Lucas, A. (2014). "Ising formulations of many NP problems." Frontiers in Physics, 2, 5. DOI: 10.3389/fphy.2014.00005. This paper:

• Exists and is widely cited (>4000 citations)
• Is already in the project bibliography (references.bib as lucas2014)
• Section 8.1 covers the TSP-to-Ising formulation using exactly the approach described in this issue (position-based binary encoding with row/column constraints)
• The formulation in the issue correctly follows Lucas's construction

The penalty coefficient choice $A > \sum w_{uv}$ is standard and correct.

Well-written

Mostly complete, with a few items to improve:

1. Overhead table notation: The table lists num_vars = n², but n is defined in the issue body, not in terms of the code getter name. For consistency with the codebase, the formula column should read num_vertices^2 (matching the num_vertices getter on TravelingSalesman). This is important because the #[reduction(overhead = {...})] macro validates variable names against getter methods.

2. Incomplete graph assumption: The $H_C$ term sums over edges $(u, v) \in E$. For a standard TSP on a complete graph this is fine, but the TravelingSalesman model in this codebase uses a general SimpleGraph. The issue should clarify how missing edges are handled — typically by assigning a large weight or by noting that the formulation naturally handles sparse graphs (non-edges simply don't contribute distance terms, but the tour must still use only existing edges). This may affect correctness if the optimal QUBO solution encodes a tour using a non-edge.

3. Example not fully worked: The example section describes the structure of the 9×9 QUBO matrix but does not show the actual matrix entries. A fully worked example should show at least a few concrete $Q[i,j]$ values so the reader can verify by hand. The "Target" subsection just says "9×9 QUBO matrix Q with penalty and distance terms" — this should be expanded.

4. Symbol m: Defined as $m = |E|$ in the Notation section but never used elsewhere. Either use it or remove it.

Recommendations

• Expand the overhead table formula to num_vertices^2 to match code getter names.
• Clarify handling of non-complete graphs (missing edges) in the reduction algorithm.
• Show 3–5 concrete Q matrix entries in the example to make it fully verifiable.
• Remove unused symbol $m$ from the notation section.