Building an iterative heuristic solver for a quantum annealer
Open accessThe DOI matches its Crossref record; 6 of the 6 references it cites were found in a registry or an index.
Abstract
A quantum annealer heuristically minimizes quadratic unconstrained binary optimization (QUBO) problems, but is limited by the physical hardware in the size and density of the problems it can handle. We have developed a meta-heuristic solver that utilizes D-Wave Systems’ quantum annealer (or any other QUBO problem optimizer) to solve larger or denser problems, by iteratively solving subproblems, while keeping the rest of the variables fixed. We present our algorithm, several variants, and the results for the optimization of standard QUBO problem instances from OR-Library of sizes 500 and 2500 as well as the Palubeckis instances of sizes 3000–7000. For practical use of the solver, we show the dependence of the time to best solution on the desired gap to the best known solution. In addition, we study the dependence of the gap and the time to best solution on the size of the problems solved by the underlying optimizer. Our results were obtained by simulation, using a tabu 1-opt solver, due to the huge number of runs required and limited quantum annealer time availability.
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.
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
Quantum 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 1×
“This might provide a speedup for some problem classes [27,41,75].”
BackgroundBoros, E., & Hammer, P. L. (2002) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(01)00341-9 · Cited by 827 · cited 2×
“Many NP-hard combinatorial optimization problems arise naturally or can easily be reformulated as QUBO problems, such as the quadratic assignment problem, the maximum cut problem, the maximum clique problem, the set packing problem, and the graph colouring problem (see, for instance, Boros and Prékopa [18], Boros and…”
BackgroundEvidence for quantum annealing with more than one hundred qubits
Boixo, S., Rønnow, T. F., Isakov, S. V., Wang, Z., Wecker, D., Lidar, D. A., Martinis, J. M., & Troyer, M. (2014) · Nature Physics · doi:10.1038/nphys2900 · Cited by 810
Defining and detecting quantum speedup
Rønnow, T. F., Wang, Z., Job, J., Boixo, S., Isakov, S. V., Wecker, D., Martinis, J. M., Lidar, D. A., & Troyer, M. (2014) · Science · doi:10.1126/science.1252319 · Cited by 601
What is the Computational Value of Finite-Range Tunneling?
Denchev, V. S., Boixo, S., Isakov, S. V., Ding, N., Babbush, R., Smelyanskiy, V., Martinis, J., & Neven, H. (2016) · Physical Review X · doi:10.1103/physrevx.6.031015 · Cited by 399
A quantum annealing architecture with all-to-all connectivity from local interactions
Lechner, W., Hauke, P., & Zoller, P. (2015) · Science Advances · doi:10.1126/sciadv.1500838 · Cited by 256
Cited by
Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
Aramon, M., Rosenberg, G., Valiante, E., Miyazawa, T., Tamura, H., & Katzgraber, H. G. (2019) · Frontiers in Physics · doi:10.3389/fphy.2019.00048 · Cited by 442
“For other alternative classical optimization techniques used in the literature to solve QUBO problems, the interested reader is referred to [22, 30, 51].”
MethodSelf-citationDesigning Peptides on a Quantum Computer
Mulligan, V. K., Melo, H., Merritt, H. I., Slocum, S., Weitzner, B. D., Watkins, A. M., Renfrew, P. D., Pelissier, C., Arora, P. S., & Bonneau, R. (2019) · doi:10.1101/752485 · Cited by 67
Multiblock ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers
Gambella, C., & Simonetto, A. (2020) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2020.3033139 · Cited by 60
Quinton, F. A., Myhr, P. A. S., Barani, M., Crespo del Granado, P., & Zhang, H. (2025) · Scientific Reports · doi:10.1038/s41598-025-96220-2 · Cited by 46
Hybrid Annealing Method Based on subQUBO Model Extraction With Multiple Solution Instances
Atobe, Y., Tawada, M., & Togawa, N. (2022) · IEEE Transactions on Computers · doi:10.1109/tc.2021.3138629 · Cited by 38
“The simplest subQUBO model extraction method randomly chooses variables from the original QUBO model [9].”
MethodInfluential
Metadata
- Authors
- Rosenberg, G., Vazifeh, M., Woods, B., & Haber, E.
- Venue
- Computational Optimization and Applications
- Published
- 2016-04-23
- Volume
- 65
- Issue
- 3
- Pages
- 845-869
- ISSN
- 0926-6003 (ISSN-L)
- 1573-2894
- OpenAlex
- W3106015846
- Cited by
- 49
- References
- 6
- FWCI
- 4.98
- Type
- journal article
- Language
- en
- Open access
- green
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Building an iterative heuristic solver for a quantum annealer. https://app.cochat.ai/papers/10.1007/s10589-016-9844-y
- The paper
- Rosenberg, G., Vazifeh, M., Woods, B., & Haber, E. (2016). Building an iterative heuristic solver for a quantum annealer. Computational Optimization and Applications. https://doi.org/10.1007/s10589-016-9844-y
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.