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

Scientific Reports

A smaller and more efficient one-hot encoding for QUBO

Shinji Takasugi, Hideo Nakaya, Yoshihiro Nakao, Kenta Sawamura

Published Jun 4, 2026• 1 citation
Publisher

Abstract

One-hot constraints are widely used for quadratic unconstrained binary optimization (QUBO) in quantum and simulated annealing to solve optimization problems. They correspond to exactly-one constraints for Boolean satisfiability problems (SAT), which have many different encodings proposed mainly to reduce SAT problem size. We have examined QUBO encodings, both corresponding to previously proposed SAT encodings and newly invented, to determine the best encoding in terms of QUBO size and solution quality. Our experiments show that reduced commander, our new encoding, gives one of the best trade-offs between QUBO size and solution quality for the benchmark problem studied in this work.

DOI
10.1038/s41598-026-55521-w

Related papers

Encoding the At-Most-One Constraint for QUBO and Quantum Annealing: Experiments with the N-Queens problem

Philippe Codognet

We present experiments in solving constrained optimization and constraint satisfaction problems by means of Quantum Annealing in terms of QUBO (Quadratic Unconstrained Binary Optimization). We investigate different QUBO formulations for the encoding of integers into Booleans and for the encoding of the At-Most-One constraint, which is used in combinatorial problems requiring capacity constraints. We compare four different QUBO models and report experiments done on the D-Wave annealing computer and the "quantum-inspired" Fixstars Amplify Annealing Engine. For this, we consider a simple example taken from the domain of Constraint Satisfaction Problems (CSP), the N-queens problem, as its formulation involves multiple instances of the At-Most-One constraints.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 15, 2023•11 citations

Analyzing the impact of 3SAT-to-QUBO transformations on simulated annealing-based optimization

Marina Maroto Gallardo

The increasing complexity of computational problems in various fields entails the development of efficient methods to solve them. Thus, the emerging technology of quantum computers comes with algorithms, such as quantum annealing, that could solve optimization problems exponentially faster. In particular, to solve the 3SAT problem on quantum annealers, it must be transformed into an instance of Quadratic Unconstrained Binary Optimization (QUBO). Given that the choice of 3SAT-to-QUBO transformation affects the solution quality on quantum annealing, an algorithmic method for creating numerous 3SAT-to-QUBO transformations has recently been proposed, aiming to investigate more deeply such effect. This represents a challenge when deciding which is the best performing 3SAT-to-QUBO transformation that should be used when solving a 3SAT instance on quantum annealing. To overcome this issue, this work investigates the impact of different 3SAT-to-QUBO transformations on the solution quality of simulated annealing, as a classical analogue to quantum annealing. We demonstrate that different QUBO encodings of the same 3SAT instance can lead to different outcomes in terms of energy and clause satisfaction. We also reveal some correlations between 3SAT features, QUBO structural properties, and solution quality. These findings underscore the importance of the choice of 3SAT-to-QUBO transformation in simulated annealing, and provide a foundation for the future development of machine learning models for guiding encoding choices in both classical and quantum environments.

•Jul 4, 2025•0 citations

Performance Comparison of Typical Binary-Integer Encodings in an Ising Machine

Kensuke Tamura, Tatsuhiko Shirai, Hosho Katsura +2 more

The differences in performance among binary-integer encodings in an Ising machine, which can solve combinatorial optimization problems, are investigated. Many combinatorial optimization problems can be mapped to find the lowest-energy (ground) state of an Ising model or its equivalent model, the Quadratic Unconstrained Binary Optimization (QUBO). Since the Ising model and QUBO consist of binary variables, they often express integers as binary when using Ising machines. A typical example is the combinatorial optimization problem under inequality constraints. Here, the quadratic knapsack problem is adopted as a prototypical problem with an inequality constraint. It is solved using typical binary-integer encodings: one-hot encoding, binary encoding, and unary encoding. Unary encoding shows the best performance for large-sized problems.

IEEE Access•Jan 1, 2021•63 citations

Comparing QUBO models for quantum annealing: integer encodings for permutation problems

