JP7790573B2 - Pseudo-Ising Hamiltonian generator, combinatorial problem calculation system, Ising machine, auxiliary variable calculation device, program - Google Patents

Description

Article 30, Paragraph 2 of the Patent Act applies. Announced on June 30, 2022 on the website (address: https://ipsj.ixsq.nii.ac.jp/ej/?action=pages_view_main&active_action=repository_view_main_item_detail&item_id=218771&item_no=1&page_id=13&block_id=8).

The present invention relates to a pseudo-Ising Hamiltonian generation device, a combinatorial problem calculation system, an Ising machine, an auxiliary variable calculation device, and a program that can pseudo-realize the input of diagonal elements using an Ising Hamiltonian transformation equivalent to ±1 variables.

The currently widely used von Neumann computers are considered to have difficulty efficiently solving combinatorial optimization problems. Therefore, in recent years, research and development has been underway into Ising machines, which are computers that can solve combinatorial optimization problems more efficiently than von Neumann computers. Specific examples of Ising machines include quantum annealing machines, coherent Ising machines, and digital annealers.

These new computers can quickly calculate the solution to a combinatorial optimization problem by inputting an objective function that expresses the problem as an Ising Hamiltonian.

Figure 1 shows an example of the functional configuration of a conventional Ising machine. Figure 2 shows an example of the operation of a conventional Ising machine. As illustrated in Figure 1, the conventional Ising machine 92 includes an Ising Hamiltonian acquisition unit 921, a solution candidate search processing unit 922, and a solution candidate output unit 923.

The Ising Hamiltonian acquisition unit 921 acquires an Ising Hamiltonian J _ij that represents a combinatorial optimization problem, where i and j represent variable indexes and t represents time.

2, the solution candidate search processor 922 sets an initial value _si ( _Tini ) of a variable at t= _Tini ( _Tini is the calculation start time) (S922A). The solution candidate search processor 922 calculates the time change of the variable _si (t) based on the Ising Hamiltonian _Jij as _si (t+dt)= _Fi ( _si (t),t; _Jij ) ( _S922B ). A specific example of _Fi is _Fi = _si (t)-[ _si3 (t)+( ¹ -p(t)) _si (t)]+ _{Σi≠jJijsj (} t). Here, p(t) is a function that is specified in advance before calculation.

Step S922B is repeatedly executed until t = _Tfin ( _Tfin is the calculation end time). The solution candidate search processing unit 922 outputs the value of the variable s _i (Tfin) at the calculation end time (t = _Tfin ) ( _S922C ). The solution candidate output unit 923 outputs the value of the variable s _i ( _Tfin ) that is a solution candidate for problem J _ij .

Among such computers, those that perform calculations using variables that take analog values (e.g., Coherent Ising Machine (Non-Patent Document 1) and Simulated Bifurcation Machine (Non-Patent Document 2)) can change their solution performance by taking advantage of their analog nature.

TAKAHIRO INAGAKI, AND 13 authors, "A coherent Ising machine for 2000-node optimization problems", [online], 20 Oct 2016, SCIENCE, Vol. 354, Issue 6312, pp. 603-606, [Retrieved June 27, 2022], Internet〈 URL: https://www.science.org/doi/full/10.1126/science.aah4243 〉 HAYATO GOTO, KOSUKE TATSUMURA, AND ALEXANDER R. DIXON, "Combinatorial optimization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems", [online], 19 Apr 2019, SCIENCE ADVANCES, Vol. 5, Issue 4, [Retrieved June 27, 2022], Internet〈URL: https://www.science.org/doi/10.1126/sciadv.aav2372〉

In the solution process using an Ising machine, the optimal solution is not necessarily obtained, but a solution is given from a probability distribution of solutions close to the optimal one. Here, the Ising Hamiltonian is a multivariate quadratic polynomial with respect to variables (spins) that take on the values +1 or -1.

There are Ising machines that allow real numbers (analog values) other than ±1 for the variables in the calculation process and calculation results, and ultimately determine a ±1 solution from the sign of the variable in the calculation result. In this specification, these are referred to as "analog variable Ising machines."

For this analog variable Ising machine, it may seem possible to adjust the absolute value of the calculation result for the corresponding variable by introducing auxiliary variables into the diagonal elements of the Ising Hamiltonian matrix that serves as input, but some analog variable Ising machines do not allow the input of diagonal elements.

Therefore, the objective of this invention is to provide a pseudo-Ising Hamiltonian generator that can pseudo-input diagonal components using an Ising Hamiltonian transformation that is equivalent on ±1 variables.

The pseudo-Ising Hamiltonian generating device of the present invention includes a pseudo-variable substitution unit and a pseudo-diagonal term generating unit.

The pseudo-variable substitution unit generates a pseudo-Ising Hamiltonian by replacing each variable in the Ising Hamiltonian with a pseudo-variable defined as a constant multiple of the sum of two or more distributed variables. The pseudo-diagonal term generation unit generates pseudo-diagonal terms that are the inverted values of the sum of the quadratic products of the distributed variables contained in each pseudo-variable.

The pseudo-Ising Hamiltonian generating device of the present invention can pseudo-input diagonal components using an Ising Hamiltonian transformation equivalent to ±1 variables.

FIG. 1 is a block diagram showing an example of the functional configuration of a conventional Ising machine. 1 is a flowchart showing an example of the operation of a conventional Ising machine. FIG. 1 is a block diagram showing the functional configuration of a pseudo-Ising Hamiltonian generating device according to a first embodiment. 3 is a flowchart showing the operation of the pseudo Ising Hamiltonian generating device according to the first embodiment. FIG. 10 is a block diagram showing a first example of the functional configuration of a combination problem calculation system according to a second embodiment. FIG. 10 is a block diagram showing a second example of the functional configuration of the combination problem calculation system according to the second embodiment. FIG. 10 is a sequence diagram showing the operation of the combination problem calculation system according to the second embodiment. FIG. 11 is a block diagram showing a first example of the functional configuration of a combination problem calculation system according to a third embodiment. FIG. 11 is a block diagram showing a second example of the functional configuration of the combination problem calculation system according to the third embodiment. FIG. 11 is a sequence diagram showing the operation of the combination problem calculation system according to the third embodiment. FIG. 10 is a diagram showing an example of the value of a pseudo variable σ _i at each time obtained in the solution candidate search process. FIG. 10 is a diagram showing an example of calculation of the time average <σ _i > _T of the pseudo variable σ _i at each time. A diagram showing an example of calculating the ensemble mean <σ ^- _i > _T, the mean between variables M, and the auxiliary variable a _i . FIG. 2 is a diagram showing an example of the functional configuration of a computer.

The following describes in detail an embodiment of the present invention. Components having the same functions are assigned the same numbers, and duplicate explanations will be omitted.

The functional configuration of the pseudo-Ising Hamiltonian generating device 110 of the first embodiment will be described below with reference to Figure 3. As shown in the figure, the pseudo-Ising Hamiltonian generating device 110 of this embodiment includes a pseudo-variable substitution unit 1101 and a pseudo-diagonal term generating unit 1102. The operation of each component will be described below with reference to Figure 4.

<Pseudo variable substitution unit 1101>
The pseudo variable substitution unit 1101 substitutes each variable of the Ising Hamiltonian with a pseudo variable σ _i defined as a constant multiple of the sum of two or more dispersion variables to generate a pseudo Ising Hamiltonian K _ij (S1101).

<Pseudo-diagonal term generation unit 1102>
The pseudo-diagonal term generation unit 1102 generates pseudo-diagonal terms Δ _i , which are the positive/negative inverted values of the sum of the second-order products of the dispersion variables x _ik included in each pseudo variable σ _i , and outputs the pseudo-Ising Hamiltonian K _ij and the pseudo-diagonal terms Δ _i to the Ising machine (S1102). Each of these pseudo-diagonal terms Δ _i is multiplied by an auxiliary variable a _i to make its absolute value adjustable.

By regarding the Ising Hamiltonian after substitution (pseudo-Ising Hamiltonian K) as the Ising Hamiltonian and regarding the pseudo-diagonal term Δ as a diagonal term and inputting it into the Ising machine, it is possible to pseudo-input diagonal components into an analog variable Ising machine, which does not allow the input of diagonal components.

In this case, the pseudo-diagonal terms Δ _i have the effect of increasing the absolute value of the pseudo-variables σ _i , and can be expected to have the same effect as the conventional diagonal terms, which increase the absolute value of the variables.

<Specific examples of pseudo-variables σ _i , pseudo-diagonal terms Δ _i , and pseudo-Ising Hamiltonian K _ij >
For example, if the original Ising model

If we consider the case where the pseudo variables σ ₀ , σ ₁ , and σ ₂ are multiplied by a constant number equal to the sum of two or more variance variables, for example,

The pseudo-diagonal terms are the sum of products (second-order products _{) of two selected variables from all variance variables x 00 ,} x ₀₁ , x ₁₀ , x ₁₁ , x ₁₂ , x ₂₀ , x ₂₁ , x ₂₂ included in each pseudo-variable σ 0 _, σ 1 , σ ₂ , that is,

In this example, the pseudo-Ising Hamiltonian (pseudo-Ising model) is

It can be seen that K _ij is an Ising model with respect to the pseudo variable σ and at the same time an Ising model with respect to the distributed variable x.

<Inverse conversion process>
The combinatorial problem calculation system described below can be used to obtain a solution for the dispersion variable _xik on the pseudo-Ising Hamiltonian _Kij . Based on this, the solution for the pseudo-variable _σi can be calculated, and the value of the original variable _sij can be determined from its sign. The table below shows examples of dispersion variables _xik and the corresponding calculation examples for the pseudo-variable _σi and original variable _sij .
<Validity of the action of pseudo-diagonal terms>
The pseudo-diagonal terms have the same effect on the pseudo-variables as the diagonal terms, because they can be decomposed into positive squared components in the direction of the pseudo-variables and negative squared components in the direction perpendicular to the direction of the pseudo-variables.

The original diagonal terms are weighted components of the squares of the variables in question, and have the effect of increasing or decreasing the absolute value of the variable _s1 .

On the other hand, for the pseudo-diagonal terms,

The first term of the equation after transformation is a positive weight component for the square of the absolute value of the pseudo variable σ _n , and acts to increase or decrease the absolute value of the pseudo variable σ _n . On the other hand, the second term of the equation after transformation is a negative weight component for the square of the direction perpendicular to the pseudo variable σ _n , and acts to escape values in directions other than the absolute value direction of the pseudo variable σ _n .

<Transformation of the variance variable by reversing the sign>
When defining pseudo variables, it is also possible to reverse the sign of the distributed variable. For example, in the example of the original Ising model mentioned above,

Reverse the sign of the variance variable for

In this example, the pseudo-diagonal terms are

In this example, the pseudo-Ising Hamiltonian (pseudo-Ising model) is

It can be transformed as follows.

<Inverse transformation when sign-reversed variance variables are included>
For inverse transformation including sign reversal of pseudo variables, the inverse transformation can be performed by reversing the sign of the corresponding variance variable.
According to the pseudo Ising Hamiltonian generation device 110 of this embodiment, even for an Ising machine that does not allow the input of diagonal components, the pseudo Ising Hamiltonian transformation equivalent to ±1 variables can be used to realize the input of diagonal components, and the probability of obtaining an optimal solution can be improved by a combinatorial problem calculation system described later.

Below, we will explain the combinatorial problem calculation systems 1-A and 1-B of Example 2, which use the above-mentioned pseudo-Ising Hamiltonian generation device 110.

In Example 2, auxiliary variables (hereinafter referred to as auxiliary variables) whose values change during the search are assigned to the input pseudo-diagonal terms, thereby providing an effect of assisting the solution search in the solution-finding process of the Ising machine. The control of these auxiliary variables is determined based on the values of the pseudo-variables calculated by the Ising machine at each time during the search. In Example 2, the solution-finding performance is improved by setting a control method for the auxiliary variables so that the absolute values of each variable are equal.

The functional configuration of the combinatorial problem calculation system of Example 2 will be described with reference to Figure 5. As shown in the figure, the combinatorial problem calculation system 1-A of this example includes the pseudo-Ising Hamiltonian generation device 110, auxiliary variable calculation device 11, and Ising machine 12 described in Example 1. The pseudo-Ising Hamiltonian generation device 110 and auxiliary variable calculation device 11 are classical computers. The auxiliary variable calculation device 11 includes an auxiliary variable calculation unit 111. The Ising machine 12 includes a pseudo-Ising Hamiltonian acquisition unit 121, a solution candidate search processing unit 122, and a solution candidate output unit 923, and differs from the conventional Ising machine 92 in the pseudo-Ising Hamiltonian acquisition unit 121 and the solution candidate search processing unit 122.

The difference is that while the conventional Ising Hamiltonian acquisition unit 921 acquires a normal Ising Hamiltonian, the pseudo-Ising Hamiltonian acquisition unit 121 of this embodiment acquires the pseudo-Ising Hamiltonian generated by the pseudo-Ising Hamiltonian generation device 110.

The functions of the pseudo-Ising Hamiltonian generator 110 may be provided in the auxiliary variable calculation device 11. In this case, as shown in the combinatorial problem calculation system 1-B in Figure 6, the auxiliary variable calculation device 11 may be configured to include a pseudo-Ising Hamiltonian generator unit 110 and an auxiliary variable calculation unit 111. In this case, the pseudo-Ising Hamiltonian generator 110 is omitted, and the pseudo-Ising Hamiltonian generator unit 110 operates in the same way as the pseudo-Ising Hamiltonian generator 110.

The auxiliary variable calculation device 11 calculates auxiliary variables that correct the pseudo-Ising Hamiltonian and outputs them to the Ising machine 12. The auxiliary variables are characterized by suppressing variations in absolute values between pseudo-variables so as not to interfere with the solution candidate search process of the Ising machine.

The Ising machine 12 corrects the pseudo-Ising Hamiltonian based on the auxiliary variables calculated by the auxiliary variable calculation device 11, and performs a solution candidate search process based on the corrected pseudo-Ising Hamiltonian.

With reference to Figure 7, the detailed operation of the auxiliary variable calculation unit 111 of the auxiliary variable calculation device 11 and the solution candidate search processing unit 122 of the Ising machine 12 will be described. Note that i, j, and k represent variable indexes, and t represents time.

The auxiliary variable calculation unit 111 sets the initial value a _i (T _ini ) of the auxiliary variable at t=T _ini (T _ini is the calculation start time) (S111A).

The solution candidate search processor 122 sets the initial value x _ik (T _ini ) of the dispersion variable at t=T _ini (S122A).

The solution candidate search processor 122 corrects the pseudo Ising Hamiltonian by the auxiliary variables _ai (t) and the pseudo diagonal terms _Δi , and executes the solution candidate search process based on the corrected pseudo Ising Hamiltonian _K'ij = _Kij + _ai (t) _Δi . Specifically, the solution candidate search processor 122 calculates the time change of the dispersion variable _xik (t) as _xik (t+dt)= _Fik ( _xik (t),t; _Kij + _ai (t) _Δi ) (S122B).

The auxiliary variable calculation unit 111 calculates the change over time of the auxiliary variable a i (t) by a _i (t+dt)=G _i (σ _i (t), _{a i} (t), t) (S111B, updating the value).

<S111B, Auxiliary variable calculation method>
The method for calculating the auxiliary variables in step S111B will be described in detail below. Based on the pseudo variable σ _i (t) acquired at each time in the calculation process of the Ising machine 12, an auxiliary variable a _i (t) that satisfies the following equation is calculated and output.

da _i (t)/dt=f(σ _i (t),t)
The function form of f is given before the optimization calculation, assuming that it satisfies the following conditions: | _σi (t)|=g(t) exists as a solution to the equation f( _σi (t),t)=0. Here, g(t) is assumed to be independent of i. The function f is essentially the same as the function G described above, but a different letter has been assigned because it is expressed differently from the above formula. The update formula for _ai (t) above is set so as to produce a function that aligns the absolute values between the pseudo-variables _σi output by the Ising machine 12 with g(t).

<Specific example of function f (example of algorithm)>
For example, the function f can be set as follows so that a _i (t) acts as a time-dependent Lagrange multiplier:

da _i (t)/dt=K(M(t)-σ _i ² (t))
M(t) satisfies M(t) ≥ 0, and its functional form is specified before the optimization calculation. K is a non-zero constant. The update formula for _ai (t) above is set so as to align the absolute values between the pseudo-variables _σi output by the Ising machine to √(M(t)).

The auxiliary variable calculation unit 111 continues to update the auxiliary variable _ai (t) by repeatedly executing step S111B using the updated auxiliary variable _σi (t) until t = _Tfin ( _Tfin is the calculation end time), and the solution candidate search processing unit 122 continues to update the pseudo variable _σi (t) by repeatedly executing step S122B using the updated auxiliary variable _ai (t) until t = _Tfin . The solution candidate search processing unit 122 outputs the value of the pseudo variable _σi (Tfin) at the calculation end time (t = _Tfin ) (S122C). The solution candidate output unit 923 outputs the value of the pseudo variable _σi ( _Tfin ) that is a solution candidate for _the problem _Kij .

Example 3 is similar to Example 2 in that it controls the solution process of the Ising machine by introducing auxiliary variables into the input pseudo-diagonal terms, but has the feature that the values of these auxiliary variables are determined based on information obtained from the optimization calculation process. In Example 3, the values of the auxiliary variables are calculated using heuristics so that the time averages of the values of each variable are equal, thereby improving solution performance.

The functional configuration of the combinatorial problem calculation system 2-A of Example 3 will be described with reference to Figure 8. As shown in the figure, the combinatorial problem calculation system 2-A of this example includes a pseudo-Ising Hamiltonian generation device 110, an auxiliary variable calculation device 21, and an Ising machine 22. The pseudo-Ising Hamiltonian generation device 110 and the auxiliary variable calculation device 21 are classical computers. The auxiliary variable calculation device 21 includes a time averaging unit 211, an ensemble averaging unit 212, an inter-variable averaging unit 213, and an auxiliary variable calculation unit 214. The Ising machine 22 includes a pseudo-Ising Hamiltonian acquisition unit 121, a solution candidate search processing unit 222, and a solution candidate output unit 923, and differs from the Ising machine 12 of Example 2 in the solution candidate search processing unit 222.

The functions of the pseudo-Ising Hamiltonian generator 110 may be provided in the auxiliary variable calculation device 21. In this case, as shown in the combinatorial problem calculation system 2-B in Figure 9, the auxiliary variable calculation device 21 may be configured to include a pseudo-Ising Hamiltonian generator 110, a time averaging unit 211, an ensemble averaging unit 212, an inter-variable averaging unit 213, and an auxiliary variable calculation unit 214. In this case, the pseudo-Ising Hamiltonian generator 110 is omitted, and the pseudo-Ising Hamiltonian generator 110 operates in the same way as the pseudo-Ising Hamiltonian generator 110.

The auxiliary variable calculation device 21 of this embodiment calculates and outputs auxiliary variables that correct the pseudo-Ising Hamiltonian based on the results of the solution candidate search process of the Ising machine 22. As in Example 2, the auxiliary variables have the characteristic of suppressing variations in absolute values between variables.

In addition, the Ising machine 22 of this embodiment corrects the pseudo-Ising Hamiltonian based on the auxiliary variables and performs the solution candidate search process based on the corrected pseudo-Ising Hamiltonian.

The auxiliary variable calculation device 21 and the Ising machine 22 repeatedly perform each of the above-mentioned processes until the specified conditions are met.

Referring to Figure 7, the detailed operation of the components (211, 212, 213, 214) excluding 110 of the auxiliary variable calculation device 21 and the detailed operation of each component (121, 222, 923) of the Ising machine 22 will be described.

The time averaging unit 211 calculates the time average <σi>T of the pseudo variable _σi at each time for each variable index i (i=1,...,N, N is the number of variables) obtained in the solution candidate search process of the Ising machine 22 (S211). The time average is defined as < _σi > _{T ≡Σtp} (σi _,t ) when the obtainable variable information is discrete _σt , and as < _σi > _{T ≡q} (∫dtp( _σi (t))) when the _variable information can be obtained as a continuous function _σi (t). Here, p(x) and q(x) are functions set in advance.

Fig. 11 shows an example of the change over time in the value of the pseudo variable _σi output from the Ising machine when i = 1, 2. In the example shown in the figure, _σ1 approaches near -1.0 as time passes, and _σ2 approaches near +1.0 as time passes. Fig. 12 shows the processing of step S211 in the example shown in Fig. 11, i.e., the calculation processing of the time averages < _σ1 > _T and < _σ2 > _T .

The ensemble average unit 212 calculates an ensemble average <σ ^- _i > _T ≡1/LΣ<σ _i > T, which is the average of the time averages <σ i > _T for each variable index corresponding to each of the multiple solution candidate search processes performed by the Ising machine 22 (S212). Fig. 13 shows the calculation process of <σ _{- 1} > _T ≡1/LΣ<σ ₁ > _T and <σ ^- ₂ > _T ≡1/LΣ<σ ₂ > _T , which are the ensemble averages of the time averages <σ ₁ > _T and < ^σ ₂ > _T corresponding to each of the L solution _candidate search processes in the example of Fig. ₁₁ .

The inter-variable averaging unit 213 calculates the inter-variable average M≡1/NΣ _i <σ ^- _i > _T , which is the average between each variable index of the ensemble average <σ ^- _i > _T (S213). Fig. 13 shows the calculation process of the inter-variable average M≡1/2(<σ ^- ₁ > _T +<σ ^- ₂ > _T ) of the ensemble averages <σ ^- ₁ > _T and <σ ^- ₂ > _T in the example of Fig. 11.

The auxiliary variable calculation unit 214 calculates and outputs an auxiliary variable a i ≡ f(<σ ^- _i > T - _M ) based on the difference between the ensemble mean <σ ^- _i > _T and the mean between variables _M , and a function f(z) that satisfies f(z) ≥ 0 when z ≥ 0 and f(z) ≤ 0 when z ≤ 0 (S214). Note that as a heuristic for aligning the absolute values of the variables, the function form of f(z) is

13 shows the calculation process of the auxiliary variables a ₁ =f(<σ ⁻ ₁ > _T −M) and a ₂ =f(<σ ⁻ ₂ > _T −M) in the example of FIG.

The pseudo Ising Hamiltonian acquisition unit 121 of the Ising machine 22 acquires a pseudo Ising Hamiltonian K _ij (S121). The solution candidate search processing unit 222 executes a solution candidate search process based on the pseudo Ising Hamiltonian K' _ij =K _ij +a _i Δ _i corrected by the auxiliary variable a _i calculated by the above-mentioned processes (S211-S214) and the pseudo diagonal term Δ _i , and outputs a pseudo variable σ _i (S222).

The auxiliary variable calculation device 21, which has acquired the pseudo variable σ _i from the Ising machine 22, executes the above-described processing (S211-S214) again to output the auxiliary variable a _i .

The auxiliary variable calculation device 21 and the Ising machine 22 repeatedly execute the above-mentioned processing (S211-S214, S222) until the specified conditions are met.

The condition for stopping the repetitive processing can be set to, for example, "when the variance g(<σ ^- _i > _T , M) of the variables becomes smaller than a predetermined constant ε." The function g() is a function that represents the variance of the variables, and specific examples will be described later. For example, in the example of FIG. 11, the above processing (S211-S214, S222) is repeatedly executed until ε>g(<σ ^- _i > _T , <σ ^- ₂ > _T , M).

Alternatively, the condition for stopping the repetitive process can be set to "the solution process has been performed a predetermined number of times."

When the condition for stopping the iterative process is satisfied, the solution candidate output unit 923 of the Ising machine 22 outputs the value of the pseudo variable σ _i , which is a solution candidate for the problem K _ij (S923).

<Time average>
For example, the following definitions can be used for the time average:

1) <σ _i > _T ≡1/T|∫ ₀ ^T dtσ _i (t)|
2) <σ _i > _T ≡1/T∫ ₀ ^T dt|σ _i (t)|
3) <σ _i > _T ≡1/T∫ ₀ ^T dtσ _i ² (t)
In the solution process, there are variables that converge in the positive direction and variables that converge in the negative direction, so absolute values, squares, etc. are used as described above to eliminate the effect of sign differences in the time average.

