This site uses cookies to provide services for the purpose of improving customer convenience, such as browsing
behavior,
and to improve the quality of content through access analysis. Cookies do not store personally identifiable
information, but you can set your browser to refuse to accept them. However, please note that if you refuse to
accept cookies, you may lose some browser functions and settings. Our site rules and regulations are described
in our Privacy Policy. You must agree to the use of cookies to browse the site.

Section 2: Annealing machines are a technology for second-order problems.

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.