Information processing apparatus, arithmetic device, and information processing method
Searching for a ground state of an Ising model is performed so that a combinatorial optimization problem is efficiently solved. An information processing apparatus stores an energy function setting an interaction between an i-th spin of a first spin group and a j-th spin of a second spin group so that the i-th spin of the first spin group and the j-th spin of the second spin group have the same value in a ground state in an interaction relationship of an Ising model represented as a complete bipartite graph connecting N spins of the first spin group and of the second spin group, and searches for the ground state of the Ising model based on the energy function and information unique to the spins. The search for the ground state of the Ising model is performed by applying an algorithm of simulated annealing method to the above-mentioned energy function.
1. An information processing apparatus comprising:
a storage unit which stores an energy function setting an interaction between an i-th spin of a first spin group and a j-th spin of a second spin group so that the i-th spin of the first spin group and the i-th spin of the second spin group have the same value in a ground state in an interaction relationship of an Ising model represented as a complete bipartite graph connecting N spins of the first spin group and N spins of the second spin group; and
a ground state searching unit which searches for the ground state of the Ising model based on the energy function and information unique to the spins,
wherein when the total number of spins of each of the first spin group and the second spin group is defined as 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 defined as J i,j , and an interaction coefficient between the i-th spin of the first spin group and the i-th spin of the second spin group is defined as w i , and
wherein the interaction coefficient w i is set to satisfy the following Formula given by a minimum eigenvalue λ of a matrix in which elements of i-th rows and j-th columns are J i,j and diagonal components are 0 and any subset C of a spin array
[
Formula
1
]
w
i
≥
{
∑
v
j
∈
V
❘
"\[LeftBracketingBar]"
J
i
,
j
⌉
-
1
2
∑
v
j
∈
C
❘
"\[LeftBracketingBar]"
J
i
,
j
❘
"\[RightBracketingBar]"
(
v
j
∈
C
)
-
λ
2
(
v
j
∉
C
)
.
2. The information processing apparatus according to claim 1 ,
wherein the ground state searching unit:
searches for the ground state of the Ising model according to a simulated annealing algorithm,
obtains an acceptance probability (transition probability) P(σ, σ′) of state transition at a temperature T which is a parameter indicating easiness of transition between states from the following Formula based on a Metropolis method in the searching,
[
Formula
2
]
P
(
σ
,
σ
′
)
=
min
{
1
,
exp
(
-
H
(
σ
′
)
-
H
(
σ
)
T
)
}
when the values of the spins of the first spin group are expressed as σ L 1 , . . . , σ L N , and the values of the spins of the second spin group are expressed as σ R 1 , . . . , σ R N ,
obtains a difference ΔH of the energy H at the time when the value σ R i of the i-th spin of the second spin group is inverted from the following Formula, and
[
Formula
3
]
Δ
H
=
2
σ
i
R
(
h
i
+
w
i
σ
i
L
+
∑
k
≠
i
J
i
,
k
σ
k
L
)
obtains the difference ΔH of the energy H when the value σ L i of the i-th spin of the first spin group is inverted from the following Formula, and
[
Formula
4
]
Δ
H
=
2
σ
i
L
(
h
i
+
w
i
σ
i
R
+
∑
k
≠
i
J
i
,
k
σ
k
R
)
when u (0<u≤1) is a uniform random number, determines a condition for accepting the state transition based on the following Formula
Δ
H
≤
-
T
·
ln
(
u
)
.
[
Formula
5
]
3. The information processing apparatus according to claim 1 ,
wherein the ground state searching unit:
obtains a next state of the second spin group by the following Formula, and
[
Formula
6
]
[
σ
1
R
⋮
σ
n
R
]
←
sign
(
2
h
+
2
J
[
σ
1
L
⋮
σ
n
L
]
+
2
[
w
i
0
⋮
⋱
⋮
0
ω
n
]
[
σ
1
L
⋮
σ
n
L
]
+
T
[
ln
u
1
0
⋮
⋱
⋮
0
ln
u
n
]
[
σ
1
R
⋮
σ
n
R
]
)
obtains a next state of the first spin group by the following Formula
[
Formula
7
]
[
σ
1
L
⋮
σ
n
L
]
←
s
ign
(
2
h
+
2
J
[
σ
1
R
⋮
σ
n
R
]
+
2
[
w
i
0
⋮
⋱
⋮
0
w
n
]
[
σ
1
R
⋮
σ
n
R
]
+
T
[
ln
u
1
0
⋮
⋱
⋮
0
ln
u
n
]
[
σ
1
L
⋮
σ
n
L
]
)
.
4. The information processing apparatus according to claim 3 , comprising one or more arithmetic devices, the arithmetic device including:
an interaction coefficient memory which stores the interaction coefficients J i,j ;
an external magnetic field coefficient memory which stores the external magnetic field coefficient h i ;
a first spin memory which stores the values σ L 1 , . . . , σ R N of the spins in the first spin group;
a second spin memory which stores the values σ R 1 , . . . , σR R N of the spins in the second spin group;
a product-sum arithmetic device which is input with a signal representing the value of the first spin memory or the value of the second spin memory, the value of the interaction coefficient memory, the value of the external magnetic field coefficient memory, and an N-dimensional vector w=(W 1 , . . . , W N );
a vector multiplier which is input with the value of the first spin memory or the value of the second spin memory and the N-dimensional vector in which elements are random numbers independent of each other; and
a comparator which is input with the N-dimensional vector output from the product-sum arithmetic device and the N-dimensional vector output from the vector multiplier, compares the corresponding elements of the input N-dimensional vectors with each other, and outputs a magnitude relationship between the elements.
5. The arithmetic device according to claim 4 , comprising
the interaction coefficient memory, the external magnetic field coefficient memory, the first spin memory, the second spin memory, the product-sum arithmetic device, the vector multiplier, and the comparator.
6. The arithmetic device according to claim 5 ,
being implemented by any of a complementary metal oxide semiconductor (CMOS) circuit, a field programmable gate array (FPGA), and an (application specific integrated circuit (ASIC).
7. An information processing method of executing steps of:
allowing an information processing apparatus to store an energy function setting an interaction between an i-th spin of a first spin group and a j-th spin of a second spin group so that the i-th spin of the first spin group and the i-th spin of the second spin group have the same value in a ground state in an interaction relationship of an Ising model represented as a complete bipartite graph connecting N spins of the first spin group and N spins of the second spin group; and
allowing the information processing apparatus to search for the ground state of the Ising model based on the energy function and information unique to the spins,
wherein when the total number of spins of each of the first spin group and the second spin group is defined as N, the value of the i-th spin of the first spin group in the ground state is defined as Si (i=1 to N), the value of the j-th spin of the second spin group in the ground state is defined as Sj (i=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 defined as J i,j , and an interaction coefficient between the i-th spin of the first spin group and the i-th spin of the second spin group is defined as w i , and
the interaction coefficient w i is set to satisfy the following Formula given by a minimum eigenvalue λ of a matrix in which elements of i-th rows and j-th columns are J i,j and diagonal components are 0 and any subset C of a spin array
[
Formula
8
]
w
i
≥
{
∑
v
j
∈
V
❘
"\[LeftBracketingBar]"
J
i
,
j
⌉
-
1
2
∑
v
j
∈
C
❘
"\[LeftBracketingBar]"
J
i
,
j
❘
"\[RightBracketingBar]"
(
v
j
∈
C
)
-
λ
2
(
v
j
∉
C
)
.
8. The information processing method according to claim 7 ,
wherein the information processing apparatus:
searches for the ground state of the Ising model according to the algorithm of a simulated annealing method,
obtains an acceptance probability (transition probability) P(σ, σ′) of state transition at a temperature T which is a parameter indicating easiness of transition between states from the following Formula based on a Metropolis method in the searching,
[
Formula
9
]
P
(
σ
,
σ
′
)
=
min
{
1
,
exp
(
-
H
(
σ
′
)
-
H
(
σ
)
T
)
}
when the values of the spins of the first spin group are expressed as σ L 1 , . . . , σ L N , and the values of the spins of the second spin group are expressed as σ R 1 , . . . , σ R N ,
obtains a difference ΔH of the energy H when the value σ R i of the i-th spin of the second spin group is inverted from the following Formula, and
[
Formula
10
]
Δ
H
=
2
σ
i
R
(
h
i
+
w
i
σ
i
L
+
∑
k
≠
i
J
i
,
k
σ
k
L
)
obtains the difference ΔH of the energy H when the value σ L i of the i-th spin value of the first spin group is inverted from the following Formula, and
[
Formula
11
]
Δ
H
=
2
σ
i
L
(
h
i
+
w
i
σ
i
R
+
∑
k
≠
i
J
i
,
k
σ
k
R
)
when u (0<u≤1) is a uniform random number, determines a condition for accepting the state transition based on the following Formula
Δ
H
≤
-
T
·
ln
(
u
)
.
[
Formula
12
]
9. The information processing method according to claim 8 ,
wherein the information processing apparatus
obtains a next state of the second spin group by the following Formula, and
[
Formula
13
]
[
σ
1
R
⋮
σ
n
R
]
←
sign
(
2
h
+
2
J
[
σ
1
L
⋮
σ
n
L
]
+
2
[
w
i
0
⋮
⋱
⋮
0
ω
n
]
[
σ
1
L
⋮
σ
n
L
]
+
T
[
ln
u
1
0
⋮
⋱
⋮
0
ln
u
n
]
[
σ
1
R
⋮
σ
n
R
]
)
obtains a next state of the first spin group by the following Formula
[
Formula
14
]
[
σ
1
L
⋮
σ
n
L
]
←
sign
(
2
h
+
2
J
[
σ
1
R
⋮
σ
n
R
]
+
2
[
w
i
0
⋮
⋱
⋮
0
w
n
]
[
σ
1
R
⋮
σ
n
R
]
+
T
[
ln
u
1
0
⋮
⋱
⋮
0
ln
u
n
]
[
σ
1
L
⋮
σ
n
L
]
)
.