Resources
Article
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 thelast 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