Philippe Codognet

Abstract QUBO (quadratic unconstrained binary optimization) has become the modeling language for quantum annealing and quantum‐inspired annealing solvers. We present different approaches in QUBO for the magic square problem and the quadratic assignment problem (QAP), which can be modeled by linear equations and a permutation constraint over integer variables. Different ways of encoding integers by Booleans in QUBO amount to models, the implementation of which could have very different performance. Experiments performed on the Fixstars Amplify Annealer Engine, a quantum‐inspired annealing solver, show that, compared to the classical one‐hot encoding, using unary encoding for integers performs slightly better for the QAP and much better for magic square.

International Transactions in Operational Research•Apr 30, 2024•17 citations

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

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

Recent advances in quantum computing have shown great potential for solving combinatorial optimization problems. A notable example is the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum-inspired algorithms require Quadratic Unconstrained Binary Optimization (QUBO) formulations. Transforming constrained optimization into QUBO impacts the algorithms' speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess them by using Simulated Annealing (SA), and find that three of our approaches outperform existing methods in terms of execution time as well as quality and quantity of feasible solutions found. Also, we tested these transformations on a quantum annealer, which was unable to solve even small instances, due to limitations in connectivity and error rates. In general, our results highlight the advantages of the new approaches, which reduce the number of variables in the QUBO representation.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 14, 2025•0 citations

On good encodings for quantum annealer and digital optimization solvers

Alberto Ceselli, Marco Premoli

Several optimization solvers inspired by quantum annealing have been recently developed, either running on actual quantum hardware or simulating it on traditional digital computers. Industry and academics look at their potential in solving hard combinatorial optimization problems. Formally, they provide heuristic solutions for Ising models, which are equivalent to quadratic unconstrained binary optimization (QUBO). Constraints on solutions feasibility need to be properly encoded. We experiment on different ways of performing such an encoding. As benchmark we consider the cardinality constrained quadratic knapsack problem (CQKP), a minimal extension of QUBO with one inequality and one equality constraint. We consider different strategies of constraints penalization and variables encoding. We compare three QUBO solvers: quantum annealing on quantum hardware (D-Wave Advantage), probabilistic algorithms on digital hardware and mathematical programming solvers. We analyze their QUBO resolution quality and time, and the persistence values extracted in the quantum annealing sampling process. Our results show that a linear penalization of CQKP inequality improves current best practice. Furthermore, using such a linear penalization, persistence values produced by quantum hardware in a generic way allow to match a specific CQKP metric from literature. They are therefore suitable for general purpose variable fixing in core algorithms for combinatorial optimization.

