Solving QUBOs to Proven Optimality

Introduction

In the last post we discussed the important distinction between a solution and the solution of a mathematical optimization problem. Many applications require to find the global optimal solution, and even if a close-to-optimal solution is good enough, one needs to be able to judge how good a given solution actually is. Many practical classic optimization approaches fail to do so and quantum approaches are no different to that. Quantum optimization algorithms like QAOA or quantum annealing are of inherent heuristic nature and only return a solution. In fact, on top of that, noisy intermediate-scale quantum machines are prone to errors resulting from, e.g., lack of fidelity of gates, crosstalk, state preparation, or measurement errors. These errors are amplified with larger quantum circuits, low degree of connectivity between qubits, etc., such that solutions returned by quantum approaches are quite often far away from the true global optimal solution – without the user knowing about it.  

In this post, we explain how our HybridSolver circumvents these drawbacks of quantum optimization by exploiting the branch-and-bound paradigm in a hybrid classic-quantum fashion. We recommend to read the last post on branch-and-bound, before diving into the details of this post.  

‍

Quantum optimization and QUBOs

A Quadratic Unconstrained Binary Optimization (QUBO) problem is a combinatorial optimization problem with a very specific structure. It can be written as

with an $n$-dimensional variable vector $x$, a real-valued and symmetric $n \times n$ matrix $Q$ and an $n$-dimensional vector $c$. Since $x_i^2=x_i$ holds for all $1\leq i \leq n$, we can also write a QUBO problem as

Hence, a QUBO maximizes linear and pairwise quadratic variables without further explicit constraints. QUBOs are NP-hard in general which means that we cannot expect to solve such problems in feasible time on classic machines. Considering the combinatorial and nonlinear nonconvex nature of QUBOs, this is not surprising.

Despite their special structure, QUBOs address a wide range of applications from various industries such as portfolio optimization, logistics and supply chain optimization, or machine scheduling. In fact, many classic combinatorial and integer optimization problems may be recast as a QUBO. For more details on applications as well as reformulating optimization problem as QUBOs, we refer to ​[1]​ and​ [2]​.

In recent years, QUBOs gained increasing popularity in the quantum computing community, mainly due to their equivalence to Ising models. Every QUBO (in $\{0,1\}$-variable space) can be transformed to an Ising model in $\{−1,1\}$-variable space; see, e.g., ​[3]​. This allows QUBOs to be solved on quantum computers through quantum annealing or variational algorithms like QAOA. The long-term bet is that via this approach, the most challenging optimization problems can be solved (much) faster than on classical computers.