Experience the CMOS Annealing Machine

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.

  1. Home
  2. Tutorials
  3. Building network robustness

Building network robustness

This tutorial explains the processing of the annealing machine in the demonstration application building network robustness

Overview

Taking the vertex cover problem for graphs as an example, let's consider solving combinatorial optimization problem with an annealing machine.

Consider the situation where the server is connected with the network (green line in the figure) as shown below. Under these circumstances, we will apply security measures to the server. It is best to apply the same measures to all servers in the same way, but it costs more, so we want to reduce the number to as few as possible. Therefore, we decide to select a server so that there is a countermeasure server at least next to even unprotected servers. The part surrounded by blue circles in the figure is an example of such a combination.

In this way, a subset of vertices where at least one vertex is included regardless of which side in the graph is taken is called "vertex cover". There are many combinations of vertex covers, but the one with the smallest number of vertices among them is particularly called the min vertex cover.

The problem this time is finding the minimum vertex cover.

Create a cost function

In this problem, we correspond "included" or "not included" in the cover for each vertex of the graph to the spin value -1 or +1 of CMOS annealing machine. In order to obtain the minimum vertex cover, the following two conditions must be met.

  • (a) The spin to be +1 (the vertex included in the vertex cover) should be as small as possible.
  • (b) The vertices on both sides of each side of the graph must not be -1.

The cost function for (a) is as follows.

$$ \tag*{Equation(1)} \sum_{i \in V}s_i $$

Here $V$ is the set of all the vertices of the input graph. For (b), we call $s_i$ , $s_j$ for the spins corresponding to the vertices on both sides of the edge. At this time, you can think of a function that cost is high only when it is -1, and it is the same cost in all other cases, but since it is hard to think as it is, think variables $x_i$ or $x_j$ which takes binary values 0 or 1 instead of $s$. At this time, if included in the vertex cover, the value of $x_i$, $x_j$ will be 1, otherwise it will be 0. In this case, it is only necessary to increase the cost only when $x_i$ and $x_j$ are both 0.

$$ \tag*{Equation(2)} (1−x_i)(1-x_j) $$

Considering the cost function of above, the value of the expression is 1 only when both $x_i$ and $x_j$ are 0, otherwise it is 0, so the desired condition is satisfied.
Since it is a spin that takes a value of ±1 only on an annealing machine, you need to convert equation (2). Because $s_i$ , $s_j$ also $x_i$, $x_j$ takes only binary values, they can be converted to each other by the following expression.

$$ x_i=\frac{s_i+1}2 $$

Substituting this into equation (2) and rearranging it will give the following form.

$$ \tag*{Equation(3)} −s_i−s_j+s_i s_j $$

By the way, in equation (3), the total coefficient of 1/4 was dropped, which is equivalent to changing the energy scale (unit). At this time, the constant term does not affect the combination of the spin values giving the ground state, so we ignore it.
When equation (3) is added to all sides of the input graph, it becomes as follows.

$$ \tag*{Equation(4)} \sum_{(i,j)\in E}(-s_i-s_j+s_is_j) $$

However, $E$ is a set of all sides of the input graph.
By adding equation (1) and equation (4), the following cost function corresponding to the vertex cover problem can be obtained.

$$ H(s)=\eta\sum_{i \in V}s_i+\sum_{(i,j)\in E}(-s_i-s_j+s_is_j) $$

$ s_i \in \{\pm1\} $: Spin value. $+ 1$ when the vertex i of the input graph is included in the vertex cover.

We introduced the parameter ($\eta$>0) before the first term. This is to adjust the strength of the two conditions.
If $\eta=0$, the cost function is only the second term. In this case, there is no effect of suppressing the number of vertices included in the vertex cover. Conversely, if $\eta$ is made very large, it is practically only the first term, so the cost function is minimized when the number of vertices in the vertex cover is zero.
In the demo of this site, it is $\eta=1$.

Share/Feedback

Comment