Abstract
The recent availability of quantum annealers has fueled a new area of information technology where such devices are applied to address practically motivated and computationally difficult problems with hardware that exploits quantum mechanical phenomena. D-Wave annealers are promising platforms to solve these problems in the form of quadratic unconstrained binary optimization. Here we provide a formulation of the Chinese postman problem that can be used as a tool for probing the local connectivity of graphs and networks. We treat the problem classically with a tabu algorithm and simulated annealing, and using a D-Wave device. The efficiency of quantum annealing with respect to the simulated annealing has been demonstrated using the optimal time to solution metric. We systematically analyze computational parameters associated with the specific hardware. Our results clarify how the interplay between the embedding due to limited connectivity of the Chimera graph, the definition of logical qubits, and the role of spin-reversal controls the probability of reaching the expected solution.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
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
Venturelli D, Mandra S, Knysh S, O’Gorman B, Biswas R, Smelyanskiy V (2015) Quantum optimization of fully connected spin glasses. Phys Rev X 5(3):031040
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
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
Li RY, Gujja S, Bajaj SR, Gamel OE, Cilfone N, Gulcher JR, Lidar D, Chittenden TW (2019) arXiv:1909.06206
Neven H, Rose G, Macready W (2008) arXiv:0804.4457
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
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)
Bian Z, Chudak F, Macready W, Roy A, Sebastiani R, Varotti S (2018). arXiv:1811.02524
Stollenwerk T, O’Gorman B, Venturelli D, Mandrà 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
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
Figueras A, De La Rosa JL, Esteva S, Cufí X. (2018) Robot team in the improvement of the neighborhood. In: 2018 IEEE international smart cities conference (ISC2), pp 1–6
Gomes FF, Gomes MC, Gonçalves AB (2016) Optimization of routes for road surface inspection - an application to the portuguese national road network. In: ICORES
Albash T, Lidar D (2018) Adiabatic quantum computation. Rev Modern Phys 90(1):015002. https://doi.org/10.1103/RevModPhys.90.015002
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
McGeoch CC (2014) Adiabatic quantum computation and quantum annealing: theory and practice. Synthesis Lectures on Quantum Computing 5(2):1
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
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
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
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
Boixo S, Rønnow 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
Albash T, Rønnow 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
Santoro GE, Martoňák 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
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
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
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
Parekh O, Wendt J, Shulenburger L, Landahl A, Moussa J, Aidun J (2016) arXiv:1604.00319
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
Garey M, Johnson D (1978) Computers and intractability: a guide to the theory of NP-completeness. Freeman, San Francisco
Mei-Ko K (1962) Graphic programming using odd or even points. Chin Math 1:273–277
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
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
Zhang B, Peng J (2012) Uncertain programming model for chinese postman problem with uncertain weights. Ind Eng Manag Syst 1(11):18–25. https://doi.org/10.7232/iems.2012.11.1.018
Eiselt H, Gendreau M, Laporte G (1995) Arc routing problems, Part I: The chinese postman problem. Oper Res 43(2):231
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–483
Euler L (1736) Solutio problematis ad geometriam situs pertinentis. Commentarii Academiae Petropolitanae 8:128–140
Hedetniemi S (1968) On minimum walks in graphs. Nav Res Logist Q 15(3):453. https://doi.org/10.1002/nav.3800150309
Goodman S, Hedetniemi S (1973) Eulerian walks in graphs. SIAM J Comput 2(1):16. https://doi.org/10.1137/0202003
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
Gendreau M (2003) An introduction to Tabu search. Springer, Berlin, pp 37–54
Humble TS, McCaskey AJ, Bennink RS, Billings JJ, D’Azevedo 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
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
Cai J, Macready WJ, Roy A (2014) arXiv:1406.2741
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
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
D-Wave Systems Inc (2018). https://github.com/dwavesystems/dwave-ocean-sdk
D-Wave Systems Inc (2018). https://github.com/dwavesystems/qbsolv release 1.2.0.
Acknowledgments
This work is supported by the Department of Energy award DE-SC0019432 and by the James H. Zumberge Faculty Research and Innovation Fund at the University of Southern California. The research is based upon work (partially) supported by the Office of the Director of National Intelligence (ODNI), Intelligence Advanced Research Projects Activity (IARPA) and the Defense Advanced Research Projects Agency (DARPA), via the U.S. Army Research Office contract W911NF-17-C-0050. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of the ODNI, IARPA, DARPA, or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright annotation thereon.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Ilaria Siloi and Virginia Carnevali contributed equally to this work.
Rights and permissions
About this article
Cite this article
Siloi, I., Carnevali, V., Pokharel, B. et al. Investigating the Chinese postman problem on a quantum annealer. Quantum Mach. Intell. 3, 3 (2021). https://doi.org/10.1007/s42484-020-00031-9
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s42484-020-00031-9