Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Transactions on Computers

Hybrid Annealing Method Based on subQUBO Model Extraction With Multiple Solution Instances

Yuta Atobe, Masashi Tawada, Nozomu Togawa

Published Dec 28, 2021• 38 citations
Publisher

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<N_I)$solution instances among them and focus on a particular binary variable$x_i$in the$N_S$solution instances. If$x_i$value is muchvariedover$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.

DOI
10.1109/tc.2021.3138629

Related papers

A Novel Classical-Ising Hybrid Annealing Method with QUBO Model Cutting

Yuta Atobe, Masashi Tawada, Nozomu Togawa

Most quantum annealers, or Ising machines have the hardware limitations in its qubit size and thus the computable problem size is much limited. This paper proposes a novel classical-Ising hybrid annealing method which virtually extends the computable size of Ising machines based on a theoretical analysis. Given a quadratic unconstrained binary optimization (QUBO) model, the proposed method selects the cutting binary variable that is most likely to have the same value as the ground-state solution. Then, we recursively cut the QUBO model based on the cutting binary variable until we obtain sufficiently small-sized subQUBO models. Experimental evaluations demonstrate that the proposed hybrid annealing method can give much better quasi-ground-state solutions than state-of-the-art existing methods for large-sized QUBO models.

IEEE International Midwest Symposium on Circuits and Systems (MWSCAS)•Aug 11, 2024•0 citations

Trip Planning Based on subQUBO Annealing

Tatsuya Noguchi, Keisuke Fukada, Siya Bao +1 more

The trip planning problem (TPP) can be formulated as a combinatorial optimization problem that searches for the best route to visit a series of landmarks and hotels. Meanwhile, Ising machines have attracted attention due to their efficiency in solving combinatorial optimization problems. The Ising machines solve the combinatorial optimization problems by transforming the problems into quadratic unconstrained binary optimization (QUBO) models. However, the possible input QUBO size of current Ising machines is quite limited. Thus, it is hard to directly embed a large-scale TPP onto the current Ising machines. In this paper, we propose a novel subQUBO annealing method based on the combined variable selection method to solve the TPP. The proposed method finds a quasi-optimal solution to a large problem by repeatedly partitioning the original QUBO model into small subQUBOs that can be embedded onto the Ising machine. Specifically, to construct a subQUBO, we select variables from the original QUBO model, which have small deviation values. Further, we select variables randomly from the original QUBO model, so as not to fall into the local optimum. We have conducted an evaluation experiment using Ising machines on TPP and confirmed that the proposed method outperforms the state-of-the-art methods in terms of POI satisfaction and POI cost.

IEEE Access•Jan 1, 2023•9 citations

SubQUBO Construction Based on Grid Reduction Method Using an Ising Machine

Koki Mita, Takeru Ota, Nozomu Togawa

Ising machines can efficiently solve combinatorial optimization problems by mapping them to Ising or QUBO formulations while satisfying given constraints. However, their hardware limits the size of QUBO instances. To overcome this, subQUBO annealing decomposes large problems into smaller ones. Meanwhile, conventional subQUBO construction methods often violate the constraints originally given. In this paper, we propose a grid reduction method for subQUBO construction that explicitly considers the 2-way 1-hot constraint. It recursively fixes a variable to 1 and sets all other variables in the same row and column to 0. Remaining variables are used to construct subQUBOs with three strategies: index-based, deviation-based, and random-based extraction. Evaluation experiments using a real Ising machine demonstrates significant energy reduction over existing subQUBO construction methods.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•0 citations

ICD2S: A Hybrid Ising-Classical-Machines Data-Driven QUBO Solver Method

Armin Abdollahi, Mehdi Kamal, Massoud Pedram

