Quantum iterative approach to the Traveling Salesman Problem

arXiv:2606.11843 · quant-ph · Submitted 2026-06-10 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: Today's paper: "Quantum iterative approach to the Traveling Salesman Problem".

Mira: The gist:

Kai: First, who's behind it and why it matters.

Title and authors: Kai: So we're looking at this paper today, "Quantum iterative approach to the Traveling Salesman Problem," and it's written by Rodríguez-Almazán, Rivas, Alonso, Falcó, and Hosseini. I want to keep it simple about what this is trying to do.

Mira: It’s tackling the Traveling Salesman Problem by using a combination of two quantum tools: Quantum Phase Estimation and Grover's search algorithm. Basically, they are trying to find the shortest route among many cities without having to check every single possible route one by one classically.

Lev: I mean, I see that they are proposing this iterative framework where costs become quantum phases and then amplitude amplification refines the solution space toward the optimal route. That sounds like a way to search much smarter than just brute force.

Kai: Exactly. They’re using QPE to compute those route costs efficiently, and then Grover-Long for that iterative refinement part, which is a modification of Grover’s search that uses phase rotations instead of just phase flips.

Mira: The core idea is encoding the route costs as quantum phases so that QPE can evaluate them well, and then using amplitude amplification to iteratively narrow down the search space until you find the best route.

Lev: It’s interesting how they set up the states, constructing those states of form Cost⟩ ⊗ Route⟩, where each route is represented by a bitstring in that register. That structure is what makes this iterative solver work for TSP.

The paper's summary: Kai: The paper summarizes how this quantum iterative approach tackles the TSP by setting up these states and then applying the appropriate operators to find the solution. They show a proof-of-concept case study with four towns in Salamanca, Spain to demonstrate how it works in practice.

Mira: That case study shows that even for small instances, you can see how many iterations are needed to identify the minimum route based on which state you select at each step. It also shows that they tested an asymmetric version incorporating altitude differences and found that cost fluctuations don't really affect the performance when those differences are big enough.

Lev: So, for someone trying to run this on actual hardware, they’re looking at a computational complexity estimate of O(m squared log2(m) log2(one/ϵ) √ϵ), which is compared against classical Held-Karp algorithms with complexity O(2mm2) <ref:2606.11843#pg1>. That shows the theoretical potential for scaling up beyond what we see now.

Kai: And the paper also breaks down the QPE part pretty thoroughly, showing how applying the inverse Quantum Fourier Transform to that control register makes it possible to access the phase information associated with a specific operator.

Mira: The summary emphasizes that they are moving away from just relying on quantum annealing by proposing this specific iterative framework for solving TSP. That’s a shift in approach to handling this NP-hard problem.

The paper's improvements: Kai: One of the key improvements they suggest is the structure of their solver, which builds those states of form Cost⟩ ⊗ Route⟩, where the size of that route register is m(ceil(log2(m))). That’s a specific way they manage the search space bitstring.

Mira: They are also addressing how to handle asymmetric TSP instances, like when you introduce altitude differences, by using an adjusted cost formula of c' = c1 − ∆y/two to help reduce those cost fluctuations <ref:2606.11843#pg1>.

Lev: From an engineering standpoint, their complexity analysis focuses on the Phase Estimation induced complexity which they estimate at O(m log2(one/ϵ)) when considering m diagonal operators Qj <ref:2606.11843#pg1>. That’s a big win if you want to see how the scaling really behaves for large inputs.

Kai: So, one of the ways they improve it is by setting up the operator U as U = m O−1j=zero Qj, which ties the cost encoding directly into that iterative structure they use with Grover-Long <ref:2606.11843#pg3>.

Mira: They are also pointing out that real-time route optimization for dynamic logistics systems could be a big application, integrating QPE for cost evaluation and Amplitude Amplification to refine the route quickly.

Conclusion: Kai: So to wrap up the paper "Quantum iterative approach to the Traveling Salesman Problem," they show that this combination of QPE and Grover-Long provides an iterative way to solve TSP by encoding costs as phases. The proof-of-concept on four cities in Salamanca, Spain, gives a tangible demonstration of how it functions.

Mira: The results suggest that even with the complexity involved, this quantum framework offers a path to handle asymmetric TSP instances better than some existing methods because they adjusted the cost formula helps manage those fluctuations.

Lev: I still see the primary challenge being the overhead for running this on real hardware, and while their complexity estimate is good for theory, we need to figure out how many qubits it actually takes before error correction makes it impractical for something like a large logistics problem.

Kai: It really depends on the error tolerance parameter epsilon they use; that factor shows how sensitive the result is to the precision you demand in this quantum search.

