3.3 Moving from Ising to QUBO and back

Consider the following problem. Let's say that you are given a set of integers and a target integer value , and you are asked whether there is any subset of whose sum is . For instance, if and , then the answer is affirmative, because . However, if and , the answer is negative because all the numbers in the set are even and they cannot add up to an odd number.

This problem, called the Subset Sum problem, is known to be -complete (see, for instance, Section 7.5 in the book by Sipser [90] for a proof). It turns out that we can reduce the Subset Sum problem to finding a spin configuration of minimal energy for an Ising model, (which is an -hard problem – see Section 3.1.3). This means that we can rewrite any instance of Subset Sum as an Ising ground state problem (check Appendix C, Computational Complexity, for a refresher on reductions).

However, it may not be directly evident how to do so.

In fact, it is much simpler to pose the Subset Sum problem as a minimization problem by using binary variables instead of variables that take or values. Indeed, if we are given and an integer , we can define binary variables , , and consider

Clearly, the Subset Sum problem has a positive answer if and only if we can find binary values , , such that . In that case, the variables that are equal to will indicate which numbers from the set are selected for the sum. But is always non-negative, so we have reduced the Subset Sum problem to finding the minimum of : if the minimum is , the Subset Sum has a positive solution; otherwise, it doesn't.

For example, for the case of and that we considered previously, the problem would be

where we have expanded to obtain the expression to be optimized. If you wish, you can simplify it a little by taking into account that always holds for binary variables. In any case, would be an optimal solution for this problem.

Notice that, in all of these cases, the function that we need to minimize is a polynomial of degree on the binary variables . We can thus generalize this setting and define Quadratic Unconstrained Binary Optimization (QUBO) problems, which are of the form

where is a quadratic polynomial on the variables. The reason why these problems are called QUBO should now be clear: we are minimizing quadratic expressions over binary variables with no restrictions (because every combination of zeroes and ones is acceptable).

From the preceding reduction of the Subset Sum problem, it follows that QUBO problems are -hard. Indeed, the QUBO model is very flexible, and it enables us to formulate many optimization problems in a natural way. For example, it is quite easy to recast any Ising minimization problem as a QUBO instance. If you need to minimize

with some variables , , taking values or , you can define new variables . Obviously, will be when is , and when is . Furthermore, if you make the substitutions , you obtain a quadratic polynomial in the binary variables that takes exactly the same values as the energy function of the original Ising model. If you minimize the polynomial for the variables , you can then recover the spin values that achieve the minimal energy.

In case you were wondering, yes, you can also use the substitution to transform Ising problems into QUBO formalism. In that case, values of equal to would be taken to values of equal to and values of equal to would be taken to in . However, we will stick to the transformation for the rest of the book.

For instance, if the Ising energy is given by , then, under the transformation , the corresponding QUBO problem will be the following:

You can also go from a QUBO problem to an Ising model instance by using the substitution. However, you will need to pay attention to a couple of details. Let's illustrate them with an example. Suppose that your QUBO problem is asking to minimize . Then, when you substitute the variables, you obtain

But the Ising model does not allow squared variables or independent terms! Fixing these problems is not difficult, though. Regarding the squared variables, we can simply notice that it always holds that , because is either or . Thus, we replace each squared variable with the constant value . In our case, we would get

Then, we can simply drop the independent term, because we are dealing with a minimization problem and it won't influence the choice of optimal variables (however, you should add it back when you want to recover the original value of the function to minimize). In the preceding example, the equivalent Ising minimization problem would then be the following:

It is easy to check that this problem has two optimal solutions: and , both attaining the value. If we add back the independent term of value that we had dropped, we obtain an optimal cost of in the QUBO problem. These solutions correspond to and , respectively, which indeed evaluate to and are optimal for the original problem.

Exercise 3.5

Write the Subset Sum problem for and as a QUBO problem and transform it into an instance of the Ising model.

So now we know how to go from QUBO problems to Ising energy minimization problems and back, and we can use either formalism — whichever is more convenient at any given moment. In fact, as we will learn in Chapters 4 and 5, the Ising model is the preferred formulation when solving combinatorial optimization problems with quantum computers. Also, the software tools that we will be using (Qiskit and D-Wave's Ocean) will help us in rewriting our QUBO problems in the Ising formalism by using transformations like the ones we have described in this section.

We now have all the mathematical tools that we need in order to work with combinatorial optimization problems if we want to solve them with quantum computers. Let's play with our new, shiny toys and use them to write some important problems in QUBO formalism.