As we learned in Part 1, QUBO (Quadratic Unconstrained Binary Optimization) problems are mathematical problems expressed in terms of binary variables, which may include constraints. They’re important to businesses who need to solve constrained optimization problems when using a quantum annealing machine. In this post, we’ll dive a little further into the structure and form of QUBOs, and how they are used in quantum computing. You won’t need any math more than algebra – so let’s get started.
The Structure of a QUBO
There are many ways to write a QUBO. One common way is to express the QUBO’s terms as a matrix. Another way to express the QUBO is to write the QUBO’s terms in a file, and then read the file into a program. In this post, we’ll express the QUBO algebraically. We’ll start with the two types of terms, and then work an example.
Linear terms
A QUBO includes linear terms in each binary variable, which are composed of a constant (which is set by the programmer), and the binary variable. Examples of these are: −2.7x, 14y, 0.2z, where the binary variables are x, y and z.
Pairwise quadratic terms
A QUBO includes terms involving two binary variables, and a constant (which is set by the programmer). Examples are these are: 1.2xy, −3yz, 0.4xz, where the binary variables are again x, y and z.
Where are the quadratic terms?
You may be wondering why there are not terms like x2, since QUBO is quadratic. The reason is that for binary variables 0 and 1, x2 = x.
A Two-Variable QUBO
To sum up this section, here’s the most general QUBO for two binary variables x and y:
QUBO = Ax + By + Cxy
Now the question is – we mentioned earlier that the constants A, B and C are set by the programmer. How does the programmer choose those values?
Solving A Two-Variable Problem
Suppose that we want to solve a two-variable problem: 1) find the combinations for which the variables have the same value; 2) influence the solver so that it returns these two combinations with lower QUBO value than other combinations.
You might be wondering – this seems like such a small problem. How can it be important? It turns out that solving larger problems depends on understanding little problems like this.
First, for two binary variables, there are four possible combinations: 00, 01, 10 and 11. (In general, for N binary variables, there are 2N combinations, so the algebra gets complicated quickly). Now we want the combinations for which the variables have the same value; that is clearly 00 and 11. The question has then become: How do we set the constants A and B and C so that the QUBO has a lower value for 00 and 11 than for 01 and 10?
First, notice that the QUBO expression will have zero value when we insert x = 0 and y = 0:
QUBO = A(0) + B(0) + C(0)(0) = 0
Noticing this, we realize that we also need to get a value of 0 for the combination 11, so that the two combinations with same variable values will have the same QUBO value. This means we need to have:
QUBO = A(1) + B(1) + C(1)(1) = 0
This doesn’t tell us very much. However, we also know that the combinations 01 and 10 must have a higher QUBO value; and putting in 10 to the QUBO, we get:
QUBO = A(1) + B(0) + C(1)(0) = A
We penalize the 10 combination – give it higher QUBO value – by setting A = 1. (We have chosen 1 for simplicity – it could be any number larger than zero.) If we do the same thing with the 01 combination, we will get B = 1. Now, if we go back to the 11 combination, we will have:
QUBO = (1)(1) + (1)(1) + C(1)(1) = 0
and this indicates that we must have C = −2. Thus, our QUBO will be:
QUBO = x + y − 2xy
What do we do with this QUBO, now that we have it?
Sending the QUBO for Processing
We can send this QUBO to QCi’s Qatalyst quantum software to be solved. We will need to follow this process:
- Express the QUBO as linear and pairwise quadratic terms (we already did this)
- Either write the QUBO values (the constants) into a computer program, or into a data file
- Include statements in the computer program which call the solver’s API. The solver’s API (for example, the Qatalyst API) will take care of sending the QUBO to the computation engine, and receiving the results which the engine returns. (known as the bitstring or solution)
- Check that the solutions returned do solve the original problem you sent.
In the future, we expect developers and companies to build software tools which eliminate the need for some of the steps in this process. We started with this small problem, though, so that you would understand what needs to happen, under the surface.
Your assignment – should you choose to accept it – is to get access to a quantum computer and try it out!