Mira: Overall, this work introduces a specific iterative quantum algorithm for TSP, and it’s an interesting step because it moves beyond just using a simple annealing approach for these combinatorial problems.

Lev: I'm looking forward to seeing how they address those scalability issues when moving from four towns in Spain to something with hundreds of cities.

Kai: Definitely keep an eye on this work; the iterative nature is what makes it stand out compared to standard search methods.

Arturo Rodriguez-Almazán, Guillermo Rivas, Ricardo S. Alonso, Daniela Falcó

AIR Institute · BISITE Research Group, University of Salamanca, International University of La Rioja

quant-ph

Submitted: 2026-06-10

Updated: 2026-06-10

DOI: 10.1088/1402-4896/aeb04d

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 75/100

The gist: The gist: This work proposes a quantum iterative framework integrating Quantum Phase Estimation and Grover’s search algorithm to solve the Traveling Salesman Problem by encoding route costs as

Key concepts

Traveling Salesman Problem (TSP)
The TSP is a classic optimization problem where the goal is to find the shortest possible route that visits every city exactly once and returns to the start. The difficulty grows exponentially with more cities because the number of possible routes becomes too large for classical computers to check all of them.
Quantum Phase Estimation (QPE)
QPE is a quantum algorithm used to estimate an unknown eigenvalue associated with a quantum operator. In this paper, it is used to efficiently calculate route costs by encoding these costs as specific quantum phases, which helps determine the optimal path information.
Amplitude Amplification (Grover-Long)
This technique enhances the probability of finding a desired solution in a search space. The Grover-Long algorithm modifies standard Grover's search by using distinct phase rotations to iteratively amplify the amplitude of states representing better routes, guiding the process toward the shortest path.
Quantum Phase Encoding
This involves representing numerical data, like route costs, as quantum phases within a unitary operator. By encoding costs as specific phases (e.g., $A_{ij} = e^{-2 imes ext{pi}i ilde{ heta}_{ij}}$), the algorithm can use QPE to extract this phase information without directly measuring the costly physical states.

Terminology

Summary

The gist: This work proposes a quantum iterative framework integrating Quantum Phase Estimation and Grover’s search algorithm to solve the Traveling Salesman Problem by encoding route costs as quantum phases and iteratively refining the solution space.

Problem and Motivation

The Traveling Salesman Problem (TSP) is an NP-hard problem in combinatorial optimization where determining the shortest route among a set of cities becomes computationally prohibitive as the problem size increases It involves finding the shortest possible route that visits a given set of cities exactly once and returns to the starting point, minimizing the total travel distance or cost. The complexity arises because as the number of cities increases, the number of possible routes grows factorially, leading to an exponential growth in the search space. This work explores quantum computing as an alternative approach to address this complexity.

Quantum Algorithms Utilized

The proposed methodology integrates two prominent quantum algorithms: Quantum Phase Estimation (QPE) and Grover’s search algorithm. QPE is utilized to compute route costs by encoding them as quantum phases, while Amplitude Amplification, implemented via the Grover-Long algorithm, iteratively refines the solution space toward the optimal route.

Quantum Phase Estimation (QPE)

The Quantum Phase Estimation (QPE) algorithm enables quantum computers to estimate the eigenvalue corresponding to an eigenstate of an operator. Given an operator U and a state ψ⟩ that is eigenstate of U, the objective of Phase Estimation is to find the value ϕ such that U ψ⟩ = e 2iπϕ ψ⟩. The algorithm commences with the initialization of two quantum registers: a control register comprising n qubits set to 0⟩ and a target register prepared in the eigenstate ψ⟩. After applying Hadamard gates to the control register, the controlled application of U is performed, encoding phase information into the control qubits by the phase kick-back phenomenon. Following this encoding process, an inverse Quantum Fourier Transform is applied to the control register to transform the superposition into a state in which the binary representation of the phase ϕ is accessible.

Amplitude Amplification (Grover-Long)

Amplitude Amplification enhances the probability of achieving specific states given an initial superposition by repeatedly applying two key operators: the oracle and the amplification operator. The Grover-Long algorithm, a modification of Grover’s search, involves executing distinct phase rotations instead of just phase flips. The process involves constructing states of the form Cost⟩ ⊗ Route⟩, represented as C⟩ ⊗ R⟩. The oracle introduces a ϕ phase shift in the desired states, and the amplification operator amplifies the amplitude of the marked states by reflecting them around the average amplitude of all states.

TSP Iterative Solver Structure

