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 International Conference on Quantum Computing and Engineering (QCE)

SubQUBO Construction Based on Grid Reduction Method Using an Ising Machine

Koki Mita, Takeru Ota, Nozomu Togawa

Published Aug 30, 2025• 0 citations
Publisher

Abstract

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.

DOI
10.1109/qce65121.2025.10408

Related papers

Construction of SubQUBOs by K-Means Clustering of QUBO Variables

Yuko Kamishima, Shuta Kikuchi, Shu Tanaka

Ising machines are specialized solvers for combinatorial optimization problems (COPs), which are typically formulated as quadratic unconstrained binary optimization (QUBO) models. To enhance their performance, various methods have been proposed to construct subQUBOs by reducing the number of variables in the original QUBO. This study proposes a general subQUBO construction method applicable to a wide range of problems. The variables are clustered based on their interaction structure using theK-means clustering. A subQUBO is constructed from a randomly selected cluster and a pre-obtained tentative solution and then solved. This process of cluster selection and subQUBOs is performed iteratively. We evaluated the performance of the method on the quadratic assignment problem and compared it with two baselines: one that randomly reduces variables and another that directly solves the original QUBO without any variable reduction. Experimental evaluations demonstrated that the proposed method achieves high-accuracy solutions within the same computation time, particularly for large problem sizes.

IEEE Access•Jan 1, 2025•1 citation

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

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

Yuta Atobe, Masashi Tawada, Nozomu Togawa

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.

IEEE Transactions on Computers•Dec 28, 2021•38 citations

Dynamic Variable Selection for subQUBO Annealing Using Hamming Weight

Yoshihito Saito, Koki Mita, Nozomu Togawa

Although Ising machines can efficiently solve combinatorial optimization problems, their direct application to largescale instances is infeasible due to an upper limit on the number of input variables. An effective approach to overcome this limitation is to partition the problem into smaller subproblems, known as subQUBOs. In this paper, we propose a dynamic variable selection method for subQUBOs that considers the Hamming weight of current solutions. Our proposed method constructs a subQUBO by dynamically selecting variables that are assigned a value of ‘1’—that is, focusing on the Hamming weight—in the current solution during the annealing process. This approach is expected to facilitate more substantial energy updates during iterations, thereby increasing the probability of finding optimal or near-optimal solutions. Finally, we demonstrate the effectiveness of our proposed method through experimental evaluations.

International Conference on Consumer Electronics•Feb 3, 2026•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

Spin-Variable Reduction Method for Handling Linear Equality Constraints in Ising Machines

Tatsuhiko Shirai, Nozomu Togawa

We propose a spin-variable reduction method for Ising machines to handle linear equality constraints in a combinatorial optimization problem. Ising machines including quantum-annealing machines can effectively solve combinatorial optimization problems. They are designed to find the lowest-energy solution of a quadratic unconstrained binary optimization (QUBO), which is mapped from the combinatorial optimization problem. The proposed method reduces the number of binary variables to formulate the QUBO compared to the conventional penalty method. We demonstrate a sufficient condition to obtain the optimum of the combinatorial optimization problem in the spin-variable reduction method and its general applicability. We apply it to typical combinatorial optimization problems, such as the graph κ-partitioning problem and the quadratic assignment problem. Experiments using simulated-annealing and quantum-annealing based Ising machines demonstrate that the spin-variable reduction method outperforms the penalty method. The proposed method extends the application of Ising machines to larger-size combinatorial optimization problems with linear equality constraints.

IEEE Transactions on Computers•Jan 24, 2023•11 citations
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.
Ising machines are specialized solvers for combinatorial optimization problems (COPs), which are typically formulated as quadratic unconstrained binary optimization (QUBO) models. To enhance their performance, various methods have been proposed to construct subQUBOs by reducing the number of variables in the original QUBO. This study proposes a general subQUBO construction method applicable to a wide range of problems. The variables are clustered based on their interaction structure using theK-means clustering. A subQUBO is constructed from a randomly selected cluster and a pre-obtained tentative solution and then solved. This process of cluster selection and subQUBOs is performed iteratively. We evaluated the performance of the method on the quadratic assignment problem and compared it with two baselines: one that randomly reduces variables and another that directly solves the original QUBO without any variable reduction. Experimental evaluations demonstrated that the proposed method achieves high-accuracy solutions within the same computation time, particularly for large problem sizes.
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.
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 selectNSN_SNS​(NS<NI)(N_S<N_I)(NS​<NI​)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.
Although Ising machines can efficiently solve combinatorial optimization problems, their direct application to largescale instances is infeasible due to an upper limit on the number of input variables. An effective approach to overcome this limitation is to partition the problem into smaller subproblems, known as subQUBOs. In this paper, we propose a dynamic variable selection method for subQUBOs that considers the Hamming weight of current solutions. Our proposed method constructs a subQUBO by dynamically selecting variables that are assigned a value of ‘1’—that is, focusing on the Hamming weight—in the current solution during the annealing process. This approach is expected to facilitate more substantial energy updates during iterations, thereby increasing the probability of finding optimal or near-optimal solutions. Finally, we demonstrate the effectiveness of our proposed method through experimental evaluations.
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.
We propose a spin-variable reduction method for Ising machines to handle linear equality constraints in a combinatorial optimization problem. Ising machines including quantum-annealing machines can effectively solve combinatorial optimization problems. They are designed to find the lowest-energy solution of a quadratic unconstrained binary optimization (QUBO), which is mapped from the combinatorial optimization problem. The proposed method reduces the number of binary variables to formulate the QUBO compared to the conventional penalty method. We demonstrate a sufficient condition to obtain the optimum of the combinatorial optimization problem in the spin-variable reduction method and its general applicability. We apply it to typical combinatorial optimization problems, such as the graph κ-partitioning problem and the quadratic assignment problem. Experiments using simulated-annealing and quantum-annealing based Ising machines demonstrate that the spin-variable reduction method outperforms the penalty method. The proposed method extends the application of Ising machines to larger-size combinatorial optimization problems with linear equality constraints.