How good is good enough?

Introduction

In this post we discuss what it means to solve mathematical optimization problems and that having a solution not necessarily means we have the best possible solution. We highlight why it is however crucial to obtain the best possible solution or at least to know how good a given solution actually is. We demonstrate how this can be achieved by the branch-and-bound paradigm and walk in detail through the various steps of branch-and-bound. We also indicate implications for and differences to quantum optimization when it comes to a vs. the solution.

‍

On mathematical optimization and optimal solutions

Arguably one of the most promising use cases for quantum computing is mathematical optimization (also known as decision making). In mathematical optimization, we want to choose decision variables $x\in\mathbb{R}^n$ in a way to maximize an objective function $f(x)$ while satisfying a set of constraints $c(x)\leq 0$, i.e.:

$$ \begin{aligned} \max_{x\in\mathbb{R}^n} \ &f(x)\\ \text{s.t. } \ &c(x)\leq 0\\ &x_i\in\mathbb{Z}, i\in I \end{aligned}$$

In most practical problems, some (or even all) decision variables are constrained to be integer (the variables $x_i$ with $i\in I$), while the remaining variables are continuous. In the general case of nonlinear and nonconvex functions $f$ and $c$, the optimization problem above is a nonconvex mixed-integer nonlinear problem (MINLP). Such problems are NP-hard due to their combinatorial and nonlinear nature, and we cannot expect to solve such problems to optimality efficiently on classic computers. Will this change with quantum computers?

Well, this new computing paradigm is supposed to be a disruptive game changer for many computational tasks and mathematical optimization is no exception to that. Quantum optimization approaches like QAOA or Quantum Annealing promise to provide solutions to QUBOs, a subclass of MINLPs, very fast. But what does solution and optimality actually mean?

This is a general discussion and not specifically linked to quantum computing. Understanding the difference between a solution (a point that fulfills all constraints) and the solution (a solution with the best possible objective value) is not tied to the hardware and is equally important for both classical and quantum computing. We discuss implications to quantum computing in more detail towards the end of this post.