We present a heuristic algorithm designed to solve Quadratic Unconstrained Binary Optimization (QUBO) problems efficiently. The algorithm, referred to as IC-D2S, leverages a hybrid approach using Ising and classical machines to address very large problem sizes. Considering the practical limitation on the size of the Ising machine (IM), our algorithm partitions the QUBO problem into a collection of QUBO subproblems (called subQUBOs) and utilizes the IM to solve each subQUBO. Our proposed heuristic algorithm uses a set of control parameters to generate the subQUBOs and explore the search space. Also, it utilizes an annealer based on cosine waveform and applies a mutation operator at each step of the search to diversify the solution space and facilitate the process of finding the global minimum of the problem. We have evaluated the effectiveness of our IC-D2S algorithm on three large-sized problem sets and compared its efficiency in finding the (near-)optimal solution with three QUBO solvers. One of the solvers is a software-based algorithm (D2TS), while the other one (D-Wave) employs a similar approach to ours, utilizing both classical and Ising machines. The results demonstrate that for large-sized problems (≥ 5000) the proposed algorithm identifies superior solutions. Additionally, for smaller-sized problems (= 2500), IC-D2S efficiently finds the optimal solution in a significantly faster manner.

Asia and South Pacific Design Automation Conference (ASP-DAC)•Jan 20, 2025•2 citations

SubQUBO Annealing Based on Efficient Binary Variable Selection for Combinatorial Optimization Problems with One-Hot Constraints

Tatsuya Noguchi, Keisuke Fukada, Siya Bao +1 more

In combinatorial optimization problems with one-hot constraints, the number of binary variables that have the value of one in the feasible solution becomes constant and small, so it is important to always consider them to escalate the solution searching process and obtain a more converged solution in annealing. In this paper, we propose a method to preferably select binary variables with the value of one in the subQUBO annealing process using Ising machines such as quantum annealers. Evaluation experiments show that the proposed method obtains a solution with lower energy than a conventional subQUBO method and a full QUBO method.

International Conference on Consumer Electronics•Jan 11, 2025•1 citation

IC-D2S: A Hybrid Ising-Classical-Machines Data-Driven QUBO Solver Method

Armin Abdollahi, Mehdi Kamal, Massoud Pedram

We present a heuristic algorithm designed to solve Quadratic Unconstrained Binary Optimization (QUBO) problems efficiently. The algorithm, referred to as IC-D2S, leverages a hybrid approach using Ising and classical machines to address very large problem sizes. Considering the practical limitation on the size of the Ising machine(IM), our algorithm partitions the QUBO problem into a collection of QUBO subproblems (called subQUBOs) and utilizes the IM to solve each subQUBO. Our proposed heuristic algorithm uses a set of control parameters to generate the subQUBOs and explore the search space. Also, it utilizes an annealer based on cosine waveform and applies a mutation operator at each step of the search to diversify the solution space and facilitate the process of finding the global minimum of the problem. We have evaluated the effectiveness of our IC-D2S algorithm on three large-sized problem sets and compared its efficiency in finding the (near-)optimal solution with three QUBO solvers. One of the solvers is a software-based algorithm (D2TS), while the other one (D-Wave) employs a similar approach to ours, utilizing both classical and Ising machines. The results demonstrate that for large-sized problems (>= 5000) the proposed algorithm identifies superior solutions. Additionally, for smaller-sized problems (= 2500), IC-D2S efficiently finds the optimal solution in a significantly faster manner.

