Transforming optimization problems into a QUBO form: A tutorial
arXiv:2410.21074 · doi:10.1134/S0032946025020036
Abstract
Practically relevant problems of quadratic optimization often contain multidimensional arrays of variables interconnected by linear constraints, such as equalities and inequalities. The values of each variable depend on its specific meaning and can be binary, integer, discrete, and continuous. These circumstances make it technically difficult to reduce the original problem statement to the QUBO form. The paper identifies and considers three main transformations of the original problem statement, namely, the transition from a multidimensional to a one-dimensional array of variables, the transition in mixed problems to binary variables, and the inclusion of linear constraints in the objective function in the form of quadratic penalties. Convenient formulas for calculations are presented and proven, simplifying the implementation of these transformations. In particular, the formulas for the transition in the problem statement from a multidimensional to a one-dimensional array of variables are based on the use of the Kronecker product of matrices. The considered transformations are illustrated by numerous examples.
26 pages, 3 figures; in Russian
References in corpus (8)
- Ising formulations of many NP problems
- Adiabatic Quantum Computing
- Quantum Annealing and Analog Quantum Computation
- Dynamic Portfolio Optimization with Real Datasets Using Quantum Processors and Quantum-Inspired Tensor Networks
- Annealing by simulating the coherent Ising machine
- Quantum-inspired optimization for wavelength assignment
- QCEDA: Using Quantum Computers for EDA
- Improving the convergence of an iterative algorithm for solving arbitrary linear equation systems using classical or quantum binary optimization