The TSP iterative solver constructs states of the form Cost⟩ ⊗ Route⟩, where each route is represented by a bitstring in the R⟩ register. The number of qubits for the R⟩ register is m⌈log2(m)⌉, where m represents the number of cities and ⌈log2(m)⌉ is the first integer greater than log2(m). The cost values are introduced as phases through a matrix A such that Aij = e-2πiϕij, and the final operator U is expressed as U = mO−1j=0 Qj.

Computational Complexity

The expected computational complexity of the algorithm is estimated at O(m squared log2(m) log2(1/ϵ) √ϵ), which depends on the error tolerance parameter ϵ. This estimation omits the initialization term, which is expected to be subdominant to Phase Estimation in future refinements. The complexity analysis focuses on the Phase Estimation induced complexity, which is O(m log2(1/ϵ)) when considering m diagonal operators Qj.

Case Study Application

A proof-of-concept case study was conducted on a small-scale TSP instance involving four towns in the province of Salamanca, Spain. The simulation utilized a symmetric TSP problem where route costs were represented by bitstrings and their corresponding costs in kilometers. The results demonstrated how the number of iterations required to identify the minimum can vary depending on the state selected in each step. The analysis was extended to an asymmetric version by incorporating altitude differences, showing that fluctuations in costs do not affect the algorithm’s performance when d is sufficiently large.

Conclusion

The study introduced a quantum iterative algorithm designed to address the Traveling Salesman Problem by integrating Quantum Phase Estimation and Amplitude Amplification through the Grover-Long algorithm. The practical applicability was demonstrated through a case study involving four cities in the province of Salamanca, Spain. Significant challenges remain regarding scalability and the efficient implementation of some of the quantum subroutines utilized. The results underscore the potential of quantum algorithms to address the Traveling Salesman Problem.

Acknowledgements

This work has been funded by the Centro para el Desarrollo Tecnológico y la Innovación (CDTI) under the Cervera Programme – Network of Excellence, promoted by the Spanish Ministry of Science and Innovation, through the project “Alianza de centros tecnológicos para el Quantum computing Accesible y dual en Defensa y sectores Estratégicos (ARQADE)”.

References

[1] Merrill M. Flood. The Traveling-Salesman Problem. Operations Research, 4(1):61–75, 1956

[2] Lov K Grover. Quantum mechanics helps in searching for a needle in a haystack. Physical review letters, 79(2):325, 1997

[3] A Yu Kitaev. Quantum measurements and the abelian stabilizer problem. arXiv preprint quant-ph/9511026, 1995

[4] Egon Balas and Paolo Toth. Branch and bound methods for the traveling salesman problem. 1983

[5] Richard Bellman. Dynamic Programming Treatment of the Travelling Salesman Problem. J. ACM, 9(1):61–63, January 1962

[6] Michael Held and Richard M Karp. A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied mathematics, 10(1):196–210, 1962

[7] Shen Lin and Brian W Kernighan. An effective heuristic algorithm for the traveling-salesman problem. Operations research, 21(2):498–516, 1973

[8] Roman Martoňák, Giuseppe E Santoro, and Erio Tosatti. Quantum annealing of the travelingsalesman problem. Physical Review E—Statistical, Nonlinear, and Soft Matter Physics, 70(5):057701, 2004

[9] Richard H Warren. Adapting the traveling salesman problem to an adiabatic quantum computer. Quantum information processing, 12(4):1781–1785, 2013

[10] Kapil Goswami, Gagan Anekonda Veereshi, Peter Schmelcher, and Rick Mukherjee. Solving the travelling salesman problem using a single qubit. arXiv preprint arXiv:2407.

Improvements for AI systems

  1. textbfReal-time Route Optimization for Dynamic Logistics Systems: The improved system can solve large-scale Traveling Salesman Problems (TSP) in real-time by integrating Quantum Phase Estimation (QPE) for cost evaluation with Amplitude Amplification via GroverLong to iteratively refine the optimal route, as described in Section 5 and the overall methodology.

  2. textbfEnhanced Scalability for NP-hard Combinatorial Problems: The system can address exponentially growing search spaces by employing a quantum iterative framework that achieves an expected computational complexity of O(m2 log2(m) log2(1/ϵ) √ϵ), which is compared favorably against classical Held-Karp algorithms with complexity O(2mm2).

  3. textbfIncreased Precision in Cost Estimation: The system can handle asymmetric TSP instances, such as those incorporating altitude differences, by utilizing the adjusted cost formula c' = c1 − ∆y/2 and increasing the precision of the control register by adding qubits (e.g., setting d = 7) to reduce fluctuations in costs as shown in Table 4.

Sources

Related papers