Search device, search method, computer program product, search system, and arbitrage system
A search device updates positions and momentums of a plurality of virtual particles, for each unit time from an initial time to an end time. The search device, for each unit time, calculates, for each of the particles, a position at a target time of a corresponding particle, calculates, for each of a plurality of nodes, a first accumulative value by cumulatively adding positions at the target time of two or more particles corresponding to outgoing two or more directed edges, calculates, for each of the nodes, a second accumulative value by cumulatively adding positions at the target time of two or more particles corresponding to incoming two or more directed edges, and calculates, for each of the particles, a momentum at the target time of a corresponding particle based on the first accumulative value and the second accumulative value.
1. A calculation system, comprising:
a calculation device configured to solve a quadratic unconstrained binary optimization (QUBO) problem of minimizing a quadratic function including N binary variables, N being an integer equal to or greater than 2;
a reception device configured to receive a packet including information indicative of a partial coefficient of A coefficients in A terms constituting the quadratic function, A being an integer equal to or greater than 2; and
a transfer circuit including a buffer memory that stores therein at least partial and a plurality of coefficients among the A coefficients,
wherein
the calculation device includes a memory that stores therein the A coefficients and calculates a solution to the QUBO problem based on the A coefficients stored in the memory; and
the transfer circuit
rewrites, when the reception device receives the packet, the partial coefficient indicated by information included in the received packet among the plurality of coefficients stored in the buffer memory, in accordance with the information included in the received packet, and
writes all the plurality of coefficients stored in the buffer memory into the memory of the calculation device, in a batch at a predefined timing.
2. The calculation system according to claim 1 , wherein the calculation device
updates N position variables representing positions of N virtual particles and N momentum variables representing momentums of the N particles for each unit time from an initial time to an end time, and
determines each value of the N binary variables among the N position variables at the end time based on a position variable of a corresponding particle; and
the N particles correspond to the N binary variables in the QUBO problem.
3. The calculation system according to claim 2 , wherein the calculation device, for the each unit time,
calculates the N position variables at a target time based on the N momentum variables; and
calculates the N momentum variables at the target time based on the N position variables and the A coefficients stored in the memory.
4. The calculation system according to claim 1 , further comprising:
an output device configured to generate an instruction to be given to an external device based on the solution to the QUBO problem and output an output packet including the instruction generated.
5. The calculation system according to claim 1 , wherein the reception device sequentially receives a plurality of packets; and
every time the reception device receives the packet, the transfer circuit rewrites the partial coefficient indicated by the information included in the received packet among the plurality of coefficients stored in the buffer memory, in accordance with the information included in the received packet.
6. The calculation system according to claim 5 , wherein the reception device sequentially receives the plurality of packets irregularly transmitted.
7. The calculation system according to claim 6 , wherein the calculation device performs, by being triggered by reception of the packet by the reception device, processing of calculating the solution to the QUBO problem.
8. The calculation system according to claim 5 , wherein the calculation device repeatedly performs processing of calculating the solution to the QUBO problem at certain time intervals.
9. The calculation system according to claim 8 , wherein the transfer circuit writes, at the certain time intervals, all the plurality of coefficients stored in the buffer memory into the memory of the calculation device in a batch.
10. The calculation system according to claim 9 , wherein when there is no change in any of the plurality of coefficients stored in the buffer memory, writing of the coefficients into the memory is skipped.
11. The calculation system according to claim 5 , wherein the transfer circuit writes all the plurality of coefficients stored in the buffer memory into the memory of the calculation device in a batch, in asynchronous with reception of the packet by the reception device.
12. The calculation system according to claim 1 , wherein
the buffer memory includes a plurality of memory circuits corresponding to the plurality of coefficients in a one-to-one manner;
each of the plurality of memory circuits stores therein a corresponding coefficient among the plurality of coefficients; and
the transfer circuit, every time the reception device receives the packet,
writes a coefficient into a memory circuit selected by using the information included in the received packet among the plurality of coefficients, and
writes, for each predefined time, all the plurality of coefficients stored in the plurality of memory circuits into the memory of the calculation device, in a batch.