<f(z)>
For example, the following functions can be used as f(z):

<Variation g(<σ ^- _i > _T ,M)>
As a specific formula for the variation g(<σ ⁻ _i > _T , M), for example, the following formula can be used.

1) g(<σ ^- _i > _T ,M)≡1/NΣ _i (<σ ^- _i > _T -M) ²
<Additional Notes>
The auxiliary variable calculation device of the present invention has, as a single hardware entity, for example, an input unit to which a keyboard or the like can be connected, an output unit to which an LCD display or the like can be connected, a communication unit to which a communication device (e.g., a communication cable) capable of communicating with an external device can be connected, a CPU (which may also include a central processing unit, cache memory, registers, etc.), memories such as RAM and ROM, an external storage device such as a hard disk, and buses connecting these input unit, output unit, communication unit, CPU, RAM, ROM, and external storage device so that data can be exchanged between them. If necessary, the hardware entity may also be provided with a device (drive) capable of reading and writing recording media such as a CD-ROM. A physical entity equipped with such hardware resources includes a general-purpose computer.

The external storage device of the hardware entity stores the programs required to realize the above-mentioned functions and the data required to process these programs (this is not limited to an external storage device; for example, the programs may be stored in ROM, which is a read-only storage device). In addition, data obtained by processing these programs is stored appropriately in RAM, external storage device, etc.

