An Efficient Quantum Algorithm for the Traveling Salesman Problem

Year: 2025

Authors: Sharma A., Deshpande N., Ghosh S., Das S., Roy S.

Autors Affiliation: Univ Bourgogne, Dept Phys, F-21000 Bourgogne, France; TCG CREST, Ctr Quantum Engn Res & Educ CQuERE, Kolkata 700091, India; Indian Inst Sci Educ & Res IISER, Dept Phys, Tirupati 517507, India; Delft Univ Technol, Fac Elect Engn Math & Comp Sci, NL-2628 CD Delft, Netherlands; UIB CSIC, Inst Fis Interdisciplinar & Sistemas Complejos IFI, UIB Campus, E-07122 Palma De Mallorca, Spain; Consiglio Nazl Ric CNR INO, Ist Nazl Ott, I-50125 Florence, Italy; European Lab Nonlinear Spect LENS, I-50019 Sesto Fiorentino, Italy; Univ Florence, Dept Phys & Astron, I-50019 Sesto Fiorentino, Italy; Acad Sci & Innovat Res AcSIR, Ghaziabad 201002, India.

Abstract: The traveling salesman problem is the problem of finding out the shortest route in a network of cities, that a salesman needs to travel to cover all the cities, without visiting the same city more than once. This problem is known to be NP-hard with a brute-force complexity of O(N-N) or O(N-2N) for N number of cities. This problem is equivalent to finding out the shortest Hamiltonian cycle in a given graph, if at least one Hamiltonian cycle exists in it. Quantum algorithms for this problem typically provide with a quadratic speedup only, using Grover’s search, thereby having a complexity of O(N-N/2) or O(N-N). We present a bounded-error quantum polynomial-time (BQP) algorithm for solving the problem, providing with an exponential speedup. The overall complexity of our algorithm is O(N-3 log(N)kappa/epsilon+ 1/epsilon(3)), where the errors varepsilon; are O(1/poly(N)), and kappa is the not-too-large condition number of the matrix encoding all Hamiltonian cycles.

Journal/Review: QUANTUM INFORMATION & COMPUTATION

Volume: 25 (1)      Pages from: 71  to: 81

More Information: S. D. acknowledges financial support from the European Union’s Horizon 2020 research and innovation program under FET-OPEN Grant Agreement No. 828946 (PATHOS) and from the European Commission’s Horizon Europe Framework Programme under Research and Innovation Action Grant Agreement No. 101070546 (MUQUABIS).
KeyWords: traveling salesman problem; Hamiltonian cycle problem; efficient quantum algorithm
DOI: 10.2478/qic-2025-0004