Information processing device, arithmetic device, and information processing method
To efficiently search for a ground state of an Ising model and efficiently solve a combinatorial optimization problem. An information processing device represents an interaction relation of an Ising model as a complete bipartite graph in which N spins of a first spin group and N spins of a second spin group are connected to each other, stores an energy function in which an interaction between an i-th spin of the first spin group and a j (=i)-th spin of the second spin group is set such that the i-th spin of the first spin group and the j-th spin of the second spin group have the same value and searches for a ground state of the Ising model based on the energy function. The information processing device searches for the ground state by applying an algorithm of a simulated annealing method to the above-described energy function.
1. An information processing device comprising:
a storage unit configured to represent an interaction relation of an Ising model as a complete bipartite graph in which each of N spins of a first spin group and each of N spins of a second spin group are connected to each other and to store an energy function in which an interaction between an i-th spin of the first spin group and a j (=i)-th spin of the second spin group is set such that the i-th spin of the first spin group and the j-th spin of the second spin group have the same value; and
a ground state searching unit configured to search for a ground state of the Ising model based on the energy function.
2. The information processing device according to claim 1 , wherein a total number of spins of each of the first spin group and the second spin group is set to be N, a value of the i-th spin of the first spin group in a ground state is set to be S i (i=1 to N), a value of the j-th spin of the second spin group in a ground state is set to be S i (j=1 to N), an interaction coefficient between the i-th spin of the first spin group and the j-th spin of the second spin group is set to be J i,j , an interaction coefficient between the i-th spin of the first spin group and the j (=i)-th spin of the second spin group is set to be w i , and the interaction coefficient J i,j is set to satisfy the following expression,
w
i
≥
1
2
(
1
-
1
N
)
∑
j
=
1
N
J
i
,
j
or the following expression,
w
i
≥
-
λ
2
which is given by a minimum fixed value λ of a matrix in which an element of an i row and a j column is J i,j and there is no diagonal component.
3. The information processing device according to claim 2 , wherein the ground state searching unit
searches for the ground state of the Ising model according to an algorithm of a simulated annealing method,
obtains an acceptance probability (transition probability) P(σ,σ′) of a state transition at a temperature T which is a parameter representing ease of a transition between states in the searching from the following expression based on a Metropolis method,
P
(
σ
,
σ
′
)
=
min
{
1
,
exp
(
-
H
(
σ
′
)
-
H
(
σ
)
T
)
}
in a case where values of the spins of the first spin group are represented by σ L 1 , . . . , and σ L N and values of the spins of the second spin group are represented by σ R 1 , . . . , and σ R N , obtains a differential ΔH of an energy H at the time of reversing the value σ R i of the i-th spin of the second spin group from the following expression,
Δ
H
=
2
σ
i
R
(
w
i
σ
i
L
+
∑
k
≠
i
J
i
,
k
σ
k
L
)
obtains a differential ΔH of an energy H at the time of reversing the value σ L i of the i-th spin of the first spin group from the following expression, and
Δ
H
=
2
σ
i
L
(
w
i
σ
i
R
+
∑
k
≠
i
J
i
,
k
σ
k
R
)
determines a condition that the state transition is accepted in a case where u (0<u≤1) is set to a uniform random number, based on the following expression
Δ H≤−T ·ln( u ).
4. The information processing device according to claim 3 , wherein the ground state searching unit
obtains a next state of the second spin group by the following expression, and
[
σ
1
R
⋮
σ
n
R
]
←
sign
(
2
J
[
σ
1
L
⋮
σ
n
L
]
+
2
[
w
i
O
⋮
⋱
⋮
O
w
n
]
[
σ
1
L
⋮
σ
n
L
]
+
T
[
ln
u
1
O
⋮
⋱
⋮
O
ln
u
n
]
[
σ
1
R
⋮
σ
n
R
]
)
obtains a next state of the first spin group by the following expression.
[
σ
1
L
⋮
σ
n
L
]
←
sign
(
2
J
[
σ
1
R
⋮
σ
n
R
]
+
2
[
w
i
O
⋮
⋱
⋮
O
w
n
]
[
σ
1
R
⋮
σ
n
R
]
+
T
[
ln
u
1
O
⋮
⋱
⋮
O
ln
u
n
]
[
σ
1
L
⋮
σ
n
L
]
)
.
5. The information processing device according to claim 4 , further comprising:
one or more arithmetic devices each of which includes
an adjacent matrix memory that stores the interaction coefficient J i,j ,
a first spin memory that stores the values σ L 1 , . . . , and σ L N of the spins of the first spin group,
a second spin memory that stores the values σ R 1 , . . . , and σ R N of the spins of the second spin group,
a product-sum arithmetic device to which the values of the first spin memory or the values of the second spin memory, the values of the adjacent matrix memory, and a signal indicating an N-dimensional vector w=(w 1 , . . . , and w N ) are input,
a vector multiplier to which the values of the first spin memory or the values of the second spin memory, and an N-dimensional vector in which elements are random numbers being independent of each other is input, and
a comparator to which the N-dimensional vector output from the product-sum arithmetic device and the N-dimensional vector output from the vector multiplier are input and which compares corresponding elements of the input N-dimensional vectors with each other and outputs a magnitude relation between the elements.
6. An arithmetic device according to claim 5 , further comprising:
the adjacent matrix memory;
the first spin memory;
the second spin memory;
the product-sum arithmetic device;
the vector multiplier; and
the comparator.
7. The arithmetic device according to claim 6 , wherein the arithmetic device is realized by any one of a complementary metal oxide semiconductor (CMOS) circuit, a field programmable gate array (FPGA), and an application specific integrated circuit (ASIC).
8. An information processing method comprising:
causing an information processing device to represent an interaction relation of an Ising model as a complete bipartite graph in which each of N spins of a first spin group and each of N spins of a second spin group are connected to each other and to store an energy function in which an interaction between an i-th spin of the first spin group and a j (=I)-th spin of the second spin group is set such that the i-th spin of the first spin group and the j-th spin of the second spin group have the same value; and
causing the information processing device to search for a ground state of the Ising model based on the energy function.
9. The information processing method according to claim 8 , wherein a total number of spins of each of the first spin group and the second spin group is set to be N, a value of the i-th spin of the first spin group in a ground state is set to be S i (i=1 to N), a value of the j-th spin of the second spin group in a ground state is set to be S j (j=1 to N), an interaction coefficient between the i-th spin of the first spin group and the j-th spin of the second spin group is set to be J i,j , an interaction coefficient between the i-th spin of the first spin group and the j (=i)-th spin of the second spin group is set to be w i , and the interaction coefficient J i,j is set to satisfy the following expression,
w
i
≥
1
2
(
1
-
1
N
)
∑
j
=
1
N
J
i
,
j
or the following expression,
w
i
≥
-
λ
2
which is given by a minimum fixed value λ of a matrix in which an element of an i row and a j column is J i,j and there is no diagonal component.
10. The information processing method according to claim 9 , wherein the information processing device
searches for the ground state of the Ising model according to an algorithm of a simulated annealing method,
obtains an acceptance probability (transition probability) P(σ,σ′) of a state transition at a temperature T which is a parameter representing ease of a transition between states in the searching from the following expression based on a Metropolis method,
P
(
σ
,
σ
′
)
=
min
{
1
,
exp
(
-
H
(
σ
′
)
-
H
(
σ
)
T
)
}
in a case where values of the spins of the first spin group are represented by σ L 1 , . . . , and σ L N and values of the spins of the second spin group are represented by σ R 1 , . . . , and σ R N , obtains a differential ΔH of an energy H at the time of reversing the value σ R i of the i-th spin of the second spin group from the following expression,
Δ
H
=
2
σ
i
R
(
w
i
σ
i
L
+
∑
k
≠
i
J
i
,
k
σ
k
L
)
obtains a differential ΔH of an energy H at the time of reversing the value σ L i of the i-th spin of the first spin group from the following expression, and
Δ
H
=
2
σ
i
L
(
w
i
σ
i
R
+
∑
k
≠
i
J
i
,
k
σ
k
R
)
determines a condition in which the state transition is accepted in a case where u (0<u≤1) is set to a uniform random number, based on the following expression
Δ H≤−T ·ln( u ).
11. The information processing method according to claim 10 , wherein the information processing device
obtains a next state of the second spin group by the following expression, and
[
σ
1
R
⋮
σ
n
R
]
←
sign
(
2
J
[
σ
1
L
⋮
σ
n
L
]
+
2
[
w
i
O
⋮
⋱
⋮
O
w
n
]
[
σ
1
L
⋮
σ
n
L
]
+
T
[
ln
u
1
O
⋮
⋱
⋮
O
ln
u
n
]
[
σ
1
R
⋮
σ
n
R
]
)
obtains a next state of the first spin group by the following expression
[
σ
1
L
⋮
σ
n
L
]
←
sign
(
2
J
[
σ
1
R
⋮
σ
n
R
]
+
2
[
w
i
O
⋮
⋱
⋮
O
w
n
]
[
σ
1
R
⋮
σ
n
R
]
+
T
[
ln
u
1
O
⋮
⋱
⋮
O
ln
u
n
]
[
σ
1
L
⋮
σ
n
L
]
)
.