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:2601.18108

Sparse QUBO Formulation for Efficient Embedding via Network-Based Decomposition of Equality and Inequality Constraints

Kohei Suda, Soshun Naito, Yoshihiko Hasegawa

quant-phSubmitted Jan 26, 2026• Announced Jan 27, 2026• 0 citations
arXivHTMLPDF

Abstract

Quantum annealing is a promising approach for solving combinatorial optimization problems. However, its performance is often limited by the overhead of additional qubits required for embedding logical QUBO models onto quantum annealers. This overhead becomes severe when logical QUBO models have dense connectivity. Such dense structures frequently arise when formulating equality and inequality constraints. To address this issue, we propose a method to construct a significantly sparser logical QUBO model for these constraints. By adding auxiliary variables based on specific network structures, our approach decomposes the original constraint into smaller, more manageable constraints. We demonstrate that this method reduces the number of edges (quadratic terms) from $O(N^2)$ to $O(N)$ for the one-hot constraint and to $O(N\log N)$ in the worst case for general equality constraints, where $N$ is the number of variables. Experimental results on D-Wave's hardware show that our formulation leads to substantial reductions in the number of qubits required for embedding, shorter average chain lengths, lower chain break rates, and higher feasible solution rates compared to conventional methods. This work provides a practical tool for efficiently solving constrained optimization problems on current and future quantum annealers.

Related papers

Resource-efficient QUBO formulations for the Knapsack and Bin Packing problem

Pim van den Heuvel

Quantum computing approaches, such as Quantum Annealing (QA) and the Quantum Approximate Optimization Algorithm (QAOA), have emerged as promising candidates for solving combinatorial optimization problems. Since these approaches typically work with Quadratic Unconstrained Binary Optimization (QUBO) problems, constraints, when present, are commonly encoded as penalty terms. Conventional approaches to incorporate inequality constraints into QUBO formulations additionally require the introduction of slack variables, increasing the required number of qubits. The Knapsack and Bin Packing problems are optimization problems with such inequality constraints. We show that the number of slack variables required to formulate the Knapsack problem as a QUBO problem can be reduced using certain properties specific to this problem. Moreover, we present two separate strategies for the Knapsack and Bin Packing problems that avoid using the costly slack variables altogether. Instead, both strategies solve several QUBO problems, with varying penalty constants, such that at least one of them is a good representation of the given optimization problem. Numerical simulations of QAOA, as well as experiments on a D-Wave quantum annealer, show that these slack-less approaches can improve performance compared to the conventional slack variable method (in terms of success probability), even when the latter is allowed to vary penalty constants too.

•Jan 1, 2025•0 citations

Embedding Equality Constraints of Optimization Problems into a Quantum Annealer

Tomáš Vyskočil, Hristo N. Djidjev

Quantum annealers such as D-Wave machines are designed to propose solutions for quadratic unconstrained binary optimization (QUBO) problems by mapping them onto the quantum processing unit, which tries to find a solution by measuring the parameters of a minimum-energy state of the quantum system. While many NP-hard problems can be easily formulated as binary quadratic optimization problems, such formulations almost always contain one or more constraints, which are not allowed in a QUBO. Embedding such constraints as quadratic penalties is the standard approach for addressing this issue, but it has drawbacks such as the introduction of large coefficients and using too many additional qubits. In this paper, we propose an alternative approach for implementing constraints based on a combinatorial design and solving mixed-integer linear programming (MILP) problems in order to find better embeddings of constraints of the type ∑ x i = k for binary variables x i. Our approach is scalable to any number of variables and uses a linear number of ancillary variables for a fixed k.

Algorithms•Apr 17, 2019•22 citations

Embedding Inequality Constraints for Quantum Annealing Optimization.

Tomáš Vyskočil, Scott Pakin, Hristo N. Djidjev

Quantum annealing is a model for quantum computing that is aimed at solving hard optimization problems by representing them as quadratic unconstrained binary optimization (QUBO) problems. Although many NP-hard problems can easily be formulated as binary-variable problems with a quadratic objective function, such formulations typically also include constraints, which are not allowed in a QUBO. Hence, such constraints are usually incorporated in the objective function as additive penalty terms. While there is substantial previous work on implementing linear equality constraints, the case of inequality constraints has not much been studied. In this paper, we propose a new approach for formulating and embedding inequality constraints as penalties and describe early implementation results.

