An annealing machine is a technique for solving combinatorial optimization problems through a mechanism in which the ground state of the Ising model (the state with the lowest energy) gives the optimal solution by setting preconditions that result in the optimal solution. To use an annealing machine, the problem must first be formulated as an Ising model.
In doing so, we need to understand what kind of Ising model structure the annealing machine we use is based on. Alternatively, the machine must be selected based on whether it is an annealing machine that can solve the problem you want to solve.
In this column, divided into the first and second parts, we will explain the structure of the model, which needs to be considered in the formulation and stage of selecting an annealing machine. The first part explains how to apply the Ising model to the problem to be solved (mathematical logic), and the second part explains the specifications of the annealing machine (implementation specifications).
When selecting an annealing machine, "sparsely connected" and "fully connected" must be considered. The Ising model takes the form of a graph in which elements (vertices) called spins are joined by interactions (edges). The term "connection" refers to whether the spins of the Ising model are connected or not. In terms of the cost function equation, if there is a product of one spin and another spin, then the spins are "interacting," that is, "the spins are connected."
Image of sparsely and fully connected
In the formulation, we formulated the number partitioning problem and derived the cost function $H = \sum(a_ia_j\sigma_i\sigma_j)$. This formula implies that all of the different elements must be multiplied together. We have seen that this is fully connected and that the number of interactions increases by $O(n^2)$ because $n(n-1)/2$ interactions must be entered for n number of elements. At this point, based on the number of interactions, we can determine if we can input them into the annealing machine.
Other problems that can be considered as fully connected problems include the problem of creating a timetable and the problem of creating a portfolio of stocks in the field of finance. For example, we discussed a timetable problem in the "organizing problems and defining requirements" , the relationship in which teachers of subjects are to be included in each class frame is considered in relation to the other frames. Also, in the portfolio creation problem, it is a fully connected problem because of the interrelationships that enter between all stock issues.
The fact that there is only interaction between some of the spins in the Ising model is called sparsely connected. So what exactly is the sparsely connected problem?
In signal control optimization, we assign a binary value to the spin of whether a signal placed on a grid street is red or blue. (The exact definition is $+1$ for a vertical signal to be blue and $-1$ for a horizontal signal to be blue.)
Since those intersections are connected to each other only by vertical and horizontal roads, one spin is connected to only a limited number of spins representing neighboring intersections, so the relationship can be expressed by sparse coupling. Even if the grid of roads extends infinitely, the number of interactions required is no more than $2n$, as the number of intersection increases by $n$, since we know that for each additional intersection, there are two more adjacent roads. Even with 10 vertical x 10 horizontal = 100 intersections, the number of interactions is less than 200. In the number partitioning problem, 4,950 interactions are needed to split 100 numbers, so you can see how the structure of the Ising model makes a big difference.
Now, if some spins are connected on the cost function, but the corresponding spins are not connected (sparsely connected) on the Ising model used to implement the annealing machine, the problem cannot be solved as it is. In the following paragraphs, we will discuss some clues to determine the network structure of the Ising model when the need to optimize a particular problem arises.
The fact that the number partitioning problems was solved by squaring the entire relational equation to obtain the product of all terms (i.e., the Ising model of all couplings with interactions among all spins) indicates that the fully connected Ising model is found in the connection among conceptual elements, i.e., variables. In such cases, the timing of the decision to determine that the structure of the Ising model is fully connected is in the middle of the formulation. Specifically, in the case of the number partitioning problem, it is "the time to make the energy function of the Ising model after the formulation of the relation.
On the other hand, in the case of the signal control problem, the fact that the decision to adopt a sparsely connected Ising model is made when the shape of the road is given as the problem, means that the sparsely connected Ising model is based on the connection of physical events such as grid roads. In other words, given the problem of optimizing signal control on a grid road, it is a good fit with the sparsely connected Ising model.
We hope that you have now understood that there are differences in the structure of the Ising model depending on the problem. Although an annealing machine can dramatically reduce the time to obtain the optimal solution if only the Ising model can be used, the fact that there are differences in the form of the Ising model chosen for different problems is one of the items that should be considered to the maximum extent possible.
In the future, when using an annealing machine as a combinatorial optimization problem for new tasks, be aware of what structure of Ising model is chosen. Having that perspective is the first step in the attempt to use an annealing machine.
Combinatorial optimization will be explained by using two easy-to-understand examples of familiar combinatorial optimization problems. The importance of finding and using fast solution methods for combinatorial optimization processes in an IoT society will also be discussed.
In the wake of the COVID-19 epidemic, we present a use case in which an annealing machine is used to create shifts for researchers under constraints that take into account the risk of infection.
This article presents a use case in which an annealing machine is used to formulate a reinsurance portfolio that leverages the vast amount of data held by an insurance company to address natural catastrophe risks.
For beginners, this article explains the procedures and key points of the process of solving optimization problems with an annealing machine. The process involves dividing the problem into four stages: "organizing problem and defining problem," "formulation," "input data preparation," and "executing CMOS annealing machine".
This article provides an easy-to-understand explanation of the mathematical assumptions you need to understand, focusing on "quadratic" and "discrete," which are some of the characteristics of the problems that annealing machines excel at solving.