Quantum Information & Computation
Volume 25, Issue 1
RESEARCH ARTICLE Open access

An Efficient Quantum Algorithm for the Traveling Salesman Problem

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

Author affiliations
  • Anant Sharma1
  • Nupur Deshpande2
  • Sanchita Ghosh3
  • Sreetama Das4
  • Shibdas Roy5
  1. Department of Physics, Université de Bourgogne, Dijon, France; Center for Quantum Engineering, Research and Education (CQuERE), TCG CREST, Kolkata, India
  2. Department of Physics, Indian Institute of Science Education and Research (IISER), Tirupati, India
  3. Center for Quantum Engineering, Research and Education (CQuERE), TCG CREST, Kolkata, India; Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, 2628 CD Delft, The Netherlands
  4. Instituto de Física Interdisciplinar y Sistemas Complejos (IFISC), UIB-CSIC UIB Campus, E-07122 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; Department of Physics and Astronomy, University of Florence, Sesto Fiorentino, Italy
  5. Center for Quantum Engineering, Research and Education (CQuERE), TCG CREST, Kolkata, India; Academy of Scientific and Innovative Research (AcSIR), Ghaziabad, India

pp. 71-81 · 10.2478/qic-2025-0004

Read PDF View on Reference Global
On this page

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 N P -hard with a brute-force complexity of O(NN) or O(N2 N) 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(NN /2) or O(NN). 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(N3 log(N) κ / ϵ + 1/ ϵ3), where the errors ϵ are O(1/poly(N)), and κ is the not-too-large condition number of the matrix encoding all Hamiltonian cycles.
Open accessCC BY-NC-ND 4.0

Keywords

  • traveling salesman problem
  • Hamiltonian cycle problem
  • efficient quantum algorithm

Suggested citation

Anant Sharma, Nupur Deshpande, Sanchita Ghosh, Sreetama Das, Shibdas Roy (2025). An Efficient Quantum Algorithm for the Traveling Salesman Problem. Quantum Information & Computation, 25(1), 71-81. https://doi.org/10.2478/qic-2025-0004

Download BibTeX