Scientific Reports•Apr 6, 2023•11 citations
One-hot constraints are widely used for quadratic unconstrained binary optimization (QUBO) in quantum and simulated annealing to solve optimization problems. They correspond to exactly-one constraints for Boolean satisfiability problems (SAT), which have many different encodings proposed mainly to reduce SAT problem size. We have examined QUBO encodings, both corresponding to previously proposed SAT encodings and newly invented, to determine the best encoding in terms of QUBO size and solution quality. Our experiments show that reduced commander, our new encoding, gives one of the best trade-offs between QUBO size and solution quality for the benchmark problem studied in this work.
We present experiments in solving constrained optimization and constraint satisfaction problems by means of Quantum Annealing in terms of QUBO (Quadratic Unconstrained Binary Optimization). We investigate different QUBO formulations for the encoding of integers into Booleans and for the encoding of the At-Most-One constraint, which is used in combinatorial problems requiring capacity constraints. We compare four different QUBO models and report experiments done on the D-Wave annealing computer and the "quantum-inspired" Fixstars Amplify Annealing Engine. For this, we consider a simple example taken from the domain of Constraint Satisfaction Problems (CSP), the N-queens problem, as its formulation involves multiple instances of the At-Most-One constraints.
The increasing complexity of computational problems in various fields entails the development of efficient methods to solve them. Thus, the emerging technology of quantum computers comes with algorithms, such as quantum annealing, that could solve optimization problems exponentially faster. In particular, to solve the 3SAT problem on quantum annealers, it must be transformed into an instance of Quadratic Unconstrained Binary Optimization (QUBO). Given that the choice of 3SAT-to-QUBO transformation affects the solution quality on quantum annealing, an algorithmic method for creating numerous 3SAT-to-QUBO transformations has recently been proposed, aiming to investigate more deeply such effect. This represents a challenge when deciding which is the best performing 3SAT-to-QUBO transformation that should be used when solving a 3SAT instance on quantum annealing. To overcome this issue, this work investigates the impact of different 3SAT-to-QUBO transformations on the solution quality of simulated annealing, as a classical analogue to quantum annealing. We demonstrate that different QUBO encodings of the same 3SAT instance can lead to different outcomes in terms of energy and clause satisfaction. We also reveal some correlations between 3SAT features, QUBO structural properties, and solution quality. These findings underscore the importance of the choice of 3SAT-to-QUBO transformation in simulated annealing, and provide a foundation for the future development of machine learning models for guiding encoding choices in both classical and quantum environments.
The differences in performance among binary-integer encodings in an Ising machine, which can solve combinatorial optimization problems, are investigated. Many combinatorial optimization problems can be mapped to find the lowest-energy (ground) state of an Ising model or its equivalent model, the Quadratic Unconstrained Binary Optimization (QUBO). Since the Ising model and QUBO consist of binary variables, they often express integers as binary when using Ising machines. A typical example is the combinatorial optimization problem under inequality constraints. Here, the quadratic knapsack problem is adopted as a prototypical problem with an inequality constraint. It is solved using typical binary-integer encodings: one-hot encoding, binary encoding, and unary encoding. Unary encoding shows the best performance for large-sized problems.
Abstract QUBO (quadratic unconstrained binary optimization) has become the modeling language for quantum annealing and quantum‐inspired annealing solvers. We present different approaches in QUBO for the magic square problem and the quadratic assignment problem (QAP), which can be modeled by linear equations and a permutation constraint over integer variables. Different ways of encoding integers by Booleans in QUBO amount to models, the implementation of which could have very different performance. Experiments performed on the Fixstars Amplify Annealer Engine, a quantum‐inspired annealing solver, show that, compared to the classical one‐hot encoding, using unary encoding for integers performs slightly better for the QAP and much better for magic square.
Recent advances in quantum computing have shown great potential for solving combinatorial optimization problems. A notable example is the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum-inspired algorithms require Quadratic Unconstrained Binary Optimization (QUBO) formulations. Transforming constrained optimization into QUBO impacts the algorithms' speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess them by using Simulated Annealing (SA), and find that three of our approaches outperform existing methods in terms of execution time as well as quality and quantity of feasible solutions found. Also, we tested these transformations on a quantum annealer, which was unable to solve even small instances, due to limitations in connectivity and error rates. In general, our results highlight the advantages of the new approaches, which reduce the number of variables in the QUBO representation.
Several optimization solvers inspired by quantum annealing have been recently developed, either running on actual quantum hardware or simulating it on traditional digital computers. Industry and academics look at their potential in solving hard combinatorial optimization problems. Formally, they provide heuristic solutions for Ising models, which are equivalent to quadratic unconstrained binary optimization (QUBO). Constraints on solutions feasibility need to be properly encoded. We experiment on different ways of performing such an encoding. As benchmark we consider the cardinality constrained quadratic knapsack problem (CQKP), a minimal extension of QUBO with one inequality and one equality constraint. We consider different strategies of constraints penalization and variables encoding. We compare three QUBO solvers: quantum annealing on quantum hardware (D-Wave Advantage), probabilistic algorithms on digital hardware and mathematical programming solvers. We analyze their QUBO resolution quality and time, and the persistence values extracted in the quantum annealing sampling process. Our results show that a linear penalization of CQKP inequality improves current best practice. Furthermore, using such a linear penalization, persistence values produced by quantum hardware in a generic way allow to match a specific CQKP metric from literature. They are therefore suitable for general purpose variable fixing in core algorithms for combinatorial optimization.