In a hardware entity, each program stored in an external storage device (or ROM, etc.) and the data required to process each program are loaded into memory as needed, and interpreted, executed, and processed by the CPU as appropriate. As a result, the CPU realizes the specified functions (each component represented as a "... unit," "... means," etc., above).

The present invention is not limited to the above-described embodiments, and modifications can be made as appropriate without departing from the spirit of the present invention. Furthermore, the processes described in the above embodiments may not only be executed chronologically in the order described, but may also be executed in parallel or individually depending on the processing capacity of the device executing the processes or as needed.

As mentioned above, when the processing functions of the hardware entities (devices of the present invention) described in the above embodiments are realized by a computer, the processing content of the functions that the hardware entities should have is described by a program. Then, by executing this program on a computer, the processing functions of the above hardware entities are realized on the computer.

The various processes described above can be implemented by loading a program that executes each step of the above method into the recording unit 10020 of the computer shown in Figure 14 and operating the control unit 10010, input unit 10030, output unit 10040, etc.

The program describing this processing can be recorded on a computer-readable recording medium. Examples of computer-readable recording media include magnetic recording devices, optical disks, magneto-optical recording media, and semiconductor memory. Specifically, for example, magnetic recording devices include hard disk drives, flexible disks, and magnetic tapes; optical disks include DVDs (Digital Versatile Discs), DVD-RAMs (Random Access Memory), CD-ROMs (Compact Disc Read Only Memory), and CD-Rs (Recordable)/RWs (Rewritable); magneto-optical recording media include MOs (Magneto-Optical discs); and semiconductor memories include EEP-ROMs (Electrically Erasable and Programmable-Read Only Memory).

