Hybrid Annealing Method Based on subQUBO Model Extraction With Multiple Solution Instances
Open Access
- 28 December 2021
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 71 (10) , 2606-2619
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 called solution instances . We extract a size-limited subQUBO model as follows based on a strong theoretical background: we randomly select $N_S$ $(N_S solution instances among them and focus on a particular binary variable $x_i$ in the $N_S$ solution instances. If $x_i$ value is much varied over $N_S$ solution instances, it is included in the subQUBO model; otherwise, it is not. We find a (quasi-)ground-state solution of the extracted subQUBO model using an Ising machine and add it as a new solution instance. By repeating this process, we can finally obtain a (quasi-)ground-state solution of the original QUBO model. Experimental evaluations confirm that the proposed method can obtain better quasi-ground-state solution than existing methods for large-sized QUBO models.
Keywords
Funding Information
- New Energy and Industrial Technology Development Organization (P16007)
This publication has 23 references indexed in Scilit:
- Mapping Constrained Optimization Problems to Quantum Annealing with Application to Fault DiagnosisFrontiers in ICT, 2016
- Building an iterative heuristic solver for a quantum annealerComputational Optimization and Applications, 2016
- 24.3 20k-spin Ising chip for combinational optimization problem with CMOS annealing2015
- Discrete optimization using quantum annealing on sparse Ising modelsFrontiers in Physics, 2014
- Architectural Considerations in the Design of a Superconducting Quantum Annealing ProcessorIEEE Transactions on Applied Superconductivity, 2014
- Ising formulations of many NP problemsFrontiers in Physics, 2014
- Quantum annealing with manufactured spinsNature, 2011
- Minor-embedding in adiabatic quantum computation: II. Minor-universal graph designQuantum Information Processing, 2010
- Minor-embedding in adiabatic quantum computation: I. The parameter setting problemQuantum Information Processing, 2008
- Adaptive Memory Tabu Search for Binary Quadratic ProgramsManagement Science, 1998