•Jan 1, 2017•0 citations

QUBO formulation using inequalities for problems with complex constraints

Tomoko Komiyama, Tomohiro Suzuki

Quantum annealing is an optimization technique that uses quantum fluctuation effects to search for solutions and is being applied as a metaheuristic method. Quantum annealing solves a problem expressed as quadratic unconstrained binary optimization (QUBO). Many practical problems have complex constraints, and formulating them can lead to third-order or higher expressions. In such cases, higher-order expressions have been converted to QUBO by order reduction. Various order reduction methods have been used, but they have issues, such as the need to add more auxiliary variables and difficulty in obtaining optimal solutions. This paper discusses a method for formulating problems with complex constraints using inequalities. In this approach, each constraint is defined as a linear function and added together to form an inequality. The inequality is then transformed to QUBO by introducing a slack variable. The application to the quantum minimum fill-in algorithm, a fill-in reduction ordering algorithm for sparse matrices, and the maximum satisfiability problem are also presented. The results of solving these problems with a quantum-inspired annealing machine show that higher-quality solutions are obtained with fewer variables than when using higher-order expressions with order reduction.

International Conference on High Performance Computing in Asia-Pacific Region (HPC Asia)•Jan 18, 2024•5 citations

Optimized QUBO formulation methods for quantum computing

Dario De Santis, Salvatore Tirone, Stefano Marmi +1 more

Abstract Quantum computers have strict requirements for the problems that they can efficiently solve. One of the principal limiting factor for the performances of noisy intermediate-scale quantum (NISQ) devices is the number of qubits required by the running algorithm. Several combinatorial optimization problems can be solved with NISQ devices once that a corresponding quadratic unconstrained binary optimization (QUBO) form is derived. Numerous techniques have been proposed to achieve such reformulations and, depending on the method chosen, the number of binary variables required, and therefore of qubits, can vary considerably. The aim of this work is to drastically reduce the variables needed for these QUBO reformulations in order to unlock the possibility to efficiently obtain optimal solutions for a class of optimization problems with NISQ devices. This goal is achieved by introducing novel tools that allow an efficient use of slack variables, even for problems with non-linear constraints, without the need to approximate the starting problem. We divide our new techniques in two independent parts, called the iterative quadratic polynomial and the master-satellite methods. Hence, we show how to apply our techniques in case of an NP-hard optimization problem inspired by a real-world financial scenario called Max-Profit Balance Settlement . We follow by submitting several instances of this problem to two D-wave quantum annealers, comparing the performances of our novel approach with the standard methods used in these scenarios. Moreover, this study allows to appreciate several performance differences between the D-wave Advantage and next-generation Advantage2 quantum annealers. We show that the adoption of our techniques in this context allows to obtain QUBO formulations with significantly fewer slack variables, i.e. around 90% less, and D-wave annealers provide considerably higher correct solution rates, which moreover do not decrease with the input size as fast as when adopting standard techniques.

arXiv:2406.07681•Quantum Science and Technology•Jan 21, 2026•7 citations

Qubit-Efficient QUBO Formulation for Constrained Optimization Problems

Meerzhan Kanatbekova, Vincenzo De Maio, Brandic, Ivona

