Paper 2024/626

Exponential Quantum Speedup for the Traveling Salesman Problem

Anant Sharma, TCG Centres for Research and Education in Science and Technology, Kolkata, India
Nupur Deshpande, Indian Institute of Science Education and Research (IISER), Tirupati, India
Sanchita Ghosh, TCG Centres for Research and Education in Science and Technology, Kolkata, India
Sreetama Das, Istituto Nazionale di Ottica del Consiglio Nazionale delle Ricerche (CNR-INO), Florence, Italy, University of Florence, Sesto Fiorentino, Italy
Shibdas Roy, TCG Centres for Research and Education in Science and Technology, Kolkata, India, Academy of Scientific and Innovative Research (AcSIR), Ghaziabad, India

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 $\epsilon$ are $O(1/{\rm poly}(N))$, and $\kappa$ is the not-too-large condition number of the matrix encoding all Hamiltonian cycles.

Note: Corrections to text below Eq. (9) on the conditional Hamiltonian evolution that is required for the "improved" phase estimation from HHL (Ref. [19]), as outlined at the end of our Section III and used in LMR (Ref. [21]).

Available format(s)
Publication info
Traveling Salesman ProblemHamiltonian Cycle ProblemQuantum AlgorithmExponential Speedup
Contact author(s)
anantsharma2410 @ gmail com
rajeshdeshpande @ students iisertirupati ac in
sanchita ghosh14 @ gmail com
sreetama das @ ino cnr it
roy shibdas @ gmail com
2024-05-24: last of 9 revisions
2024-04-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Anant Sharma and Nupur Deshpande and Sanchita Ghosh and Sreetama Das and Shibdas Roy},
      title = {Exponential Quantum Speedup for the Traveling Salesman Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2024/626},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.