Information processing apparatus and information processing method

Patent metadata

Field	Value
Publication number	US-2023350972-A1
Application number	US-202318128966-A
Country	US
Kind code	A1
Filing date	Mar 30, 2023
Priority date	Mar 31, 2022
Publication date	Nov 2, 2023
Grant date	—

Abstract

A storage unit stores some of a plurality of coupling coefficients stored in a storage device. A processing unit takes a plurality of first state variables among a plurality of state variables as a trial target set. The processing unit performs a process of reading a plurality of first coupling coefficients corresponding to a plurality of first pairs of the first state variables belonging to the trial target set from the storage device, storing the plurality of first coupling coefficients in the storage unit, and conducting, a plurality of times, a trial on whether to update the value of any first state variable belonging to the trial target set using the plurality of first coupling coefficients. The processing unit repeats change of the trial target set and the process, so as to target all the plurality of state variables in the trials.

First claim

What is claimed is:

1 . An information processing apparatus for finding a solution to a combinatorial optimization problem using an energy function of an Ising model, the information processing apparatus comprising:
a first memory; and a processor, wherein:
the first memory is configured to store some of a plurality of coupling coefficients, the plurality of coupling coefficients corresponding to a plurality of pairs of a plurality of state variables included in the energy function, the plurality of coupling coefficients being stored in a storage device;
the processor is configured to perform a process of
reading, with respect to a trial target set including a plurality of first state variables among the plurality of state variables as targets for a trial on whether to perform value update, a plurality of first coupling coefficients corresponding to a plurality of first pairs of the plurality of first state variables belonging to the trial target set from the storage device, and storing the plurality of first coupling coefficients in the first memory, and
conducting, a plurality of times, the trial on whether to update a value of any of the plurality of first state variables belonging to the trial target set, using the plurality of first coupling coefficients stored in the first memory; and

the processor is further configured to repeat change of the trial target set and the process, so as to target all the plurality of state variables in the trial.

2 . The information processing apparatus according to claim 1 , further comprising
a second memory that stores values of the plurality of state variables and a plurality of local fields corresponding to the plurality of state variables, the plurality of local fields being used in calculating a change in a value of the energy function due to a change in a value of one of the plurality of state variables, wherein: the processor is further configured to
read, from the storage device, a plurality of second coupling coefficients corresponding to a plurality of second pairs each including one of the plurality of first state variables and one of a plurality of second state variables that do not belong to the trial target set, together with the plurality of first coupling coefficients, and store the plurality of second coupling coefficients, as well as the plurality of first coupling coefficients in the first memory; and
the trial includes
calculating a change in the value of the energy function due to a change in a value of a first state variable among the plurality of first state variables, based on a local field corresponding to the first state variable among the plurality of local fields,
updating the value of the first state variable depending on the calculated change, and
updating, upon updating the value of the first state variable, a plurality of first local fields corresponding to the plurality of first state variables among the plurality of local fields, based on first coupling coefficients associated with the updated first state variable among the plurality of first coupling coefficients, and updating a plurality of second local fields corresponding to the plurality of second state variables among the plurality of local fields, based on second coupling coefficients associated with the updated first state variable among the plurality of second coupling coefficients.

3 . The information processing apparatus according to claim 1 , further comprising
a third memory that stores values of the plurality of first state variables and a plurality of first local fields corresponding to the plurality of first state variables, the plurality of first local fields being used in calculating a change in a value of the energy function due to a change in a value of one of the plurality of first state variables, wherein:
the processor is able to access a fourth memory, the fourth memory storing values of the plurality of state variables and a plurality of second local fields corresponding to the plurality of state variables;
the change of the trial target set includes
reading, from the storage device, a plurality of second coupling coefficients corresponding to a plurality of second pairs each including a first differential state variable that is included in a previous trial target set but is not included in a current trial target set among the plurality of state variables and one of a plurality of other state variables than the first differential state variable, together with the plurality of first coupling coefficients, and storing the plurality of second coupling coefficients, as well as the plurality of first coupling coefficients in the first memory,
updating a second value of the first differential state variable stored in the fourth memory with a first value of the first differential state variable stored in the third memory, and updating the plurality of second local fields stored in the fourth memory, based on a difference in the second value between before and after the updating of the second value and the plurality of second coupling coefficients, and
obtaining, from the fourth memory, a third value of a second differential state variable that is not included in the previous trial target set but is included in the current trial target set among the plurality of state variables, storing the third value in the third memory, calculating a local field corresponding to the second differential state variable, based on differences between fourth and fifth values of each of the plurality of first state variables respectively stored in the third memory and the fourth memory, a second local field of the second differential state variable stored in the fourth memory, and the plurality of first coupling coefficients stored in the first memory, and storing the calculated local field in the third memory; and

the trial includes
calculating a change in the value of the energy function due to a change in a value of a first state variable belonging to the current trial target set, based on a first local field corresponding to the first state variable among the plurality of first local fields stored in the third memory,
updating the value of the first state variable stored in the third memory depending on the calculated change, and
updating, upon updating the value of the first state variable, the plurality of first local fields stored in the third memory, based on first coupling coefficients associated with the updated first state variable among the plurality of first coupling coefficients.

4 . The information processing apparatus according to claim 3 , wherein the processor performs the updating of the plurality of second local fields stored in the fourth memory and the trial on the current trial target set in parallel.

5 . The information processing apparatus according to claim 3 , wherein in reading the plurality of second coupling coefficients from the storage device, the processor omits reading coupling coefficients corresponding to pairs each including the first differential state variable and one of other state variables belonging to the previous trial target set.

6 . The information processing apparatus according to claim 1 , wherein the processor is further configured to read coupling coefficients associated with a differential state variable between a previous trial target set and a current trial target set from the storage device, and to omit reading coupling coefficients associated with a state variable overlapping between the previous trial target set and the current trial target set from the storage device.

7 . The information processing apparatus according to claim 1 , wherein the processor is further configured to preread, from the storage device, coupling coefficients associated with a state variable b

Assignees

• Fujitsu Ltd
• Governing Council Univ Toronto

Inventors

• Chen Sigeng
• Rosenthal Jeffrey Seth
• Sheikholeslami Ali
• Tamura Hirotaka
• Matsubara Satoshi

Classifications

• G06F17/11 Primary

  for solving equations {, e.g. nonlinear equations, general mathematical optimization problems (optimization specially adapted for a specific administrative, business or logistic context G06Q10/04)} · 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

• G06N5/01 Primary

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

• G06N7/01

  Probabilistic graphical models, e.g. probabilistic networks · CPC title