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