JP7829925B2 - Calculation method, calculation system, and program - Google Patents

Description

Application of Article 30, Paragraph 2 of the Patent Act January 17, 2020 IEICE Technical Research Report Vol. 121, No. 342 https://ken. ieice. org/ken/index/ieice-techrep-121-342. Publish as html

Applicable under Article 30, Paragraph 2 of the Patent Law. January 24, 2022. Online meeting URL: https://us02web.zoom.us/j/82741085453?pwd=TGhRUjMwNjQrSlpGTzVnbFVGRWZlZz09. Disclosed at the System and LSI Design Technology Research Meeting (held from January 24th to January 25th, 2022).

Application of Article 30, Paragraph 2 of the Patent Act March 1, 2020 Collection of lecture summaries for the 77th Annual Conference of the Physical Society of Japan (2022) https://jps2022s. gakkai-web. net/data/pdf/17aB19-05. Published as pdf

Applicable under Article 30, Paragraph 2 of the Patent Law. March 17, 2022. Online meeting URL: https://gakkai-web.net/p/jps/jps_t/mod2.php. This URL was made public at the 77th Annual Meeting of the Physical Society of Japan (2022) held on March 15, 2022 to March 19, 2022.

Article 30, Paragraph 2 of the Patent Act applies May 27, 2020 IEEE Transactions on Computers (Early Access) https://ieeexplore. ieee. Published at org/document/9783142

Applicable under Article 30, Paragraph 2 of the Patent Law. Published on May 30, 2022, on the Waseda University official website at https://www.waseda.jp/top/news/80999.

Applicable under Article 30, Paragraph 2 of the Patent Law. June 22, 2022. Online meeting URL: https://zoom.us/meeting/register/tJwpde2ppzIsG9ZnYSTXY-qjxivvQbGMkVk2. Publicly available at the ICTP Conference on Adiabatic Quantum Computation/Quantum Annealing (hosting AQC2022) (held from June 20, 2022 to June 24, 2022).

This invention relates to a computational method, computational system, and program for solving the Ising model.

Ising machines are attracting attention as hardware with the potential to efficiently solve combinatorial optimization problems. A combinatorial optimization problem is the problem of finding the combination of variables that minimizes or maximizes an objective function under multiple constraints. When using an Ising machine, a combinatorial optimization problem is transformed into an Ising problem. The Ising problem uses a format called the Ising model, which is given by multiple spin variables with values of +1 or -1. The Ising problem is the problem of finding the spin configuration that gives the ground state energy of the Hamiltonian (energy function) of the Ising model. Various methods for transforming combinatorial optimization problems into Ising problems have been proposed to date (see, for example, Patent Document 1).

When a constrained combinatorial optimization problem is formulated as an Ising problem, the Hamiltonian H is given by H = H _obj + H _c , where H _obj and H _c are the objective function and constraint term, respectively. H _c = 0 when the constraints are satisfied, and H _c > 0 when they are not satisfied. A solution that satisfies the constraints is called a feasible solution, and a solution that gives the ground energy is called a basis solution. The hardware of many Ising machines operates on the principle of single-spin-flip simulated annealing (SA) when searching for a basis solution. Here, a spin flip is the conversion of the spin variable value between +1 and -1.

For example, consider an Ising model consisting of two spin variables ( _σ₁ , _σ₂ ) whose Hamiltonian H is given by equation (1).

As shown in Figure 1, feasible solutions have lower energy than non-feasible solutions. Feasible solutions occur when ( _σ₁ , _σ₂ ) are (+1, -1) and (-1, +1), and non-feasible solutions occur when (-1, -1) and (+1, +1). Among the feasible solutions, (-1, +1), which gives the ground energy, is the ground solution, and (+1, -1) is a local solution. A local solution is a solution in which the energy increases when any spin variable is flipped. Flipping either spin variable of the local solution (+1, -1) results in a non-feasible solution, and flipping _σ₂ of the non-feasible solution (-1, -1) or flipping _σ₁ of (+1, +1) results in a ground solution.

In this system, a state change that results in lower energy (transition from a non-feasible solution to a feasible solution) is always accepted, while a state change that results in higher energy (transition from a local minimum to a non-feasible solution) is accepted probabilistically. This acceptance probability depends on temperature, being higher at high temperatures and lower at low temperatures. Therefore, when in a local minimum state, transitions to higher-energy solutions are less likely at low temperatures, leading to trapping in the local minimum and preventing the search for a ground solution. This results in a degradation of the Ising machine's performance.

