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)

Constraint Coefficient Tuning of Spin-Variable Reduction for QAP

Raio Aoki, Tatsuhiko Shirai, Nozomu Togawa

Published Aug 30, 2025• 1 citation
Publisher

Abstract

Ising machines, including quantum annealers, have attracted much attention as an efficient solver for COPs (Combinatorial optimization problems). The SVR (Spin-Variable Reduction) method maps a COP with linear equality constraints to QUBO (Quadratic Unconstrained Binary Optimization) model, which is a common input for using the Ising machines. In this paper, we conduct a tuning of a constraint coefficient for this method using Quadratic Assignment Problems as a case study. We find that the optimal value of the constraint coefficient can be either larger or smaller than that used in the conventional penalty method, depending on the problem instance. We discuss the underlying mechanism responsible for this difference.

DOI
10.1109/qce65121.2025.10435

Related papers

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

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

Variable Reduction Method for Quadratic Three-Dimensional Assignment Problem with FMQA

Sora Tomita, Tatsuhiko Shirai, Nozomu Togawa

Ising machines including quantum annealers have attracted attention as efficient solvers for combinatorial optimization problems (COPs). To use Ising machines, the objective function and constraints of a COP must be expressed in a QUBO (quadratic unconstrained binary optimization) form. However, their application range is practically limited since some COPs are difficult to formulate in a QUBO form, or require a large number of binary variables. Quadratic three-dimensional assignment problem (Q3AP) is a challenging problem for Ising machines to solve since the number of required binary variables rapidly increases with the problem size N. In this paper, to overcome the difficulty, we propose a method to reduce the number of necessary variables from$N^{3}$to$2N^{2}$by using a factorization machine with quantum annealing (FMQA) to estimate QUBO through machine learning. Experimental results with a real Ising machine demonstrate that the proposed method can obtain the best-known solution in a short time.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•0 citations

Techniques to enhance a QUBO solver for permutation-based combinatorial optimization

Siong Thye Goh, Jianyuan Bo, Sabrish Gopalakrishnan +1 more

Many combinatorial optimization problems can be formulated as a problem to determine the order of sequence or to find a corresponding mapping of the objects. We call such problems permutation-based optimization problems. Many such problems can be formulated as a quadratic unconstrained binary optimization (QUBO) or Ising model by introducing a penalty coefficient to the permutation constraint terms. While classical and quantum annealing approaches have been proposed to solve QUBOs to date, they face issues with optimality and feasibility. Here we treat a given QUBO solver as a black box and propose techniques to enhance its performance. First, to ensure an effective search for good quality solutions, a smooth energy landscape is needed; we propose a data scaling approach that reduces the amplitudes of the input without compromising optimality. Second, we need to tune the penalty coefficient. In this paper, we illustrate that for certain problems, it suffices to tune the parameter by performing random sampling on the penalty coefficients to achieve good performance. Finally, to handle possible infeasibility of the solution, we introduce a polynomial-time projection algorithm. We apply these techniques along with a divide-and-conquer strategy to solve some large-scale permutation-based problems and present results for TSP and QAP.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 9, 2022•10 citations

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

Multi-Penalty Sample Persistence Variable Reduction for Constrained Combinatorial Optimization Problems

Shunta Ide, Shuta Kikuchi, Shu Tanaka

Ising machines, including quantum annealing machines, are promising for solving combinatorial optimization problems with high quality solutions. For constrained combinatorial optimization problems, choosing appropriate penalty coefficients is crucial for obtaining better feasible solutions. When tackling the large-scale combinatorial optimization problems, the variable reduction method is one of the most effective methods. To address these difficulties, we propose a new variable reduction method called multi-penalty sample persistence variable reduction (MP-SPVAR). The method is based on the sample persistence variable reduction method, and utilizes the solution samples across multiple penalty coefficients to fix the variables. The proposed method is evaluated on the 60-facility quadratic assignment problem tai60b from QAPLIB using an Ising machine. The experimental results show that MP-SPVAR can obtain better feasible solutions than solving the problem without any variable reduction. The proposed method is promising for solving the large-scale constrained combinatorial optimization problems with Ising machines.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•0 citations
Ising machines, including quantum annealers, have attracted much attention as an efficient solver for COPs (Combinatorial optimization problems). The SVR (Spin-Variable Reduction) method maps a COP with linear equality constraints to QUBO (Quadratic Unconstrained Binary Optimization) model, which is a common input for using the Ising machines. In this paper, we conduct a tuning of a constraint coefficient for this method using Quadratic Assignment Problems as a case study. We find that the optimal value of the constraint coefficient can be either larger or smaller than that used in the conventional penalty method, depending on the problem instance. We discuss the underlying mechanism responsible for this difference.
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.
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.
Ising machines including quantum annealers have attracted attention as efficient solvers for combinatorial optimization problems (COPs). To use Ising machines, the objective function and constraints of a COP must be expressed in a QUBO (quadratic unconstrained binary optimization) form. However, their application range is practically limited since some COPs are difficult to formulate in a QUBO form, or require a large number of binary variables. Quadratic three-dimensional assignment problem (Q3AP) is a challenging problem for Ising machines to solve since the number of required binary variables rapidly increases with the problem size N. In this paper, to overcome the difficulty, we propose a method to reduce the number of necessary variables fromN3N^{3}N3to2N22N^{2}2N2by using a factorization machine with quantum annealing (FMQA) to estimate QUBO through machine learning. Experimental results with a real Ising machine demonstrate that the proposed method can obtain the best-known solution in a short time.
Many combinatorial optimization problems can be formulated as a problem to determine the order of sequence or to find a corresponding mapping of the objects. We call such problems permutation-based optimization problems. Many such problems can be formulated as a quadratic unconstrained binary optimization (QUBO) or Ising model by introducing a penalty coefficient to the permutation constraint terms. While classical and quantum annealing approaches have been proposed to solve QUBOs to date, they face issues with optimality and feasibility. Here we treat a given QUBO solver as a black box and propose techniques to enhance its performance. First, to ensure an effective search for good quality solutions, a smooth energy landscape is needed; we propose a data scaling approach that reduces the amplitudes of the input without compromising optimality. Second, we need to tune the penalty coefficient. In this paper, we illustrate that for certain problems, it suffices to tune the parameter by performing random sampling on the penalty coefficients to achieve good performance. Finally, to handle possible infeasibility of the solution, we introduce a polynomial-time projection algorithm. We apply these techniques along with a divide-and-conquer strategy to solve some large-scale permutation-based problems and present results for TSP and QAP.
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.
Ising machines, including quantum annealing machines, are promising for solving combinatorial optimization problems with high quality solutions. For constrained combinatorial optimization problems, choosing appropriate penalty coefficients is crucial for obtaining better feasible solutions. When tackling the large-scale combinatorial optimization problems, the variable reduction method is one of the most effective methods. To address these difficulties, we propose a new variable reduction method called multi-penalty sample persistence variable reduction (MP-SPVAR). The method is based on the sample persistence variable reduction method, and utilizes the solution samples across multiple penalty coefficients to fix the variables. The proposed method is evaluated on the 60-facility quadratic assignment problem tai60b from QAPLIB using an Ising machine. The experimental results show that MP-SPVAR can obtain better feasible solutions than solving the problem without any variable reduction. The proposed method is promising for solving the large-scale constrained combinatorial optimization problems with Ising machines.