This tutorial explains the processing of the annealing machine in the demonstration application "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.
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.
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.
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.