arXiv:2502.13947•Feb 19, 2025•0 citations
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 obtainsNIN_INI​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 selectN_S$$(N_S<N_I)solution instances among them and focus on a particular binary variablexix_ixi​in theNSN_SNS​solution instances. Ifxix_ixi​value is muchvariedoverNSN_SNS​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.
Most quantum annealers, or Ising machines have the hardware limitations in its qubit size and thus the computable problem size is much limited. This paper proposes a novel classical-Ising hybrid annealing method which virtually extends the computable size of Ising machines based on a theoretical analysis. Given a quadratic unconstrained binary optimization (QUBO) model, the proposed method selects the cutting binary variable that is most likely to have the same value as the ground-state solution. Then, we recursively cut the QUBO model based on the cutting binary variable until we obtain sufficiently small-sized subQUBO models. Experimental evaluations demonstrate that the proposed hybrid annealing method can give much better quasi-ground-state solutions than state-of-the-art existing methods for large-sized QUBO models.
The trip planning problem (TPP) can be formulated as a combinatorial optimization problem that searches for the best route to visit a series of landmarks and hotels. Meanwhile, Ising machines have attracted attention due to their efficiency in solving combinatorial optimization problems. The Ising machines solve the combinatorial optimization problems by transforming the problems into quadratic unconstrained binary optimization (QUBO) models. However, the possible input QUBO size of current Ising machines is quite limited. Thus, it is hard to directly embed a large-scale TPP onto the current Ising machines. In this paper, we propose a novel subQUBO annealing method based on the combined variable selection method to solve the TPP. The proposed method finds a quasi-optimal solution to a large problem by repeatedly partitioning the original QUBO model into small subQUBOs that can be embedded onto the Ising machine. Specifically, to construct a subQUBO, we select variables from the original QUBO model, which have small deviation values. Further, we select variables randomly from the original QUBO model, so as not to fall into the local optimum. We have conducted an evaluation experiment using Ising machines on TPP and confirmed that the proposed method outperforms the state-of-the-art methods in terms of POI satisfaction and POI cost.
Ising machines can efficiently solve combinatorial optimization problems by mapping them to Ising or QUBO formulations while satisfying given constraints. However, their hardware limits the size of QUBO instances. To overcome this, subQUBO annealing decomposes large problems into smaller ones. Meanwhile, conventional subQUBO construction methods often violate the constraints originally given. In this paper, we propose a grid reduction method for subQUBO construction that explicitly considers the 2-way 1-hot constraint. It recursively fixes a variable to 1 and sets all other variables in the same row and column to 0. Remaining variables are used to construct subQUBOs with three strategies: index-based, deviation-based, and random-based extraction. Evaluation experiments using a real Ising machine demonstrates significant energy reduction over existing subQUBO construction methods.
We present a heuristic algorithm designed to solve Quadratic Unconstrained Binary Optimization (QUBO) problems efficiently. The algorithm, referred to as IC-D2S, leverages a hybrid approach using Ising and classical machines to address very large problem sizes. Considering the practical limitation on the size of the Ising machine (IM), our algorithm partitions the QUBO problem into a collection of QUBO subproblems (called subQUBOs) and utilizes the IM to solve each subQUBO. Our proposed heuristic algorithm uses a set of control parameters to generate the subQUBOs and explore the search space. Also, it utilizes an annealer based on cosine waveform and applies a mutation operator at each step of the search to diversify the solution space and facilitate the process of finding the global minimum of the problem. We have evaluated the effectiveness of our IC-D2S algorithm on three large-sized problem sets and compared its efficiency in finding the (near-)optimal solution with three QUBO solvers. One of the solvers is a software-based algorithm (D2TS), while the other one (D-Wave) employs a similar approach to ours, utilizing both classical and Ising machines. The results demonstrate that for large-sized problems (≥ 5000) the proposed algorithm identifies superior solutions. Additionally, for smaller-sized problems (= 2500), IC-D2S efficiently finds the optimal solution in a significantly faster manner.
In combinatorial optimization problems with one-hot constraints, the number of binary variables that have the value of one in the feasible solution becomes constant and small, so it is important to always consider them to escalate the solution searching process and obtain a more converged solution in annealing. In this paper, we propose a method to preferably select binary variables with the value of one in the subQUBO annealing process using Ising machines such as quantum annealers. Evaluation experiments show that the proposed method obtains a solution with lower energy than a conventional subQUBO method and a full QUBO method.
We present a heuristic algorithm designed to solve Quadratic Unconstrained Binary Optimization (QUBO) problems efficiently. The algorithm, referred to as IC-D2S, leverages a hybrid approach using Ising and classical machines to address very large problem sizes. Considering the practical limitation on the size of the Ising machine(IM), our algorithm partitions the QUBO problem into a collection of QUBO subproblems (called subQUBOs) and utilizes the IM to solve each subQUBO. Our proposed heuristic algorithm uses a set of control parameters to generate the subQUBOs and explore the search space. Also, it utilizes an annealer based on cosine waveform and applies a mutation operator at each step of the search to diversify the solution space and facilitate the process of finding the global minimum of the problem. We have evaluated the effectiveness of our IC-D2S algorithm on three large-sized problem sets and compared its efficiency in finding the (near-)optimal solution with three QUBO solvers. One of the solvers is a software-based algorithm (D2TS), while the other one (D-Wave) employs a similar approach to ours, utilizing both classical and Ising machines. The results demonstrate that for large-sized problems (>= 5000) the proposed algorithm identifies superior solutions. Additionally, for smaller-sized problems (= 2500), IC-D2S efficiently finds the optimal solution in a significantly faster manner.