Quantum computing has emerged as a promising alternative for solving combinatorial optimization problems. The standard approach for encoding optimization problems on quantum processing units (QPUs) involves transforming them into their Quadratic Unconstrained Binary Optimization (QUBO) representation. However, encoding constraints of optimization problems, particularly inequality constraints, into QUBO requires additional variables, which results in more qubits. Considering the limited availability of qubits in NISQ machines, existing encoding methods fail to scale due to their reliance on large numbers of qubits. We propose a generalized exponential penalty framework for QUBO inequality constraints inspired by a class of exponential functions, which we call exponential penalization. This paper presents an encoding strategy for inequality constraints in combinatorial optimization problems, inspired by a class of exponential functions, which we call exponential penalization. The initial idea of using exponential penalties for QUBO formulation was introduced by Montanez-Barrera et al. by applying a specific exponential function to reduce qubit requirements. In this work, we extend that approach by conducting a comprehensive study on a broader class of exponential functions, analyzing their theoretical properties and empirical performance. Our experimental results demonstrate that an exponential penalization achieves 57%, 83% qubit number reduction for Bin Packing Problem (BPP) and Traveling Salesman Problem (TSP), respectively. And we demonstrate comparable solution quality to classical with a probability of 6% and 21% accuracy for BPP with 8 and TSP with 12 qubits, respectively.

