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

arXiv:1906.07385 · Scientific Reports

Efficient partition of integer optimization problems with one-hot encoding

Shuntaro Okada, Masayuki Ohzeki, Shinichiro Taguchi

Published Sep 10, 2019• 191 citations
arXivHTMLPDF

Abstract

Quantum annealing is a heuristic algorithm for solving combinatorial optimization problems, and hardware for implementing this algorithm has been developed by D-Wave Systems Inc. The current version of the D-Wave quantum annealer can solve unconstrained binary optimization problems with a limited number of binary variables. However, the cost functions of several practical problems are defined by a large number of integer variables. To solve these problems using the quantum annealer, integer variables are generally binarized with one-hot encoding, and the binarized problem is partitioned into small subproblems. However, the entire search space of the binarized problem is considerably larger than that of the original integer problem and is dominated by infeasible solutions. Therefore, to efficiently solve large optimization problems with one-hot encoding, partitioning methods that extract subproblems with as many feasible solutions as possible are required. In this study, we propose two partitioning methods and demonstrate that they result in improved solutions.

DOI
10.1038/s41598-019-49539-6

Related papers

Improving solutions by embedding larger subproblems in a D-Wave quantum annealer

Shuntaro Okada, Masayuki Ohzeki, Masayoshi Terabe +1 more

Quantum annealing is a heuristic algorithm that solves combinatorial optimization problems, and D-Wave Systems Inc. has developed hardware implementation of this algorithm. However, in general, we cannot embed all the logical variables of a large-scale problem, since the number of available qubits is limited. In order to handle a large problem, qbsolv has been proposed as a method for partitioning the original large problem into subproblems that are embeddable in the D-Wave quantum annealer, and it then iteratively optimizes the subproblems using the quantum annealer. Multiple logical variables in the subproblem are simultaneously updated in this iterative solver, and using this approach we expect to obtain better solutions than can be obtained by conventional local search algorithms. Although embedding of large subproblems is essential for improving the accuracy of solutions in this scheme, the size of the subproblems are small in qbsolv since the subproblems are basically embedded by using an embedding of a complete graph even for sparse problem graphs. This means that the resource of the D-Wave quantum annealer is not exploited efficiently. In this paper, we propose a fast algorithm for embedding larger subproblems, and we show that better solutions are obtained efficiently by embedding larger subproblems.

arXiv:1901.00924•Scientific Reports•Feb 14, 2019•92 citations

Quantum Annealing Hyperparameter Analysis for Optimal Sensor Placement in Production Environments

Nico Kraus, Marvin Erdmann, Alexander Kuzmany +2 more

To increase efficiency in automotive manufacturing, newly produced vehicles can move autonomously from the production line to the distribution area. This requires an optimal placement of sensors to ensure full coverage while minimizing the number of sensors used. The underlying optimization problem poses a computational challenge due to its large-scale nature. Currently, classical solvers rely on heuristics, often yielding nonoptimal solutions for large instances, resulting in suboptimal sensor distributions and increased operational costs. We explore quantum computing methods that may outperform classical heuristics in the future. We implemented quantum annealing with D-Wave, transforming the problem into a quadratic unconstrained binary optimization formulation with one-hot and binary encoding. Hyperparameters like the penalty terms and the annealing time are optimized and the results are compared with default parameter settings. Our results demonstrate that quantum annealing is capable of solving instances derived from real-world scenarios. Through the use of decomposition techniques, we are able to scale the problem size further, bringing it closer to practical, industrial applicability. Through this work, we provide key insights into the importance of quantum annealing parametrization, demonstrating how quantum computing could contribute to cost-efficient, large-scale optimization problems once the hardware matures.

arXiv:2507.16584•IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 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•10 citations

Efficient solution of the number partitioning problem on a quantum annealer: a hybrid quantum-classical decomposition approach

Zongji Li, Tobias Seidel, Dominik Leib +2 more

Abstract Current quantum computers can only solve optimization problems of a very limited size. For larger problems, decomposition methods are required in which the original problem is broken down into several smaller sub-problems. These are then solved on the quantum computer and their solutions are recombined into a final solution for the original problem. Often, these decomposition methods do not take the specific problem structure into account. In this paper, we present a tailored method using a divide-and-conquer strategy to solve the 2-way Number partitioning problem (NPP) with a large number of variables. The idea is to perform a specialized decomposition into smaller NPPs, which are solved on a quantum computer, and then recombine the results into another small auxiliary NPP. Solving this auxiliary problem yields an approximate solution of the original larger problem. We experimentally verify that our method allows to solve NPPs with over a thousand variables using the D-Wave Advantage quantum annealer (Advantage_system6.4).

arXiv:2312.08940•Journal of Heuristics•Apr 17, 2025•4 citations

Performance enhancing of hybrid quantum-classical Benders approach for MILP optimization

Sergio López-Baños, Elisabeth Lobe, Ontje Lünsdorf +1 more