To escape from local minima and transition between feasible solutions, there is a multi-spin flip technique that simultaneously flips multiple spin variables, as shown in Figure 2. In this regard, Non-Patent Literature 1 discusses the effectiveness of multi-spin flips that transition to the ground solution without passing through non-feasible solutions, and reports that this improves the performance of SA (Simulation Analysis).

Japanese Patent Publication No. 2020-64536

Mohammad Bagherbeik, Parastoo Ashtari, Seyed Farzad Mousavi, Kouichi Kanda, Hirotaka Tamura, Ali Sheikholeslami, "A Permutational Boltzmann Machine with Parallel Tempering for Solving Combinatorial Optimization Problems", in International Conference on Parallel Problem Solving from Nature, 2020, pp. 317-331.

However, since existing Ising machines operate on a single-spin flip principle, implementing multi-spin flips in an Ising machine would require modifying its operating principle, which is extremely difficult.

This invention has been made in view of the above-mentioned problems, and aims to provide a calculation method, a calculation system, and a program that enable the implementation of multi-spin flips in an Ising machine.

The calculation method according to the present invention is a calculation method for solving the Ising model, and involves: (a) calculating the Hamiltonian of an Ising model having a predetermined number of spin variables from a constrained combinatorial optimization problem using a classical computer; (b) randomly selecting a first spin variable from the number of spin variables, setting a predetermined proportion of spin variables other than the first spin variable as the second spin variable, merging the second spin variable with the first spin variable based on a provisional solution of the Ising model to eliminate the second spin variable from the Hamiltonian, thereby calculating a deformed Hamiltonian; (c) obtaining a solution for the deformed Hamiltonian using an Ising machine; and (d) obtaining the solution to the Ising model by calculating the value of the second spin variable from the solution obtained by the Ising machine using a classical computer.

The computational system according to the present invention is a computational system for solving the Ising model, comprising: a classical computer having a processor that calculates the Hamiltonian of an Ising model having a predetermined number of spin variables from a constrained combinatorial optimization problem, randomly selects a first spin variable from the number of spin variables, sets a predetermined proportion of spin variables other than the first spin variable as a second spin variable from the number of spin variables, and calculates a deformed Hamiltonian by merging the second spin variable with the first spin variable based on a provisional solution of the Ising model and eliminating the second spin variable from the Hamiltonian; and an Ising machine that finds a solution for the deformed Hamiltonian. The processor finds the solution to the Ising model by calculating the value of the second spin variable from the solution obtained by the Ising machine.

The program according to the present invention is a program that causes a classical computer to execute a computational method for solving the Ising model in conjunction with an Ising machine. The program calculates the Hamiltonian of an Ising model having a predetermined number of spin variables from a constrained combinatorial optimization problem, randomly selects a first spin variable from the multiple spin variables, sets a predetermined proportion of the spin variables other than the first spin variable as the second spin variable, and calculates a deformed Hamiltonian by merging the second spin variable with the first spin variable based on a provisional solution of the Ising model, thereby eliminating the second spin variable from the Hamiltonian. Finally, it calculates the value of the second spin variable from the solution obtained by the Ising machine using the deformed Hamiltonian, thereby obtaining the solution to the Ising model.

According to this invention, by deforming the Hamiltonian through the merging of spin variables in the Ising model, a process equivalent to a multi-spin flip can be realized with a single-spin flip.

This is a schematic diagram illustrating the simulated annealing (SA) of a single-spin flip, which is the operating principle of an Ising machine. This is a schematic diagram to explain multispin flips. This block diagram shows the configuration of the calculation system according to this embodiment. Figure 3 is a block diagram showing the hardware configuration of a classic computer. This is a conceptual diagram illustrating the deformation of energy terrain using the merge method. This is a schematic diagram illustrating an example of the energy landscape of a two-spin Ising model. Figure 6A is a schematic diagram representing the deformed energy landscape obtained by merging the spin parameters of the Ising model. This is a schematic diagram illustrating an example of the energy landscape of a four-spin Ising model. Figure 7A is a schematic diagram representing the deformed energy landscape obtained by merging the spin parameters of the Ising model. This flowchart shows the calculation method according to this embodiment.