This program may be distributed, for example, by selling, transferring, or lending portable recording media such as DVDs or CD-ROMs on which the program is recorded. Furthermore, this program may be distributed by storing it in a storage device of a server computer and transferring it from the server computer to other computers via a network.

A computer that executes such a program, for example, first stores the program recorded on a portable recording medium or transferred from a server computer in its own storage device. Then, when executing a process, the computer reads the program stored on its own recording medium and executes the process in accordance with the read program. Alternatively, the computer may read the program directly from a portable recording medium and execute the process in accordance with the program. Furthermore, each time a program is transferred from a server computer to the computer, the computer may execute the process in accordance with the received program. Alternatively, the server computer may not transfer the program to the computer, but may instead execute the process through a so-called ASP (Application Service Provider) service, which realizes the processing function simply by issuing execution instructions and obtaining the results. In this embodiment, the program includes information used for processing by a computer that is equivalent to a program (such as data that does not directly instruct the computer but has properties that define computer processing).

In addition, in this form, a hardware entity is configured by executing a specified program on a computer, but at least part of these processing contents may also be realized by hardware.

Claims (8)

a pseudo-variable replacement unit that replaces each variable of the Ising Hamiltonian with a pseudo-variable defined by a constant multiple of the sum of two or more dispersion variables to generate a pseudo-Ising Hamiltonian;
a pseudo-diagonal term generation unit that generates pseudo-diagonal terms that are positive/negative inversions of the sum of quadratic products of the distributed variables included in each of the pseudo variables. an auxiliary variable calculation device that generates a pseudo-Ising Hamiltonian by replacing each variable of the Ising Hamiltonian with a pseudo variable defined by a constant multiple of the sum of two or more distributed variables, generates pseudo-diagonal terms that are positive/negative inversion values of the sum of the quadratic products of the distributed variables included in each of the pseudo variables, outputs the pseudo-Ising Hamiltonian and the pseudo-diagonal terms to an Ising machine, calculates auxiliary variables that correct the pseudo-Ising Hamiltonian, and correct non-uniformity of the variables while maintaining a time evolution similar to that of the variables in the calculation process of the Ising machine , and outputs the auxiliary variables to the Ising machine;
a combination problem calculation system including the Ising machine that corrects the pseudo Ising Hamiltonian based on the auxiliary variables and executes a solution candidate search process based on the corrected pseudo Ising Hamiltonian. an auxiliary variable calculation device that generates a pseudo-Ising Hamiltonian by replacing each variable of the Ising Hamiltonian with a pseudo variable defined by a constant multiple of the sum of two or more distributed variables, generates pseudo-diagonal terms that are positive/negative inversion values of the sum of the quadratic products of the distributed variables included in each of the pseudo variables, outputs the pseudo-Ising Hamiltonian and the pseudo-diagonal terms to an Ising machine, calculates auxiliary variables that correct the pseudo-Ising Hamiltonian based on the result of a solution candidate search process of the Ising machine, and outputs the calculated auxiliary variables to the Ising machine;
the Ising machine correcting the pseudo Ising Hamiltonian based on the auxiliary variables and performing a solution candidate search process based on the corrected pseudo Ising Hamiltonian,
The auxiliary variable calculation device and the Ising machine are
A combination problem calculation system that repeatedly executes each process up to a specified number of times . An Ising machine that acquires auxiliary variables, a pseudo Ising Hamiltonian, and pseudo diagonal terms from an auxiliary variable calculation device, corrects the pseudo Ising Hamiltonian based on the acquired auxiliary variables, and performs a solution candidate search process based on the corrected pseudo Ising Hamiltonian,
The auxiliary variable calculation device
an Ising machine that generates a pseudo-Ising Hamiltonian by replacing each variable of an Ising Hamiltonian with a pseudo-variable defined as a constant multiple of the sum of two or more distributed variables, generates the pseudo-diagonal terms that are positive/negative inverted values of the sum of second-order products of the distributed variables included in each of the pseudo-variables, outputs the pseudo-Ising Hamiltonian and the pseudo-diagonal terms to the Ising machine, calculates the auxiliary variables that correct non-uniformity of the variables while maintaining a time evolution similar to that of the variables in the calculation process of the Ising machine, and outputs the auxiliary variables to the Ising machine. An Ising machine that repeatedly executes a process of acquiring auxiliary variables, a pseudo Ising Hamiltonian, and pseudo diagonal terms from an auxiliary variable calculation device, correcting the pseudo Ising Hamiltonian based on the acquired auxiliary variables, and executing a solution candidate search process based on the corrected pseudo Ising Hamiltonian, up to a predetermined number of times ,
The auxiliary variable calculation device
an Ising machine that generates a pseudo-Ising Hamiltonian by replacing each variable of an Ising Hamiltonian with a pseudo-variable defined as a constant multiple of the sum of two or more distributed variables, generates the pseudo-diagonal terms that are positive/negative inverted values of the sum of second-order products of the distributed variables included in each of the pseudo-variables, outputs the pseudo-Ising Hamiltonian and the pseudo-diagonal terms to the Ising machine, and calculates the auxiliary variables based on the results of a solution candidate search process of the Ising machine and outputs the auxiliary variables to the Ising machine. an auxiliary variable calculation device that generates a pseudo-Ising Hamiltonian by replacing each variable of an Ising Hamiltonian with a pseudo-variable defined as a constant multiple of the sum of two or more distributed variables, generates pseudo-diagonal terms that are positive/negative inverted values of the sum of the second-order products of the distributed variables included in each of the pseudo-variables, outputs the pseudo-Ising Hamiltonian and the pseudo-diagonal terms to an Ising machine, calculates auxiliary variables that correct the pseudo-Ising Hamiltonian, and correct non-uniformity of the variables while maintaining a time evolution similar to that of the variables in the calculation process of the Ising machine, and outputs the auxiliary variable calculation device to the Ising machine. an auxiliary variable calculation device that repeatedly executes the process of: generating a pseudo-Ising Hamiltonian by replacing each variable of an Ising Hamiltonian with a pseudo-variable defined as a constant multiple of the sum of two or more distributed variables; generating pseudo-diagonal terms that are positive/negative inverted values of the sum of second-order products of the distributed variables included in each of the pseudo-variables; outputting the pseudo-Ising Hamiltonian and the pseudo-diagonal terms to an Ising machine; calculating auxiliary variables that correct the pseudo-Ising Hamiltonian based on a result of a solution candidate search process of the Ising machine; and outputting the calculated auxiliary variables to the Ising machine, up to a predetermined number of times . A program that causes a computer to function as the auxiliary variable calculation device described in claim 6 or 7.