Mixed-integer linear programming problems are extensively used in industry for a wide range of optimization tasks. However, as they get larger, they present computational challenges for classical solvers within practical time limits. Quantum annealers can, in principle, accelerate the solution of problems formulated as quadratic unconstrained binary optimization instances, but their limited scale currently prevents achieving practical speedups. Quantum-classical algorithms have been proposed to take advantage of both paradigms and to allow current quantum computers to be used in larger problems. In this work, a hardware-agnostic Benders' decomposition algorithm and a series of enhancements with the goal of taking the most advantage of quantum computing are presented. The decomposition consists of a master problem with integer variables, which is reformulated as a quadratic unconstrained binary optimization problem and solved with a quantum annealer, and a linear subproblem solved by a classical computer. The enhancements consist, among others, of different embedding processes that substantially reduce the pre-processing time of the embedding computation without compromising solution quality, a conservative handling of cut constraints, and a stopping criterion that accounts for the limited size of current quantum computers and their heuristic nature. The proposed algorithm is benchmarked against classical approaches using a D-Wave quantum annealer for a scalable family of transmission network expansion planning problems.

quant-pharXiv:2601.14024•Jan 21, 2026•0 citations

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
Quantum annealing is a heuristic algorithm for solving combinatorial optimization problems, and hardware for implementing this algorithm has been developed by D-Wave Systems Inc. The current version of the D-Wave quantum annealer can solve unconstrained binary optimization problems with a limited number of binary variables. However, the cost functions of several practical problems are defined by a large number of integer variables. To solve these problems using the quantum annealer, integer variables are generally binarized with one-hot encoding, and the binarized problem is partitioned into small subproblems. However, the entire search space of the binarized problem is considerably larger than that of the original integer problem and is dominated by infeasible solutions. Therefore, to efficiently solve large optimization problems with one-hot encoding, partitioning methods that extract subproblems with as many feasible solutions as possible are required. In this study, we propose two partitioning methods and demonstrate that they result in improved solutions.
Quantum annealing is a heuristic algorithm that solves combinatorial optimization problems, and D-Wave Systems Inc. has developed hardware implementation of this algorithm. However, in general, we cannot embed all the logical variables of a large-scale problem, since the number of available qubits is limited. In order to handle a large problem, qbsolv has been proposed as a method for partitioning the original large problem into subproblems that are embeddable in the D-Wave quantum annealer, and it then iteratively optimizes the subproblems using the quantum annealer. Multiple logical variables in the subproblem are simultaneously updated in this iterative solver, and using this approach we expect to obtain better solutions than can be obtained by conventional local search algorithms. Although embedding of large subproblems is essential for improving the accuracy of solutions in this scheme, the size of the subproblems are small in qbsolv since the subproblems are basically embedded by using an embedding of a complete graph even for sparse problem graphs. This means that the resource of the D-Wave quantum annealer is not exploited efficiently. In this paper, we propose a fast algorithm for embedding larger subproblems, and we show that better solutions are obtained efficiently by embedding larger subproblems.
To increase efficiency in automotive manufacturing, newly produced vehicles can move autonomously from the production line to the distribution area. This requires an optimal placement of sensors to ensure full coverage while minimizing the number of sensors used. The underlying optimization problem poses a computational challenge due to its large-scale nature. Currently, classical solvers rely on heuristics, often yielding nonoptimal solutions for large instances, resulting in suboptimal sensor distributions and increased operational costs. We explore quantum computing methods that may outperform classical heuristics in the future. We implemented quantum annealing with D-Wave, transforming the problem into a quadratic unconstrained binary optimization formulation with one-hot and binary encoding. Hyperparameters like the penalty terms and the annealing time are optimized and the results are compared with default parameter settings. Our results demonstrate that quantum annealing is capable of solving instances derived from real-world scenarios. Through the use of decomposition techniques, we are able to scale the problem size further, bringing it closer to practical, industrial applicability. Through this work, we provide key insights into the importance of quantum annealing parametrization, demonstrating how quantum computing could contribute to cost-efficient, large-scale optimization problems once the hardware matures.
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.
Abstract Current quantum computers can only solve optimization problems of a very limited size. For larger problems, decomposition methods are required in which the original problem is broken down into several smaller sub-problems. These are then solved on the quantum computer and their solutions are recombined into a final solution for the original problem. Often, these decomposition methods do not take the specific problem structure into account. In this paper, we present a tailored method using a divide-and-conquer strategy to solve the 2-way Number partitioning problem (NPP) with a large number of variables. The idea is to perform a specialized decomposition into smaller NPPs, which are solved on a quantum computer, and then recombine the results into another small auxiliary NPP. Solving this auxiliary problem yields an approximate solution of the original larger problem. We experimentally verify that our method allows to solve NPPs with over a thousand variables using the D-Wave Advantage quantum annealer (Advantage_system6.4).
Mixed-integer linear programming problems are extensively used in industry for a wide range of optimization tasks. However, as they get larger, they present computational challenges for classical solvers within practical time limits. Quantum annealers can, in principle, accelerate the solution of problems formulated as quadratic unconstrained binary optimization instances, but their limited scale currently prevents achieving practical speedups. Quantum-classical algorithms have been proposed to take advantage of both paradigms and to allow current quantum computers to be used in larger problems. In this work, a hardware-agnostic Benders' decomposition algorithm and a series of enhancements with the goal of taking the most advantage of quantum computing are presented. The decomposition consists of a master problem with integer variables, which is reformulated as a quadratic unconstrained binary optimization problem and solved with a quantum annealer, and a linear subproblem solved by a classical computer. The enhancements consist, among others, of different embedding processes that substantially reduce the pre-processing time of the embedding computation without compromising solution quality, a conservative handling of cut constraints, and a stopping criterion that accounts for the limited size of current quantum computers and their heuristic nature. The proposed algorithm is benchmarked against classical approaches using a D-Wave quantum annealer for a scalable family of transmission network expansion planning problems.
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.