The embodiments of the present invention will be described below with reference to the drawings.

<Calculation System>
First, the configuration of the computing system of this embodiment will be described. As shown in Figure 3, the computing system 10 of this embodiment comprises a classical computer 20 and an Ising machine 30 connected to the classical computer 20. The classical computer 20 is a von Neumann type computer such as a personal computer.

The Ising machine 30 is a well-known Ising machine, such as a D-Wave 2000Q machine, a CMOS annealing machine, or a Digital Annealer (registered trademark).

As shown in Figure 4, the classical computer 20 comprises a processor 202, memory 204, storage device 206, input unit 208, display 210, and I/F 212, and these devices are connected via a bus.

The processor 202 includes a Central Processing Unit (CPU) and other components, and executes various processes according to the programs stored in the memory 204 and storage device 206. Details of the calculation methods performed by the processor 202 will be described later (see Figures 5 to 8).

Furthermore, instead of a general-purpose computer such as a CPU, a dedicated computer such as an Application Specific Integrated Circuits (ASIC) or Field Programmable Gate Array (FPGA) for executing the calculation method of this embodiment may be used as the processor 202.

Memory 204 comprises Read Only Memory (ROM) and Random Access Memory (RAM). ROM stores boot programs such as the BIOS. When the processor 202 reads a program stored in ROM or a program stored in storage device 206, these programs are loaded into RAM.

The storage device 206 has a non-temporary computer-readable storage medium and stores a program for executing the calculation method of this embodiment, data necessary for program execution, and the like. Examples of computer-readable storage media include hard disk drives (HDDs), solid-state drives (SSDs), and optical discs.

Furthermore, the program executed by processor 202 may be stored in another computer connected via a network, and processor 202 may read the program from the other computer via I/F 212.

The input unit 208 has input devices such as a mouse and keyboard. The display 210 is a display such as a Liquid Crystal Display (LCD) and displays the results of processing performed by the processor 202.

I/F212 is an interface for connecting the classical computer 20 to a network such as a Local Area Network (LAN), Wide Area Network (WAN), and/or the Internet.

<Calculation method>
Next, the calculation method of this embodiment will be described with reference to Figures 5 to 8. In this embodiment, in order to realize multi-spin flips in the Ising machine 30, a merging method is used to deform the energy landscape of the Ising model by merging at least some of the spin variables of the Ising model, as shown in Figure 5. This makes the single-spin flip in the deformed Hamiltonian equivalent to the multi-spin flip in the original Hamiltonian.

The merging method will be explained below using examples of two-spin and four-spin Ising models.

As an Ising model for a two-spin system, we consider an Ising model (hereinafter referred to as Ising model I) that gives the same Hamiltonian _H1 ( _σ1 , _σ2 ) as equation (1) above. Ising model I has a one-hot constraint that satisfies the constraint when one of _σ1 and _σ2 is +1 and the other is -1. Figure 6A shows the energy landscape of _H1 ( _σ1 , _σ2 ). Ising model I has a local solution (+1, -1) with an energy value of -2 and a base solution (-1, +1) with an energy value of -4. The remaining non-feasible solutions are (-1, -1) and (+1, +1), which give energy values of 20 and 14, respectively. In Ising model I, a double spin flip is required to transition between feasible solutions.

Now, assume we are in a local optimum of _H₁ ( _σ₁ , _σ₂ ). Since _σ₁σ₂ = -1 in the local optimum, we can use _σ₂ = _-σ₁ to merge _σ₂ with _σ₁ and eliminate _σ₂ from _H₁ ( _σ₁ , _σ₂ ), which gives us the transformed Hamiltonian _{H₁ ′} ( _σ₁ ) as shown in equation (2).

_H1 '( _σ1 ) is independent of the merged spin variable _σ2 . Figure 6B shows the energy landscape of _H1 '( _σ1 ). In the original _H1 ( _σ1 , _σ2 ), there was an energy barrier between the local solution and the ground solution, but in H1 _' ( _σ1 ), the energy barrier has disappeared. When _H1 '( _σ1 ) is input to the Ising machine 30, the ground solution of _H1 '( _σ1 ) can be found with a single spin flip. In _H1 '( _σ1 ), the energy value is -2 when _σ1 = +1 and the energy value is -4 when _σ1 = -1, so _σ1 = -1 is the ground solution. That is, in _H1 '( _σ1 ), _σ1 = +1 is no longer a local solution, and a single spin flip transitions to the ground solution _σ1 = -1.

