⚛️ quantum physics

Traveling Salesman Problem with a preprocessing method for classical and quantum optimization

This paper proposes a preprocessing strategy for the Traveling Salesman Problem that reduces model complexity by limiting candidate arcs to the lowest-cost neighbors, thereby improving computational efficiency and scalability for both classical and quantum optimization solvers.

Original authors: Alessia Ciacco, Luigi Di Puglia Pugliese, Francesca Guerriero

Published 2026-03-25

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Alessia Ciacco, Luigi Di Puglia Pugliese, Francesca Guerriero

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a delivery driver with a list of 50 cities to visit. Your goal is to find the shortest possible route that takes you to every single city exactly once and brings you back home. This is the famous Traveling Salesman Problem (TSP).

While the idea sounds simple, the math behind it is a nightmare. If you have 50 cities, the number of possible routes is so huge it's like trying to find a specific grain of sand on every beach on Earth, all at once. Computers get overwhelmed trying to check every single possibility.

This paper introduces a clever "shortcut" to help both traditional computers and the new, futuristic Quantum Computers solve this puzzle faster. Here is the breakdown using simple analogies:

1. The Problem: The "Too Many Choices" Trap

Think of the cities as dots on a piece of paper. To solve the problem, a computer has to draw a line between every possible pair of dots.

The Issue: As you add more cities, the number of lines explodes. It's like trying to navigate a maze where every intersection has 50 different paths to choose from. The computer gets stuck in the "maze" because there are too many dead ends to check.
The Quantum Hurdle: New Quantum Computers are powerful, but they are like "high-performance race cars with very small gas tanks." They can't handle huge, complex mazes yet. If you give them a map with too many roads, they run out of fuel (computing power) before they finish.

2. The Solution: The "Smart Filter" (CAF)

The authors created a preprocessing method called Cost-Based Arc Filtering (CAF). Think of this as a Smart GPS that cleans up your map before you even start driving.

Instead of looking at every possible road between cities, the Smart Filter says:

"Hey, if you are in City A, you probably don't need to consider driving to City Z if it's 500 miles away, when City B is only 5 miles away. Let's just keep the 10 closest neighbors for every city and throw away the long, expensive roads."

The Magic Rule:
The authors used a mathematical trick (based on a theorem by Dirac) to prove that even if you throw away 70% of the roads, you still have enough roads left to form a perfect loop. It's like pruning a tree: you cut off the dead branches, but the tree is still alive and can still bear fruit.

3. The Results: Smaller Maps, Faster Trips

The team tested this on standard maps used by scientists (called TSPLIB) using two types of computers:

Traditional Computers (The Workhorses):
- Without the filter: The computer had to check millions of paths. It took a long time.
- With the filter: The computer only had to check a fraction of the paths. It solved the problem 30% to 50% faster and could handle larger maps that were previously too difficult.
Quantum Computers (The Race Cars):
- Without the filter: The Quantum computer was too small to handle the big maps. It couldn't even start the race.
- With the filter: By shrinking the map, the Quantum computer could actually run the race! They were able to solve problems with up to 15 cities (which is a big deal for current Quantum tech) and found better solutions than they could without the filter.

4. Why This Matters

This paper is like giving a pair of binoculars to a hiker.

Before, the hiker (the computer) was looking at the whole forest and getting confused by every single leaf.
Now, with the "Smart Filter," the hiker only looks at the clear, well-worn paths.

The Takeaway:
You don't need a bigger, more expensive computer to solve hard problems. Sometimes, you just need a smarter way to look at the data. By filtering out the "noise" (the long, unlikely roads) before the computer starts working, we make the problem manageable for both today's computers and the quantum computers of the future.

In short: They taught the computer to ignore the long, boring detours so it can focus on finding the perfect, shortest route much faster.

1. Problem Definition

The paper addresses the Traveling Salesman Problem (TSP), a fundamental NP-hard combinatorial optimization problem. The objective is to find the minimum-cost Hamiltonian cycle (a route visiting every city exactly once and returning to the start) in a complete graph $G=(V, A)$ .

The primary challenge highlighted is the exponential growth of the search space and the computational burden imposed by the large number of decision variables and constraints (specifically subtour elimination constraints) required in standard Integer Linear Programming (ILP) formulations. This complexity is particularly acute for Quantum Annealing (QA) and hybrid quantum-classical solvers, which currently suffer from hardware limitations (qubit count and connectivity) that restrict them to solving only very small instances.

2. Methodology: Cost-Based Arc Filtering (CAF)

The authors propose a novel preprocessing strategy called Cost-Based Arc Filtering (CAF) to reduce the model size while guaranteeing solution feasibility.

