Ising machine data input apparatus and method of inputting data into an Ising machine

Patent metadata

Field	Value
Publication number	US-12001812-B2
Application number	US-202016832674-A
Country	US
Kind code	B2
Filing date	Mar 27, 2020
Priority date	Jun 21, 2019
Publication date	Jun 4, 2024
Grant date	Jun 4, 2024

Abstract

Apparatus and method of inputting data into an Ising machine. The apparatus may comprise at least one processor to carry out a conversion process to convert an input expression, in a format unsuitable for inputting into an Ising machine, to a suitable format, including creating a dataset of input-output data pairs on the basis of the input expression, deriving a mathematical expression by fitting a first dataset subset to coefficients of an exemplary mathematical expression in the suitable format, and using a second dataset subset, different from the first, to assess whether the derived expression meets a preset quality metric. The derived expression is input to the Ising machine when it is assessed as meeting the metric. The conversion process may be repeated using a different input expression when the derived expression is assessed as failing to meet the metric.

First claim

What is claimed is:

1. An Ising machine data input apparatus to communicate with a computer operating as an Ising machine, the Ising machine data input apparatus, comprising:
an inputter to receive an input expression representing an optimization problem, formulation of the input expression received by the inputter being in a format unsuitable for inputting into the computer operating as the Ising machine;
a converter to carry out a conversion process to convert the input expression, which is received through the inputter, from the format unsuitable for inputting into the computer operating as the Ising machine to a format suitable for inputting into the computer operating as the Ising machine, the converter including:
a dataset creator to receive the input expression from the inputter and create a dataset of input-output data pairs on basis of an evaluation of the formulation of the input expression, whereby a set number of data points are identified to create the dataset of input-output pairs to evolve the optimization problem as initially represented in the input expression received through the inputter into a form in the format suitable for inputting into the computer operating as the Ising machine,
a database to store the dataset of input-output data pairs created by the dataset creator, including a first subset of the dataset which forms a training dataset and a second subset of the dataset which forms a test data set, the second subset of the dataset being different from the first subset of the dataset,
a fitter to obtain the first subset of the dataset stored in the database and derive a mathematical expression by fitting the first subset of the dataset obtained from the database to coefficients of an exemplary mathematical expression in the format suitable for inputting into the Ising machine, and
a tester to compare an output value produced by the formulation of the input expression received and an output value produced by input-output data pairs of the test data set formed by the second subset to thereby assess whether an aggregated difference value between the formulation of the input expression received and the derived mathematical expression meets a preset quality threshold; and

a validator to output, by the Ising machine data input apparatus, the derived mathematical expression, as the optimization problem in the format suitable for input to the computer operating as the Ising machine, when the derived mathematical expression is assessed as meeting the preset quality threshold, and cause the converter to repeat the conversion process when the derived mathematical expression is assessed as being below the preset quality threshold;
wherein the converter repeats the conversion process using a different input expression representing the optimization problem until the aggregated difference value between the formulation of the input expression and the derived mathematical expression is below the preset quality threshold, the conversion process to allow a human user to input the different input expression.

2. The Ising machine data input apparatus as claimed in claim 1 , wherein the format suitable is a Quadratic Unconstrained Binary Optimization—QUBO—formulation, a Cubic Unconstrained Binary Optimization—CUBO—formulation, or a higher order Unconstrained Binary Optimization formulation.

3. The Ising machine data input apparatus as claimed in claim 1 , wherein the dataset is created by a software interpreter.

4. The Ising machine data input apparatus as claimed in claim 1 , wherein a number of input-output data pairs in the first subset is equal to a number of coefficients in the exemplary mathematical expression.

5. The Ising machine data input apparatus as claimed in claim 1 , wherein repeating the conversion process includes prompting the human user to input the different input expression.

6. The Ising machine data input apparatus as claimed in claim 1 , wherein whether the derived mathematical expression meets the preset quality threshold is assessed by determining whether outputs obtained using the derived mathematical expression are sufficiently similar to results obtained using the input expression.

7. The Ising machine data input apparatus as claimed in claim 6 , wherein the results are determined to be sufficiently similar when a difference between the results meets a preset criterion.

8. The Ising machine data input apparatus as claimed in claim 7 , wherein the preset criterion is that the difference between the results is below a preset threshold.

9. The Ising machine data input apparatus as claimed in claim 7 , wherein the difference is the aggregated difference value.

10. The Ising machine data input apparatus as claimed in claim 1 , wherein the input expression is in non-binary form.

11. The Ising machine data input apparatus as claimed in claim 1 , wherein the input expression is not a mathematical expression.

12. The Ising machine data input apparatus as claimed in claim 1 , wherein formulation of the different input expression is guided by the human user.

13. A computer-implemented method of an Ising machine data input apparatus to communicate with a computer operating as an Ising machine, the computer-implemented method comprising:
receiving, by an inputter, an input expression representing an optimization problem, formulation of the input expression received by the inputter being in a format unsuitable for inputting into the computer operating as the Ising machine;
carrying out a conversion process, by a converter, to convert the input expression, which is received through the inputter, from the format unsuitable for inputting into the computer operating as the Ising machine to a format suitable for inputting into the computer operating as the Ising machine, the converter including:
a dataset creator to receive the input expression from the inputter and create a dataset of input-output data pairs on basis of an evaluation of the formulation of the input expression, whereby a set number of data points are identified to create the dataset of input-output pairs to evolve the optimization problem as initially represented in the input expression received through the inputter into a form in the format suitable for inputting into the computer operating as the Ising machine,
a database to store the dataset of input-output data pairs created by the dataset creator, including a first subset of the dataset which forms a training dataset and a second subset of the dataset which forms a test data set, the second subset of the dataset being different from the first subset of the dataset;
a fitter to obtain the first subset of the dataset stored in the database and derive a mathematical expression corresponding to the input expression received by fitting first subset of the dataset obtained from the database to coefficients of an exemplary mathematical expression in the format suitable for inputting into the Ising machine; and
a tester to compare an output value produced by the formulation of the input expression received and an output value produced by input-output data pairs of the test data set formed by the second subset to thereby determine whether an aggregated difference value between the formulation of the input expression received and the derived mathematical expression meets a preset quality threshold; and

outputting, by a validator, the derived mathematical expression, as the optimization problem in the format suitable, for input to the Ising machine, when the derived mathematical expression is assessed as meeting the preset quality threshold, and cause the converter to repeat the conversion process when the derived mathematical expres

Assignees

• Fujitsu Ltd

Inventors

• Moraglio Alberto
• Georgescu Serban

Classifications

• G06F7/548 Primary

  Trigonometric functions; Co-ordinate transformations · 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

• 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

• G06N5/01 Primary

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

• G06F17/16

  Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} · CPC title