Next, we find the value of the eliminated _σ² from _σ² = _-σ² . From the basis solution _σ² = -1 of _H₁ ′( _σ² ), we obtain ( _σ² , _σ² ) = (-1, +1), and the energy function takes its minimum value of -4. Therefore, ( _σ² , _σ² ) = (-1, +1) is the basis solution of the original _H₁ ( _σ² ). Thus, the single spin flip from _σ² = +1 to _σ² = -1 in _H₁ ′( _{σ² )} is equivalent to the double spin flip from ( _σ² , _σ² ) = ( ₊₁ , -1) to ( _σ² , _σ² ) = (-1, +1) in the original _H₁ ( _σ² ).

Next, we consider the Ising model of a four-spin system that gives the Hamiltonian _H2 ( _σ1 , _σ2 , _σ3 , _σ4 ) in equation (3) (hereinafter referred to as Ising model II).

The Ising model II has _a one-hot constraint that satisfies the constraints when one spin variable is +1 and the other spin variable is -1 for { _σ₁ , _σ₂ }, { _σ₃ , _{σ₴ }} , { _σ₁ , _σ₃ }, and {σ₂, σ₴}. Figure 7A shows the energy landscape of _H₂ ( _σ₁ , _σ₂ , _σ₃ , σ _₴ ). The Ising model II has a local solution (-1, +1, +1, -1) that gives an energy value of +1 and a base solution (+1, -1, -1, +1) that gives an energy value of -1. The remaining non-feasible solutions are (+1, +1, +1, -1), (+1, -1, +1, -1) and (+1, -1, +1, +1) that give a large energy value of 799. Four spin flips are required to transition between feasible solutions in the Ising model II.

Let's assume we are currently at a local optimum of _H₂ ( _σ₁ , _σ₂ , _σ₃ , _σ₄ ). Of the four spin variables, let σ₁ be the spin variable used as the criterion for merging (hereinafter referred to as the first spin variable), and let _σ₂ , _σ₃ , and _σ₄ be the spin variables merged into _{σ₁ (} hereinafter referred to as the second spin variables). In the local minimum, _σ₁σ₂ = _-1 , _σ₁σ₃ = -1, and _σ₁σ₄ = +1. Therefore, by merging σ₂, _σ₃ , and _σ₄ with σ₁ using _σ₂ = _-σ₁ , _σ₃ = _-σ₁ , and _σ₄ = _{σ₁ ,} we can eliminate _σ₂ , _σ₃ , and _σ₄ from _{H₂ ( σ₁} , _σ₂ , _σ₃ , _σ₄ ), and obtain the transformed Hamiltonian _{H₂ '} ( _{σ₁ )} as shown in equation (4).

_H2 '( _σ1 ) is independent of the merged second spin variables _σ2 , _σ3 , and _σ4 . Figure 7B shows the energy landscape of _H2 '( _σ1 ). In the original _H2 ( _σ1 , _σ2 , _σ3 , _σ4 ), there was an energy barrier between the local minima and the ground solution, but in _H2 '( _σ1 ), the energy barrier has disappeared. When _H2 '( _σ1 ) is input into the Ising machine 30, the ground solution of _H2 '( _σ1 ) can be found using a single spin flip. In _H2 '( _σ1 ), the energy value is +1 when _σ1 = -1, and the energy value is -1 when _σ1 = +1, so _σ1 = +1 is the ground solution. In other words, in _H2 '( _σ1 ), _σ1 = -1 is no longer a local solution, and a single spin flip transitions to the base solution _σ1 = +1.

