Hybrid Annealing Method Based on subQUBO Model Extraction With Multiple Solution Instances
Open accessThe DOI matches its Crossref record; 35 of the 35 references it cites were found in a registry or an index.
Abstract
Ising machines are expected to solve combinatorial optimization problems efficiently by representing them as Ising models or equivalent quadratic unconstrained binary optimization (QUBO) models . However, upper bound exists on the computable problem size due to the hardware limitations of Ising machines. This paper propose a new hybrid annealing method based on partial QUBO extraction, called subQUBO model extraction, with multiple solution instances. For a given QUBO model, the proposed method obtains$N_I$quasi-optimal solutions (quasi-ground-state solutions) in some way using a classical computer. The solutions giving these quasi-optimal solutions are calledsolution instances. We extract a size-limited subQUBO model as follows based on a strong theoretical background: we randomly select$N_S$$(N_S
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 source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“HQA (Leap Hybrid solver), developed by D-Wave systems, also decomposes large QUBO into smaller subproblems wellsuited for QA ' s QPU, and then aggregates the results 27,44 .”
From Quantum annealing for combinatorial optimization: a benchmarking study (2025) · cites this paper as [27]
Experimental — accuracy not yet measuredThe cited source says what the claim attributes to it.
In the citing paper
“In addition, a QUBO decomposition algorithm (i.e., QBSolv) splits a large QUBO matrix into small pieces of subQUBO matrices, allowing us to handle a QUBO matrix with dimensions higher than the maximum number of qubits in the QA hardware 26,27 .”
From Quantum annealing for combinatorial optimization: a benchmarking study (2025) · cites this paper as [27]
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
An Effective Heuristic Algorithm for the Traveling-Salesman Problem
Lin, S., & Kernighan, B. W. (1973) · Operations Research · doi:10.1287/opre.21.2.498 · Cited by 3,821 · cited 2×
“A method based on the impact values was proposed in [10], while a method based on k-opt local search [12], [13] was proposed in [9].”
MethodIsing formulations of many NP problems
Lucas, A. (2014) · Frontiers in Physics · doi:10.3389/fphy.2014.00005 · Cited by 2,512 · cited 1×
“(1) [1], [14], [15].”
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 1×
“Isingmachinesinclude,forexample,D-Wave Systems’quantumannealingmachines[4],[16],[17],Hitachi’s CMOSannealingmachines[18],[19],andFujitsu’sdigital annealers[5],[6].”
A Method for Solving Traveling-Salesman Problems
Croes, G. A. (1958) · Operations Research · doi:10.1287/opre.6.6.791 · Cited by 1,570
Traffic Flow Optimization Using a Quantum Annealer
Neukart, F., Compostella, G., Seidel, C., von Dollen, D., Yarkoni, S., & Parney, B. (2017) · Frontiers in ICT · doi:10.3389/fict.2017.00029 · Cited by 458 · cited 2×
“, route optimization for transportation or logistics and optimal control of robot behavior) [1], [2], [3].”
BackgroundPhysics-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 · cited 3×
“To tackle this problem, Ising machines have recently been focused on as a new computer architecture [4], [5], [6].”
MethodMinor-embedding in adiabatic quantum computation: I. The parameter setting problem
Choi, V. (2008) · Quantum Information Processing · doi:10.1007/s11128-008-0082-9 · Cited by 410 · cited 2×
“AlthoughtheD-Wave2000Qmachine[4]hasapproxi-mately 2000 qubits, it can only deal with a maximum of 64 binary variables of a QUBO model if all the binary variables are connected to each other due to hardware limitations [7], [8].”
BackgroundCombinatorial optimization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems
Goto, H., Tatsumura, K., & Dixon, A. R. (2019) · Science Advances · doi:10.1126/sciadv.aav2372 · Cited by 405 · cited 1×
“Isingmachines based on computational principles different from quantum annealing and simulated annealing includeNTT’s coherent Isingmachines [20] and Toshiba’s simulatedbifurcationmachines [21].”
BackgroundQAPLIB-A quadratic assignment problem library
Burkard, R. E., Karisch, S., & Rendl, F. (1991) · European Journal of Operational Research · doi:10.1016/0377-2217(91)90197-4 · Cited by 332
Architectural Considerations in the Design of a Superconducting Quantum Annealing Processor
Bunyk, P. I., Hoskinson, E. M., Johnson, M. W., Tolkacheva, E., Altomare, F., Berkley, A. J., Harris, R., Hilton, J. P., Lanting, T., Przybysz, A. J., et al. (2014) · IEEE Transactions on Applied Superconductivity · doi:10.1109/tasc.2014.2318294 · Cited by 312 · cited 1×
“Isingmachinesinclude,forexample,D-Wave Systems’quantumannealingmachines[4],[16],[17],Hitachi’s CMOSannealingmachines[18],[19],andFujitsu’sdigital annealers[5],[6].”
Minor-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×
“AlthoughtheD-Wave2000Qmachine[4]hasapproxi-mately 2000 qubits, it can only deal with a maximum of 64 binary variables of a QUBO model if all the binary variables are connected to each other due to hardware limitations [7], [8].”
BackgroundAdaptive Memory Tabu Search for Binary Quadratic Programs
Glover, F., Kochenberger, G. A., & Alidaee, B. (1998) · Management Science · doi:10.1287/mnsc.44.3.336 · Cited by 209 · cited 1×
“For evaluations (1) and (2), the Ising machine was simulated by the tabu search [31] on the CPU of a local machine.”
MethodA Hybrid Solution Method for the Capacitated Vehicle Routing Problem Using a Quantum Annealer
Feld, S., Roch, C., Gabor, T., Seidel, C., Neukart, F., Galter, I., Mauerer, W., & Linnhoff-Popien, C. (2019) · Frontiers in ICT · doi:10.3389/fict.2019.00013 · Cited by 188 · cited 1×
“However, it is not directly related to annealing process time [34], [35].”
BackgroundApplication of Ising Machines and a Software Development for Ising Machines
Tanahashi, K., Takayanagi, S., Motohashi, T., & Tanaka, S. (2019) · Journal of the Physical Society of Japan · doi:10.7566/jpsj.88.061010 · Cited by 142 · cited 1×
“(1) [1], [14], [15].”
Discrete optimization using quantum annealing on sparse Ising models
Bian, Z., Chudak, F., Israel, R., Lackey, B., Macready, W. G., & Roy, A. (2014) · Frontiers in Physics · doi:10.3389/fphy.2014.00056 · Cited by 129 · cited 1×
“Note that several studies proposed subQUBO model extraction methods for specific problems, such as the maximum-clique problem in [24], [25], [26], the constraint satisfaction problem in [27], and the maximum constraint satisfaction problem in [28].”
Background24.3 20k-spin Ising chip for combinational optimization problem with CMOS annealing
Yamaoka, M., Yoshimura, C., Hayashi, M., Okuyama, T., Aoki, H., & Mizuno, H. (2015) · Digest of technical papers/Digest of technical papers - IEEE International Solid-State Circuits Conference · doi:10.1109/isscc.2015.7063111 · Cited by 114 · cited 1×
“Isingmachinesinclude,forexample,D-Wave Systems’quantumannealingmachines[4],[16],[17],Hitachi’s CMOSannealingmachines[18],[19],andFujitsu’sdigital annealers[5],[6].”
Path relinking for unconstrained binary quadratic programming
Wang, Y., Lü, Z., Glover, F., & Hao, J. (2012) · European Journal of Operational Research · doi:10.1016/j.ejor.2012.07.012 · Cited by 101 · cited 1×
“This method utilized path relinking [23].”
An Accelerator Architecture for Combinatorial Optimization Problems
Tsukamoto, S., Motomu, T., Matsubara, S., & Hirotaka, T. (2017) · Fujitsu Scientific and Technical Journal · Cited by 91
Mapping Constrained Optimization Problems to Quantum Annealing with Application to Fault Diagnosis
Bian, Z., Chudak, F., Israel, R. B., Lackey, B., Macready, W. G., & Roy, A. (2016) · Frontiers in ICT · doi:10.3389/fict.2016.00014 · Cited by 87 · cited 1×
“Note that several studies proposed subQUBO model extraction methods for specific problems, such as the maxi-mum-clique problem in [24], [25], [26], the constraint satisfaction problem in [27], and the maximum constraint satisfaction problem in [28].”
BackgroundFinding Maximum Cliques on the D-Wave Quantum Annealer
Chapuis, G., Djidjev, H., Hahn, G., & Rizk, G. (2019) · Journal of Signal Processing Systems · doi:10.1007/s11265-018-1357-8 · Cited by 70 · cited 1×
“Note that several studies proposed subQUBO model extraction methods for specific problems, such as the maximum-clique problem in [24], [25], [26], the constraint satisfaction problem in [27], and the maximum constraint satisfaction problem in [28].”
BackgroundBuilding an iterative heuristic solver for a quantum annealer
Rosenberg, G., Vazifeh, M., Woods, B., & Haber, E. (2016) · Computational Optimization and Applications · doi:10.1007/s10589-016-9844-y · Cited by 49 · cited 5×
“The simplest subQUBO model extraction method randomly chooses variables from the original QUBO model [9].”
MethodInfluentialMultirobot Routing Algorithms for Robots Operating in Vineyards
Thayer, T. C., Vougioukas, S. G., Goldberg, K., & Carpin, S. (2020) · IEEE Transactions on Automation Science and Engineering · doi:10.1109/tase.2020.2980854 · Cited by 40 · cited 2×
“the NP-hard problem, which is difficult to solve in a practical time using conventional computers because the number of variable combinations explosively increases as the number of variables increases [3].”
BackgroundSugie, Y., Yoshida, Y., Mertig, N., Takemoto, T., Teramoto, H., Nakamura, A., Takigawa, I., Minato, S.-I., Yamaoka, M., & Komatsuzaki, T. (2021) · Soft Computing · doi:10.1007/s00500-020-05502-6 · Cited by 39 · cited 1×
“Even for the CMOS annealing machines with approximately 100,000 bits, they can only deal with a maximum of approximately 300 binary variables when they are fully connected in the QUBO model [22].”
MethodSolving Large Maximum Clique Problems on a Quantum Annealer
Pelofske, E., Hahn, G., & Djidjev, H. (2019) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-14082-3_11 · Cited by 38 · cited 1×
“Note that several studies proposed subQUBO model extraction methods for specific problems, such as the maximum-clique problem in [24], [25], [26], the constraint satisfaction problem in [27], and the maximum constraint satisfaction problem in [28].”
BackgroundGarden optimization problems for benchmarking quantum annealers
Calaza, C. D. G., Willsch, D., & Michielsen, K. (2021) · Quantum Information Processing · doi:10.1007/s11128-021-03226-6 · Cited by 36 · cited 1×
“However, it is not directly related to annealing process time [34], [35].”
BackgroundSpatial computing architecture using randomness of memory cell stability under voltage control
Yoshimura, C., Yamaoka, M., Aoki, H., & Mizuno, H. (2013) · European Conference on Circuit Theory and Design · doi:10.1109/ecctd.2013.6662276 · Cited by 29 · cited 1×
“Isingmachinesinclude,forexample,D-Wave Systems’quantumannealingmachines[4],[16],[17],Hitachi’s CMOSannealingmachines[18],[19],andFujitsu’sdigital annealers[5],[6].”
Garden optimization problems for benchmarking quantum annealers
Gonzalez Calaza, C. D., Willsch, D., & Michielsen, K. F. L. (2021) · RWTH Publications (RWTH Aachen) · doi:10.18154/rwth-2021-09173 · Cited by 18
Bass, G., Tomlin, C., Kumar, V., Rihaczek, P., & Dulny, J. (2018) · Quantum Science and Technology · doi:10.1088/2058-9565/aaadc2 · Cited by 16 · cited 3×
“Several methods for extracting subQUBO models from an original QUBO model have been proposed [9], [10], [11].”
MethodCombinatorial Optimization by Decomposition on Hybrid CPU--non-CPU Solver ArchitecturesPreprint
Narimani, A., Rezaei, S. S. C., & Zaribafiyan, A. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1708.03439 · Cited by 11 · cited 1×
“Note that several studies proposed subQUBO model extraction methods for specific problems, such as the maxi-mum-clique problem in [24], [25], [26], the constraint satisfaction problem in [27], and the maximum constraint satisfaction problem in [28].”
BackgroundYanling, W., Deli, Y., & Guoqing, Y. (2010) · International Conference on Logistics Systems and Intelligent Management · doi:10.1109/iclsim.2010.5461441 · Cited by 10 · cited 1×
“, route optimization for transportation or logistics and optimal control of robot behavior) [1], [2], [3].”
BackgroundEQUAL: Improving the Fidelity of Quantum Annealers by Injecting Controlled Perturbations
Ayanzadeh, R., Das, P., Tannu, S., & Qureshi, M. K. (2022) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce53715.2022.00074 · Cited by 9
Finding Maximum Cliques on the D-Wave Quantum AnnealerPreprint
Chapuis, G., Djidjev, H. N., Hahn, G., & Rizk, G. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1801.08649 · Cited by 5 · cited 1×
“Note that several studies proposed subQUBO model extraction methods for specific problems, such as the maximum-clique problem in [24], [25], [26], the constraint satisfaction problem in [27], and the maximum constraint satisfaction problem in [28].”
BackgroundSolving large Maximum Clique problems on a quantum annealerPreprint
Pelofske, E., Hahn, G., & Djidjev, H. N. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1901.07657 · cited 1×
“Note that several studies proposed subQUBO model extraction methods for specific problems, such as the maximum-clique problem in [24], [25], [26], the constraint satisfaction problem in [27], and the maximum constraint satisfaction problem in [28].”
BackgroundSugie, Y., Yoshida, Y., Mertig, N., et al. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2004.03819 · cited 1×
“Even for the CMOS annealing machines with approximately 100,000 bits, they can only deal with a maximum of approximately 300 binary variables when they are fully connected in the QUBO model [22].”
MethodEQUAL: Improving the Fidelity of Quantum Annealers by Injecting Controlled PerturbationsPreprint
Ayanzadeh, R., Das, P., Tannu, S., et al. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2108.10964
Research works printed but not linked: 2
- [4] D-Wave Systems Inc., 'D-Wave announces D-Wave 2000Q quantum computer,' Accessed: Jan., 2021. [Online]. Available: https:// www.dwavesys.com/press-releases/d-wave-announces-d-wave2000q-quantum-computer -
- [20] T. Inagaki et al. , 'A coherent Ising machine for 2000-node optimization problems,' Science , vol. 354, no. 6312, pp. 603-606, 2016. [Online]. Available: https://science.sciencemag.org/content/354/ 6312/603 -
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
“In addition, a QUBO decomposition algorithm(i.e.,QBSolv)splitsalargeQUBOmatrixintosmallpiecesofsub-QUBOmatrices,allowingustohandleaQUBOmatrixwithdimensions higherthanthemaximumnumberofqubitsintheQAhardware 26,27 .”
Kim, S., Pascuzzi, V. R., Xu, Z., Luo, T., Lee, E., & Suh, I. (2026) · npj Quantum Information · doi:10.1038/s41534-026-01283-2 · Cited by 31
“This QUBO decomposition can fi nd a true global optimal solution of an original large QUBO when preserving essential structure and interactions of the original problem 51,52 .”
Diverse Adaptive Bulk Search: a Framework for Solving QUBO Problems on Multiple GPUs
Nakano, K., Takafuji, D., Ito, Y., Yazane, T., Yano, J., Ozaki, S., Katsuki, R., & Mori, R. (2023) · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · doi:10.1109/ipdpsw59300.2023.00060 · Cited by 21
“QAP problems tai20a and tho30 have been used for evaluating a QUBO solver using the subQUBO model [40].”
MethodQuantum annealing-aided design of an ultrathin-metamaterial optical diode
Kim, S., Park, S.-J., Moon, S., Zhang, Q., Hwang, S., Kim, S.-K., Luo, T., & Lee, E. (2024) · Nano Convergence · doi:10.1186/s40580-024-00425-6 · Cited by 20
An Ising-Machine-Based Solver of Vehicle Routing Problem With Balanced Pick-Up
Bao, S., Tawada, M., Tanaka, S., & Togawa, N. (2023) · IEEE Transactions on Consumer Electronics · doi:10.1109/tce.2023.3335392 · Cited by 21
Self-citation
Metadata
- Authors
- Atobe, Y., Tawada, M., & Togawa, N.
- Affiliations
- Waseda University (JP)
- Venue
- IEEE Transactions on Computers
- Published
- 2022-10-01
- Volume
- 71
- Issue
- 10
- Pages
- 2606-2619
- ISSN
- 0018-9340 (ISSN-L)
- 1557-9956
- 2326-3814
- OpenAlex
- W4206549951
- Cited by
- 38
- References
- 32
- Citations by year
- 2026: 5 · 2025: 19 · 2024: 8 · 2023: 6
- FWCI
- 1.24
- Type
- journal article
- Language
- en
- Open access
- hybrid
- doi.org
- Licence
- Locations
- IEEE Transactions on Computers (publishedVersion, cc-by-nc-nd)
- Funders
- New Energy and Industrial Technology Development Organization (P16007)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Artificial Intelligence › Metaheuristic Optimization Algorithms Research
- Physical Sciences › Mathematics › Numerical Analysis › Advanced Optimization Algorithms Research
- Keywords
- Ising machines, combinatorial optimization, quasi-optimal solutions, classical optimization, quantum annealing
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.