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)

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

Sora Tomita, Tatsuhiko Shirai, Nozomu Togawa

Published Sep 15, 2024• 0 citations
Publisher

Abstract

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.

DOI
10.1109/qce60285.2024.10327

Related papers

Constraint Coefficient Tuning of Spin-Variable Reduction for QAP

Raio Aoki, Tatsuhiko Shirai, Nozomu Togawa

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.

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

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

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

Ising Machine Approach to the Lecturer–Student Assignment Problem

Sora Tomita, Tatsuhiko Shirai, Nozomu Togawa

Ising machines are efficient solvers for combinatorial optimization problems (COPs). After mapping COPs to Quadratic Unconstrained Binary Optimization (QUBO) problems, Ising machines search for the lowest energy solution of the QUBO corresponding to the optimal solution of the COP. Herein we propose an efficient method to formulate a lecturer–student assignment problem as a QUBO problem. In this problem, the sets of subjects, lecturers, students, lecturers’ teachable subjects, and students’ required subjects are given. To minimize lecture costs, the number of lecturers in charge of students must be minimized. The number of combinations drastically increases as the number of lecturers or students increases. Using these results, we theoretically prove the optimality, i.e., the formulated QUBO takes the lowest energy if and only if the students are optimally assigned to the lecturers. Additionally, we demonstrate that an Ising machine outperforms simulated annealing in terms of solution quality and execution time.

IEEE Access•Jan 1, 2024•2 citations

Decomposed Quadratization: Efficient QUBO Formulation for Learning Bayesian Network

Yuta Shikuri

Algorithms and hardware for solving quadratic unconstrained binary optimization (QUBO) problems have made significant recent progress. This advancement has focused attention on formulating combinatorial optimization problems as quadratic polynomials. To improve the performance of solving large QUBO problems, it is essential to minimize the number of binary variables used in the objective function. In this paper, we propose a QUBO formulation that offers a bit capacity advantage over conventional quadratization techniques. As a key application, this formulation significantly reduces the number of binary variables required for score-based Bayesian network structure learning. Experimental results on 16 instances, ranging from 37 to 223 variables, demonstrate that our approach requires fewer binary variables than quadratization by orders of magnitude. Moreover, an annealing machine that implement our formulation have outperformed existing algorithms in score maximization.

arXiv:2006.06926•Proceedings of the AAAI Conference on Artificial Intelligence•Apr 11, 2025•5 citations

New QUBO Transformations to Improve Quantum and Simulated Annealing Performance for Quadratic Knapsack

Nicolás Borrajo, Juan Ramírez, Farzam Nosrati +3 more

Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transformations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated Annealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total number of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.

International Conference on Agents and Artificial Intelligence (ICAART)•Jan 1, 2026•1 citation
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.
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.
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 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 are efficient solvers for combinatorial optimization problems (COPs). After mapping COPs to Quadratic Unconstrained Binary Optimization (QUBO) problems, Ising machines search for the lowest energy solution of the QUBO corresponding to the optimal solution of the COP. Herein we propose an efficient method to formulate a lecturer–student assignment problem as a QUBO problem. In this problem, the sets of subjects, lecturers, students, lecturers’ teachable subjects, and students’ required subjects are given. To minimize lecture costs, the number of lecturers in charge of students must be minimized. The number of combinations drastically increases as the number of lecturers or students increases. Using these results, we theoretically prove the optimality, i.e., the formulated QUBO takes the lowest energy if and only if the students are optimally assigned to the lecturers. Additionally, we demonstrate that an Ising machine outperforms simulated annealing in terms of solution quality and execution time.
Algorithms and hardware for solving quadratic unconstrained binary optimization (QUBO) problems have made significant recent progress. This advancement has focused attention on formulating combinatorial optimization problems as quadratic polynomials. To improve the performance of solving large QUBO problems, it is essential to minimize the number of binary variables used in the objective function. In this paper, we propose a QUBO formulation that offers a bit capacity advantage over conventional quadratization techniques. As a key application, this formulation significantly reduces the number of binary variables required for score-based Bayesian network structure learning. Experimental results on 16 instances, ranging from 37 to 223 variables, demonstrate that our approach requires fewer binary variables than quadratization by orders of magnitude. Moreover, an annealing machine that implement our formulation have outperformed existing algorithms in score maximization.
Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transformations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated Annealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total number of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.