Next, we use the values of _σ² = _-σ₁ , _σ₃ = _-σ₁ , and _σ₄ = _σ₁ obtained by merging to find the value of the second spin variable. From the basis solution _σ₁ = +1 of _H₂ '( _σ₁ ), we obtain ( _σ₁ , _σ₂ , _σ₃ , _σ₄ ) = (+1, -1, -1, +1), and the energy function takes its minimum value of -1. Therefore, ( _σ₁ , _σ₂ , _σ₃ , _σ₄ ) = (+1, -1, -1, +1) is the basis solution of the original _H₂ ( _σ₁ , _σ₂ , _σ₃ , _σ₄ ). Thus, a single spin flip from _σ1 = -1 to _σ1 = +1 in _H2 '( _σ1 ) is equivalent to a _four -spin flip from ( _σ1 , _σ2 , _σ3 , _σ4 ) = (-1, ₊₁ , +1, -1) to ( _σ1 , _σ2 , _σ3 , _σ4 ) = (+1, -1, -1, +1) in the original H2( _σ1 , σ2 _, σ3, _σ4 ).

In the examples of the two-spin and four-spin Ising models mentioned above, all remaining spin variables were merged with one spin variable. However, in actual Ising models, the number of spin variables is very large. Therefore, it is possible to probabilistically determine which second spin variable is merged, so that only a portion of all spin variables (e.g., 30%) are merged. It is also possible for the user to specify the second spin variable. In simulated annealing (SA), even if an energy barrier remains, at high temperatures, the system probabilistically transitions to a solution with higher energy, potentially allowing it to overcome the energy barrier.

Although we have illustrated the merging method for two-spin and four-spin Ising models, the merging method can be applied to any Ising model consisting of N spin variables. In general, the Hamiltonian H of an Ising model consisting of N spin variables _σi (i ∈ {1, 2, ..., N}) is defined as shown in equation (5).
Here, J _ij is the interaction coefficient between σ _i and σ _j , h _i is the external magnetic field coefficient of σ _i , and H ₀ is a constant. J _ij is symmetric (J _ij = J _ji ), and its diagonal components are zero (J _ii = 0).

For the Ising model in equation (5), we can derive the theorem for the merge method as follows.
<Theorem> For all i ∈ {1, 2, ..., N}, we define _mi and _si as parameters that provide information about the set of spin variables that perform multi-spin flips, as shown in equation (6).
At this point, the Hamiltonian H ^M of the Ising model consisting of N spin variables ({s _i } _i=1 ^N , {m _i } _i=1 ^N ; H) is obtained as shown in equation (7).
Here, J _ij ^M , _hi ^M , and H ₀ ^M satisfy equations (8), (9), and (10), respectively.

In this case, for all i, the state that satisfies σ _i σ _mi = s _i , then H ^M ({s _i } _i=1 ^N , {mi _i } _i=1 ^N ; H) and H take the same energy value, as shown in equation (11).

H ^M ({s _i } _i=1 ^N , {m _i } _i=1 ^N ; H) represents the deformed Hamiltonian obtained by the merge method. This theorem means that the energy value does not change even when the Hamiltonian is deformed in the merge method. Since the spin variable takes a value of +1 or -1, we obtain σ _{i = s i} σ _mi = s _i . Using this relationship, we can eliminate σ _i with _i that satisfies _mi ≠ i from H in equation (5) to obtain H ^M ({s _i } _i=1 ^N , {m _i } _i=1 ^N ; H) in equation (7).

Next, the flow of the calculation method executed by the calculation system 10 will be explained with reference to the flowchart shown in Figure 8. The calculation method in this embodiment is a hybrid algorithm that incorporates the merge technique described above into the SA.

First, the classical computer 20 calculates the Hamiltonian _Horg of the Ising model from a constrained combinatorial optimization problem (step 802), and sets the initial solution (provisional solution) of the Ising model and the initial temperature of SA (e.g., 100 degrees) (step 804).

Next, the classical computer 20 randomly selects a first spin variable from all the spin variables of the Ising model to serve as the basis for merging, and sets a predetermined percentage of the spin variables other than the first spin variable (for example, 30% of all spin variables) as the second spin variable. Then, based on the current provisional solution, the classical computer 20 merges the second spin variable with the first spin variable and eliminates the second spin variable from the original Hamiltonian _Horg to obtain a modified Hamiltonian H' (step 806). The modified Hamiltonian H' is input into the Ising machine 30.

The Ising machine 30 finds a solution for the deformed Hamiltonian H' and updates the solution (step 808). Next, the classical computer 20 finds a new provisional solution for the Ising model by calculating the value of the second spin variable that was eliminated in the merge in step 806 from the solution obtained by the Ising machine 30 (step 810). Then, the classical computer 20 returns the Hamiltonian to the original H _org (step 812).

