{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T16:31:30Z","timestamp":1783787490945,"version":"3.55.0"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,4,8]],"date-time":"2023-04-08T00:00:00Z","timestamp":1680912000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Quantum Comput."],"published-print":{"date-parts":[[2023,9,30]]},"abstract":"<jats:p>Quantum processing units (QPUs) executing annealing algorithms have shown promise in optimization and simulation applications. Hybrid algorithms are a natural bridge to larger applications. We present a simple greedy method for solving larger-than-QPU lattice-structured Ising optimization problems. The method, implemented in the open source D-Wave Hybrid framework, uses a QPU coprocessor operating with generic parameters. Performance is evaluated for standard spin-glass problems on two lattice types with up to 11,616 spin variables, double the size that is directly programmable on any available QPU. The proposed method is shown to converge to low-energy solutions faster than an open source simulated annealing method that is either directly employed or substituted as a coprocessor in the hybrid method. Using newer Advantage QPUs in place of D-Wave 2000Q QPUs is shown to enhance convergence of the hybrid method to low energies and to achieve a lower final energy.<\/jats:p>","DOI":"10.1145\/3579368","type":"journal-article","created":{"date-parts":[[2023,2,9]],"date-time":"2023-02-09T13:48:57Z","timestamp":1675950537000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":38,"title":["Hybrid Quantum Annealing for Larger-than-QPU Lattice-structured Problems"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1808-6039","authenticated-orcid":false,"given":"Jack","family":"Raymond","sequence":"first","affiliation":[{"name":"D-Wave Systems, Burnaby, BC, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2881-0123","authenticated-orcid":false,"given":"Radomir","family":"Stevanovic","sequence":"additional","affiliation":[{"name":"D-Wave Systems, Burnaby, BC, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2455-2606","authenticated-orcid":false,"given":"William","family":"Bernoudy","sequence":"additional","affiliation":[{"name":"D-Wave Systems, Burnaby, BC, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6870-0466","authenticated-orcid":false,"given":"Kelly","family":"Boothby","sequence":"additional","affiliation":[{"name":"D-Wave Systems, Burnaby, BC, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4023-0551","authenticated-orcid":false,"given":"Catherine C.","family":"McGeoch","sequence":"additional","affiliation":[{"name":"D-Wave Systems, Burnaby, BC, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4235-8452","authenticated-orcid":false,"given":"Andrew J.","family":"Berkley","sequence":"additional","affiliation":[{"name":"D-Wave Systems, Burnaby, BC, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7807-4806","authenticated-orcid":false,"given":"Pau","family":"Farr\u00e9","sequence":"additional","affiliation":[{"name":"D-Wave Systems, Burnaby, BC, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3409-3543","authenticated-orcid":false,"given":"Joel","family":"Pasvolsky","sequence":"additional","affiliation":[{"name":"D-Wave Systems, Burnaby, BC, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8362-8941","authenticated-orcid":false,"given":"Andrew D.","family":"King","sequence":"additional","affiliation":[{"name":"D-Wave Systems, Burnaby, BC, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,4,8]]},"reference":[{"issue":"022107","key":"e_1_3_3_2_2","first-page":"2007","article-title":"Decoherence in adiabatic quantum computation","volume":"79","author":"Amin M. H. S.","year":"2009","unstructured":"M. H. S. Amin, Dmitri V. Averin, and James A. Nesteroff. 2009. Decoherence in adiabatic quantum computation. Phys. Rev. A 79, 022107 (2009), 2007\u20132010.","journal-title":"Phys. Rev. A"},{"issue":"15","key":"e_1_3_3_3_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1103\/PhysRevLett.118.157202","article-title":"Matching microscopic and macroscopic responses in glasses","volume":"118","author":"Baity-Jesi M.","year":"2017","unstructured":"M. Baity-Jesi, E. Calore, A. Cruz, L. A. Fernandez, J. M. Gil-Narvion, A. Gordillo-Guerrero, D. I\u00f1iguez, A. Maiorano, E. Marinari, V. Martin-Mayor, J. Monforte-Garcia, A. Mu\u00f1oz-Sudupe, D. Navarro, G. Parisi, S. Perez-Gaviro, F. Ricci-Tersenghi, J. J. Ruiz-Lorenzo, S. F. Schifano, B. Seoane, A. Tarancon, R. Tripiccione, and D. Yllanes. 2017. Matching microscopic and macroscopic responses in glasses. Phys. Rev. Lett. 118, 15 (2017), 1\u20136.","journal-title":"Phys. Rev. Lett."},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1088\/0305-4470\/15\/10\/028"},{"key":"e_1_3_3_5_2","article-title":"Partitioning Optimization Problems for Hybrid Classical\/Quantum Execution","author":"Booth Michael","year":"2017","unstructured":"Michael Booth, Steven P. Reinhardt, and Aidan Roy. 2017. Partitioning Optimization Problems for Hybrid Classical\/Quantum Execution. D-Wave White Paper.","journal-title":"D-Wave White Paper"},{"key":"e_1_3_3_6_2","unstructured":"Kelly Boothby Paul Bunyk Jack Raymond and Aidan Roy. 2019. Next-generation topology of D-Wave quantum processors. arxiv:2003.00133. Retrieved from https:\/\/arxiv.org\/abs\/2003.00133."},{"key":"e_1_3_3_7_2","unstructured":"Kelly Boothby Colin Enderud Trevor Lanting Reza Molavi Nicholas Tsai Mark H. Volkmann Fabio Altomare Mohammad H. Amin Michael Babcock Andrew J. Berkley Catia Baron Aznar Martin Boschnak Holly Christiani Sara Ejtemaee Bram Evert Matthew Gullen Markus Hager Richard Harris Emile Hoskinson Jeremy P. Hilton Kais Jooya Ann Huang Mark W. Johnson Andrew D. King Eric Ladizinsky Ryan Li Allison MacDonald Teresa Medina Fernandez Richard Neufeld Mana Norouzpour Travis Oh Isil Ozfidan Paul Paddon Ilya Perminov Gabriel Poulin-Lamarre Thomas Prescott Jack Raymond Mauricio Reis Chris Rich Aidan Roy Hossein Sadeghi Esfahani Yuki Sato Ben Sheldan Anatoly Smirnov Loren J. Swenson Jed Whittaker Jason Yao Alexander Yarovoy and Paul I. Bunyk. 2021. Architectural considerations in the design of a third-generation superconducting quantum annealing processor. arxiv:2108.02322. Retrieved from https:\/\/arxiv.org\/abs\/2108.02322."},{"key":"e_1_3_3_8_2","article-title":"Zephyr Topology of D-Wave Quantum Processors","author":"Boothby Kelly","year":"2021","unstructured":"Kelly Boothby, Andrew D. King, and Jack Raymond. 2021. Zephyr Topology of D-Wave Quantum Processors. D-Wave White Paper.","journal-title":"D-Wave White Paper"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-015-1150-6"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.284.5415.779"},{"key":"e_1_3_3_11_2","unstructured":"J. Cai W. G. Macready and A. Roy. 2014. A practical heuristic for finding graph minors. arxiv:1406.2741. Retrieved from https:\/\/arxiv.org\/abs\/1406.2741."},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-010-0200-3"},{"key":"e_1_3_3_13_2","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/978-3-030-19212-9_11","volume-title":"Integration of Constraint Programming, Artificial Intelligence, and Operations Research","author":"Coffrin Carleton","year":"2019","unstructured":"Carleton Coffrin, Harsha Nagarajan, and Russell Bent. 2019. Evaluating ising processing units with integer programming. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research, Louis-Martin Rousseau and Kostas Stergiou (Eds.). Springer International Publishing, Cham, 163\u2013181."},{"key":"e_1_3_3_14_2","unstructured":"D-Wave. 2022. Ocean-SDK. https:\/\/docs.ocean.dwavesys.com\/en\/stable\/index.html."},{"key":"e_1_3_3_15_2","unstructured":"D-Wave. 2022. A Simple D-Wave Hybrid Workflow for Fast Optimization in Lattice Structured Problems\u2014Qubits 2021. Retrieved December 23 2022 from https:\/\/www.youtube.com\/watch?v=vfQpV8gwmSY."},{"key":"e_1_3_3_16_2","unstructured":"D-Wave. 2022. D-Wave System Documentation. Retrieved December 23 2022 from https:\/\/docs.dwavesys.com\/docs\/latest\/."},{"key":"e_1_3_3_17_2","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/3-540-48086-2_15","volume-title":"Parallel Processing and Applied Mathematics","author":"Drozdowski Maciej","year":"2002","unstructured":"Maciej Drozdowski. 2002. Estimating execution time of distributed applications. In Parallel Processing and Applied Mathematics, Roman Wyrzykowski, Jack Dongarra, Marcin Paprzycki, and Jerzy Wa\u015bniewski (Eds.). Springer, Berlin, 137\u2013144."},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.1057726"},{"key":"e_1_3_3_19_2","first-page":"243","volume-title":"Proceedings of the Conference on Uncertainty in Artificial Intelligence","author":"Hamze F.","year":"2004","unstructured":"F. Hamze and N. de Freitas. 2004. From fields to trees: On blocked and collapsed mcmc algorithms for undirected probabilistic graphical models. In Proceedings of the Conference on Uncertainty in Artificial Intelligence. AUAI Press, 243\u2013250."},{"issue":"4","key":"e_1_3_3_20_2","doi-asserted-by":"crossref","first-page":"43303","DOI":"10.1103\/PhysRevE.97.043303","article-title":"From near to eternity: Spin-glass planting, tiling puzzles, and constraint satisfaction problems","volume":"97","author":"Hamze Firas","year":"2017","unstructured":"Firas Hamze, Darryl C. Jacob, Andrew J. Ochoa, Wenlong Wang, Helmut G. Katzgraber, D Perera, Wenlong Wang, and Helmut G. Katzgraber. 2017. From near to eternity: Spin-glass planting, tiling puzzles, and constraint satisfaction problems. Phys. Rev. E 97, 4 (2017), 43303.","journal-title":"Phys. Rev. E"},{"issue":"11","key":"e_1_3_3_21_2","doi-asserted-by":"crossref","first-page":"117003","DOI":"10.1103\/PhysRevLett.101.117003","article-title":"Probing noise in flux qubits via macroscopic resonant tunneling","volume":"101","author":"Harris R.","year":"2008","unstructured":"R. Harris, M. W. Johnson, S. Han, A. J. Berkley, J. Johansson, P. Bunyk, E. Ladizinsky, S. Govorkov, M. C. Thom, S. Uchaikin, B. Bumble, A. Fung, A. Kaul, A. Kleinsasser, M. H. S. Amin, and D. V. Averin. 2008. Probing noise in flux qubits via macroscopic resonant tunneling. Phys. Rev. Lett. 101, 11 (2008), 117003.","journal-title":"Phys. Rev. Lett."},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.aat2025"},{"key":"e_1_3_3_23_2","doi-asserted-by":"crossref","first-page":"843","DOI":"10.1145\/860575.860711","volume-title":"Proceedings of the 2nd International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201903)","author":"Helsinger Aaron","year":"2003","unstructured":"Aaron Helsinger, Richard Lazarus, William Wright, and John Zinky. 2003. Tools and techniques for performance measurement of large distributed multiagent systems. In Proceedings of the 2nd International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201903). Association for Computing Machinery, New York, NY, 843\u2013850."},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cpc.2015.02.015"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1038\/nature10012"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.58.5355"},{"issue":"2","key":"e_1_3_3_27_2","first-page":"1","article-title":"Glassy chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines","volume":"4","author":"Katzgraber Helmut G.","year":"2014","unstructured":"Helmut G. Katzgraber, Firas Hamze, and Ruben S. Andrist. 2014. Glassy chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines. Phys. Rev. X 4, 2 (2014), 1\u20137.","journal-title":"Phys. Rev. X"},{"key":"e_1_3_3_28_2","unstructured":"Andrew D. King and William Bernoudy. 2020. Performance benefits of increased qubit connectivity in quantum annealing 3-dimensional spin glasses. arxiv:2009.12479. Retrieved from https:\/\/arxiv.org\/abs\/2009.12479."},{"key":"e_1_3_3_29_2","unstructured":"Andrew D. King Jack Raymond Trevor Lanting Richard Harris Alex Zucca Fabio Altomare Andrew J. Berkley Kelly Boothby Sara Ejtemaee Colin Enderud Emile Hoskinson Shuiyuan Huang Eric Ladizinsky Allison J. R. MacDonald Gaelen Marsden Reza Molavi Travis Oh Gabriel Poulin-Lamarre Mauricio Reis Chris Rich Yuki Sato Nicholas Tsai Mark Volkmann Jed D. Whittaker Jason Yao Anders W. Sandvik and Mohammad H. Amin. 2022. Quantum critical dynamics in a 5000-qubit programmable spin glass. arxiv:2207.13800. Retrieved from https:\/\/arxiv.org\/abs\/2207.13800."},{"issue":"6","key":"e_1_3_3_30_2","doi-asserted-by":"crossref","first-page":"61007","DOI":"10.7566\/JPSJ.88.061007","article-title":"Quantum annealing amid local ruggedness and global frustration","volume":"88","author":"King James","year":"2019","unstructured":"James King, Sheir Yarkoni, Jack Raymond, Isil Ozfidan, Andrew D. King, Mayssam Mohammadi Nevisi, Jeremy P. Hilton, and Catherine C. McGeoch. 2019. Quantum annealing amid local ruggedness and global frustration. J. Phys. Soc. Jpn. 88, 6 (2019), 61007.","journal-title":"J. Phys. Soc. Jpn."},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.220.4598.671"},{"key":"e_1_3_3_32_2","unstructured":"Frauke Liers Michael J\u00fcnger Petra Mutzel Giovanni Rinaldi Angelika Wiegele Martin Diehl Gerhard Reinelt and Sven Mallach. 2022. Spin Glass Service. Retrieved December 23 2022 from http:\/\/spinglass.uni-bonn.de\/."},{"issue":"14","key":"e_1_3_3_33_2","first-page":"1","article-title":"Quantum versus classical annealing: Insights from scaling theory and results for spin glasses on 3-regular graphs","volume":"114","author":"Liu Cheng Wei","year":"2015","unstructured":"Cheng Wei Liu, Anatoli Polkovnikov, and Anders W. Sandvik. 2015. Quantum versus classical annealing: Insights from scaling theory and results for spin glasses on 3-regular graphs. Phys. Rev. Lett. 114, 14 (2015), 1\u20135.","journal-title":"Phys. Rev. Lett."},{"key":"e_1_3_3_34_2","first-page":"23","volume-title":"Proceedings of the ACM International Conference on Computing Frontiers","author":"McGeoch C. C.","year":"2013","unstructured":"C. C. McGeoch and C. Wang. 2013. Experimental evaluation of an adiabiatic quantum system for combinatorial optimization. In Proceedings of the ACM International Conference on Computing Frontiers. ACM, New York, NY, 23."},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198509417.001.0001"},{"issue":"1","key":"e_1_3_3_36_2","first-page":"1","article-title":"Improving solutions by embedding larger subproblems in a D-Wave quantum annealer","volume":"9","author":"Okada Shuntaro","year":"2019","unstructured":"Shuntaro Okada, Masayuki Ohzeki, Masayoshi Terabe, and Shinichiro Taguchi. 2019. Improving solutions by embedding larger subproblems in a D-Wave quantum annealer. Sci. Rep. 9, 1 (2019), 1\u201310.","journal-title":"Sci. Rep."},{"key":"e_1_3_3_37_2","unstructured":"Dilina Perera Inimfon Akpabio Firas Hamze Salvatore Mandra Nathan Rose Maliheh Aramon and Helmut G. Katzgraber. 2020. Chook\u2014A comprehensive suite for generating binary optimization problems with planted solutions. arxiv:2005.14344. Retrieved from https:\/\/arxiv.org\/abs\/2005.14344."},{"issue":"12","key":"e_1_3_3_38_2","doi-asserted-by":"crossref","first-page":"123034","DOI":"10.1088\/1367-2630\/aa5079","article-title":"Inhomogeneous quasi-adiabatic driving of quantum critical dynamics in weakly disordered spin chains","volume":"18","author":"Rams Marek M.","year":"2016","unstructured":"Marek M. Rams, Masoud Mohseni, and Adolfo Del Campo. 2016. Inhomogeneous quasi-adiabatic driving of quantum critical dynamics in weakly disordered spin chains. New J. Phys. 18, 12 (2016), 123034.","journal-title":"New J. Phys."},{"key":"e_1_3_3_39_2","doi-asserted-by":"crossref","first-page":"025308","DOI":"10.1103\/PhysRevE.104.025308","article-title":"Approximate optimization, sampling, and spin-glass droplet discovery with tensor networks","volume":"104","author":"Rams Marek M.","year":"2021","unstructured":"Marek M. Rams, Masoud Mohseni, Daniel Eppens, Konrad Ja\u0142owiecki, and Bart\u0142omiej Gardas. 2021. Approximate optimization, sampling, and spin-glass droplet discovery with tensor networks. Phys. Rev. E 104, 2 (August2021), 025308.","journal-title":"Phys. Rev. E"},{"key":"e_1_3_3_40_2","unstructured":"J. Raymond and K. Boothby. 2022. The optimized C++ code is attached to paper supplementary materials."},{"key":"e_1_3_3_41_2","first-page":"295","volume-title":"Proceedings of the IEEE International Conference on Quantum Computing and Engineering (QCE\u201920)","author":"Raymond Jack","year":"2020","unstructured":"Jack Raymond, Ndiame Ndiaye, Gautam Rayaprolu, and Andrew D. King. 2020. Improving performance of logical qubits by parameter tuning and topology compensation. In Proceedings of the IEEE International Conference on Quantum Computing and Engineering (QCE\u201920). IEEE, 295\u2013305."},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.1068774"},{"key":"e_1_3_3_43_2","unstructured":"A Selby. 2014. QUBO-Chimera. Retrieved from https:\/\/github.com\/alex1770\/QUBO-Chimera."},{"key":"e_1_3_3_44_2","doi-asserted-by":"crossref","first-page":"013303","DOI":"10.1103\/PhysRevE.92.013303","article-title":"Comparing monte carlo methods for finding ground states of Ising spin glasses: Population annealing, simulated annealing, and parallel tempering","volume":"92","author":"Wang Wenlong","year":"2015","unstructured":"Wenlong Wang, Jonathan Machta, and Helmut G. Katzgraber. 2015. Comparing monte carlo methods for finding ground states of Ising spin glasses: Population annealing, simulated annealing, and parallel tempering. Phys. Rev. E 92, 1 (July2015), 013303.","journal-title":"Phys. Rev. E"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/1007771.55618"},{"issue":"7","key":"e_1_3_3_46_2","doi-asserted-by":"crossref","first-page":"77201","DOI":"10.1103\/PhysRevLett.115.077201","article-title":"Efficient cluster algorithm for spin glasses in any space dimension","volume":"115","author":"Zhu Zheng","year":"2015","unstructured":"Zheng Zhu, Andrew J. Ochoa, and Helmut G. Katzgraber. 2015. Efficient cluster algorithm for spin glasses in any space dimension. Phys. Rev. Lett. 115, 7 (August2015), 77201.","journal-title":"Phys. Rev. Lett."}],"container-title":["ACM Transactions on Quantum Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3579368","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3579368","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:27Z","timestamp":1750182567000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3579368"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,8]]},"references-count":45,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,9,30]]}},"alternative-id":["10.1145\/3579368"],"URL":"https:\/\/doi.org\/10.1145\/3579368","relation":{},"ISSN":["2643-6809","2643-6817"],"issn-type":[{"value":"2643-6809","type":"print"},{"value":"2643-6817","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,4,8]]},"assertion":[{"value":"2022-03-24","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-12-27","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-04-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}