Potts model calculation device

Patent metadata

Field	Value
Publication number	US-11436394-B2
Application number	US-201816757246-A
Country	US
Kind code	B2
Filing date	Oct 19, 2018
Priority date	Oct 19, 2017
Publication date	Sep 6, 2022
Grant date	Sep 6, 2022

Abstract

A Potts model computing device capable of computing a Potts problem that is a multivalued spin problem are described herein. The Potts model computing device includes: an Ising model computing device; a computation result storage and determination unit configured to store a value of a spin of the Ising model obtained in a case where a coupling coefficient is set in the Ising model computing device and to determine whether a computation is finished; and a coupling coefficient overwriting unit configured to update a coupling coefficient generated based on the stored value of the spin to the Ising model computing device. According to a value of a set of spins obtained as a computation result corresponding to a coupling coefficient set for an m-th time in the Ising model computing device, the coupling coefficient overwriting unit generates again a coupling coefficient to be set for an (m+1)-th iterative computation.

First claim

The invention claimed is:

1. A Potts model computing device comprising:
an Ising model computing device;
a computation result storage and determination unit configured to store a value of a set of spins of the Ising model obtained in a case where a coupling coefficient is set in the Ising model computing device and to determine whether a computation is finished; and
a coupling coefficient overwriting unit configured to update a coupling coefficient generated based on the stored value of the set of spins to the Ising model computing device,
wherein, according to values of the spins of the Ising model obtained as a computation result for an m-th time iterative computation using the Ising model computing device, the coupling coefficient overwriting unit generates a coupling coefficient to be set for an (m+1)-th time computation and updates the generated coupling coefficient to the Ising model computing device,
the computation result storage and determination unit determines that a computation is finished in a case where a number of iteration times reaches to Ms (Ms is a natural number), and computes a value S i by substituting a value σ i m of a spin obtained as a computation result of the m-th time iterative Ising model computation into the following formula to compute a problem mapped to the Potts model using the Ising model computing devices:
S i =Σ m=1 Ms (1+σ im )2 m−2

wherein a possible value of a multivalued spin of the Potts model is S i =0, 1, 2, . . . , M−1 (M is a natural number) and M≤2 M S .

2. The Potts model computing device according to claim 1 , wherein
the Ising model computing device comprises:
a phase sensitive amplifier configured to parametrically oscillate an optical pulse train having a same oscillation frequency in a 0 or π phase, which emulates a set of binary spins of the Ising model;
a ring resonator configured to allow the optical pulse train to circulate and propagate;
an optical pulse measurement unit configured to measure phases and amplitudes of the optical pulse train each time the optical pulse train circulates and propagates through the ring resonator;
an interaction computing unit configured to compute an interaction between optical pulses using information about phases and amplitudes of optical pulses measured in the optical pulse measurement unit as input, the interaction being determined from the coupling coefficient of the Ising model and the measured optical pulses;
an interaction implementation unit configured to implement the interaction between the optical pulse train determined based on the coupling coefficient of the Ising model and the phases and amplitudes of the measured optical pulses by controlling and overlapping amplitudes and phases of optical pulses on the optical pulse train in the interaction computing unit; and
a problem overwriting unit configured to update the coupling coefficient of the Ising model,
in a process of repeating feedback loop control formed by the optical pulse measurement unit, the interaction computing unit, and the interaction implementation unit, the optical pulse measurement unit obtains a spin set of solution of the Ising model by converting the phases of the optical pulse train into binary Ising spins after the optical pulse train reaches a stable state.

3. The Potts model computing device according to claim 2 , wherein
the interaction computing unit multiplies a column vector having phases and amplitudes c 1 m , c 2 m , c 3 m , c 4 m , c i m , c (N−1)m , c N m of N measured optical pulses as elements by the following matrix having coupling coefficients of the Ising model as arithmetic parameters and computes elements f 1 m , f 2 m , f 3 m , f 4 m , f i m , f (N−1)m , f N m of the obtained column vector Ms times as interactions relating to N optical pulses corresponding to the N optical pulses while varying m from 1 to Ms, wherein K ij =J ij m :

(

f

1
⁢
m

f

2
⁢
m

f

3
⁢
m

⋮

f

(

N
-
1

)

⁢
m

f
Nm

)

=

(

0

K
12

K
13

⋯

K

1
⁢

(

N
-
1

)

K

1
⁢
N

K
21

0

K
23

⋯

K

2

Assignees

• Nippon Telegraph & Telephone

Inventors

• Inaba Kensuke
• Takesue Hiroki
• Honjo Toshimori
• Inagaki Takahiro

Classifications

• G06N5/01 Primary

  Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound · CPC title

• G06F30/20 Primary

  Design optimisation, verification or simulation (optimisation, verification or simulation of circuit designs G06F30/30) · CPC title

• G06F17/18

  for evaluating statistical data {, e.g. average values, frequency distributions, probability functions, regression analysis (forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04)} · CPC title

• G06E3/008

  Matrix or vector computation · CPC title

• G06E3/005

  using electro-optical or opto-electronic means · CPC title