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

International Conference on Consumer Electronics

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

Tatsuya Noguchi, Keisuke Fukada, Siya Bao, Nozomu Togawa

Published Jan 11, 2025• 1 citation
Publisher

Abstract

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.

DOI
10.1109/icce63647.2025.10929951

Related papers

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

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

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

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

Constraint-Parameterized Spin-Variable Reduction Method for QAP

Raio Aoki, Takeru Ota, Tatsuhiko Shirai +1 more

Developing novel quadratic unconstrained binary optimization (QUBO) formulations is important to enhance the performance of the Ising machines. The spin-variable reduction (SVR) method formulates the QUBO with fewer binary variables than the penalty method. However, the SVR method can complicate the energy landscape. To address this issue, we propose a constraint-parameterized SVR method for the combinatorial optimization problems with a 2-way 1-hot constraint such as the quadratic assignment problem (QAP). Our proposed method introduces two key elements: (1) preliminary analysis using simulated annealing (SA) to statistically identify the variable that has a high probability of being the value of 1, and (2) parameterization of the SVR constraint term using this statistical information. Experiments on QAP benchmarks show that our method can find higher-precision solutions more efficiently than conventional SVR or the penalty method in certain cases.

International Conference on Consumer Electronics•Feb 3, 2026•0 citations
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.
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.
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 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.
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.
Developing novel quadratic unconstrained binary optimization (QUBO) formulations is important to enhance the performance of the Ising machines. The spin-variable reduction (SVR) method formulates the QUBO with fewer binary variables than the penalty method. However, the SVR method can complicate the energy landscape. To address this issue, we propose a constraint-parameterized SVR method for the combinatorial optimization problems with a 2-way 1-hot constraint such as the quadratic assignment problem (QAP). Our proposed method introduces two key elements: (1) preliminary analysis using simulated annealing (SA) to statistically identify the variable that has a high probability of being the value of 1, and (2) parameterization of the SVR constraint term using this statistical information. Experiments on QAP benchmarks show that our method can find higher-precision solutions more efficiently than conventional SVR or the penalty method in certain cases.