Experience the CMOS Annealing Machine

# Solve number partitioning problems with Ising Editor!

### Overview

EXECUTING CMOS ANNEALING MACHINE explains how to divide four numbers with a CMOS annealing machine from the WEB-API, but the same thing can be accomplished with the Ising Editor. The Ising Editor is a learning tool that provides a visual representation of the CMOS annealing machine in action, but it also doubles as a unique tool for visually seeing what to input to the CMOS annealing machine and how to obtain a solution.

• Intended audiencePeople who want to understand a little more about annealing machine processing before executing an annealing machine with WEB-API, and people who want to understand annealing machine processing without executing it themselves.

### Prepare data (interactions) to be input into the Ising Editor An Ising Editor value is a value assigned to a vertex or edge. A vertex in the Ising model is a spin variable that takes $s=±1;$ whether it is $+1$ or $-1$ is indicated by the result obtained by annealing. The value of the input to the vertex is the external magnetic field coefficient $h_i$. The external magnetic field coefficient $h_i$ represents the first order term in the cost function. Since there is no first-order term in the cost function of the problem we are solving, there is no value to be entered as the external magnetic field $h_i$.

On the other hand, the value to be entered as an edge is the interaction. Interactions are essential input data for an annealing machine.

In the Ising Editor, the values that can be entered are limited to $-3, -2, -1, 0, 1, 2,$ and $3$. Therefore, both the interaction and the external magnetic field must be entered within these ranges.

STEP UP

When running this project from the WEB-API, you can set the variables from a wider array of values. It depends on the machine type; for Executing CMOS annealing machine, we use type3

• type3: -2147483648 <= p <=2147483647
• type4: -3.402823e+38 <=p <=3.402823e+38
• type5: -7 <=p <=7

*p denotes the coefficient

Now we will prepare values that satisfy the cost function of the Ising model and the specifications of the Ising Editor. First, the following equation was established as the Ising model for the cost function of the number partitioning problem. In this problem, $a_ia_j$ is the interaction (input data preparation). Let us now determine the number of divisions to be made. The interaction constraint is $-3 ≤ a_i a_j ≤ 3$ ($a_i a_j$ is an integer), so here we calculate all the interactions for splitting the four numbers $(a_1,a_2,a_3,a_4)=(-1,-1,1,2)$. Divide them into two groups so that the sums are as equal as possible, there should be a group with a total of 1 and a group with a total of $0$. We can also assume what would happen if the results were bad. If the total is divided into two groups of $3$ and $-2$, respectively. First, name the elements as follows, and then use the diagram to determine which interactions should be placed where in the Ising Editor. You can see that the lattice Ising editor allows you to enter interactions for all four number divisions; there are six of them. Each interaction of $J_{12}, J_{13}, ...$ is as follows. Enter the ising editor with that arrangement. It will look like the following Here we see that if we had chosen two or more 2s or 3s at the same time for the number to be divided, we would need 4s, 6s, or 9s as interactions, so we would not be able to enter them.

STEP UP

Common mistake: wouldn't you enter the number of vertices you want to divide in the Ising Editor?

The input to the vertex is the coefficient $h_i$, the external magnetic field coefficient, not the number you want to divide. If the cost function has a first order term (= only one term with $\sigma$ instead of two), this coefficient is the external magnetic field coefficient. In the cost function of a number-splitting problem, there is only a term of the second order (= two terms multiplied by two $\sigma$). Therefore, it is correct to enter nothing at the Ising Editor vertices. As an example, the cost function below has an external magnetic field coefficient of 3. Frequently Asked Questions: Why did you arrange the grid without entering the number of divisions needed in the Ising Editor?

That is because the placement of the interaction coefficients is important. Interactions are meaningless unless they are aligned not only in value but also in position. If the values are the same but the positions are lousy, the assumption that it is the number you want to divide is broken. ### Execution

Press the Run button.
The OUTPUT window will show the orientation of the spins. It means that spins with the same orientation will be in the same group. The above case is divided into $(-1,2)$ and $(-1,1)$. The numbers sum to $1$ and $0$, respectively.

After that, you can press the Run button as many times as you like, sometimes exactly the same as the first time. In the above case, the position has changed, but the two $-1$'s have just been exchanged. The sum of the numbers is $1$ and $0$ respectively. In the above case, it was divided into 1 and 3. The total is only $1$ for the upward ↑ group and $(-1,-1,2)$ for the downward ↓ group, so their sum is $0$.

Interesting, there are some like this. All of them are now in a downward group. The total is $1$ because $(-1,-1,1,2)$, and the other group has no elements, so the total is $0$. The other group has no elements, so the sum is 0. No matter how many times I run it, the total is never split between $3$ and $-2$. It appears that we have successfully optimized the system.

### What happens if I put in the wrong value?

Even if the wrong value is entered, the execution process will still be performed. In other words, if you enter a different value for the edge than the value obtained by multiplying the number of values you want to divide by, you will not get an error, and the spin will be determined and OUTPUT for the time being. In that case, however, the direction of the spin is meaningless. It is important to input the exact value in order to obtain a solution.

STEP UP

Demo App: Hidden Conditions for Solving Network Robustness Construction with Ising Editor

Building network robustness of the demo application can be viewed in the Ising Editor to view the problem setup and optimization process. Can any physical network challenge be solved with the Ising Editor? Or is there some secret that is exclusive to the Network Robustness app?

Actually, there are two secrets. First, there is a hidden condition that should be called the "secret of obtaining the optimal solution"; this condition works with Annealing Cloud Web's CMOS annealing machine, not with the Ising Editor. Another thing to note: not all network optimization problems can be solved with a CMOS annealing machine. Moving ahead, in this demo application, no matter how many servers are installed, each server is only connected with up to 4 other servers. The CMOS annealing machine running on the Annealing Cloud Web performs optimization processing using a lattice-like (also known as a King's graph, a structure in which one spin is connected to eight spins) Ising model. The optimization process is performed on an Ising model of the lattice.Therefore, although the limitation on the number of servers that can be connected is not taken into account in the formulation, it is possible to run this application that derives the optimal solution from a network that connects four vertices, which is less than eight. In addition, the specification to connect only to 4 servers is realized as an application specification.

Another secret answers the question of why the network robustness optimization process can be performed by the Ising Editor, which is even more constrained than the Annealing Cloud Web annealing machine. The interaction coefficient for network robustness construction is only 1 in this case. The Ising Editor can be populated with any value in the range -3 to 3.

### Summary

• The solution obtained by the optimization process of the annealing machine is a combination of which spins are upward or downward.
• The Ising Editor can solve the Ising model problem by entering spin external field coefficients and interaction coefficients between -3 and 3.
• The solution (spin direction) that emerges from each run is different, but the energies are all minimal, indicating that an optimal solution* is obtained.
*Inherently, only the optimal solution is not always derived, and this result shows only the optimal solution due to the small size of the problem.
• If you put in the wrong input data, it will not return an error.