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