An Efficient Quantum Algorithm for the Traveling Salesman Problem

Anant Sharma; Nupur Deshpande; Sanchita Ghosh; Sreetama Das; Shibdas Roy

Paper 2024/626

An Efficient Quantum Algorithm for the Traveling Salesman Problem

Anant Sharma, Université de Bourgogne, Dijon, France, 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, Delft University of Technology, Delft, Netherlands, TCG Centres for Research and Education in Science and Technology, Kolkata, India

Sreetama Das

, Instituto de Física Interdisciplinar y Sistemas Complejos (IFISC), UIB-CSIC UIB Campus, Palma de Mallorca, Spain, Istituto Nazionale di Ottica del Consiglio Nazionale delle Ricerche (CNR-INO), Florence, Italy, European Laboratory for Non-Linear Spectroscopy (LENS), Sesto Fiorentino, 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

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 -hard with a brute-force complexity of or for 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 or . 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 , where the errors are , and is the not-too-large condition number of the matrix encoding all Hamiltonian cycles.

Note: Added Discussion and Conclusion sections, and also an Appendix with an example. Accepted in a reputed journal.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
Keywords: Traveling Salesman Problem Hamiltonian Cycle Problem Efficient Quantum Algorithm
Contact author(s): anantsharma2410 @ gmail com
dnupur79 @ gmail com
sanchita ghosh14 @ gmail com
sreetama @ ifisc uib-csic es
roy shibdas @ gmail com
History: 2025-02-26: last of 12 revisions; 2024-04-23: received; See all versions
Short URL: https://ia.cr/2024/626
License: CC BY

BibTeX

@misc{cryptoeprint:2024/626,
      author = {Anant Sharma and Nupur Deshpande and Sanchita Ghosh and Sreetama Das and Shibdas Roy},
      title = {An Efficient Quantum Algorithm for the Traveling Salesman Problem},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/626},
      year = {2024},
      url = {https://eprint.iacr.org/2024/626}
}