{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,25]],"date-time":"2026-01-25T08:58:42Z","timestamp":1769331522728,"version":"3.49.0"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,1,24]],"date-time":"2025-01-24T00:00:00Z","timestamp":1737676800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,1,24]],"date-time":"2025-01-24T00:00:00Z","timestamp":1737676800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Data Sci. Eng."],"published-print":{"date-parts":[[2025,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Combinatorial optimization problems over graphs, such as the traveling salesman problem, longest path problem, and maximum independent set problem, are well-known for being computationally costly, some even NP-hard problems. In this paper, we propose a general quantum algorithm framework searching for approximate solutions to combinatorial optimization problems with linear objective functions. Our framework provides APIs (application programming interfaces) that enable developers to encode weighted graph structures onto quantum circuits and utilize variational algorithms to generate approximate solutions. One key advantage of our framework is that it allows developers to design new graph algorithms for the graph problem represented as linear combinations of edge weights without requiring expertise in quantum programming. Besides, it only uses a logarithmic level of quantum bit scale, making our framework work on quantum computers with limited physical resources. Our experimental results demonstrate that our framework can provide good approximations for the traveling salesman problem compared to current quantum algorithm.<\/jats:p>","DOI":"10.1007\/s41019-024-00269-4","type":"journal-article","created":{"date-parts":[[2025,1,24]],"date-time":"2025-01-24T09:30:39Z","timestamp":1737711039000},"page":"246-257","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["A Quantum Framework for Combinatorial Optimization Problem over Graphs"],"prefix":"10.1007","volume":"10","author":[{"given":"Meng","family":"Shi","sequence":"first","affiliation":[]},{"given":"Sai","family":"Wu","sequence":"additional","affiliation":[]},{"given":"Ying","family":"Li","sequence":"additional","affiliation":[]},{"given":"Gongsheng","family":"Yuan","sequence":"additional","affiliation":[]},{"given":"Chang","family":"Yao","sequence":"additional","affiliation":[]},{"given":"Gang","family":"Chen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,1,24]]},"reference":[{"key":"269_CR1","doi-asserted-by":"crossref","unstructured":"Aharonov D, Jones V, Landau Z (2006) A polynomial quantum algorithm for approximating the jones polynomial. quant-ph\/0511096","DOI":"10.1145\/1132516.1132579"},{"key":"269_CR2","doi-asserted-by":"crossref","unstructured":"Ambainis A, Balodis K, Iraids J, et al (2019) Quantum speedups for exponential- time dynamic programming algorithms. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, pp 1783\u20131793","DOI":"10.1137\/1.9781611975482.107"},{"issue":"1","key":"269_CR3","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1145\/321105.321111","volume":"9","author":"R Bellman","year":"1962","unstructured":"Bellman R (1962) Dynamic programming treatment of the travelling salesman problem. J ACM (JACM) 9(1):61\u201363","journal-title":"J ACM (JACM)"},{"key":"269_CR4","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1016\/j.hm.2020.04.003","volume":"53","author":"R van Bevern","year":"2020","unstructured":"van Bevern R, Slugina VA (2020) A historical note on the 3\/2-approximation algorithm for the metric traveling salesman problem. Hist Math 53:118\u2013127","journal-title":"Hist Math"},{"key":"269_CR5","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/j.tcs.2017.04.016","volume":"701","author":"CS Calude","year":"2017","unstructured":"Calude CS, Dinneen MJ, Hua R (2017) Qubo formulations for the graph isomorphism problem and related problems. Theoret Comput Sci 701:54\u201369","journal-title":"Theoret Comput Sci"},{"key":"269_CR6","unstructured":"Cormen TH, Leiserson CE, Rivest RL, et al (2001) Introduction to algorithms, chapter 11"},{"key":"269_CR7","unstructured":"Durr C, Hoyer P (1996) A quantum algorithm for finding the minimum. arXiv preprint quant-ph\/9607014"},{"issue":"6","key":"269_CR8","doi-asserted-by":"publisher","first-page":"1310","DOI":"10.1137\/050644719","volume":"35","author":"C Du\u00a8rr","year":"2006","unstructured":"Du\u00a8rr C, Heiligman M, Hoyer P et al (2006) Quantum query complexity of some graph problems. SIAM J Comput 35(6):1310\u20131328","journal-title":"SIAM J Comput"},{"key":"269_CR9","unstructured":"Farhi E, Goldstone J, Gutmann S (2014) A quantum approximate optimization algorithm. arXiv preprint arXiv:14114028"},{"key":"269_CR10","doi-asserted-by":"crossref","unstructured":"Fieger K, Balyo T, Schulz C, et al (2019) Finding optimal longest paths by dynamic programming in parallel. In: Proceedings of the International Symposium on Combinatorial Search, pp 61\u201369","DOI":"10.1609\/socs.v10i1.18503"},{"key":"269_CR11","first-page":"1","volume":"15","author":"T Fujimura","year":"2020","unstructured":"Fujimura T (2020) Quantum algorithm for longest path problem by hybrid method of grover\u2019s database search and shor\u2019s data decrease. Adva Theo Appl Math 15:1\u201310","journal-title":"Adva Theo Appl Math"},{"key":"269_CR12","doi-asserted-by":"crossref","unstructured":"Grover LK (1996) A fast quantum mechanical algorithm for database search. In: Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pp 212\u2013219","DOI":"10.1145\/237814.237866"},{"key":"269_CR13","doi-asserted-by":"crossref","unstructured":"Jain S (2021) Solving the traveling salesman problem on the d-wave quantum computer. Frontiers in Physics p 646","DOI":"10.3389\/fphy.2021.760783"},{"key":"269_CR14","doi-asserted-by":"crossref","unstructured":"Khumalo MT, Chieza HA, Prag K, et al (2022) An investigation of ibm quantum computing device performance on combinatorial optimisation problems. Neural Computing and Applications pp 1\u201316","DOI":"10.1007\/s00521-022-07438-4"},{"key":"269_CR15","unstructured":"Kitaev AY (1995) Quantum measurements and the abelian stabilizer problem. arXiv preprint quant-ph\/9511026"},{"issue":"4","key":"269_CR16","doi-asserted-by":"publisher","first-page":"986","DOI":"10.1002\/rsa.21200","volume":"64","author":"M Krivelevich","year":"2024","unstructured":"Krivelevich M, M\u2019esz\u2019aros T, Michaeli P et al (2024) Greedy maximal independent sets via local limits. Random Struct Algor 64(4):986\u20131015","journal-title":"Random Struct Algor"},{"issue":"12","key":"269_CR17","doi-asserted-by":"publisher","first-page":"706","DOI":"10.1038\/nphoton.2009.231","volume":"3","author":"AI Lvovsky","year":"2009","unstructured":"Lvovsky AI, Sanders BC, Tittel W (2009) Optical quantum memory. Nat Photon 3(12):706\u2013714. https:\/\/doi.org\/10.1038\/nphoton.2009.231","journal-title":"Nat Photon"},{"issue":"2","key":"269_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3569095","volume":"4","author":"N Mariella","year":"2023","unstructured":"Mariella N, Simonetto A (2023) A quantum algorithm\u00a0for the sub-graph isomorphism problem. ACM Trans Quant Comput 4(2):1\u201334. https:\/\/doi.org\/10.1145\/3569095","journal-title":"ACM Trans Quant Comput"},{"issue":"5","key":"269_CR19","doi-asserted-by":"publisher","first-page":"057701","DOI":"10.1103\/PhysRevE.70.057701","volume":"70","author":"R Marton\u02c7\u2019ak","year":"2004","unstructured":"Marton\u02c7\u2019ak R, Santoro GE, Tosatti E (2004) Quantum annealing of the traveling-salesman problem. Phys Rev E 70(5):057701","journal-title":"Phys Rev E"},{"key":"269_CR20","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.tcs.2021.02.021","volume":"863","author":"J McCollum","year":"2021","unstructured":"McCollum J, Krauss T (2021) Qubo formulations of the longest path problem. Theoret Comput Sci 863:86\u2013101","journal-title":"Theoret Comput Sci"},{"issue":"1","key":"269_CR21","doi-asserted-by":"publisher","first-page":"4213","DOI":"10.1038\/ncomms5213","volume":"5","author":"A Peruzzo","year":"2014","unstructured":"Peruzzo A, McClean J, Shadbolt P et al (2014) A variational eigenvalue solver on a photonic quantum processor. Nat Commun 5(1):4213","journal-title":"Nat Commun"},{"issue":"1","key":"269_CR22","doi-asserted-by":"publisher","first-page":"57","DOI":"10.15625\/1813-9663\/35\/1\/12935","volume":"35","author":"NT Phuong","year":"2019","unstructured":"Phuong NT, Duc TV et al (2019) On the performance of a simple approximation algorithm for the longest path problem. J Comput Sci Cybernet 35(1):57\u201368","journal-title":"J Comput Sci Cybernet"},{"key":"269_CR23","doi-asserted-by":"crossref","unstructured":"Shende VV, Bullock SS, Markov IL (2005) Synthesis of quantum logic circuits. In: Proceedings of the 2005 Asia and South Pacific Design Automation Conference, pp 272\u2013275","DOI":"10.1109\/ASPDAC.2005.1466172"},{"key":"269_CR24","doi-asserted-by":"crossref","unstructured":"Shor PW (1994) Algorithms for quantum computation: discrete logarithms and fac- toring. In: Proceedings 35th annual symposium on foundations of computer science, Ieee, pp 124\u2013134","DOI":"10.1109\/SFCS.1994.365700"},{"key":"269_CR25","unstructured":"Srinivasan K, Satyajit S, Behera BK, et al (2018) Efficient quantum algorithm for solving travelling salesman problem: An ibm quantum experience. arXiv preprint arXiv:180510928"},{"key":"269_CR26","doi-asserted-by":"crossref","unstructured":"Tabi Z, El-Safty KH, Kallus Z, et al (2020) Quantum optimization for the graph color- ing problem with space-efficient embedding. In: 2020 IEEE International Conference on Quantum Computing and Engineering (QCE), IEEE, pp 56\u201362","DOI":"10.1109\/QCE49297.2020.00018"},{"key":"269_CR27","unstructured":"Tang Y, Yan J, Edwin H (2022) From quantum graph computing to quantum graph learning: A survey. arXiv preprint arXiv:220209506"},{"key":"269_CR28","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/j.ic.2017.06.001","volume":"255","author":"M Xiao","year":"2017","unstructured":"Xiao M, Nagamochi H (2017) Exact algorithms for maximum independent set. Inf Comput 255:126\u2013146","journal-title":"Inf Comput"},{"issue":"3","key":"269_CR29","doi-asserted-by":"publisher","DOI":"10.1088\/0256-307X\/38\/3\/030304","volume":"38","author":"H Yu","year":"2021","unstructured":"Yu H, Wilczek F, Wu B (2021) Quantum algorithm for approximating maximum independent sets. Chin Phys Lett 38(3):030304","journal-title":"Chin Phys Lett"},{"key":"269_CR30","unstructured":"Zhu J, Gao Y, Wang H, et al (2022) A realizable gas-based quantum algorithm for traveling salesman problem. arXiv preprint arXiv:221202735"}],"container-title":["Data Science and Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41019-024-00269-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41019-024-00269-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41019-024-00269-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,6]],"date-time":"2025-06-06T08:57:45Z","timestamp":1749200265000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s41019-024-00269-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,24]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["269"],"URL":"https:\/\/doi.org\/10.1007\/s41019-024-00269-4","relation":{},"ISSN":["2364-1185","2364-1541"],"issn-type":[{"value":"2364-1185","type":"print"},{"value":"2364-1541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,24]]},"assertion":[{"value":"3 January 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 November 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 November 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 January 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}