Core Concept: Instead of considering all possible arcs in a complete graph ( $|A| = n(n-1)$ ), the method restricts the candidate set to the $k$ lowest-cost neighbors for each vertex.
Theoretical Basis: The method is grounded in Dirac's Theorem from graph theory, which states that a graph with $n$ vertices is Hamiltonian if the minimum degree $\delta(G) \geq n/2$ .
Algorithm:
1. For each vertex $i$ , sort all other vertices $j$ by increasing travel cost $c_{ij}$ .
2. Retain only the first $k = \lceil n/2 \rceil$ neighbors.
3. Construct a reduced graph $\tilde{G}$ containing only these selected arcs.
Feasibility Guarantee: By setting $k = \lceil n/2 \rceil$ , the authors prove (Theorem 1) that the reduced graph maintains a minimum degree sufficient to guarantee the existence of at least one Hamiltonian cycle. Thus, the problem remains feasible.
Optimality Rationale: While the method does not guarantee the original optimal solution is preserved in the reduced set, it leverages the geometric properties of Euclidean TSP instances. In such problems, optimal tours typically consist of short, local connections rather than long-distance arcs. CAF effectively filters out long-distance, high-cost connections, concentrating the search space on the most promising regions.

3. Experimental Setup

The study evaluates the CAF method using both classical and quantum optimization frameworks:

Datasets: Benchmark instances from the TSPLIB library (specifically derived from berlin52.tsp), ranging from 5 to 50 vertices.
Classical Solver: Gurobi Optimizer 11.0.1 (ILP formulation).
Quantum Solver: D-Wave's Leap CQM Hybrid solver (Constrained Quadratic Model) running on the Advantage2_system1.4 quantum processing unit (4596 qubits).
Metrics: Number of decision variables, computational time, optimality gap, and solution quality.

4. Key Results

A. Impact on Model Size

Variable Reduction: CAF reduces the number of decision variables by approximately 30% on average across all instance sizes.
Scalability: The reduction becomes more significant as the number of vertices ( $V$ ) increases. For example, with $V=50$ , the variable count drops from 2,450 (standard) to 1,652 (CAF).

B. Classical Optimization Performance

Optimality Preservation: For instances up to $V=20$ , CAF preserved the optimal objective value (0% gap) compared to the full formulation.
Computational Efficiency: CAF significantly reduced solving times.
- At $V=18$ , time dropped from ~107s to ~57s.
- At $V=19$ , time dropped from ~257s to ~139s.
- At $V=20$ , time was reduced by more than half (from ~670s to ~316s).
Large Instances: For $V=21$ , the standard model hit the 300-second time limit without finding a valid lower bound, whereas the CAF model found a valid solution with a lower objective value, demonstrating superior tractability.

C. Quantum Optimization Performance

Solvability: The hybrid quantum solver could reliably solve instances up to $V=15$ only when CAF was applied. Larger instances were intractable without preprocessing.
Solution Quality: CAF significantly improved the quality of solutions found by the quantum solver:
- Optimality Gap: The average gap was reduced by approximately 29–31%. For instance, at $V=13$ , the gap dropped from 43% (without CAF) to 11% (with CAF).
- Success Rate: For $V=15$ , the solver successfully solved 40% of runs with CAF, whereas the unfiltered model struggled significantly.
Efficiency: Average solution time decreased by roughly 5–17% depending on the instance size, as the reduced model allowed the solver to converge faster.

5. Key Contributions

Theoretical Guarantee: The paper provides a rigorous proof that a specific arc filtering strategy ( $k = \lceil n/2 \rceil$ ) preserves the feasibility of the TSP by satisfying Dirac's condition for Hamiltonian graphs.
Bridging Classical and Quantum: It demonstrates that a simple preprocessing step can make TSP instances tractable for current quantum hardware, enabling the solution of instances ( $V=15$ ) that are typically too large for direct quantum formulation.
Benchmarking on Real Data: Unlike many quantum TSP studies that use artificially generated toy problems, this research utilizes established TSPLIB benchmarks, providing a realistic assessment of quantum optimization potential.
Dual-Utility: The method is shown to be beneficial for both classical solvers (reducing time and improving scalability) and quantum solvers (enabling larger problem sizes and improving solution quality).

6. Significance

This work addresses a critical bottleneck in applying quantum computing to combinatorial optimization: model size. By proving that a significant portion of the search space (long-distance arcs) can be safely discarded without destroying feasibility, the authors provide a practical pathway to scale quantum optimization. The results suggest that preprocessing is not merely an optional step but a necessity for solving real-world routing problems on near-term quantum hardware. Furthermore, the method enhances the scalability of classical solvers, offering immediate value for traditional operations research applications.