arXiv:2509.08080•Sep 9, 2025•0 citations
Quantum annealing is a promising approach for solving combinatorial optimization problems. However, its performance is often limited by the overhead of additional qubits required for embedding logical QUBO models onto quantum annealers. This overhead becomes severe when logical QUBO models have dense connectivity. Such dense structures frequently arise when formulating equality and inequality constraints. To address this issue, we propose a method to construct a significantly sparser logical QUBO model for these constraints. By adding auxiliary variables based on specific network structures, our approach decomposes the original constraint into smaller, more manageable constraints. We demonstrate that this method reduces the number of edges (quadratic terms) from O(N2)O(N^2)O(N2) to O(N)O(N)O(N) for the one-hot constraint and to O(Nlog⁡N)O(N\log N)O(NlogN) in the worst case for general equality constraints, where NNN is the number of variables. Experimental results on D-Wave's hardware show that our formulation leads to substantial reductions in the number of qubits required for embedding, shorter average chain lengths, lower chain break rates, and higher feasible solution rates compared to conventional methods. This work provides a practical tool for efficiently solving constrained optimization problems on current and future quantum annealers.
Quantum computing approaches, such as Quantum Annealing (QA) and the Quantum Approximate Optimization Algorithm (QAOA), have emerged as promising candidates for solving combinatorial optimization problems. Since these approaches typically work with Quadratic Unconstrained Binary Optimization (QUBO) problems, constraints, when present, are commonly encoded as penalty terms. Conventional approaches to incorporate inequality constraints into QUBO formulations additionally require the introduction of slack variables, increasing the required number of qubits. The Knapsack and Bin Packing problems are optimization problems with such inequality constraints. We show that the number of slack variables required to formulate the Knapsack problem as a QUBO problem can be reduced using certain properties specific to this problem. Moreover, we present two separate strategies for the Knapsack and Bin Packing problems that avoid using the costly slack variables altogether. Instead, both strategies solve several QUBO problems, with varying penalty constants, such that at least one of them is a good representation of the given optimization problem. Numerical simulations of QAOA, as well as experiments on a D-Wave quantum annealer, show that these slack-less approaches can improve performance compared to the conventional slack variable method (in terms of success probability), even when the latter is allowed to vary penalty constants too.
Quantum annealers such as D-Wave machines are designed to propose solutions for quadratic unconstrained binary optimization (QUBO) problems by mapping them onto the quantum processing unit, which tries to find a solution by measuring the parameters of a minimum-energy state of the quantum system. While many NP-hard problems can be easily formulated as binary quadratic optimization problems, such formulations almost always contain one or more constraints, which are not allowed in a QUBO. Embedding such constraints as quadratic penalties is the standard approach for addressing this issue, but it has drawbacks such as the introduction of large coefficients and using too many additional qubits. In this paper, we propose an alternative approach for implementing constraints based on a combinatorial design and solving mixed-integer linear programming (MILP) problems in order to find better embeddings of constraints of the type ∑ x i = k for binary variables x i. Our approach is scalable to any number of variables and uses a linear number of ancillary variables for a fixed k.
Quantum annealing is a model for quantum computing that is aimed at solving hard optimization problems by representing them as quadratic unconstrained binary optimization (QUBO) problems. Although many NP-hard problems can easily be formulated as binary-variable problems with a quadratic objective function, such formulations typically also include constraints, which are not allowed in a QUBO. Hence, such constraints are usually incorporated in the objective function as additive penalty terms. While there is substantial previous work on implementing linear equality constraints, the case of inequality constraints has not much been studied. In this paper, we propose a new approach for formulating and embedding inequality constraints as penalties and describe early implementation results.
Quantum annealing is an optimization technique that uses quantum fluctuation effects to search for solutions and is being applied as a metaheuristic method. Quantum annealing solves a problem expressed as quadratic unconstrained binary optimization (QUBO). Many practical problems have complex constraints, and formulating them can lead to third-order or higher expressions. In such cases, higher-order expressions have been converted to QUBO by order reduction. Various order reduction methods have been used, but they have issues, such as the need to add more auxiliary variables and difficulty in obtaining optimal solutions. This paper discusses a method for formulating problems with complex constraints using inequalities. In this approach, each constraint is defined as a linear function and added together to form an inequality. The inequality is then transformed to QUBO by introducing a slack variable. The application to the quantum minimum fill-in algorithm, a fill-in reduction ordering algorithm for sparse matrices, and the maximum satisfiability problem are also presented. The results of solving these problems with a quantum-inspired annealing machine show that higher-quality solutions are obtained with fewer variables than when using higher-order expressions with order reduction.
Abstract Quantum computers have strict requirements for the problems that they can efficiently solve. One of the principal limiting factor for the performances of noisy intermediate-scale quantum (NISQ) devices is the number of qubits required by the running algorithm. Several combinatorial optimization problems can be solved with NISQ devices once that a corresponding quadratic unconstrained binary optimization (QUBO) form is derived. Numerous techniques have been proposed to achieve such reformulations and, depending on the method chosen, the number of binary variables required, and therefore of qubits, can vary considerably. The aim of this work is to drastically reduce the variables needed for these QUBO reformulations in order to unlock the possibility to efficiently obtain optimal solutions for a class of optimization problems with NISQ devices. This goal is achieved by introducing novel tools that allow an efficient use of slack variables, even for problems with non-linear constraints, without the need to approximate the starting problem. We divide our new techniques in two independent parts, called the iterative quadratic polynomial and the master-satellite methods. Hence, we show how to apply our techniques in case of an NP-hard optimization problem inspired by a real-world financial scenario called Max-Profit Balance Settlement . We follow by submitting several instances of this problem to two D-wave quantum annealers, comparing the performances of our novel approach with the standard methods used in these scenarios. Moreover, this study allows to appreciate several performance differences between the D-wave Advantage and next-generation Advantage2 quantum annealers. We show that the adoption of our techniques in this context allows to obtain QUBO formulations with significantly fewer slack variables, i.e. around 90% less, and D-wave annealers provide considerably higher correct solution rates, which moreover do not decrease with the input size as fast as when adopting standard techniques.
Quantum computing has emerged as a promising alternative for solving combinatorial optimization problems. The standard approach for encoding optimization problems on quantum processing units (QPUs) involves transforming them into their Quadratic Unconstrained Binary Optimization (QUBO) representation. However, encoding constraints of optimization problems, particularly inequality constraints, into QUBO requires additional variables, which results in more qubits. Considering the limited availability of qubits in NISQ machines, existing encoding methods fail to scale due to their reliance on large numbers of qubits. We propose a generalized exponential penalty framework for QUBO inequality constraints inspired by a class of exponential functions, which we call exponential penalization. This paper presents an encoding strategy for inequality constraints in combinatorial optimization problems, inspired by a class of exponential functions, which we call exponential penalization. The initial idea of using exponential penalties for QUBO formulation was introduced by Montanez-Barrera et al. by applying a specific exponential function to reduce qubit requirements. In this work, we extend that approach by conducting a comprehensive study on a broader class of exponential functions, analyzing their theoretical properties and empirical performance. Our experimental results demonstrate that an exponential penalization achieves 57%, 83% qubit number reduction for Bin Packing Problem (BPP) and Traveling Salesman Problem (TSP), respectively. And we demonstrate comparable solution quality to classical with a probability of 6% and 21% accuracy for BPP with 8 and TSP with 12 qubits, respectively.