Optimization and QUBOs: A Primer Part One

Optimization and QUBOs: A Primer Part 1

Rebel Brown

QUBO is one of the buzzwords that you hear a lot if you’re around quantum computing. Yet there are many different perceptions about what a QUBO really is and why you need it. Since Qatalyst automatically creates QUBOs for its users – we wanted to spend a bit of time talking about what a QUBO is, where it is applied and why you need it.

What is a QUBO?

QUBO stands for Quadratic Unconstrained Binary Optimization. You hear it mentioned, in articles about solving problems on D-Wave (and potentially future) quantum annealing computers.

A QUBO is actually a mathematical class of problems, as well as a specific mathematical problem, with a specific mathematical form.

Let’s look at each of the components of the Quadratic Unconstrained Binary Optimization, starting with the Optimization itself.

Optimization is a QUBO-friendly mathematics problem

Optimization refers to the kind of problem that is expressed by a specific mathematical form. Optimization mathematics seeks the best answer for a problem, based on a set of criteria which possibly conflict with each other.

The widely known use of optimization in business is for logistics planning. A truck driver has a series of deliveries to make, to a group of houses.The company wants the driver to minimize her time spent driving, which will save fuel, and allow her to reach more houses during a full day. The company might also wish to minimize the distance driven.

However, there are some tradeoffs. For example, highways might offer longer paths which take less time, because of the absence of stoplights. Additionally, if the houses are in areas which involve heavy traffic, outlying roads might offer better paths.

We can write this problem as an optimization problem, in which the company weighs the criteria and determines the best solution for potentially hundreds of drivers.

Another optimization problem is familiar for those who travel often – the problem of assigning airline prices. If the ticket prices are set too high, flights won’t fill. If the ticket prices are set too low, particular types of seats will fill quickly,  but others may not. In this complicated problem there are many variables – the day of the week, whether there is a holiday, the time of day, the  demand in the market etc.

Optimization problems are used in so many ways in business. Especially now, as supply chains grow more complex, logistics shift to demand fast, last mile delivery to consumers, drug discovery becomes more sophisticated and financial applications demand deeper insights for  portfolio management, risk assessment and more.

Next up, Binary

A solver refers to the software, and sometimes hardware, that runs the computations to solve an optimization problem. We say that we send the problem to the solver, and the solver returns the best solutions it could find. It is then up to the user to interpret the solutions in terms of the problem’s binary variables, to see whether the optimization criteria have been met successfully.

In the above case, binary means that the mathematical form is expressed in binary variables; that is, variables which can only take two values, “off” and “on.” Often we write 0 for the value “Off” and 1 for the value “On,” so that the binary variables are just 0 and 1. There are other choices; for example, in Ising model problems (named after the German physicist Ernst Ising), the binary choices are -1 and 1.

How can we solve a complicated problem by using variables which can only take two values?

First, let’s look at what’s called constrained optimization. An optimization problem is routinely expressed in terms of a set of variables, an objective function (a quantity to be minimized or maximized) and a set of constraints.

Consider choices for that delivery truck we mentioned earlier. Suppose it has four different routes between house A and house B. If we’re expressing the problem in binary variables, we could use four binary variables. The first represents the decision: do we choose the first route? Yes or No? The second route represents the decision: do we choose the second route? Yes or No? You get the idea. You can also realize that when we actually try the optimization, we want only one of these binary variables to be Yes, while the others need to be No. This is called a constraint – a condition on the binary variables.

Confused about the Unconstrained in the QUBO?

What does Unconstrained mean, given that we just explained what a constraint is?

The term Unconstrained in the QUBO definition refers to the fact that QUBOs allow the computation to satisfy all the constraints, but won’t rigorously insist that all the constraints MUST be solved.

A QUBO gives us methods to penalize potential solutions which violate constraints, but makes it possible to still find solutions which violate constraints. In this sense, the QUBO is unconstrained because we have not rigorously insisted in following all of the constraints.

Consider the alternate routes to be taken, in the truck problem we’ve been discussing. If we can choose between four possible routes between A and B, we clearly have a constraint which should be followed by selecting one, and only one, of those routes. But we do not force the solutions to select only one. We allow the computation to find the best solutions – optimized solutions – which have only one of those routes selected.

This offers an advantage with QUBOs when processing optimizations, since it allows for multiple answers to be provided as results, even though they do not rigorously meet every single constraint. In large scale problems, this diversity of results often offers much deeper insights than a single, constrained result.

What about Quadratic? 

Finally, let’s consider the word quadratic. You might remember back to your high school algebra, where the word quadratic means “to the power two”. You might remember graphs like circles and parabolas, which were equations involving quadratic powers of a single variable.

The word quadratic tells us that the mathematical form of a QUBO may not include anything besides linear terms (like x and y, if those are the independent variables), and xy (known as a “pairwise quadratic” term).

Problems expressed in terms of QUBOs are sometimes said to be “models,” and the mathematics of a particular problem determines whether linear terms are sufficient, or whether quadratic terms are needed as well. For example, consider a model that attempts to predict the NCAA basketball tournament winners. Linear terms might describe an individual team’s conference and competitive level of opponents in general; and linear terms might describe whether a team’s roster is depleted, etc. In contrast, quadratic terms would add “pair terms” describing how one team performed versus another specific team, during the course of a season. The research involved in creating quadratic terms might be more expensive and detailed; and a betting pool competitor might want to use only linear terms to save money.

The Bottom Line

OK, so now that we’ve given you a deeper dive into the mathematics terms that form the QUBO, let’s do a simple summary.

A QUBO is:

  • A mathematical problem
  • Stated in binary variables,
  • Where variables are linear or pairwise quadratic,
  • Which may include constraints.

A QUBO empowers quantum computers to find solutions which satisfy those constraints, without forcing the constraints to hold true. Which adds significant value in problems where multiple results offer deeper insights and more discretion for making better business decisions.

In the next blog, we’ll discuss the structure and form of a QUBO and how it is used in quantum computing.