Chapter 3: Annealing Machines, Quadratic Expressions, and Discrete Values

Section 2: Annealing machines are for Quadratic problems

As mentioned in the previous section, linear (first-order) optimization problems can be easily solved by many methods. In contrast, the quadratic (second-order) optimization problem is considered to be efficiently solved by an annealing machine. As explained in Section 1, a quadratic equation is one in which two variables are multiplied by a term. For example, in the formulation of image noise reduction explained in Chapter 1, there is a term $s_is_j$ or $h_is_i$ multiplied by $s_i$ and $s_j$, so it is quadratic. So what effect does this $s_is_j$ give us with the annealing machine?

In Chapter 1, we learned about finding the state of $s_i$ (spin) with the lowest energy by annealing. At this time, if there were only a so-called first-order term, $a_is_i$ (where $a_i$ is a coefficient), the cost function would be lower if $s_i$ is $−1$ if the coefficient is positive. On the other hand, if the coefficient is negative, the cost function is lower when $s_i$ is $+1$. In other words, since the coefficients are fixed for the first-order terms, the coefficients are optimal depending on the value of $s_i$ ($+1$ or $-1$). On the other hand, in the second-order term $a_{ij}s_is_j$, the energy will be negative (lower) if the coefficient $a_{ij}$ is positive and $s_is_j$ is negative. There are two patterns where $s_is_j$ becomes negative: when $s_i$ is positive and $s_j$ is negative, or when $s_i$ is negative and $s_j$ is positive. Conversely, if the coefficient $a_{ij}$ is negative, the energy is negative when $s_is_j$ is positive, so in this case the optimal solution is when $s_i$ is positive and $s_j$ is positive or $s_i$ is negative and $s_j$ is negative (as explained in the Ising model). In summary, if there is a second-order term $a_{ij}s_is_j$, the pair $s_i$ and $s_j$ will have lower or higher energy, i.e., be an optimal solution or not, depending on the partner. This is very tricky when determining the value of $s_i$. If the other party's $s_j$ does not determine the state of $s_i$, it does not know which value will be optimal, so it is a sort of "standoff." Therefore, it is difficult to solve this problem using the conventional method because it requires a very long time to simulate the second-order terms by brute force.

Related Articles

What is a combinatorial optimization problem?

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.

Optimization of researcher shifts with consideration for COVID-19 infection control

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.

Optimize an insurer's reinsurance portfolio

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.

Easy-to-learn optimization flow

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