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

Problems of Information Transmission

REDUCING DISCRETE OPTIMIZATION PROBLEMS TO THE QUBO FORM

A.M. Semenov, S.R. Usmanov, Aleksey K. Fedorov

Published Jan 1, 2025• 2 citations
Publisher

Abstract

Practical discrete optimization problems often contain multidimensional arrays of variables with linear constraints, which complicates their conversion to QUBO (quadratic unconstrained binary optimization) form. The article proposes a systematic approach to transforming such problems, which includes three key steps: the transition from a multidimensional representation of variables to a one-dimensional one using the Kronecker product of matrices, the reduction of mixed variables to binary ones, and the introduction of linear constraints into the objective function through quadratic penalties. Explicit computational formulas are obtained for each stage, simplifying their software implementation. The developed method is illustrated with examples from graph theory and combinatorial optimization, including classical formulations, confirming its universality. The results of the article allow standardizing the process of adapting problems for solving on quantum annealing algorithms (e.g., D-Wave) and classical QUBO solvers.

DOI
10.7868/s3034583925020041

Related papers

Technique for Transforming Discrete Optimization Problems into QUBO Form

A. M. Semenov, Sergey R. Usmanov, Aleksey K. Fedorov

Practical discrete optimization problems often contain multidimensional arrays of variables interrelated by linear constraints such as equalities and inequalities. Values of each variable depend on its specific meaning and can be binary, integer, or discrete. These conditions make it technically difficult to reduce the original problem statement to QUBO form. We identify and examine three necessary transformations of the original problem statement to reduce it to QUBO form, namely transition from a multidimensional to a one-dimensional array, transition to binary variables in mixed problems, and incorporating linear constraints into the objective function in the form of quadratic penalties. We present and prove computationally convenient formulas to simplify these transformations. In particular, the formulas for the transition from a multidimensional to a one-dimensional array of variables are based on the application of the Kronecker product of matrices. The transformations considered are illustrated by numerous examples and used, as an application, to reduce a number of well-known problems in graph theory and combinatorial optimization to QUBO form.

arXiv:2410.21074•Problems of Information Transmission•Sep 1, 2025•2 citations

Multidimensional Knapsack Problem Based on QUBO Model

Wang Qiwei, Yang Hongli

Multidimensional knapsack problem is a classical combinatorial optimization problem, the goal is to find a set of optimal options to satisfy all the constraints. The traditional algorithms for solving multidimensional knapsack problems generally have some disadvantages, such as slow computation speed and exponential increase of computation with the increase of problem dimension. To solve these problems, a QUBO (quadratic unconstrained binary optimization) model is proposed, and the multidimensional knapsack problem is expressed as a quadratic unconstrained binary optimization problem. Binary variables are used to represent the objective function of the multidimensional knapsack problem. The constraints are added to the objective function in the form of quadratic terms by means of penalty terms. The objective function is further transformed into QUBO form. The model is created by PyQUBO, an open source Python library, and solved by quantum annealing algorithm on D-Wave platform. The results show that the QUBO model has a strong ability of mathematical expression, which makes the problem more structured, and is suitable for large-scale problems, dealing with multidimensional knapsack problems with a lot of variables and constraints.

Computer Science and Technology•Sep 19, 2023•0 citations

Quadratic constrained mixed discrete optimization with an adiabatic quantum optimizer

Rishabh Chandra, N. Tobias Jacobson, Jonathan E. Moussa +2 more

We extend the family of problems that may be implemented on an adiabatic quantum optimizer (AQO). When a quadratic optimization problem has at least one set of discrete controls and the constraints are linear, we call this a quadratic constrained mixed discrete optimization (QCMDO) problem. QCMDO problems are NP-hard, and no efficient classical algorithm for their solution is known. Included in the class of QCMDO problems are combinatorial optimization problems constrained by a linear partial differential equation (PDE) or system of linear PDEs. An essential complication commonly encountered in solving this type of problem is that the linear constraint may introduce many intermediate continuous variables into the optimization while the computational cost grows exponentially with problem size. We resolve this difficulty by developing a constructive mapping from QCMDO to quadratic unconstrained binary optimization (QUBO) such that the size of the QUBO problem depends only on the number of discrete control variables. With a suitable embedding, taking into account the physical constraints of the realizable coupling graph, the resulting QUBO problem can be implemented on an existing AQO. The mapping itself is efficient, scaling cubically with the number of continuous variables in the general case and linearly in the PDE case if an efficient preconditioner is available.

arXiv:1310.1933•Physical Review A•Jul 8, 2014•3 citations

