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.

However, today and in the nearer future, there are several strings attached to it.  

1. Availability: An obvious drawback is that today and in the nearer future, quantum machines are available only in very limited numbers and dimensions. It will certainly take some more time until quantum computers are a) widely available and b) large enough (in terms of number of qubits) to tackle real-world optimization problems.  

2. Optimality: Even more important (because invariant to availability), quantum-based approaches to solve QUBOs typically only return a solution which is in some energy-minimal state, but this state is very likely to be only a local energy minimum without any guarantees that there isn’t a better solution to the optimization problem (the global optimum). This is due to (i) algorithmic aspects (most quantum approaches, e.g., quantum annealing or QAOA are heuristic by nature) and (ii) physical aspects: Noisy intermediate-scale quantum machines are prone to inaccuracy caused by, e.g., infidelity of gates, crosstalk, state preparation, or measurement errors and these errors are amplified with larger quantum circuits, low connectivity between qubits, etc. Overall, (i) and (ii) mean that quantum optimization approaches only provide a solution without any guarantees on its quality and it is well known that these solutions may be far off from the true globally optimal solution. For many applications, however, it is crucial to derive the proven globally optimal solution or at least some quality assessment on how good the solution actually is. See also our last blog post dedicated to this topic.  

Quantagonia’s HybridSolver circumvents both drawbacks by exploiting three things:

1. Hardware agnostic-approach: QUBOs are suited to be solved on both classical and quantum computers. Thus, QUBO constitutes a one-fits-all modeling approach that can be leveraged across an evolving range of hardware (CPUs, GPUs, QPUs, FPGAs, and more).  

2. Solution assessment and global optimization: Quantagonia’s QUBO solver works in a way that improves the solution over time until global optimality is proven. At every step of the algorithm a quality evaluation of the solution in the spirit “What is the maximum improvement I could get by running the algorithm longer?” is available.

3. Splitting problems into chunks: Our solver iteratively splits the problem into smaller chunks, which makes it easier to integrate today’s limited-in-size quantum hardware. The splits are carried out in a way to still be able to return the true globally optimal solution to the optimization problem.  

The second and third point are addressed by solving QUBOs with a branch-and-bound algorithm, see the last post for more details. The first point is addressed by using specially tailored algorithms for solving the subproblems of branch-and-bound, which are perfectly well suited to be carried out on a wide range of different hardware. Let’s dive into the details.

‍

Quantum-powered Branch-and-Bound for QUBOs

In general, QUBOs are nonconvex mixed-integer nonlinear optimization problems due to products of variables in the objective function. This renders the application of branch-and-bound a lot harder than for case of convex mixed-integer problems that we discussed in the last blog post. The good news however is that every QUBO can be transformed into an equivalent convex QUBO with the same optimum by applying a large-enough shift $s$ to the objective function:

$$\max_{x\in\{0,1\}^n}x^T(Q+\text{diag}(s))x+s^Tx.$$

The shift can be obtained in various ways, e.g., by computing the largest Eigenvalue of $Q$ or by solving an auxiliary semidefinite optimization problem (SDP). This method is also known as the Quadratic Convex Reformulation, see ​[4]​. The convexified QUBO can then be tackled by branch-and-bound methods as outlined in the last post. One interesting aspect is that the shift computation may be carried out on a quantum machine, see, e.g., the paper ​[5]​ on how to solve SDPs on quantum computers.

In addition to the shift computation, many subroutines of the branch-and-bound are perfectly suited to leverage quantum computing. Even the coordination of the branch-and-bound tree may be carried out on a QPU by exploiting quantum tree search and quantum tree size estimation, see [6].

Heuristic solutions from quantum

We already mentioned that quantum approaches to solve QUBOs are of heuristic nature. While using such algorithms as standalone approaches is a drawback in our opinion due to the lack of solution quality guarantees, etc., all these approaches may be used as very powerful heuristics at (potentially) every node of the branch-and-bound tree.  

Bounding with quantum

The bounding step at branch-and-bound nodes may be carried out in a way to simultaneously update the bound and tighten the QUBO convexification - stay tuned for a technical paper that has all the details. The important take away is that the bounding step is again a SDP that may be solved on a quantum machine. 

Conclusion

Of course, quantum computing is still in its infancy, and it will take some more time until quantum computers will be available to the public at scale. While our QUBO solver is fully quantum-ready today, every component of the algorithm can also be carried out on CPUs and GPUs. This allows to solve QUBOs hassle-free on todays and tomorrow's hardware. Interested to see it in action? Reach out for a free trial!

‍

​​Bibliography

​[1] A. Lucas, „Ising formulations of many NP problems“, Frontiers in Physics , Bd. 2, 2014.  

​[2]  F. Glover, G. Kochenberger und Y. Du, „Quantum Bridge Analytics I: a tutorial on formulating and using QUBO models“, 4OR, Vol. 17, pp. 335-371, 2019.  

​[3] ​F. Barahona, M. Jünger und G. Reinelt, „Experiments in quadratic 0–1 programming“, Mathematical Programming, Vol. 44, Nr. 1-3, pp. 127-137, 1989.  

​[4] A. Billionnet und S. Elloumi, „Using a mixed integer quadratic programming solver for the unconstrained quadratic 0-1 problem“, Mathematical Programming, Vol. 109, pp. 55-68, 2007.  

​[5] ​B. Augustino, G. Nannicini, T. Terlaky und L. Zuluaga, „Solving the semidefinite relaxation of QUBOs in matrix multiplication time, and faster with a quantum computer“, arXiv, 2023.

[6] A. Montanaro, "Quantum speedup of branch-and-bound algorithms", Physical Review Research, Vol. 2, Iss. 1, 2020