Quadratic unconstrained binary optimization (QUBO) has become the standard format for optimization using quantum computers, i.e., for both the quantum approximate optimization algorithm (QAOA) and quantum annealing (QA). We present a toolkit of methods to transform almost arbitrary problems to QUBO by (i) approximating them as a polynomial and then (ii) translating any polynomial to QUBO. We showcase the usage of our approaches on two example problems (ratio cut and logistic regression).
Quadratic unconstrained binary optimization (QUBO) has become the standard format for optimization using quantum computers, i.e., for both the quantum approximate optimization algorithm (QAOA) and quantum annealing (QA). We present a toolkit of methods to transform almost arbitrary problems to QUBO by (i) approximating them as a polynomial and then (ii) translating any polynomial to QUBO. We showcase the usage of our approaches on two example problems (ratio cut and logistic regression).
Quadratic Unconstrained Binary Optimization (QUBO) is a broad class of optimization problems with many practical applications. To solve its hard instances in an exact way, known classical algorithms require exponential time and several approximate methods have been devised to reduce such cost. With the growing maturity of quantum computing, quantum algorithms have been proposed to speed up the solution by using either quantum annealers or universal quantum computers. Here we apply the divide-and-conquer approach to reduce the original problem to a collection of smaller problems whose solutions can be assembled to form a single Polynomial Binary Unconstrained Optimization instance with fewer variables. This technique can be applied to any QUBO instance and leads to either an all-classical or a hybrid quantum-classical approach. When quantum heuristics like the Quantum Approximate Optimization Algorithm (QAOA) are used, our proposal leads to a double advantage: a substantial reduction of quantum resources, specifically an average of ~42% fewer qubits to solve MaxCut on random 3-regular graphs, together with an improvement in the quality of the approximate solutions reached.
This paper introduces an innovative approach to explore the capabilities of Quantum Annealing (QA) for trajectory optimization in dynamic systems. The proposed method involves transforming trajectory optimization problems into equivalent binary optimization problems using Quadratic Unconstrained Binary Optimization (QUBO) representation. The procedure is general and adaptable, making it applicable to a wide range of optimal control problems that entail the satisfaction of dynamic, boundary, and path constraints. Specifically, the trajectory is discretized and approximated using polynomials. In contrast to the conventional approach of determining the polynomial degree (n) solely based on the number of boundary conditions, a specific factor is introduced in our method to augment the polynomial degree. As a result, the ultimate polynomial degree is calculated as a composite of two components: n = l + (m−1), where m denotes the count of boundary conditions and l signifies the number of independent variables. By leveraging inverse dynamics, the control required to follow the approximated trajectory can be determined as a linear function of independent variables l. As a result, the optimization function, which is represented by the integral of the square of the control, can be formulated as a QUBO problem and the QA is employed to find the optimal binary solutions.
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.
Quantum computers are expected to offer advantages in solving optimization problems challenging for classical computers. Quadratic Unconstrained Binary Optimization (QUBO) problems represent an important class of problems with relevance in finance and logistics. The Quantum Approximate Optimization Algorithm (QAOA) is a prominent candidate for solving QUBO problems on near-term quantum devices. In this paper, we evaluate the performance of both the standard QAOA and the adaptive derivative assembled problem tailored QAOA (ADAPT-QAOA) to solve QUBO problems of varying sizes and hardnesses for financial feature selection problems. Our main observation is that ADAPT-QAOA achieves substantially higher approximation ratios than standard QAOA for harder feature-selection problems (α = 0.6) with statistically significant improvements observed for problem sizes n = 6 and 14. However, the standard QAOA remains competitive for simpler problems. Additionally, we evaluate the practical feasibility and limitations of QAOA through a hardware-aware scaling analysis based on the real-device calibration data for various hardware platforms. We estimate that standard QAOA implementation on superconducting quantum computers provides a shorter time-to-solution compared to trapped-ion devices, while trapped-ion devices yield more favorable error rates. Our findings provide a comprehensive overview of the challenges, trade-offs, and strategies for deploying QAOA-based methods on near-term quantum hardware.
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.
The Quantum Approximate Optimization Algorithm (QAOA) is a promising variational quantum algorithm introduced to tackle classically intractable combinatorial optimization problems. This tutorial offers a comprehensive, first-principles introduction to QAOA and its properties, focusing on its application to Quadratic and Polynomial Unconstrained Binary Optimization (QUBO and PUBO) problems. The tutorial begins by outlining variational quantum circuits and QUBO problems, focusing on their key properties and the encoding of problem constraints through quadratic penalty terms. Next, it explores the QAOA in detail, covering its Hamiltonian formulation, gate decomposition, and example applications, along with their implementation and performance results. This is followed by an analysis of the algorithm's energy landscape, where proofs are provided for its symmetry and periodicity, and where a resulting parameter space reduction is proposed. Finally, the tutorial extends these concepts to PUBO problems by generalizing the results to higher-order Hamiltonians and discussing the associated symmetries and circuit construction.