QUBO Sampling for Mixed Binary Quadratic Programming without Continuous Variable Binarization

Taisei Takabayashi, Masayuki Ohzeki

Quantum annealing and related combinatorial optimization methods typically accept quadratic unconstrained binary optimization (QUBO) problems as input, whereas many practical models include constraints and continuous variables. Standard QUBO conversions discretize continuous variables, increasing the binary dimension and often making feasible low-energy states harder to sample. We develop a Lagrange-multiplier method for a separable class of mixed-binary quadratic programs (MBQPs) without discretizing continuous variables. The method is based on a finite-temperature free-energy formulation and uses QUBO sampling for the binary sector. At fixed Lagrange multipliers, the continuous sector is integrated out analytically and enters only the multiplier update, leaving a QUBO over the original binary variables. We evaluate the method on the continuous relaxation of the quadratic $p$-median problem. Compared with a penalty-based QUBO formulation, it generates feasible solutions more reliably. At an appropriate inverse temperature, its conditional relative error is comparable to that of local search for small instances and often lower for the larger tested instances. In the time-to-target comparisons, the proposed method maintains high target-reached rates for stringent fixed-accuracy targets. For the larger instances within the tested range, it also reaches the prescribed targets faster than a commercial mixed-integer optimization solver.

quant-pharXiv:2607.21286•Scientific Reports•Jul 24, 2026•0 citations

Constraint Embedding for Solving Optimization Problems on Quantum Annealers

Tomáš Vyskočil, Hristo N. Djidjev

Quantum annealers such as the commercially available D-Wave machines are designed to natively solve quadratic unconstrained binary optimization (QUBO) problems. While most of the well-known NP-hard optimization problems can easily be formulated as quadratic binary problems, such formulations also contain constraints, which commonly are added to the objective function in the form of penalties to obtain a QUBO version. However, the standard method for defining such penalties leads to QUBOs that are dense and therefore take too much of the resources of the quantum annealer. In this paper, we describe an alternative approach to the constraint embedding problem that uses mixed-integer linear programming (MILP) and is scalable to problems of arbitrary number of variables.

IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum•May 1, 2019•2 citations

Logical and Inequality Implications for Reducing the Size and Complexity of Quadratic Unconstrained Binary Optimization Problems

Fred Glover, Mark W. Lewis, Gary A. Kochenberger

The quadratic unconstrained binary optimization (QUBO) problem arises in diverse optimization applications ranging from Ising spin problems to classical problems in graph theory and binary discrete optimization. The use of preprocessing to transform the graph representing the QUBO problem into a smaller equivalent graph is important for improving solution quality and time for both exact and metaheuristic algorithms and is a step towards mapping large scale QUBO to hardware graphs used in quantum annealing computers. In an earlier paper (Lewis and Glover, 2016) a set of rules was introduced that achieved significant QUBO reductions as verified through computational testing. Here this work is extended with additional rules that provide further reductions that succeed in exactly solving 10% of the benchmark QUBO problems. An algorithm and associated data structures to efficiently implement the entire set of rules is detailed and computational experiments are reported that demonstrate their efficacy.