References (24)

  1. M. A. Nielsen and I. L. Chuang (2002). Quantum Computation and Quantum Information, Cambridge University Press.DOI: 10.1119/1.1463744Google Scholar
  2. G. Dantzig, R. Fulkerson and S. Johnson (1954). “Solution of a large-scale traveling-salesman problem”. Operations Research, 2, 393.DOI: 10.1287/opre.2.4.393Google Scholar
  3. M. Grötschel and O. Holland (1991). “Solution of large-scale symmetric travelling salesman problems”. Mathematical Programming, 51, 141.DOI: 10.1007/BF01586932Google Scholar
  4. M. Padberg and G. Rinaldi (1991). “A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems”. SIAM Review, 33, 60.DOI: 10.1137/1033004Google Scholar
  5. D. Applegate, R. Bixby, V. Chvátal and W. Cook (1998). “On the solution of traveling salesman problems”. Documenta Mathematica, 3, 645.DOI: 10.4171/dms/1-3/62Google Scholar
  6. J. D. C. Little, K. G. Murty, D. W. Sweeney and C. Karel (1963). “An algorithm for the traveling salesman problem”. Operations Research, 11, 972.DOI: 10.1287/opre.11.6.972Google Scholar
  7. M. Held and R. M. Karp (1971). “The traveling-salesman problem and minimum spanning trees: Part II”. Mathematical Programming, 1, 6.DOI: 10.1007/BF01584070Google Scholar
  8. D. Applegate, R. Bixby, V. Chvátal and W. Cook (2003). “Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems”. Mathematical Programming, 97, 91.DOI: 10.1007/s10107-003-0440-4Google Scholar
  9. V. Černý (1985). “Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm”. Journal of Optimization Theory and Applications, 45, 41.DOI: 10.1007/BF00940812Google Scholar
  10. H. He (2024). “Quantum annealing and GNN for solving TSP with QUBO”, in S. Ghosh and Z. Zhang (eds), Algorithmic Aspects in Information and Management (AAIM) 2024, Lecture Notes in Computer Science, 15180, Singapore: Springer.DOI: 10.1007/978-981-97-7801-0_12Google Scholar
  11. R. Martoňák, G. E. Santoro and E. Tosatti (2004). “Quantum annealing of the traveling-salesman problem”. Physical Review E, 70, 057701.DOI: 10.1103/PhysRevE.70.057701Google Scholar
  12. E. Rodriguez, E. Osaba and I. Oregi (2022). “Analyzing the behaviour of D-Wave quantum annealer: fine-tuning parameterization and tests with restrictive Hamiltonian formulations”, in 2022 IEEE Symposium Series on Computational Intelligence (SSCI), 938–946.DOI: 10.1109/SSCI51031.2022.10022300Google Scholar
  13. W. Qian, R. A. M. Basili, M. M. Eshaghian-Wilner, A. Khokhar, G. Luecke and J. P. Vary (2023) “Comparative study of variations in quantum approximate optimization algorithms for the traveling salesman problem”. Entropy, 25, 1238.DOI: 10.3390/e25081238Google Scholar
  14. A. Matsuo, Y. Suzuki, I. Hamamura and S. Yamashita (2023). “Enhancing VQE convergence for optimization problems with problem-specific parameterized quantum circuits”. IEICE Transactions on Information and Systems, E106.D, 1772.DOI: 10.1587/transinf.2023EDP7071Google Scholar
  15. J. Bang, J. Ryu, C. Lee, S. Yoo, J. Lim and J. Lee (2013). “A quantum heuristic algorithm for the traveling salesman problem.” Journal of the Korean Physical Society, 61, 1944.DOI: 10.3938/jkps.61.1944Google Scholar
  16. K. Srinivasan, S. Satyajit, B. K. Behera and P. K. Panigrahi (2018). “Efficient quantum algorithm for solving travelling salesman problem: An IBM quantum experience.” arXiv:1805.10928.Google Scholar
  17. A. Moylett, N. Linden and A. Montanaro (2017). “Quantum speedup of the traveling-salesman problem for boundeddegree graphs.” Physical Review A, 95, 032323.DOI: 10.1103/PhysRevA.95.032323Google Scholar
  18. C. Tszyunsi and I. I. Beterov (2023). “A quantum algorithm for solving the travelling salesman problem by quantum phase estimation and quantum search”. Journal of Experimental and Theoretical Physics, 137, 210.DOI: 10.1134/S1063776123080095Google Scholar
  19. A. W. Harrow, A. Hassidim and S. Lloyd (2009). “Quantum algorithm for linear systems of equations”. Physical Review Letters, 103, 150502.DOI: 10.1103/PhysRevLett.103.150502Google Scholar
  20. D. W. Berry, G. Ahokas, R. Cleve and B. C. Sanders (2006). “Efficient quantum algorithms for simulating sparse Hamiltonians”. Communications in Mathematical Physics, 270, 359.DOI: 10.1007/s00220-006-0150-xGoogle Scholar
  21. S. Lloyd, M. Mohseni and P. Rebentrost (2014). “Quantum principal component analysis”. Nature Physics, 10: 631, 79DOI: 10.1038/nphys3029Google Scholar
  22. M. Kjaergaard, M. E. Schwartz, A. Greene, G. O. Samach, A. Bengtsson, M. O’Keeffe, et al. (2022). “Demonstration of density matrix exponentiation using a superconducting quantum processor”. Physical Review X, 12, 011005.DOI: 10.1103/PhysRevX.12.011005Google Scholar
  23. TSP-Data. Tests of Our Empirical Method for TSP. Available at: https://shorturl.at/npLN7 (Accessed on 5 February 2025).Google Scholar
  24. S. Kimmel, C. Y.-Y. Lin, G. H. Low, M. Ozols and T. J. Yoder (2017). “Hamiltonian simulation with optimal sample complexity”. npj Quantum Information, 3, 13.DOI: 10.1038/s41534-017-0013-7Google Scholar