Solving QUBOs to Proven Optimality

Quantagonia macht alte Software fit für Quantencomputer. Würde Frank Thelen investieren?

Aug 16, 2023
min read
Read full article


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.

Related articles
Partnership brings Quantagonia’s HybridSolver to the Strangeworks Ecosystem.
Sep 12, 2023
min read

Partnership brings Quantagonia’s HybridSolver to the Strangeworks Ecosystem.

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Suspendisse varius enim in eros.
How good is good enough?
Aug 1, 2023
min read

How good is good enough?

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Suspendisse varius enim in eros.
Quantagonia Application Logo

Want to get entangled or stay up to date?

Let's push the boundaries of technology and create a quantum-powered future.