# US 2025/0094526 A1 · Information processing system, solver device, information processing method, computer program product, and device

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2025/0094526 A1
- Document ID: US20250094526A1
- Status: Published application
- Kind: A1
- Application number: 18/760,332
- Filed: 2024-07-01
- Published: 2025-03-20
- Earliest claimed: 2023-09-14
- Assignees: Kabushiki Kaisha Toshiba
- Applicants: Kabushiki Kaisha Toshiba
- Inventors: Yohei HAMAKAWA; Kosuke TATSUMURA
- Web page: https://patentgrep.com/patent/US20250094526A1

## CPC

- G06F 17/11: for solving equations {, e.g. nonlinear equations, general mathematical optimization problems (optimization specially adapted for a specific administrative, business or logistic context G06Q10/04)}
- G06N 5/01: Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
- G06F 7/5443: {Sum of products (for applications thereof, see the relevant places, e.g. G06F17/10, H03H17/00)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

An information processing system according to an embodiment solves a combinatorial optimization problem. The information processing system includes an information processing device and a solver device. A first coefficient among the plurality of coefficients is expressed by a predetermined first data type. The coefficient information includes, instead of the first coefficient, a first identification value expressed by a second data type having a smaller data size than the first data type. The solver device stores restoration information indicating a first restoration value corresponding to the first identification value. The first restoration value is expressed by the first data type. The solver device acquires the first identification value included in the coefficient information, and uses the first restoration value corresponding to the first identification value represented by the restoration information as the first coefficient when executing the operation on the first coefficient among the plurality of coefficients.

## Claims

### Claim 1

An information processing system for solving a combinatorial optimization problem, the information processing system comprising:
an information processing device that outputs coefficient information representing a plurality of coefficients in a cost function including the plurality of coefficients and N decision variables, where N is an integer of two or more; and
a solver device that calculates ground state information representing values of the N decision variables by executing a solving process for minimizing the cost function based on the coefficient information, wherein
a first coefficient among the plurality of coefficients is expressed by a predetermined first data type,
the coefficient information includes, instead of the first coefficient, a first identification value expressed by a second data type having a smaller data size than the first data type, and
the solver device:
stores restoration information indicating a first restoration value corresponding to the first identification value, the first restoration value being expressed by the first data type; and
acquires the first identification value included in the coefficient information and uses the first restoration value corresponding to the first identification value represented by the restoration information as the first coefficient when executing an operation on the first coefficient among the plurality of coefficients.

### Claim 2 (depends on 1)

The system according to claim 1, wherein
the information processing device generates the restoration information based on the plurality of coefficients to output the restoration information to the solver device, and
the solver device acquires the restoration information from the information processing device.

### Claim 3 (depends on 1)

The system according to claim 1, wherein
the solver device stores the restoration information prior to acquiring the coefficient information.

### Claim 4 (depends on 1)

The system according to claim 1, wherein
each of the plurality of coefficients is expressed by the first data type and belongs to any one of P groups, where P is an integer of two or more,
the restoration information represents P restoration values corresponding to P identification values,
a p-th restoration value among the P restoration values corresponds to a p-th identification value among the P identification values, where p is an integer of one or more and P or less,
the p-th identification value is expressed by the second data type and identifies a p-th group among the P groups,
the p-th restoration value is expressed by the first data type and is a value of representing a coefficient group belonging to the p-th group, and
the coefficient information includes, instead of the first coefficient among the plurality of coefficients, the first identification value for identifying a group to which the first coefficient among the P groups belongs.

### Claim 5 (depends on 4)

The system according to claim 4, wherein
the solver device includes:
a coefficient information memory that stores the coefficient information;
a restoration information memory that stores the restoration information; and
a solving circuit that executes the solving process based on the coefficient information stored in the coefficient information memory and the restoration information stored in the restoration information memory.

### Claim 6 (depends on 5)

The system according to claim 5, wherein
when executing an operation on the first coefficient, the solving circuit:
acquires the first identification value included instead of the first coefficient, from the coefficient information stored in the coefficient information memory;
acquires the first restoration value corresponding to the first identification value, the first restoration value being represented by the restoration information stored in the restoration information memory; and
executes an arithmetic process using the first restoration value as the first coefficient.

### Claim 7 (depends on 5)

The system according to claim 5, wherein
the solving circuit includes a product-sum operation circuit that executes a product-sum operation on N first variables corresponding to the N decision variables and N restoration values corresponding to N coefficients of the plurality of coefficients,
the product-sum operation circuit includes:
P cumulative addition circuits each of which stores a cumulative value, adds an acquired value to the cumulative value, and resets the cumulative value to 0 before acquiring the N first variables;
a demultiplexer circuit that gives each of the N first variables to any cumulative addition circuit of the P cumulative addition circuits; and
a subsequent stage circuit that performs a product-sum operation on P cumulative values stored in the P cumulative addition circuits and the P restoration values represented in the restoration information,
a p-th cumulative addition circuit among the P cumulative addition circuits corresponds to the p-th group, where p is an integer of one or more and P or less, and
the demultiplexer circuit:
acquires N identification values included instead of the N coefficients, from the coefficient information; and
when acquiring an n-th first variable among the N first variables, gives it to a cumulative addition circuit corresponding to a group identified by an n-th identification value among the N identification values among the P cumulative addition circuits, where n is an integer of one or more and N or less.

### Claim 8 (depends on 7)

The system according to claim 7, wherein
the subsequent stage circuit outputs, as a product-sum operation value of the N first variables and the N restoration values, a value obtained by performing a product-sum operation on the P cumulative values and the P restoration values, after acquiring all of the N first variables.

### Claim 9 (depends on 8)

The system according to claim 8, wherein
the subsequent stage circuit includes:
P multiplication circuits; and
an addition circuit that adds the P multiplication values output from the P multiplication circuits,
a p-th multiplication circuit among the P multiplication circuits corresponds to the p-th group, and
after acquiring all of the N first variables,
the p-th multiplication circuit outputs a multiplication value obtained by multiplying the cumulative value stored in the p-th cumulative addition circuit by a restoration value corresponding to the p-th identification value, and
the addition circuit outputs, as the product-sum operation value, a value obtained by adding the P multiplication values.

### Claim 10 (depends on 7)

The system according to claim 7, wherein
each of the N first variables is expressed by a third data type having a smaller data size than the first data type,
the information processing system further comprises P data type conversion circuits,
a p-th data type conversion circuit among the P data type conversion circuits corresponds to the p-th cumulative addition circuit, and
the p-th data type conversion circuit converts the cumulative value stored in the p-th cumulative addition circuit from the third data type to the first data type and gives it to the subsequent stage circuit.

### Claim 11 (depends on 1)

The system according to claim 1, wherein
each of the N decision variables included in the cost function is a binary discrete variable.

### Claim 12 (depends on 11)

The system according to claim 11, wherein
the information processing device formulates the combinatorial optimization problem into the cost function of a quadratic unconstrained binary optimization (QUBO) problem.

### Claim 13 (depends on 11)

The system according to claim 11, wherein
the information processing device formulates the combinatorial optimization problem into the cost function in an Ising problem that minimizes an Ising model.

### Claim 14 (depends on 12)

The system according to claim 12, wherein
the solver device solves the QUBO problem while reducing it to an Ising problem that minimizes an Ising model.

### Claim 15 (depends on 13)

The system according to claim 13, wherein
the solver device solves the Ising problem by a simulated bifurcation algorithm.

### Claim 16 (depends on 11)

The system according to claim 11, wherein
the cost function is a cubic or higher function of the N decision variables, and
the combinatorial optimization problem is a higher order binary optimization (HUBO) problem.

### Claim 17

A solver device used by an information processing device that solves a combinatorial optimization problem, wherein
the information processing device outputs coefficient information representing a plurality of coefficients in a cost function including the plurality of coefficients and N decision variables, where N is an integer of two or more,
the solver device calculates ground state information representing values of the N decision variables by executing a solving process for minimizing the cost function based on the coefficient information,
a first coefficient among the plurality of coefficients is expressed by a predetermined first data type,
the coefficient information including, instead of the first coefficient, a first identification value expressed by a second data type having a smaller data size than the first data type, and
the solver device:
stores restoration information indicating a first restoration value corresponding to the first identification value, the first restoration value being expressed by the first data type; and
acquires the first identification value included in the coefficient information and uses the first restoration value corresponding to the first identification value represented by the restoration information as the first coefficient when executing an operation on the first coefficient among the plurality of coefficients.

### Claim 18

An information processing method of solving a combinatorial optimization problem by an information processing device and a solver device, the method comprising:
by the information processing device, outputting coefficient information representing a plurality of coefficients in a cost function including the plurality of coefficients and N decision variables, where N is an integer of two or more;
by the solver device, calculating the ground state information representing values of the N decision variables by executing a solving process for minimizing the cost function based on the coefficient information,
a first coefficient among the plurality of coefficients being expressed by a predetermined first data type,
the coefficient information including, instead of the first coefficient, a first identification value expressed by a second data type having a smaller data size than the first data type; and
by the solver device,
storing restoration information indicating a first restoration value corresponding to the first identification value, the first restoration value being expressed by the first data type, and
acquiring the first identification value included in the coefficient information and using the first restoration value corresponding to the first identification value represented by the restoration information as the first coefficient when executing an operation on the first coefficient among the plurality of coefficients.

### Claim 19

A computer program product comprising a computer-readable medium including programmed instructions, the instructions causes a computer to function as a solver device used in an information processing device that solves a combinatorial optimization problem, wherein
the information processing device outputs coefficient information representing a plurality of coefficients in a cost function including the plurality of coefficients and N decision variables, where N is an integer of two or more,
the solver device calculates the ground state information representing values of the N decision variables by executing a solving process for minimizing the cost function based on the coefficient information,
a first coefficient among the plurality of coefficients is expressed by a predetermined first data type,
the coefficient information includes, instead of the first coefficient, a first identification value expressed by a second data type having a smaller data size than the first data type,
the instructions cause the computer to operate to:
store restoration information indicating a first restoration value corresponding to the first identification value, the first restoration value being expressed by the first data type; and
acquire the first identification value included in the coefficient information and use the first restoration value corresponding to the first identification value represented by the restoration information as the first coefficient when executing an operation on the first coefficient among the plurality of coefficients.

### Claim 20

A computer program product comprising a non-transitory computer-readable recording medium on which circuit information described in a hardware description language and representing a configuration of a circuit is recorded, the circuit information causing the circuit to function as a solver device used by an information processing device that solves a combinatorial optimization problem, wherein
the information processing device outputs coefficient information representing a plurality of coefficients in a cost function including the plurality of coefficients and N decision variables, where N is an integer of two or more,
the solver device calculates ground state information representing values of the N decision variables by executing a solving process for minimizing the cost function based on the coefficient information,
a first coefficient among the plurality of coefficients is expressed by a predetermined first data type,
the coefficient information includes, instead of the first coefficient, a first identification value expressed by a second data type having a smaller data size than the first data type, and
the solver device:
stores restoration information indicating a first restoration value corresponding to the first identification value, the first restoration value being expressed by the first data type; and
acquires the first identification value included in the coefficient information and uses the first restoration value corresponding to the first identification value represented by the restoration information as the first coefficient when executing an operation on the first coefficient among the plurality of coefficients.

### Claim 21 (depends on 20)

A device comprising the computer program product according to claim 20.

### Claim 22

A computer program product comprising a non-transitory computer-readable recording medium on which circuit information to be written in a reconfigurable semiconductor device for operating the reconfigurable semiconductor device is recorded, the circuit information causing the reconfigurable semiconductor device to function as a solver device used by an information processing device that solves a combinatorial optimization problem, wherein
the information processing device outputs coefficient information representing a plurality of coefficients in a cost function including the plurality of coefficients and N decision variables, where N is an integer of two or more,
the solver device calculates ground state information representing values of the N decision variables by executing a solving process for minimizing the cost function based on the coefficient information,
a first coefficient among the plurality of coefficients is expressed by a predetermined first data type,
the coefficient information includes, instead of the first coefficient, a first identification value expressed by a second data type having a smaller data size than the first data type, and
the solver device:
stores restoration information indicating a first restoration value corresponding to the first identification value, the first restoration value being expressed by the first data type; and
acquires the first identification value included in the coefficient information and uses the first restoration value corresponding to the first identification value represented by the restoration information as the first coefficient when executing an operation on the first coefficient among the plurality of coefficients.

### Claim 23 (depends on 22)

A device comprising the computer program product according to claim 22.
