Hybrid Quantum Annealing for Larger-than-QPU Lattice-structured Problems
Open accessThe DOI matches its Crossref record; 37 of the 37 references it cites were found in a registry or an index.
Abstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The check wasn’t confident either way, so it gives no verdict — never disputed.
In the citing paper
“This algorithm enables us to handle a wide range of complex realworld problems 21,22,43 .”
From Quantum annealing for combinatorial optimization: a benchmarking study (2025) · cites this paper as [43]
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Optimization by Simulated Annealing
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983) · Science · doi:10.1126/science.220.4598.671 · Cited by 45,134 · cited 3×
“A variety of classical non-hybrid methods might be employed for optimization, including singlebit-flip based SA and steepest greedy descent (SGD) presented in this section [30].”
InfluentialQuantum annealing in the transverse Ising model
Kadowaki, T., & Nishimori, H. (1998) · Physical Review E · doi:10.1103/physreve.58.5355 · Cited by 2,339 · cited 3×
“For these models, quantum annealing (QA) and simulated (thermal) annealing (SA) are well-motivated heuristics for obtaining good upper bounds on the ground state on short timescales [2, 8–10]; we examine performance of these methods alongside other canonical algorithms.”
BackgroundMethodA Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
Farhi, E., Goldstone, J., Gutmann, S., Lapan, J., Lundgren, A., & Preda, D. (2001) · Science · doi:10.1126/science.1057726 · Cited by 2,056 · cited 1×
“1 The adiabatic theorem guarantees that slow evolution achieves a ground state of the problem Hamiltonian [11].”
Quantum annealing with manufactured spins
Johnson, M. W., Amin, M. H. S., Gildert, S., Lanting, T., Hamze, F., Dickson, N., Harris, R., Berkley, A. J., Johansson, J., Bunyk, P., et al. (2011) · Nature · doi:10.1038/nature10012 · Cited by 1,891 · cited 2×
“QA in the Advantage QPU operates with lux qubit states, which can be approximated as Ising spins [5, 24].”
Self-citationOn the computational complexity of Ising spin glass models
Barahona, F. (1982) · Journal of Physics A: Mathematical and General · doi:10.1088/0305-4470/15/10/028 · Cited by 1,306 · cited 1×
“Ising model ground state search is equivalent to quadratic unconstrained binary optimization (QUBO), an NP-complete problem [1].”
Statistical Physics of Spin Glasses and Information Processing: An Introduction
Nishimori, H. (2001) · doi:10.1093/acprof:oso/9780198509417.001.0001 · Cited by 1,182
Theory of Quantum Annealing of an Ising Spin Glass
Santoro, G. E., Martoňák, R., Tosatti, E., & Car, R. (2002) · Science · doi:10.1126/science.1068774 · Cited by 734 · cited 1×
“Thermal and quantum evolution-based heuristics such as SA and QA can perform well in spin glasses relative to other heuristics and exact methods, with experimental and theoretical work indicating quantum mechanisms that may bestow some advantages to QA [9, 23, 28, 41, 43].”
Quantum Annealing of a Disordered Magnet
Brooke, J., Bitko, D., F., T., Rosenbaum, & Aeppli, G. (1999) · Science · doi:10.1126/science.284.5415.779 · Cited by 518 · cited 3×
“For these models, quantum annealing (QA) and simulated (thermal) annealing (SA) are well-motivated heuristics for obtaining good upper bounds on the ground state on short timescales [2, 8–10]; we examine performance of these methods alongside other canonical algorithms.”
BackgroundMinor-embedding in adiabatic quantum computation: II. Minor-universal graph design
Choi, V. (2011) · Quantum Information Processing · doi:10.1007/s11128-010-0200-3 · Cited by 278 · cited 2×
“Minor embedding allows Ising problems that do not match the QPU architecture to be solved by annealing on D-Wave 2000Q and Advantage QPUs [6].”
BackgroundMethodPhase transitions in a programmable quantum spin glass simulator
Harris, R., Sato, Y., Berkley, A. J., Reis, M., Altomare, F., Amin, M. H., Boothby, K., Bunyk, P., Deng, C., Enderud, C., et al. (2018) · Science · doi:10.1126/science.aat2025 · Cited by 259 · cited 6×
“Spin glasses have been a staple of annealing benchmarking studies since the inception of annealing meth-ods, and have regularly been examined in the context of D-Wave QPUs and competitor technologies [2, 7, 8, 10, 17, 23, 36–41].”
InfluentialSelf-citationQuantum critical dynamics in a 5,000-qubit programmable spin glass
King, A. D., Raymond, J., Lanting, T., Harris, R., Zucca, A., Altomare, F., Berkley, A. J., Boothby, K., Ejtemaee, S., Enderud, C., et al. (2023) · Nature · doi:10.1038/s41586-023-05867-2 · Cited by 242 · cited 1×
“A demonstration that quantum annealing outperforms classical methods via quantum mechanisms in this algorithm is an outstanding issue, but direct solution of spin glasses in theory and practice show promising signs [28].”
Self-citationA practical heuristic for finding graph minors
Cai, J. L., Macready, W. G., & Roy, A. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1406.2741 · Cited by 219 · cited 1×
“Determining an embedding using chains of minimal size is NP-hard, and heuristics must be employed [10, 13, 35].”
Experimental evaluation of an adiabiatic quantum system for combinatorial optimization
McGeoch, C. C., & Wang, C. (2013) · Proceedings of the ACM International Conference on Computing Frontiers · doi:10.1145/2482767.2482797 · Cited by 166 · cited 3×
“QPU structured (Pegasus, Chimera, and Zephry) spin glasses are less studied but are a common benchmark for approximate optimization and like cubic lattices amenable to classical and quantum annealing heuristics [5, 7, 23, 26, 33].”
Self-citationFast clique minor generation in Chimera qubit connectivity graphs
Boothby, T., King, A. D., & Roy, A. (2016) · Quantum Information Processing · doi:10.1007/s11128-015-1150-6 · Cited by 156 · cited 2×
“For QPU architectures the most efficient forms of embedding are well understood for cliques [5, 21, 22].”
BackgroundSelf-citationOptimised simulated annealing for Ising spin glasses
Isakov, S. V., Zintchenko, I. N., Rønnow, T. F., & Troyer, M. (2015) · Computer Physics Communications · doi:10.1016/j.cpc.2015.02.015 · Cited by 149 · cited 2×
“in classical software frameworks [32], though these optimizations tend to be fragile to small changes in the lattice definition or coupler values, and yield only prefactor-type speed ups.”
BackgroundKatzgraber, H. G., Hamze, F., & Andrist, R. S. (2014) · Physical Review X · doi:10.1103/physrevx.4.021008 · Cited by 140 · cited 3×
“Some classical heuristics have demonstrated strong performance beyond annealing in lower dimensions, including 3D [38, 41], and additional methods have been proposed for leveraging structure in QPU architectures, in particular the cellular-level structure of Chimera graphs [4, 16, 36, 37].”
Next-Generation Topology of D-Wave Quantum Processors
Boothby, K., Bunyk, P., Raymond, J., & Roy, A. (2020) · arXiv · doi:10.48550/arxiv.2003.00133 · Cited by 125 · cited 8×
“For example, an 8 × 8 × 8 subspace of a cubic TABLE I. Properties of optimal embeddings by lattice class and QPU solver at maximum embeddable scale, given a fully-yielded QPU [5, 21, 23].”
InfluentialSelf-citationEfficient Cluster Algorithm for Spin Glasses in Any Space Dimension
Zhu, Z., Ochoa, A. J., & Katzgraber, H. G. (2015) · Physical Review Letters · doi:10.1103/physrevlett.115.077201 · Cited by 106
Improving solutions by embedding larger subproblems in a D-Wave quantum annealer
Okada, S., Ohzeki, M., Terabe, M., & Taguchi, S. (2019) · Scientific Reports · doi:10.1038/s41598-018-38388-4 · Cited by 92
Decoherence in adiabatic quantum computation
Amin, M. H. S., Averin, D. V., & Nesteroff, J. A. (2009) · Physical Review A · doi:10.1103/physreva.79.022107 · Cited by 88
Quantum Annealing amid Local Ruggedness and Global Frustration
King, J., Yarkoni, S., Raymond, J., Ozfidan, I., King, A. D., Nevisi, M. M., Hilton, J. P., & McGeoch, C. C. (2019) · Journal of the Physical Society of Japan · doi:10.7566/jpsj.88.061007 · Cited by 84 · cited 1×
“Alternative hardware platforms such as GPUs can also be leveraged exploiting lattice structure [14, 29].”
Self-citationWang, W., Machta, J., & Katzgraber, H. G. (2015) · Physical Review E · doi:10.1103/physreve.92.013303 · Cited by 81 · cited 1×
“Some classical heuristics have demonstrated strong performance beyond annealing in lower dimensions, including 3D [38, 41], and additional methods have been proposed for leveraging structure in QPU architectures, in particular the cellular-level structure of Chimera graphs [4, 16, 36, 37].”
Probing Noise in Flux Qubits via Macroscopic Resonant Tunneling
Harris, R., Johnson, M. W., Han, S., Berkley, A. J., Johansson, J., Bunyk, P., Ladizinsky, E., Govorkov, S., Thom, M. C., Uchaikin, S., et al. (2008) · Physical Review Letters · doi:10.1103/physrevlett.101.117003 · Cited by 81 · cited 1×
“In practice, evolution is subject to a inite evolution time, analog noise and model non-idealities, so that we arrive at a sample drawn from a distribution over low energy states, without a guarantee of optimality [1, 20].”
Self-citationLiu, C.-W., Polkovnikov, A., & Sandvik, A. W. (2015) · Physical Review Letters · doi:10.1103/physrevlett.114.147203 · Cited by 55
From near to eternity: Spin-glass planting, tiling puzzles, and constraint-satisfaction problems
Hamze, F., Jacob, D. C., Ochoa, A. J., Perera, D., Wang, W., & Katzgraber, H. G. (2018) · Physical review. E · doi:10.1103/physreve.97.043303 · Cited by 55
Tools and techniques for performance measurement of large distributed multiagent systems
Helsinger, A., Lazarus, R., Wright, W., & Zinky, J. A. (2003) · Adaptive Agents and Multi-Agents Systems · doi:10.1145/860575.860711 · Cited by 50 · cited 1×
“Unfortunately, the challenges of time measurement in distributed computation [16, 22, 44] mean that it is not possible to obtain wall-clock times for the full hybrid computation in a way that would meet acceptable levels of both precision and replicability.”
BackgroundInhomogeneous quasi-adiabatic driving of quantum critical dynamics in weakly disordered spin chains
Rams, M. M., Mohseni, M., & del Campo, A. (2016) · New Journal of Physics · doi:10.1088/1367-2630/aa5079 · Cited by 49 · cited 2×
“guided way between solved regions [25], or conditional indepen-”
BackgroundMethodMatching Microscopic and Macroscopic Responses in Glasses
Baity‐Jesi, M., Calore, E., la Cruz, A. D., Fernández, L. A., Gil-Narvion, J. M., Gordillo-Guerrero, A., Íñiguez, D., Maiorano, A., Marinari, E., Martín-Mayor, V., et al. (2017) · Physical Review Letters · doi:10.1103/physrevlett.118.157202 · Cited by 44 · cited 2×
“An exemplar for hard optimization problems over lat-tices are spin glasses [18].”
BackgroundApproximate optimization, sampling, and spin-glass droplet discovery with tensor networks
Rams, M. M., Mohseni, M., Eppens, D., Jałowiecki, K., & Gardas, B. (2021) · Physical review. E · doi:10.1103/physreve.104.025308 · Cited by 37 · cited 1×
“Classical methods have been proposed for leveraging structure in QPU architectures, in particular the low-connectivity and the gridlike cellular-level structure of Chimera graphs [6, 23, 26, 38, 42].”
Evaluating Ising Processing Units with Integer Programming
Coffrin, C., Nagarajan, H., & Bent, R. W. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-19212-9_11 · Cited by 36
Monitoring and performance measuring distributed systems during operation
Wybranietz, D., & Haban, D. (1988) · ACM SIGMETRICS Performance Evaluation Review · doi:10.1145/1007771.55618 · Cited by 35
Improving performance of logical qubits by parameter tuning and topology compensation
Raymond, J., Ndiaye, N., Rayaprolu, G., & King, A. D. (2020) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce49297.2020.00044 · Cited by 30 · cited 4×
“Post-processing may improve results when the QPU differs only by a few local (perhaps thermal) excitations from the ground state [35, 40].”
InfluentialSelf-citationProceedings of the ACM International Conference on Computing Frontiers
(2013) · doi:10.1145/2482767 · Cited by 21
Performance benefits of increased qubit connectivity in quantum annealing 3-dimensional spin glassesPreprint
King, A. D., & Bernoudy, W. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2009.12479 · Cited by 20 · cited 7×
“For example, an 8 × 8 × 8 subspace of a cubic TABLE I. Properties of optimal embeddings by lattice class and QPU solver at maximum embeddable scale, given a fully-yielded QPU [5, 21, 23].”
InfluentialSelf-citationChook -- A comprehensive suite for generating binary optimization problems with planted solutionsPreprint
Perera, D., Akpabio, I., Hamze, F., Mandrà, S., Rose, N., Aramon, M., & Katzgraber, H. G. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2005.14344 · Cited by 16 · cited 1×
“This is consistent with literature results on these tile-planted instances, which are hard for a variety of heuristics when frustration is large [19, 36].”
Estimating Execution Time of Distributed Applications
Drozdowski, M. (2002) · Lecture notes in computer science · doi:10.1007/3-540-48086-2_15 · Cited by 9 · cited 1×
“Unfortunately, the challenges of time measurement in distributed computation [16, 22, 43] mean that it is not possible to obtain wall-clock times for the full hybrid computation, in a way that would meet acceptable levels of both precision and replicability.”
Tools and techniques for performance measurement of large distributed multiagent systems
Helsinger, A., Lazarus, R., Wright, W., & Zinky, J. (2003) · Proceedings of the second international joint conference on Autonomous agents and multiagent systems - AAMAS '03 · doi:10.1145/860710.860711
Research works printed but not linked: 4
- Michael Booth, Steven P. Reinhardt, and Aidan Roy. 2017. Partitioning Optimization Problems for Hybrid Classical/Quantum Execution. D-Wave White Paper.
- 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. · arXiv
- Kelly Boothby, Andrew D. King, and Jack Raymond. 2021. Zephyr Topology of D-Wave Quantum Processors. D-Wave White Paper.
- 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–250.
Cited by
Quantum annealing for combinatorial optimization: a benchmarking study
Kim, S., Ahn, S.-W., Suh, I.-S., Dowling, A. W., Lee, E., & Luo, T. (2025) · npj Quantum Information · doi:10.1038/s41534-025-01020-1 · Cited by 46
“Thisalgorithmenablesustohandleawiderangeofcomplexreal-worldproblems 21,22,43 .”
Lim, Q. J., Ross, C., Ghosh, A., Vook, F. W., Gradoni, G., & Peng, Z. (2023) · IEEE Transactions on Antennas and Propagation · doi:10.1109/tap.2023.3298134 · Cited by 39
“In this article, we explore a hybrid classical–quantum algorithm based on the large neighborhood search heuristic algorithm [67], [68], [69].”
MethodSolving larger maximum clique problems using parallel quantum annealing
Pelofske, E., Hahn, G., & Djidjev, H. N. (2023) · Quantum Information Processing · doi:10.1007/s11128-023-03962-x · Cited by 44
“Usually, the programmed weight of the logical variable is uniformly distributed across the chain qubits, although alternative weight distributions are possible [61, 62].”
BackgroundFederated Quantum-Train with Batched Parameter Generation
Liu, C.-Y., & Chen, S. Y.-C. (2024) · International Conference on Information and Communication Technology Convergence (ICTC) · doi:10.1109/ictc62082.2024.10827567 · Cited by 32
Quantum annealing-assisted lattice optimization
Xu, Z., Shang, W., Kim, S., Lee, E., & Luo, T. (2025) · npj Computational Materials · doi:10.1038/s41524-024-01505-1 · Cited by 41
“In this work, we use the hybrid QA (HQA, powered by the hybrid partitioning algorithm 66 ) to address the challenge of high dimensional optimization (see Methods section for the details).”
Metadata
- Authors
- Raymond, J., Stevanovic, R., Bernoudy, W., Boothby, K., McGeoch, C. C., Berkley, A. J., Farré, P., Pasvolsky, J., & King, A. D.
- Affiliations
- D-Wave Systems (Canada) (CA)
- ORCID
- Venue
- ACM Transactions on Quantum Computing
- Published
- 2023-04-08
- Volume
- 4
- Issue
- 3
- Pages
- 1-30
- ISSN
- 2643-6809 (ISSN-L)
- 2643-6817
- OpenAlex
- W4319736340
- Cited by
- 39
- References
- 29
- Citations by year
- 2026: 4 · 2025: 13 · 2024: 11 · 2023: 11
- FWCI
- 3.45
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- ACM Transactions on Quantum Computing (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Artificial Intelligence › Metaheuristic Optimization Algorithms Research
- Physical Sciences › Computer Science › Hardware and Architecture › Parallel Computing and Optimization Techniques
- Keywords
- spin glass, simulated annealing, large-scale optimization
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.