Quantum iterative approach to the Traveling Salesman Problem
Abstract
The Traveling Salesman Problem (TSP) is a classical NP-hard problem in combinatorial optimization, where determining the shortest route among a set of cities becomes computationally prohibitive as the problem size increases. This work explores quantum computing as an alternative approach to address this complexity. Unlike existing methods that primarily rely on quantum annealing, we propose a quantum iterative framework integrating Quantum Phase Estimation (QPE) and Grover's search algorithm. Route costs are encoded as quantum phases, enabling QPE to efficiently evaluate them, while Amplitude Amplification, implemented via the Grover-Long algorithm, iteratively refines the solution space toward the optimal route. A proof-of-concept case study on a small-scale TSP instance demonstrates the feasibility of this approach and its potential for scaling to larger optimization problems. Furthermore, under an expectation-based analysis, the algorithm exhibits an expected computational complexity of O(m2log2(m)log2(1/ε)/√ε) which depends on the error tolerance parameter ε. This estimation omits the initialization term, which we expect future refinements to render subdominant to Phase Estimation.
Versions
Related
- Exact cost of the Euclidean Maximum Traveling Salesman Problem in one dimension
- Quantum Heuristic Separation of Comb Inequalities for the Travelling Salesman Problem
- Grover Search for a Threshold-Fraction Variant of the Travelling Salesman Problem: A Circuit-Level Construction
- Near-Quantum-Limited Readout for the Princeton Axion Search using a sub-GHz Kinetic Inductance Traveling Wave Parametric Amplifier
- Metastability, collective excitations, and traveling states of one-dimensional spin-orbit-coupled quantum droplets
BibTeX
@misc{rodriguezalmazan2026quantum,
title = {{Quantum iterative approach to the Traveling Salesman Problem}},
author = {Arturo Rodríguez-Almazán and Guillermo Rivas and Ricardo S. Alonso and Daniela Falcó and Mir Amir Hosseini},
howpublished = {arXiv},
year = {2026},
month = jun,
doi = {10.48550/arxiv.2606.11843},
eprint = {2606.11843},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.11843},
}
RIS
TY - UNPB
TI - Quantum iterative approach to the Traveling Salesman Problem
AU - Arturo Rodríguez-Almazán
AU - Guillermo Rivas
AU - Ricardo S. Alonso
AU - Daniela Falcó
AU - Mir Amir Hosseini
PY - 2026
DA - 2026/06/10
PB - arXiv
DO - 10.48550/arxiv.2606.11843
UR - https://arxiv.org/abs/2606.11843
AB - The Traveling Salesman Problem (TSP) is a classical NP-hard problem in combinatorial optimization, where determining the shortest route among a set of cities becomes computationally prohibitive as the problem size increases. This work explores quantum computing as an alternative approach to address this complexity. Unlike existing methods that primarily rely on quantum annealing, we propose a quantum iterative framework integrating Quantum Phase Estimation (QPE) and Grover's search algorithm. Route costs are encoded as quantum phases, enabling QPE to efficiently evaluate them, while Amplitude Amplification, implemented via the Grover-Long algorithm, iteratively refines the solution space toward the optimal route. A proof-of-concept case study on a small-scale TSP instance demonstrates the feasibility of this approach and its potential for scaling to larger optimization problems. Furthermore, under an expectation-based analysis, the algorithm exhibits an expected computational complexity of O(m^2log_2(m)log_2(1/ε)/√ε) which depends on the error tolerance parameter ε. This estimation omits the initialization term, which we expect future refinements to render subdominant to Phase Estimation.
ER -