Information processing system

Abstract

According to an embodiment, an information processing system solves a combinatorial optimization problem. The information processing system includes an Ising machine and a host unit. The Ising machine is hardware configured to perform a search process for searching for the ground state of an Ising model that represents the combinatorial optimization problem. The host unit is hardware connected to the Ising machine via an interface and configured to control the Ising machine. In the search process, for each of a plurality of Ising spins, the Ising machine alternately repeats an auxiliary variable update process for updating an auxiliary variable by a main variable and a main variable update process for updating the main variable by the auxiliary variable multiple times. Prior to the search process, the host unit transmits, to the Ising machine, an initial value of the auxiliary variable corresponding to each of the plurality of Ising spins.

1 - 13 . (canceled) 
     
     
         14 . An information processing apparatus, comprising:
 a host unit connected to an Ising machine via an interface, the host unit being configured to control the Ising machine,   wherein:
 the Ising machine includes a reconfigurable semiconductor device and is configured to perform a search process for searching for a ground state of an Ising model representing a combinatorial optimization problem, and 
 the host unit is configured to:
 prior to the search process, among a plurality of pieces of circuit information indicating circuits for the semiconductor device to perform the search process, select one circuit information indicating a circuit capable of searching for the ground state of the Ising model, and reconfigure the Ising machine according to the selected circuit information. 
 
   
     
     
         15 . The information processing apparatus according to  claim 14 , wherein, when a search process for searching for a ground state of a second Ising model is performed in a state where a first circuit capable of searching for a ground state of a first Ising model is configured in the semiconductor device,
 the host unit is configured to:
 determine whether the ground state of the second Ising model is searchable by the first circuit; 
 when searchable, cause the Ising machine to perform the search process without reconfiguring the Ising machine; and 
 when not searchable, cause the Ising machine to perform the search process by reconfiguring the Ising machine. 
   
     
     
         16 . The information processing apparatus according to  claim 14 , wherein:
 the Ising machine stores N main variables and N auxiliary variables, N being an integer of 2 or more, wherein:
 an i-th main variable of the N main variables corresponds to an i-th Ising spin of N Ising spins included in the Ising model, i being an integer greater than or equal to 1 and less than or equal to N, and 
 an i-th auxiliary variable of the N auxiliary variables corresponds to the i-th Ising spin; 
   in the search process, the Ising machine is configured to:
 alternately repeat an auxiliary variable update process for updating the i-th auxiliary variable by the i-th main variable and a main variable update process for updating the i-th main variable by the i-th auxiliary variable multiple times for the i-th Ising spin, and 
 output, as a search result, a value based on the N main variables after alternately repeating the main variable update process and the auxiliary variable update process multiple times; and 
   the host unit is configured to:
 prior to the search process, transmit an initial value of each of the N auxiliary variables to the Ising machine, and 
 after the search process, receive the search result from the Ising machine, and output a solution of the combinatorial optimization problem based on the received search result. 
   
     
     
         17 . The information processing apparatus according to  claim 16 , wherein:
 prior to the search process, the Ising machine sets an initial value of each of the N main variables to a predetermined value.   
     
     
         18 . The information processing apparatus according to  claim 16 , wherein:
 prior to the search process, the host unit transmits an initial value of each of the N main variables to the Ising machine.   
     
     
         19 . The information processing apparatus according to  claim 14 , wherein:
 the Ising machine stores N main variables and N auxiliary variables, N being an integer of 2 or more, wherein:
 an i-th main variable of the N main variables corresponds to an i-th Ising spin of N Ising spins included in the Ising model, i being an integer greater than or equal to 1 and less than or equal to N, and 
 an i-th auxiliary variable of the N auxiliary variables corresponds to the i-th Ising spin; 
   in the search process, the Ising machine is configured to:
 alternately repeat an auxiliary variable update process for updating the i-th auxiliary variable by the i-th main variable and a main variable update process for updating the i-th main variable by the i-th auxiliary variable multiple times for the i-th Ising spin, and 
 output, as a search result, a value based on the N main variables after alternately repeating the main variable update process and the auxiliary variable update process multiple times; and 
   the host unit is configured to:
 prior to the search process, transmit an initial value of each of the N main variables to the Ising machine, and 
 after the search process, receive the search result from the Ising machine, and output a solution of the combinatorial optimization problem based on the received search result. 
   
     
     
         20 . The information processing apparatus according to  claim 19 , wherein:
 prior to the search process, the Ising machine sets an initial value of each of the N auxiliary variables to a predetermined value.   
     
     
         21 . The information processing apparatus according to  claim 19 , wherein:
 prior to the search process, the host unit transmits an initial value of each of the N auxiliary variables to the Ising machine.   
     
     
         22 . The information processing apparatus according to  claim 16 , wherein:
 prior to the search process, the host unit transmits, to the Ising machine, definition information for defining the Ising model and a control parameter for controlling the search process.   
     
     
         23 . The information processing apparatus according to  claim 16 , further comprising:
 a first flag storage circuit configured to store a first flag indicating whether or not the search process is completed,   wherein:   the first flag storage circuit updates a value of the first flag in response to a notification transmitted from the Ising machine when the search process is completed, and   the host unit receives the search result from the Ising machine according to the value of the first flag.   
     
     
         24 . The information processing apparatus according to  claim 16 , wherein:
 when a first search process for searching for a ground state of a first Ising model is performed and then a second search process for searching for a ground state of a second Ising model is performed,   the host unit performs a first main process for generating information used for performing the first search process;   the Ising machine performs the first search process after the first main process is performed by the host unit;   the host unit performs a second main process for generating information used for performing the second search process during a period in which the Ising machine is performing the first search process; and   the Ising machine performs the second search process after the second main process is performed by the host unit.   
     
     
         25 . The information processing apparatus according to  claim 24 , wherein:
 when the first search process is completed while the second main process is being performed, the host unit transmits a new initial value of each of the N auxiliary variables and causes the Ising machine to re-perform the first search process according to the new initial value of each of the N auxiliary variables, and   when plural search results of the first search process with different initial values of the N auxiliary variables are received while the second main process is being performed, the host unit generates a search result of the first search process based on the received plural search results.   
     
     
         26 . The information processing apparatus according to  claim 16 , further comprising a circuit information storage device configured to store a plurality of pieces of circuit information. 
     
     
         27 . The information processing apparatus according to  claim 16 , wherein:
 when performing the search process for searching for a ground state of a second Ising model that is searchable by a first circuit in a state where the first circuit capable of searching for a ground state of a first Ising model is configured in the semiconductor device,   the host unit:
 compares a first time representing an estimated execution time of the search process performed by the first circuit with a second time including a reconfiguration time for reconfiguring the semiconductor device as a second circuit and an estimated execution time of the search process performed by the second circuit, and 
 when the second time is shorter than the first time, reconfigures the semiconductor device as the second circuit and causes the Ising machine to perform the search process; and 
   the second circuit is a circuit which is capable of searching for the ground state of the second Ising model and for which a search time is shorter than that of the first circuit.   
     
     
         28 . The information processing apparatus according to  claim 16 , wherein: the host unit:
 acquires coefficient information including a plurality of coupling coefficients that define the Ising model; and   selects, based on a number of the plurality of coupling coefficients included in the coefficient information, one circuit information indicating a circuit capable of searching for the ground state of the Ising model among the plurality of pieces of circuit information.   
     
     
         29 . The information processing apparatus according to  claim 16 , wherein the host unit:
 acquires coefficient information including a coupling coefficient that defines the Ising model; and   selects, based on an accuracy of the coupling coefficient included in the coefficient information, one circuit information indicating a circuit capable of searching for the ground state of the Ising model among the plurality of pieces of circuit information.   
     
     
         30 . The information processing apparatus according to  claim 16 , wherein:
 when being instructed to search for the ground state of the Ising model, the host unit:
 selects two or more pieces of circuit information with different algorithms for calculating the N main variables and the N auxiliary variables in the main variable update process and the auxiliary variable update process among the plurality of pieces of circuit information; 
 for each of the two or more pieces of circuit information, sequentially reconfigures the semiconductor device and causes the semiconductor device to perform the search process, and receives the search result; and 
 outputs the search result received from the semiconductor device. 
   
     
     
         31 . The information processing apparatus according to  claim 16 , wherein:
 the Ising machine stores values of the N main variables in association with a number of repetitions of the main variable update process each time the main variable update process is performed, and   after the search process, the host unit receives the values of the N main variables associated with the number of repetitions of the main variable update process.   
     
     
         32 . An information processing method implemented by an information processing apparatus connected to an Ising machine via an interface and configured to control the Ising machine including a reconfigurable semiconductor device, the Ising machine being configured to perform a search process for searching for a ground state of an Ising model representing a combinatorial optimization problem, the method comprising:
 prior to the search process, among a plurality of pieces of circuit information indicating circuits for the semiconductor device to perform the search process,   by the information processing apparatus, selecting one circuit information indicating a circuit capable of searching for the ground state of the Ising model, and reconfiguring the Ising machine according to the selected circuit information.   
     
     
         33 . A computer program product having a non-transitory computer readable medium including programmed instructions stored thereon, wherein the instructions, when executed by a computer of an information processing apparatus, cause the computer to function as:
 a host unit connected to an Ising machine via an interface, the host unit being configured to control the Ising machine, wherein:
 the Ising machine includes a reconfigurable semiconductor device and is configured to perform a search process for searching for a ground state of an Ising model representing a combinatorial optimization problem, and 
 the instructions cause the host unit to:
 prior to the search process, among a plurality of pieces of circuit information indicating circuits for the semiconductor device to perform the search process, select one circuit information indicating a circuit capable of searching for the ground state of the Ising model, and reconfigure the Ising machine according to the selected circuit information.