arXiv:1705.09545•May 26, 2017•0 citations
Practical discrete optimization problems often contain multidimensional arrays of variables with linear constraints, which complicates their conversion to QUBO (quadratic unconstrained binary optimization) form. The article proposes a systematic approach to transforming such problems, which includes three key steps: the transition from a multidimensional representation of variables to a one-dimensional one using the Kronecker product of matrices, the reduction of mixed variables to binary ones, and the introduction of linear constraints into the objective function through quadratic penalties. Explicit computational formulas are obtained for each stage, simplifying their software implementation. The developed method is illustrated with examples from graph theory and combinatorial optimization, including classical formulations, confirming its universality. The results of the article allow standardizing the process of adapting problems for solving on quantum annealing algorithms (e.g., D-Wave) and classical QUBO solvers.
Practical discrete optimization problems often contain multidimensional arrays of variables interrelated by linear constraints such as equalities and inequalities. Values of each variable depend on its specific meaning and can be binary, integer, or discrete. These conditions make it technically difficult to reduce the original problem statement to QUBO form. We identify and examine three necessary transformations of the original problem statement to reduce it to QUBO form, namely transition from a multidimensional to a one-dimensional array, transition to binary variables in mixed problems, and incorporating linear constraints into the objective function in the form of quadratic penalties. We present and prove computationally convenient formulas to simplify these transformations. In particular, the formulas for the transition from a multidimensional to a one-dimensional array of variables are based on the application of the Kronecker product of matrices. The transformations considered are illustrated by numerous examples and used, as an application, to reduce a number of well-known problems in graph theory and combinatorial optimization to QUBO form.
Multidimensional knapsack problem is a classical combinatorial optimization problem, the goal is to find a set of optimal options to satisfy all the constraints. The traditional algorithms for solving multidimensional knapsack problems generally have some disadvantages, such as slow computation speed and exponential increase of computation with the increase of problem dimension. To solve these problems, a QUBO (quadratic unconstrained binary optimization) model is proposed, and the multidimensional knapsack problem is expressed as a quadratic unconstrained binary optimization problem. Binary variables are used to represent the objective function of the multidimensional knapsack problem. The constraints are added to the objective function in the form of quadratic terms by means of penalty terms. The objective function is further transformed into QUBO form. The model is created by PyQUBO, an open source Python library, and solved by quantum annealing algorithm on D-Wave platform. The results show that the QUBO model has a strong ability of mathematical expression, which makes the problem more structured, and is suitable for large-scale problems, dealing with multidimensional knapsack problems with a lot of variables and constraints.
We extend the family of problems that may be implemented on an adiabatic quantum optimizer (AQO). When a quadratic optimization problem has at least one set of discrete controls and the constraints are linear, we call this a quadratic constrained mixed discrete optimization (QCMDO) problem. QCMDO problems are NP-hard, and no efficient classical algorithm for their solution is known. Included in the class of QCMDO problems are combinatorial optimization problems constrained by a linear partial differential equation (PDE) or system of linear PDEs. An essential complication commonly encountered in solving this type of problem is that the linear constraint may introduce many intermediate continuous variables into the optimization while the computational cost grows exponentially with problem size. We resolve this difficulty by developing a constructive mapping from QCMDO to quadratic unconstrained binary optimization (QUBO) such that the size of the QUBO problem depends only on the number of discrete control variables. With a suitable embedding, taking into account the physical constraints of the realizable coupling graph, the resulting QUBO problem can be implemented on an existing AQO. The mapping itself is efficient, scaling cubically with the number of continuous variables in the general case and linearly in the PDE case if an efficient preconditioner is available.
Quantum annealing and related combinatorial optimization methods typically accept quadratic unconstrained binary optimization (QUBO) problems as input, whereas many practical models include constraints and continuous variables. Standard QUBO conversions discretize continuous variables, increasing the binary dimension and often making feasible low-energy states harder to sample. We develop a Lagrange-multiplier method for a separable class of mixed-binary quadratic programs (MBQPs) without discretizing continuous variables. The method is based on a finite-temperature free-energy formulation and uses QUBO sampling for the binary sector. At fixed Lagrange multipliers, the continuous sector is integrated out analytically and enters only the multiplier update, leaving a QUBO over the original binary variables. We evaluate the method on the continuous relaxation of the quadratic ppp-median problem. Compared with a penalty-based QUBO formulation, it generates feasible solutions more reliably. At an appropriate inverse temperature, its conditional relative error is comparable to that of local search for small instances and often lower for the larger tested instances. In the time-to-target comparisons, the proposed method maintains high target-reached rates for stringent fixed-accuracy targets. For the larger instances within the tested range, it also reaches the prescribed targets faster than a commercial mixed-integer optimization solver.
Quantum annealers such as the commercially available D-Wave machines are designed to natively solve quadratic unconstrained binary optimization (QUBO) problems. While most of the well-known NP-hard optimization problems can easily be formulated as quadratic binary problems, such formulations also contain constraints, which commonly are added to the objective function in the form of penalties to obtain a QUBO version. However, the standard method for defining such penalties leads to QUBOs that are dense and therefore take too much of the resources of the quantum annealer. In this paper, we describe an alternative approach to the constraint embedding problem that uses mixed-integer linear programming (MILP) and is scalable to problems of arbitrary number of variables.
The quadratic unconstrained binary optimization (QUBO) problem arises in diverse optimization applications ranging from Ising spin problems to classical problems in graph theory and binary discrete optimization. The use of preprocessing to transform the graph representing the QUBO problem into a smaller equivalent graph is important for improving solution quality and time for both exact and metaheuristic algorithms and is a step towards mapping large scale QUBO to hardware graphs used in quantum annealing computers. In an earlier paper (Lewis and Glover, 2016) a set of rules was introduced that achieved significant QUBO reductions as verified through computational testing. Here this work is extended with additional rules that provide further reductions that succeed in exactly solving 10% of the benchmark QUBO problems. An algorithm and associated data structures to efficiently implement the entire set of rules is detailed and computational experiments are reported that demonstrate their efficacy.