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.
