Chapter 3
Working with Quadratic Unconstrained Binary Optimization Problems

The universe cannot be read until we have learned the language and become familiar with the characters in which it is written.
— Galileo Galilei

Starting with this chapter, we will be studying different algorithms that have been proposed to solve optimization problems with quantum computers. We will work both with quantum annealers and with computers that implement the quantum circuit model. We will use methods such as the Quantum Approximate Optimization Algorithm (QAOA), Grover’s Adaptive Search (GAS), and the Variational Quantum Eigensolver (VQE). We will also learn how to adapt these algorithms to different types of problems, and how to run them on simulators and actual quantum computers.

But before we can do all that, we need a language in which we can state problems in a manner that makes it possible for a quantum computer to solve them. In this regard, with the Quadratic Unconstrained Binary...

3.1 The Max-Cut problem and the Ising model

In order for us to understand how to use quantum computers to solve optimization problems, we need to get used to some abstractions and techniques that we will develop throughout this chapter. To get started, we will consider the problem of finding what we call maximum cuts in a mathematical structure called a graph. This is possibly the simplest problem that can be written in the formalism that we will be using in the following chapters. It will help us in gaining intuition and it will provide a solid foundation for formulating more complicated problems later on.

3.1.1 Graphs and cuts

When you are given a graph, you are essentially given some elements, which we will refer to as vertices, and some connections between pairs of these vertices, which we will call edges. See Figure 3.1 for an example of a graph with five vertices and six edges.

Figure 3.1: Example of a graph

Given a graph, the Max-Cut problem consists in finding a maximum...

3.2 Enter quantum: formulating optimization problems the quantum way

In this section, we will unveil how all the work that we have done so far in this chapter has followed a secret plan! Was the choice of as the name for the variables in our problems completely arbitrary? Of course not! If it made you think of those lovely quantum gates and matrices that we introduced back in Chapter 1, Foundations of Quantum Computing, you were on the right track. It will be the key to introducing the quantum factor into our problems, as we will begin to see in the next subsection.

3.2.1 From classical variables to qubits

So far, the formulations that we have considered for the Max-Cut problem and for the Ising model are purely classical. They do not mention quantum elements such as qubits, quantum gates, or measurements. But we are closer than you might think to being able to give a quantum formulation for these problems. We will start with a very simple instance of the Max-Cut problem and show...

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...

3.4 Combinatorial optimization problems with the QUBO model

In this final section of the chapter, we are going to introduce some techniques that will allow us to write many important optimization problems as QUBO and Ising instances, so we can later solve them with different quantum algorithms. These examples will also help you understand how to formulate your own optimization problems under these models, which is the first step in order to be able to use quantum computers to solve them.

3.4.1 Binary linear programming

Binary linear programming problems involve optimizing a linear function on binary variables subject to linear constraints. Thus, the general form is

where are integer coefficients, is an integer matrix, is the transpose of , and is an integer column vector.

An example of this type of problem could be the following:

Binary linear programming (also known as zero-one linear programming) is -hard. In fact, the decision version in which the goal is to determine if there...

Summary

This chapter has been devoted to introducing two different mathematical frameworks, the Ising model and the QUBO formalism, which allow us to write combinatorial optimization problems in a way that we will later be able to use to find approximate solutions with the help of quantum computers. We started with some simple examples and worked our way up to some famous problems such as graph coloring and the Traveling Salesperson Problem.

In order to achieve that, we studied different techniques that find wider applications in the process of writing optimization problems for quantum computers. We saw, for example, how to use slack variables and how to replace constraints with penalty terms. We also learned how to transform integer variables into a series of binary ones.

After all that we have covered in this chapter, you are now prepared to write your own problems in the languages required by optimization algorithms that can run on quantum computers. The rest of the chapters in this...