Ising editor

This tutorial explains the processing of the annealing machine in the demonstration application "Ising editor

How to use the Ising editor

In the Ising editor, you can execute an annealing process by directly entering the Ising model.

The lattice-like figure on the right side of the screen shows the graph structure of the Ising model which can be expressed by CMOS annealing machine. This is a graph structure called King's Graph, except for the spin at the end, each spin can interact with a total of 8 directions spinning up and down, left and right, and diagonal.

In the tutorial "what is Ising model?", the following Hamiltonian of Ising model is listed, but $E$ in the part written as $(i,j)∈E$ in this expression becomes a set of edges which make up King's graph.

$$ E (\lbrace s _i \rbrace) = \sum _ { i \in V } h _ { i } s _ { i } + \sum _ { ( i , j ) \in E } J _ { i j } s _ { i } s _ { j } $$

To enter the Ising model in the Ising editor, first select the value you want to set as a factor in the "Set value". Next, clicking the edge on the graph allows you to set the interaction coefficient $J_{ij}$ on the selected edge. By clicking the vertex, you can also set the external magnetic field coefficient of the spin corresponding to that vertex. Here, if the interaction coefficient value is set to 0, there is no interaction between the spins. This is same as not connecting spins on the graph.

Move the mouse cursor over an edge or vertex on the graph to display the interaction coefficient and the external magnetic field coefficient. If there is no external magnetic field, the coefficients will not be displayed.

When processing is completed, the spin value obtained as a result of annealing is displayed in the form of up and down arrows. The upward arrow corresponds to the spin value +1, and the downward arrow corresponds to the spin value -1. Annealing results can be obtained separately for the number of times specified by the number of annealing in the "Set parameters". You can check the result of each annealing by moving the slider on the graph.

By clicking "Advanced" in "Set parameters", you can set parameters called Annealing scheduler. This is described in detail below.

Explanation on temperature schedule related to Ising editor

The CMOS annealing machine is a computer specialized in computation of so-called ground state search of the Ising model.
Therefore, when using an annealing machine, it is necessary to input parameters such as an interaction coefficient and an external magnetic field coefficient for describing the Ising model for which a ground state search is to be performed.
However, when actually calculating, you need to input parameters for controlling the time required for calculation and the accuracy of the solution at the same time. This tutorial will explain these parameters.

Various algorithms can be used to perform the ground state search of the Ising model, but in CMOS annealing machines, calculations are done based on the idea of ​​annealing (especially simulated annealing) as indicated by name.
In annealing, calculations are started from the initial state where the initial value of spin is appropriately determined, and repeat the operation of updating the spin value at each step.
Since the ground state is the spin state where the energy of the whole Ising model is the lowest, when updating the spin, calculate the next spin value so that the energy becomes low from the spin value to be updated and the spin around it.
However, since with this operation alone, energy is directed only downwards in the Ising model as a whole, the energy is trapped in the valley of the locally existing energy called local solution, making it difficult to explore the state where the energy is lower than that. Therefore, we will allow the energy to rise with a certain probability when updating the spin value in order to escape the local solution and search for a combination of spin values with lower energy.
However, if the probability of allowing energy to rise is too high, the total energy will never decrease, and conversely if the probability of allowing energy to rise is too low, it will be impossible to escape the local solution.
For this reason, it is important to properly determine this probability during annealing, which is a parameter when using the CMOS annealing machine mentioned at the beginning.

In simulated annealing, in order to control the probability of allowing energy to rise as described above, we generally use a parameter called temperature.
The higher the temperature, the more actively it accepts the rise in energy, the lower the temperature, the less acceptable it is; at temperature 0 it will never accept the rise of energy.
Here, we will refer to how the temperature changes during the calculation process as "temperature schedule". Normally, the temperature schedule is decided so that the temperature is raised at the start of calculation and gradually lowered. This is because at the start of calculation, the temperature is raised to search a wide range of solution space, and as the calculation progresses, it goes to a state of lower energy, so that it is easier to obtain a better solution by avoiding the local solution.
There are various ways of deciding the specific temperature schedule, but in the CMOS annealing machine, we use a cooling schedule called "geometric cooling". This is widely used in a simple way to start from a certain initial temperature and update the spin value by using a predetermined number of steps, then multiply the current temperature value by a factor of less than 1 to lower the temperature.

In order to determine the cooling schedule based on geometric cooling, the CMOS annealing machine of this site uses the following four parameters.

• Initial temperature: Temperature at the start of annealing
• Final temperature: Temperature at the end of annealing
• Step length: Number of updates of spin until updating temperature value
• Number of steps: Number of updates of temperature from initial temperature to final temperature

The cooling coefficient described before is calculated based on four parameter values.

In general, it is easier to obtain a better solution by increasing the number of steps and making the annealing time longer, but this will also increase the required time.
Also, because the appropriate annealing schedule differs depending on the target Ising model coefficient value, it is also effective to trial and error to some extent.