{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,20]],"date-time":"2025-12-20T22:21:31Z","timestamp":1766269291557,"version":"3.37.3"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,1,8]],"date-time":"2021-01-08T00:00:00Z","timestamp":1610064000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,8]],"date-time":"2021-01-08T00:00:00Z","timestamp":1610064000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000015","name":"Department of Energy","doi-asserted-by":"crossref","award":["DE-SC0019432"],"award-info":[{"award-number":["DE-SC0019432"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Mach. Intell."],"published-print":{"date-parts":[[2021,6]]},"DOI":"10.1007\/s42484-020-00031-9","type":"journal-article","created":{"date-parts":[[2021,1,8]],"date-time":"2021-01-08T01:14:43Z","timestamp":1610068483000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Investigating the Chinese postman problem on a quantum annealer"],"prefix":"10.1007","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3806-2034","authenticated-orcid":false,"given":"Ilaria","family":"Siloi","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8905-2928","authenticated-orcid":false,"given":"Virginia","family":"Carnevali","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4284-1353","authenticated-orcid":false,"given":"Bibek","family":"Pokharel","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6527-8511","authenticated-orcid":false,"given":"Marco","family":"Fornari","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7772-6550","authenticated-orcid":false,"given":"Rosa","family":"Di Felice","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,1,8]]},"reference":[{"key":"31_CR1","doi-asserted-by":"publisher","first-page":"5355","DOI":"10.1103\/PhysRevE.58.5355","volume":"58","author":"T Kadowaki","year":"1998","unstructured":"Kadowaki T, Nishimori H (1998) Quantum annealing in the transverse Ising model. Phys Rev E 58:5355. https:\/\/doi.org\/10.1103\/PhysRevE.58.5355","journal-title":"Phys Rev E"},{"issue":"3","key":"31_CR2","first-page":"031040","volume":"5","author":"D Venturelli","year":"2015","unstructured":"Venturelli D, Mandra S, Knysh S, O\u2019Gorman B, Biswas R, Smelyanskiy V (2015) Quantum optimization of fully connected spin glasses. Phys Rev X 5(3):031040","journal-title":"Phys Rev X"},{"issue":"1","key":"31_CR3","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1038\/s41534-018-0060-8","volume":"4","author":"R Li","year":"2018","unstructured":"Li R, Di Felice R, Rohs R, Lidar D (2018) Quantum annealing versus classical machine learning applied to a simplified computational biology problem. NPJ Quantum Inf 4(1):14. https:\/\/doi.org\/10.1038\/s41534-018-0060-8","journal-title":"NPJ Quantum Inf"},{"key":"31_CR4","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1038\/srep00571","volume":"2","author":"A Perdomo-Ortiz","year":"2012","unstructured":"Perdomo-Ortiz A, Dickson N, Drew-Brook M, Rose G, Aspuru-Guzik. A. (2012) Finding low-energy conformations of lattice protein models by quantum annealing. Sci Rep 2:571","journal-title":"Sci Rep"},{"key":"31_CR5","unstructured":"Li RY, Gujja S, Bajaj SR, Gamel OE, Cilfone N, Gulcher JR, Lidar D, Chittenden TW (2019) arXiv:1909.06206"},{"key":"31_CR6","unstructured":"Neven H, Rose G, Macready W (2008) arXiv:0804.4457"},{"key":"31_CR7","doi-asserted-by":"publisher","first-page":"14","DOI":"10.3389\/fict.2016.00014","volume":"3","author":"Z Bian","year":"2016","unstructured":"Bian Z, Chudak F, Israel RB, Lackey B, Macready W, Roy A (2016) Mapping constrained optimization problems to quantum annealing with application to fault diagnosis. Front ICT 3:14. https:\/\/doi.org\/10.3389\/fict.2016.00014. https:\/\/www.frontiersin.org\/article\/10.3389\/fict.2016.00014","journal-title":"Front ICT"},{"key":"31_CR8","doi-asserted-by":"crossref","unstructured":"Neukart F, Compostella G, Seidel C, von Dollen D, Yarkoni S, Parney B (2017) Traffic flow optimization using a quantum annealer. Front ICT 4(29)","DOI":"10.3389\/fict.2017.00029"},{"key":"31_CR9","unstructured":"Bian Z, Chudak F, Macready W, Roy A, Sebastiani R, Varotti S (2018). arXiv:1811.02524"},{"issue":"1","key":"31_CR10","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1109\/TITS.2019.2891235","volume":"21","author":"T Stollenwerk","year":"2020","unstructured":"Stollenwerk T, O\u2019Gorman B, Venturelli D, Mandr\u00e0 S, Rodionova O, Ng H, Sridhar B, Rieffel EG, Biswas R (2020) Quantum annealing applied to de-conflicting optimal trajectories for air traffic management. IEEE Trans Intell Transp Syst 21(1):285. https:\/\/doi.org\/10.1109\/TITS.2019.2891235","journal-title":"IEEE Trans Intell Transp Syst"},{"issue":"2","key":"31_CR11","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1016\/j.actaastro.2014.09.013","volume":"105","author":"DJ Showalter","year":"2014","unstructured":"Showalter DJ, Black JT (2014) Near-optimal geostationary transfer maneuvers with cooperative en-route inspection using hybrid optimal control. Acta Astronaut 105(2):395. https:\/\/doi.org\/10.1016\/j.actaastro.2014.09.013","journal-title":"Acta Astronaut"},{"key":"31_CR12","doi-asserted-by":"crossref","unstructured":"Figueras A, De La Rosa JL, Esteva S, Cuf\u00ed X. (2018) Robot team in the improvement of the neighborhood. In: 2018 IEEE international smart cities conference (ISC2), pp 1\u20136","DOI":"10.1109\/ISC2.2018.8656874"},{"key":"31_CR13","doi-asserted-by":"crossref","unstructured":"Gomes FF, Gomes MC, Gon\u00e7alves AB (2016) Optimization of routes for road surface inspection - an application to the portuguese national road network. In: ICORES","DOI":"10.5220\/0005711803620365"},{"issue":"1","key":"31_CR14","doi-asserted-by":"publisher","first-page":"015002","DOI":"10.1103\/RevModPhys.90.015002","volume":"90","author":"T Albash","year":"2018","unstructured":"Albash T, Lidar D (2018) Adiabatic quantum computation. Rev Modern Phys 90(1):015002. https:\/\/doi.org\/10.1103\/RevModPhys.90.015002","journal-title":"Rev Modern Phys"},{"key":"31_CR15","doi-asserted-by":"publisher","first-page":"1061","DOI":"10.1103\/RevModPhys.80.1061","volume":"80","author":"A Das","year":"2008","unstructured":"Das A, Chakrabarti BK (2008) Colloquium: Quantum annealing and analog quantum computation. Rev Mod Phys 80:1061. https:\/\/doi.org\/10.1103\/RevModPhys.80.1061","journal-title":"Rev Mod Phys"},{"issue":"2","key":"31_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2200\/S00585ED1V01Y201407QMC008","volume":"5","author":"CC McGeoch","year":"2014","unstructured":"McGeoch CC (2014) Adiabatic quantum computation and quantum annealing: theory and practice. Synthesis Lectures on Quantum Computing 5(2):1","journal-title":"Synthesis Lectures on Quantum Computing"},{"issue":"4","key":"31_CR17","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1137\/080734479","volume":"50","author":"D Aharonov","year":"2008","unstructured":"Aharonov D, Van Dam W, Kempe J, Landau Z, Lloyd S, Regev O (2008) Adiabatic quantum computation is equivalent to standard quantum computation. SIAM review 50(4):755","journal-title":"SIAM review"},{"issue":"7346","key":"31_CR18","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1038\/nature10012","volume":"473","author":"MW Johnson","year":"2011","unstructured":"Johnson MW, Amin MH, Gildert S, Lanting T, Hamze F, Dickson N, Harris R, Berkley AJ, Johansson J, Bunyk P, et al. (2011) Quantum annealing with manufactured spins. Nature 473 (7346):194","journal-title":"Nature"},{"key":"31_CR19","doi-asserted-by":"publisher","unstructured":"Raymond J, Yarkoni S, Andriyash E (2016) Global warming: temperature estimation in annealers. Front ICT 3(23). https:\/\/doi.org\/10.3389\/fict.2016.00023. https:\/\/www.frontiersin.org\/article\/10.3389\/fict.2016.00023","DOI":"10.3389\/fict.2016.00023"},{"issue":"4","key":"31_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TASC.2014.2318294","volume":"24","author":"PI Bunyk","year":"2014","unstructured":"Bunyk PI, Hoskinson EM, Johnson MW, Tolkacheva E, Altomare F, Berkley AJ, Harris R, Hilton JP, Lanting T, Przybysz AJ, Whittaker J (2014) Architectural considerations in the design of a superconducting quantum annealing processor. IEEE Trans Appl Supercond 24(4):1. 10.1109\/TASC.2014.2318294","journal-title":"IEEE Trans Appl Supercond"},{"issue":"3","key":"31_CR21","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1038\/nphys2900","volume":"10","author":"S Boixo","year":"2014","unstructured":"Boixo S, R\u00f8nnow TF, Isakov SV, Wang Z, Wecker D, Lidar D, Martinis J, Troyer M (2014) Evidence for quantum annealing with more than one hundred qubits. Nature Phys 10(3):218","journal-title":"Nature Phys"},{"issue":"1","key":"31_CR22","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1140\/epjst\/e2015-02346-0","volume":"224","author":"T Albash","year":"2015","unstructured":"Albash T, R\u00f8nnow TF, Troyer M, Lidar D (2015) Reexamining classical and quantum models for the D-Wave One processor. Eur Phys J Spec Top 224(1):111","journal-title":"Eur Phys J Spec Top"},{"issue":"5564","key":"31_CR23","doi-asserted-by":"publisher","first-page":"2427","DOI":"10.1126\/science.1068774","volume":"295","author":"GE Santoro","year":"2002","unstructured":"Santoro GE, Marto\u0148\u00e1k R., Tosatti E, Car R (2002) Theory of quantum annealing of an Ising spin glass. Science 295(5564):2427. https:\/\/doi.org\/10.1126\/science.1068774","journal-title":"Science"},{"key":"31_CR24","doi-asserted-by":"publisher","first-page":"031015","DOI":"10.1103\/PhysRevX.6.031015","volume":"6","author":"VS Denchev","year":"2016","unstructured":"Denchev VS, Boixo S, Isakov SV, Ding N, Babbush R, Smelyanskiy V, Martinis J, Neven H (2016) What is the computational value of finite-range tunneling? Phys Rev X 6:031015. https:\/\/doi.org\/10.1103\/PhysRevX.6.031015","journal-title":"Phys Rev X"},{"issue":"1","key":"31_CR25","doi-asserted-by":"publisher","first-page":"2917","DOI":"10.1038\/s41467-018-05239-9","volume":"9","author":"A Mishra","year":"2018","unstructured":"Mishra A, Albash T, Lidar D (2018) Finite temperature quantum annealing solving exponentially small gap problem with non-monotonic success probability. Nat Commun 9 (1):2917. https:\/\/doi.org\/10.1038\/s41467-018-05239-9","journal-title":"Nat Commun"},{"key":"31_CR26","doi-asserted-by":"publisher","first-page":"031016","DOI":"10.1103\/PhysRevX.8.031016","volume":"8","author":"T Albash","year":"2018","unstructured":"Albash T, Lidar D (2018) Demonstration of a scaling advantage for a quantum annealer over simulated annealing. Phys Rev X 8:031016. https:\/\/doi.org\/10.1103\/PhysRevX.8.031016","journal-title":"Phys Rev X"},{"key":"31_CR27","unstructured":"Parekh O, Wendt J, Shulenburger L, Landahl A, Moussa J, Aidun J (2016) arXiv:1604.00319"},{"issue":"1","key":"31_CR28","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/s11128-011-0235-0","volume":"11","author":"K Karimi","year":"2012","unstructured":"Karimi K, Dickson NG, Hamze F, Amin MH, Drew-Brook M, Chudak FA, Bunyk PI, Macready W, Rose G (2012) Investigating the performance of an adiabatic quantum optimization processor. Quantum Inf Process 11(1):77","journal-title":"Quantum Inf Process"},{"key":"31_CR29","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"M Garey","year":"1978","unstructured":"Garey M, Johnson D (1978) Computers and intractability: a guide to the theory of NP-completeness. Freeman, San Francisco"},{"key":"31_CR30","first-page":"273","volume":"1","author":"K Mei-Ko","year":"1962","unstructured":"Mei-Ko K (1962) Graphic programming using odd or even points. Chin Math 1:273\u2013277","journal-title":"Chin Math"},{"issue":"5","key":"31_CR31","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1016\/0305-0548(94)00036-8","volume":"22","author":"WL Pearn","year":"1995","unstructured":"Pearn WL, Liu C (1995) Algorithms for the Chinese postman problem on mixed networks. Comput Oper Res 22(5):479. https:\/\/doi.org\/10.1016\/0305-0548(94)00036-8","journal-title":"Comput Oper Res"},{"issue":"12","key":"31_CR32","doi-asserted-by":"publisher","first-page":"3403","DOI":"10.1016\/j.cor.2005.02.011","volume":"33","author":"D Ahr","year":"2006","unstructured":"Ahr D, Reinelt G (2006) A tabu search algorithm for the min?max k-Chinese postman problem. Comput Oper Res 33(12):3403. https:\/\/doi.org\/10.1016\/j.cor.2005.02.011","journal-title":"Comput Oper Res"},{"issue":"11","key":"31_CR33","doi-asserted-by":"publisher","first-page":"18","DOI":"10.7232\/iems.2012.11.1.018","volume":"1","author":"B Zhang","year":"2012","unstructured":"Zhang B, Peng J (2012) Uncertain programming model for chinese postman problem with uncertain weights. Ind Eng Manag Syst 1(11):18\u201325. https:\/\/doi.org\/10.7232\/iems.2012.11.1.018","journal-title":"Ind Eng Manag Syst"},{"issue":"2","key":"31_CR34","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1287\/opre.43.2.231","volume":"43","author":"H Eiselt","year":"1995","unstructured":"Eiselt H, Gendreau M, Laporte G (1995) Arc routing problems, Part I: The chinese postman problem. Oper Res 43(2):231","journal-title":"Oper Res"},{"key":"31_CR35","doi-asserted-by":"publisher","unstructured":"Assad AA, Golden BL (1995) Chapter 5 Arc routing methods and applications. In: Network routing, handbooks in operations research and management science. https:\/\/doi.org\/10.1016\/S0927-0507(05)80109-4. http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0927050705801094, vol 8. Elsevier, pp 375\u2013483","DOI":"10.1016\/S0927-0507(05)80109-4"},{"key":"31_CR36","first-page":"128","volume":"8","author":"L Euler","year":"1736","unstructured":"Euler L (1736) Solutio problematis ad geometriam situs pertinentis. Commentarii Academiae Petropolitanae 8:128\u2013140","journal-title":"Commentarii Academiae Petropolitanae"},{"issue":"3","key":"31_CR37","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1002\/nav.3800150309","volume":"15","author":"S Hedetniemi","year":"1968","unstructured":"Hedetniemi S (1968) On minimum walks in graphs. Nav Res Logist Q 15(3):453. https:\/\/doi.org\/10.1002\/nav.3800150309","journal-title":"Nav Res Logist Q"},{"issue":"1","key":"31_CR38","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1137\/0202003","volume":"2","author":"S Goodman","year":"1973","unstructured":"Goodman S, Hedetniemi S (1973) Eulerian walks in graphs. SIAM J Comput 2(1):16. https:\/\/doi.org\/10.1137\/0202003","journal-title":"SIAM J Comput"},{"issue":"3","key":"31_CR39","doi-asserted-by":"publisher","first-page":"454","DOI":"10.1287\/opre.18.3.454","volume":"18","author":"DJ Laughhunn","year":"1970","unstructured":"Laughhunn DJ (1970) Quadratic binary programming with application to capital-budgeting problems. Oper Res 18(3):454. https:\/\/doi.org\/10.1287\/opre.18.3.454","journal-title":"Oper Res"},{"key":"31_CR40","first-page":"37","volume-title":"An introduction to Tabu search","author":"M Gendreau","year":"2003","unstructured":"Gendreau M (2003) An introduction to Tabu search. Springer, Berlin, pp 37\u201354"},{"issue":"1","key":"31_CR41","doi-asserted-by":"publisher","first-page":"015006","DOI":"10.1088\/1749-4680\/7\/1\/015006","volume":"7","author":"TS Humble","year":"2014","unstructured":"Humble TS, McCaskey AJ, Bennink RS, Billings JJ, D\u2019Azevedo EF, Sullivan BD, Klymko CF, Seddiqi H (2014) An integrated development environment for adiabatic quantum programming. Comput Sci Discov 7(1):015006. https:\/\/doi.org\/10.1088\/1749-4680\/7\/1\/015006","journal-title":"Comput Sci Discov"},{"issue":"1","key":"31_CR42","doi-asserted-by":"publisher","first-page":"2045","DOI":"10.1038\/s41598-018-38388-4","volume":"9","author":"S Okada","year":"2019","unstructured":"Okada S, Ohzeki M, Terabe M, Taguchi S (2019) Improving solutions by embedding larger subproblems in a D-Wave quantum annealer. Sci Rep 9(1):2045. https:\/\/doi.org\/10.1038\/s41598-018-38388-4","journal-title":"Sci Rep"},{"key":"31_CR43","unstructured":"Cai J, Macready WJ, Roy A (2014) arXiv:1406.2741"},{"issue":"3","key":"31_CR44","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/s11128-010-0200-3","volume":"10","author":"V Choi","year":"2011","unstructured":"Choi V (2011) Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design. Quantum Inf Process 10(3):343. https:\/\/doi.org\/10.1007\/s11128-010-0200-3","journal-title":"Quantum Inf Process"},{"issue":"10","key":"31_CR45","doi-asserted-by":"publisher","first-page":"3241","DOI":"10.1088\/0305-4470\/15\/10\/028","volume":"15","author":"F Barahona","year":"1982","unstructured":"Barahona F (1982) On the computational complexity of Ising spin glass models. J Phys A Math Gen 15(10):3241. https:\/\/doi.org\/10.1088\/0305-4470\/15\/10\/028","journal-title":"J Phys A Math Gen"},{"key":"31_CR46","unstructured":"D-Wave Systems Inc (2018). https:\/\/github.com\/dwavesystems\/dwave-ocean-sdk"},{"key":"31_CR47","unstructured":"D-Wave Systems Inc (2018). https:\/\/github.com\/dwavesystems\/qbsolv release 1.2.0."}],"container-title":["Quantum Machine Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42484-020-00031-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42484-020-00031-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42484-020-00031-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,2]],"date-time":"2021-07-02T08:21:17Z","timestamp":1625214077000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42484-020-00031-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,8]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["31"],"URL":"https:\/\/doi.org\/10.1007\/s42484-020-00031-9","relation":{},"ISSN":["2524-4906","2524-4914"],"issn-type":[{"type":"print","value":"2524-4906"},{"type":"electronic","value":"2524-4914"}],"subject":[],"published":{"date-parts":[[2021,1,8]]},"assertion":[{"value":"19 March 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 November 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 January 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"3"}}