The Ising model is the simplest model in the field of "statistical mechanics". It is a model that expresses what kind of behavior as a whole (macro) when an enormous number of microelements interact with each other and when a force is given to each microelement. The micro element in the Ising model is called spin and takes two values of ±1. The Ising model is defined on an undirected graph $G=(V,E)$. Here $V$ is a set of vertices, $E$ is a set of edges. The spin variable exists on the vertex and it is expressed as $s_i$. That means $s_i=±1$.

$s _ { i } = \pm 1$

In order to use an annealing machine, it is necessary to **express cost function of
combinatorial optimization problem and constraint condition by Hamiltonian (energy function) of
Ising model**.

The energy function is given as follows.

Here, $h_i$ is a magnetic field that applied to the site $i \in V$, $J_{ij}$ is a interaction that applied to the site $i \in V$ and $j \in V ( ( i , j ) \in E )$. In terms of physics, the minimum state of energy $E({s_i})$ is called a stable state.

Let's consider a case where there is only one spin.

At this time, the energy function is given as

The energy value according to the value of $s_1$ is as follows.

Spin state | Energy value |
---|---|

$s_1=+1$ | $h_1$ |

$s_1=-1$ | $-h_1$ |

When $h_1>0$, $s_1=-1$ is stable. Conversely, when $h_1<0$, $s_1=+1$ is stable.

Let's consider a case where there are only two spins. Here we assume only the interaction is working between the two spins.

At this time, the energy function is given as

The energy value according to the value of $s_1$ and $s_2$ is as follows.

Spin state | Energy value | |
---|---|---|

$s_1=+1$ | $s_2=+1$ | $J_12$ |

$s_1=+1$ | $s_2=-1$ | $-J_12$ |

$s_1=-1$ | $s_2=+1$ | $-J_12$ |

$s_1=-1$ | $s_2=-1$ | $J_12$ |

When $J_12>0$, $s_1≠s_2$ is stable. Conversely, when $J_12<0$, $s_1=s_2$is stable.

Let's consider a case where there are only two spins. Here we assume not only the interaction is working between the two spins but also a magnetic field is applied to each spin.

At this time, the energy function is given as

The energy value according to the value of $s_1$ and $s_2$ is as follows.

Spin state | Energy value | |
---|---|---|

$s_1=+1$ | $s_2=+1$ | $J_12+h_1+h_2$ |

$s_1=+1$ | $s_2=-1$ | $-J_12+h_1-h_2$ |

$s_1=-1$ | $s_2=+1$ | $-J_12-h_1+h_2$ |

$s_1=-1$ | $s_2=-1$ | $J_12-h_1-h_2$ |

The stable state will change according to the value of $J_12, h_1, h_2$. For example, when $J_12=1, h_1=-2, h_2=3$, $s_1=+1, s_2=-1$ is stable.

Finally, let's consider the case where there are only four spins. See the case like the figure.

Here we assume the interaction is working between $s_1,s_2$, $s_2,s_3$, and $s_3,s_4$ and a magnetic field is applied to only $s_1$ and $s_4$.

At this time, the energy function is

The energy value according to the value of $s_1,s_2,s_3,s_4$ is as follows.

Spin state | Energy value | |||
---|---|---|---|---|

$s_1=+1$ | $s_2=+1$ | $s_3=+1$ | $s_4=+1$ | $J_12+J_23+J_34+h_1+h_4$ |

$s_1=+1$ | $s_2=+1$ | $s_3=+1$ | $s_4=-1$ | $J_12+J_23-J_34+h_1-h_4$ |

$s_1=+1$ | $s_2=+1$ | $s_3=-1$ | $s_4=+1$ | $J_12-J_23-J_34+h_1+h_4$ |

$s_1=+1$ | $s_2=+1$ | $s_3=-1$ | $s_4=-1$ | $ J_12+J_23+J_34+h_1-h_4$ |

$s_1=+1$ | $s_2=-1$ | $s_3=+1$ | $s_4=+1$ | $-J_12-J_23+J_34+h_1+h_4$ |

$s_1=+1$ | $s_2=-1$ | $s_3=+1$ | $s_4=-1$ | $-J_12-J_23-J_34+h_1-h_4$ |

$s_1=+1$ | $s_2=-1$ | $s_3=-1$ | $s_4=+1$ | $-J_12+J_23-J_34+h_1+h_4$ |

$s_1=+1$ | $s_2=-1$ | $s_3=-1$ | $s_4=-1$ | $-J_12+J_23+J_34+h_1-h_4$ |

$s_1=-1$ | $s_2=+1$ | $s_3=+1$ | $s_4=+1$ | $-J_12+J_23+J_34-h_1+h_4$ |

$s_1=-1$ | $s_2=+1$ | $s_3=+1$ | $s_4=-1$ | $-J_12+J_23-J_34-h_1-h_4$ |

$s_1=-1$ | $s_2=+1$ | $s_3=-1$ | $s_4=+1$ | $-J_12-J_23-J_34-h_1+h_4$ |

$s_1=-1$ | $s_2=+1$ | $s_3=-1$ | $s_4=-1$ | $-J_12-J_23+J_34-h_1-h_4$ |

$s_1=-1$ | $s_2=-1$ | $s_3=+1$ | $s_4=+1$ | $J_12-J_23+J_34-h_1+h_4$ |

$s_1=-1$ | $s_2=-1$ | $s_3=+1$ | $s_4=-1$ | $J_12-J_23-J_34-h_1-h_4$ |

$s_1=-1$ | $s_2=-1$ | $s_3=-1$ | $s_4=+1$ | $J_12+J_23-J_34-h_1+h_4$ |

$s_1=-1$ | $s_2=-1$ | $s_3=-1$ | $s_4=-1$ | $J_12+J_23+J_34-h_1-h_4$ |

The stable state will change according to the value of $J_12, J_23, J_34, h_1, h_4$. For example, when $J_12=1, J_23=3, J_34=-1, h_1=2, h_4=3$, $s_1=-1, s_2=+1, s_3=-1, s_4=-1$ is stable.

This article is part of the ACW Skills Roadmap. Use the skills roadmap to learn with ACW.

Did you find the article helpful? Please share it with others.

If you want to know specific examples of solving
combinatorial optimization problems with 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.

If you want to know how to use an annealing machine

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.