Next, the classical computer 20 lowers the temperature in SA by a predetermined temperature interval (step 814) and determines whether the current temperature has reached a preset final temperature (e.g., 1 degree) (step 816). If the current temperature has not reached the final temperature (step 816; NO), the process returns to step 806, and steps 806-814 are repeated. By repeating steps 806-814 until the final temperature is reached, the provisional solution gradually approaches the optimal solution. On the other hand, if the current temperature reaches the final temperature (step 816; YES), the most recently obtained provisional solution is determined as the basis solution of the Ising model, and the calculation method of this embodiment ends.

Thus, by deforming the Hamiltonian of the Ising model using a merge method and obtaining a solution for the deformed Hamiltonian using the Ising machine 30, a process equivalent to a multi-spin flip can be realized with a single-spin flip. Therefore, a multi-spin flip can be implemented without changing the operating principle (single-spin flip) of the Ising machine 30, thereby improving the performance of the Ising machine 30.

To evaluate the calculation method using the merge technique of this embodiment, we applied the method to the quadratic knapsack problem (QKP), which is an NP-hard problem. Compared to a calculation method without the merge technique, we succeeded in reducing the residual energy (magnitude of error from the optimal value) by an average of 68%. Similarly, when we applied the calculation method of this embodiment to the quadratic assignment problem (QAP), we were able to reduce the residual energy by an average of 15%.

Furthermore, the present invention is not limited to the embodiments described above, and various modifications are possible without departing from the spirit of the invention. Other embodiments and modifications made by those skilled in the art are also included in the present invention.

10 Computing System 20 Classical Computer 30 Ising Machine 202 Processor 204 Memory 206 Storage Device 208 Input Unit 210 Display 212 I/F

Claims (4)

A computational method for solving the Ising model,
Classical computers,
(a) Compute the Hamiltonian of an Ising model with a given number of spin variables from a constrained combinatorial optimization problem,
(b) Randomly select a first spin variable from the plurality of spin variables, set a predetermined proportion of spin variables other than the first spin variable from the plurality of spin variables as a second spin variable, and calculate the deformed Hamiltonian by merging the second spin variable with the first spin variable based on the provisional solution of the Ising model and eliminating the second spin variable from the Hamiltonian.
Using the Ising machine,
(c) Find the solution for the modified Hamiltonian,
According to the aforementioned classical computer,
(d) A method for obtaining the solution of the Ising model by calculating the value of the second spin variable from the solution obtained by the Ising machine. The aforementioned classical computer sets the initial temperature in simulated annealing, and after processes (b) to (d), lowers the temperature.
The calculation method according to claim 1, wherein the basis solution of the Ising model is obtained by repeating the processes (b) to (d) until a predetermined final temperature is reached. A computational system for solving the Ising model,
A classical computer having a processor that calculates the Hamiltonian of an Ising model having a predetermined number of spin variables from a constrained combinatorial optimization problem, randomly selects a first spin variable from the plurality of spin variables, sets a predetermined proportion of spin variables other than the first spin variable as second spin variables from the plurality of spin variables, and calculates a deformed Hamiltonian by merging the second spin variables with the first spin variables based on a provisional solution of the Ising model and eliminating the second spin variables from the Hamiltonian, and
An Ising machine for finding a solution to the aforementioned deformed Hamiltonian,
Equipped with,
The aforementioned processor,
A computational system for obtaining the solution to the Ising model by calculating the value of the second spin variable from the solution obtained by the Ising machine. This is a program that allows a classical computer to execute a computational method for solving the Ising model in conjunction with an Ising machine.
We compute the Hamiltonian of an Ising model with a given number of spin variables from a constrained combinatorial optimization problem.
A first spin variable is randomly selected from the aforementioned plurality of spin variables, a predetermined proportion of spin variables other than the first spin variable are set as the second spin variable, and the second spin variable is merged with the first spin variable based on the provisional solution of the Ising model to eliminate the second spin variable from the Hamiltonian, thereby calculating the deformed Hamiltonian.
A program for causing a process to obtain a solution to the Ising model by calculating the value of the second spin variable from the solution obtained by the Ising machine for the modified Hamiltonian.