{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,3]],"date-time":"2026-05-03T01:23:08Z","timestamp":1777771388952,"version":"3.51.4"},"reference-count":24,"publisher":"Walter de Gruyter GmbH","issue":"1","license":[{"start":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T00:00:00Z","timestamp":1740182400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,3,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    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                    <jats:italic>N P<\/jats:italic>\n                    -hard with a brute-force complexity of\n                    <jats:italic>O<\/jats:italic>\n                    (\n                    <jats:italic>N<\/jats:italic>\n                    <jats:sup>\n                      <jats:italic>N<\/jats:italic>\n                    <\/jats:sup>\n                    ) or\n                    <jats:italic>O<\/jats:italic>\n                    (\n                    <jats:italic>N<\/jats:italic>\n                    <jats:sup>\n                      2\n                      <jats:italic>N<\/jats:italic>\n                    <\/jats:sup>\n                    ) for\n                    <jats:italic>N<\/jats:italic>\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\u2019s search, thereby having a complexity of\n                    <jats:italic>O<\/jats:italic>\n                    (\n                    <jats:italic>N<\/jats:italic>\n                    <jats:sup>\n                      <jats:italic>N<\/jats:italic>\n                      \/2\n                    <\/jats:sup>\n                    ) or\n                    <jats:italic>O<\/jats:italic>\n                    (\n                    <jats:italic>\n                      N\n                      <jats:sup>N<\/jats:sup>\n                    <\/jats:italic>\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\n                    <jats:italic>O<\/jats:italic>\n                    (\n                    <jats:italic>N<\/jats:italic>\n                    <jats:sup>3<\/jats:sup>\n                    log(\n                    <jats:italic>N<\/jats:italic>\n                    )\n                    <jats:italic>\u03ba<\/jats:italic>\n                    \/\n                    <jats:italic>\u03f5<\/jats:italic>\n                    + 1\/\n                    <jats:italic>\u03f5<\/jats:italic>\n                    <jats:sup>3<\/jats:sup>\n                    ), where the errors\n                    <jats:italic>\u03f5<\/jats:italic>\n                    are\n                    <jats:italic>O<\/jats:italic>\n                    (1\/poly(\n                    <jats:italic>N<\/jats:italic>\n                    )), and\n                    <jats:italic>\u03ba<\/jats:italic>\n                    is the not-too-large condition number of the matrix encoding all Hamiltonian cycles.\n                  <\/jats:p>","DOI":"10.2478\/qic-2025-0004","type":"journal-article","created":{"date-parts":[[2025,6,26]],"date-time":"2025-06-26T02:40:02Z","timestamp":1750905602000},"page":"71-81","source":"Crossref","is-referenced-by-count":1,"title":["An Efficient Quantum Algorithm for the Traveling Salesman Problem"],"prefix":"10.2478","volume":"25","author":[{"given":"Anant","family":"Sharma","sequence":"first","affiliation":[{"name":"Department of Physics , Universit\u00e9 de Bourgogne , Dijon , France"},{"name":"Center for Quantum Engineering, Research and Education (CQuERE), TCG CREST , Kolkata , India"}]},{"given":"Nupur","family":"Deshpande","sequence":"additional","affiliation":[{"name":"Department of Physics , Indian Institute of Science Education and Research (IISER) , Tirupati , India"}]},{"given":"Sanchita","family":"Ghosh","sequence":"additional","affiliation":[{"name":"Center for Quantum Engineering, Research and Education (CQuERE), TCG CREST , Kolkata , India"},{"name":"Faculty of Electrical Engineering, Mathematics and Computer Science , Delft University of Technology , 2628 CD Delft , The Netherlands"}]},{"given":"Sreetama","family":"Das","sequence":"additional","affiliation":[{"name":"Instituto de F\u00edsica Interdisciplinar y Sistemas Complejos (IFISC), UIB-CSIC UIB Campus , E-07122 Palma de Mallorca , Spain"},{"name":"Istituto Nazionale di Ottica del Consiglio Nazionale delle Ricerche (CNR-INO) , Florence , Italy"},{"name":"European Laboratory for Non-Linear Spectroscopy (LENS) , Sesto Fiorentino , Italy"},{"name":"Department of Physics and Astronomy , University of Florence , Sesto Fiorentino , Italy"}]},{"given":"Shibdas","family":"Roy","sequence":"additional","affiliation":[{"name":"Center for Quantum Engineering, Research and Education (CQuERE), TCG CREST , Kolkata , India"},{"name":"Academy of Scientific and Innovative Research (AcSIR) , Ghaziabad , India"}]}],"member":"374","published-online":{"date-parts":[[2025,2,22]]},"reference":[{"key":"2026042910584011836_j_qic-2025-0004_ref_001","doi-asserted-by":"crossref","unstructured":"M. A. Nielsen and I. L. Chuang (2002). Quantum Computation and Quantum Information, Cambridge University Press.","DOI":"10.1119\/1.1463744"},{"key":"2026042910584011836_j_qic-2025-0004_ref_002","doi-asserted-by":"crossref","unstructured":"G. Dantzig, R. Fulkerson and S. Johnson (1954). \u201cSolution of a large-scale traveling-salesman problem\u201d. Operations Research, 2, 393.","DOI":"10.1287\/opre.2.4.393"},{"key":"2026042910584011836_j_qic-2025-0004_ref_003","doi-asserted-by":"crossref","unstructured":"M. Gr\u00f6tschel and O. Holland (1991). \u201cSolution of large-scale symmetric travelling salesman problems\u201d. Mathematical Programming, 51, 141.","DOI":"10.1007\/BF01586932"},{"key":"2026042910584011836_j_qic-2025-0004_ref_004","doi-asserted-by":"crossref","unstructured":"M. Padberg and G. Rinaldi (1991). \u201cA branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems\u201d. SIAM Review, 33, 60.","DOI":"10.1137\/1033004"},{"key":"2026042910584011836_j_qic-2025-0004_ref_005","doi-asserted-by":"crossref","unstructured":"D. Applegate, R. Bixby, V. Chv\u00e1tal and W. Cook (1998). \u201cOn the solution of traveling salesman problems\u201d. Documenta Mathematica, 3, 645.","DOI":"10.4171\/dms\/1-3\/62"},{"key":"2026042910584011836_j_qic-2025-0004_ref_006","doi-asserted-by":"crossref","unstructured":"J. D. C. Little, K. G. Murty, D. W. Sweeney and C. Karel (1963). \u201cAn algorithm for the traveling salesman problem\u201d. Operations Research, 11, 972.","DOI":"10.1287\/opre.11.6.972"},{"key":"2026042910584011836_j_qic-2025-0004_ref_007","doi-asserted-by":"crossref","unstructured":"M. Held and R. M. Karp (1971). \u201cThe traveling-salesman problem and minimum spanning trees: Part II\u201d. Mathematical Programming, 1, 6.","DOI":"10.1007\/BF01584070"},{"key":"2026042910584011836_j_qic-2025-0004_ref_008","doi-asserted-by":"crossref","unstructured":"D. Applegate, R. Bixby, V. Chv\u00e1tal and W. Cook (2003). \u201cImplementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems\u201d. Mathematical Programming, 97, 91.","DOI":"10.1007\/s10107-003-0440-4"},{"key":"2026042910584011836_j_qic-2025-0004_ref_009","doi-asserted-by":"crossref","unstructured":"V. \u010cern\u00fd (1985). \u201cThermodynamical approach to the traveling salesman problem: An efficient simulation algorithm\u201d. Journal of Optimization Theory and Applications, 45, 41.","DOI":"10.1007\/BF00940812"},{"key":"2026042910584011836_j_qic-2025-0004_ref_010","doi-asserted-by":"crossref","unstructured":"H. He (2024). \u201cQuantum annealing and GNN for solving TSP with QUBO\u201d, 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_12"},{"key":"2026042910584011836_j_qic-2025-0004_ref_011","doi-asserted-by":"crossref","unstructured":"R. Marto\u0148\u00e1k, G. E. Santoro and E. Tosatti (2004). \u201cQuantum annealing of the traveling-salesman problem\u201d. Physical Review E, 70, 057701.","DOI":"10.1103\/PhysRevE.70.057701"},{"key":"2026042910584011836_j_qic-2025-0004_ref_012","doi-asserted-by":"crossref","unstructured":"E. Rodriguez, E. Osaba and I. Oregi (2022). \u201cAnalyzing the behaviour of D-Wave quantum annealer: fine-tuning parameterization and tests with restrictive Hamiltonian formulations\u201d, in 2022 IEEE Symposium Series on Computational Intelligence (SSCI), 938\u2013946.","DOI":"10.1109\/SSCI51031.2022.10022300"},{"key":"2026042910584011836_j_qic-2025-0004_ref_013","doi-asserted-by":"crossref","unstructured":"W. Qian, R. A. M. Basili, M. M. Eshaghian-Wilner, A. Khokhar, G. Luecke and J. P. Vary (2023) \u201cComparative study of variations in quantum approximate optimization algorithms for the traveling salesman problem\u201d. Entropy, 25, 1238.","DOI":"10.3390\/e25081238"},{"key":"2026042910584011836_j_qic-2025-0004_ref_014","doi-asserted-by":"crossref","unstructured":"A. Matsuo, Y. Suzuki, I. Hamamura and S. Yamashita (2023). \u201cEnhancing VQE convergence for optimization problems with problem-specific parameterized quantum circuits\u201d. IEICE Transactions on Information and Systems, E106.D, 1772.","DOI":"10.1587\/transinf.2023EDP7071"},{"key":"2026042910584011836_j_qic-2025-0004_ref_015","doi-asserted-by":"crossref","unstructured":"J. Bang, J. Ryu, C. Lee, S. Yoo, J. Lim and J. Lee (2013). \u201cA quantum heuristic algorithm for the traveling salesman problem.\u201d Journal of the Korean Physical Society, 61, 1944.","DOI":"10.3938\/jkps.61.1944"},{"key":"2026042910584011836_j_qic-2025-0004_ref_016","unstructured":"K. Srinivasan, S. Satyajit, B. K. Behera and P. K. Panigrahi (2018). \u201cEfficient quantum algorithm for solving travelling salesman problem: An IBM quantum experience.\u201d arXiv:1805.10928."},{"key":"2026042910584011836_j_qic-2025-0004_ref_017","doi-asserted-by":"crossref","unstructured":"A. Moylett, N. Linden and A. Montanaro (2017). \u201cQuantum speedup of the traveling-salesman problem for boundeddegree graphs.\u201d Physical Review A, 95, 032323.","DOI":"10.1103\/PhysRevA.95.032323"},{"key":"2026042910584011836_j_qic-2025-0004_ref_018","doi-asserted-by":"crossref","unstructured":"C. Tszyunsi and I. I. Beterov (2023). \u201cA quantum algorithm for solving the travelling salesman problem by quantum phase estimation and quantum search\u201d. Journal of Experimental and Theoretical Physics, 137, 210.","DOI":"10.1134\/S1063776123080095"},{"key":"2026042910584011836_j_qic-2025-0004_ref_019","doi-asserted-by":"crossref","unstructured":"A. W. Harrow, A. Hassidim and S. Lloyd (2009). \u201cQuantum algorithm for linear systems of equations\u201d. Physical Review Letters, 103, 150502.","DOI":"10.1103\/PhysRevLett.103.150502"},{"key":"2026042910584011836_j_qic-2025-0004_ref_020","doi-asserted-by":"crossref","unstructured":"D. W. Berry, G. Ahokas, R. Cleve and B. C. Sanders (2006). \u201cEfficient quantum algorithms for simulating sparse Hamiltonians\u201d. Communications in Mathematical Physics, 270, 359.","DOI":"10.1007\/s00220-006-0150-x"},{"key":"2026042910584011836_j_qic-2025-0004_ref_021","doi-asserted-by":"crossref","unstructured":"S. Lloyd, M. Mohseni and P. Rebentrost (2014). \u201cQuantum principal component analysis\u201d. Nature Physics, 10: 631, 79","DOI":"10.1038\/nphys3029"},{"key":"2026042910584011836_j_qic-2025-0004_ref_022","doi-asserted-by":"crossref","unstructured":"M. Kjaergaard, M. E. Schwartz, A. Greene, G. O. Samach, A. Bengtsson, M. O\u2019Keeffe, et al. (2022). \u201cDemonstration of density matrix exponentiation using a superconducting quantum processor\u201d. Physical Review X, 12, 011005.","DOI":"10.1103\/PhysRevX.12.011005"},{"key":"2026042910584011836_j_qic-2025-0004_ref_023","unstructured":"TSP-Data. Tests of Our Empirical Method for TSP. Available at: https:\/\/shorturl.at\/npLN7 (Accessed on 5 February 2025)."},{"key":"2026042910584011836_j_qic-2025-0004_ref_024","doi-asserted-by":"crossref","unstructured":"S. Kimmel, C. Y.-Y. Lin, G. H. Low, M. Ozols and T. J. Yoder (2017). \u201cHamiltonian simulation with optimal sample complexity\u201d. npj Quantum Information, 3, 13.","DOI":"10.1038\/s41534-017-0013-7"}],"container-title":["Quantum Information &amp; Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/reference-global.com\/pdf\/10.2478\/qic-2025-0004","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T16:49:37Z","timestamp":1777481377000},"score":1,"resource":{"primary":{"URL":"https:\/\/reference-global.com\/article\/10.2478\/qic-2025-0004"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,22]]},"references-count":24,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,2,22]]},"published-print":{"date-parts":[[2025,3,1]]}},"alternative-id":["10.2478\/qic-2025-0004"],"URL":"https:\/\/doi.org\/10.2478\/qic-2025-0004","relation":{},"ISSN":["1533-7146"],"issn-type":[{"value":"1533-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,22]]}}}