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

Description

Article 30, Paragraph 2 of the Patent Act applies: https://ieeexplore. ieee. org/document/9664360, December 28, 2021 https://www. Waseda. jp/top/news/77751, January 11, 2020

The present invention relates to a calculation method, calculation system, and program for solving the Ising model.

A technique is known in which a combinatorial optimization problem, which involves selecting the best combination from a large number of combinations, is converted into an Ising model (or a quadratic unconstrained binary optimization (QUBO) model, which is equivalent to the Ising model), and then solved using an Ising machine. Because many hardware constraints exist on the spin variables of the Ising model that can be input to an Ising machine, it is not possible to input an Ising model with an arbitrary number of spin variables into an Ising machine. For example, the D-Wave 2000Q machine has approximately 2,000 qubits, but when all of the variables are interconnected, it can only handle a maximum of 64 variables in the QUBO model.

To solve this problem, a hybrid method has been proposed that uses a classical computer and an Ising machine in combination to extract a partial QUBO (subQUBO) model that is small enough to fit on the Ising machine from the original QUBO model with many spin variables, and then optimize the original QUBO model (see, for example, Non-Patent Document 1).

M. Booth and S. P. Reinhardt, “Partitioning optimization problems for hybrid classical / quantum execution technical report,” 2017.

However, conventional hybrid methods are heuristic and not necessarily theoretically backed. Furthermore, in conventional hybrid methods, subQUBO models are extracted from fixed solutions, so the extracted subQUBO models also tend to be fixed. Therefore, there is a problem in that it is not possible to expect to obtain a globally optimal solution using conventional hybrid methods.

The present invention was made in consideration of the above-mentioned problems, and aims to provide a computational method, computational system, and program that can efficiently and globally obtain optimal solutions to Ising models using a classical computer and an Ising machine, based on theoretical evidence.

The computational method of the present invention is a computational method for solving an Ising model having a predetermined number of variables, and involves using a classical computer to (a) generate multiple solution instances that are multiple quasi-base solutions of the Ising model and register them in an instance pool, (b) calculate the variability of the values of the multiple variables in the multiple solution instances, (c) extract from the multiple variables a number of variables that can be processed by the Ising machine in descending order of variability, and construct a partial Ising model consisting only of the extracted variables using one solution instance randomly selected from the multiple solution instances as a tentative solution of the Ising model, (d) obtain a base solution of the partial Ising model using the Ising machine, and (e) obtain a new solution instance by incorporating the base solution into the tentative solution of the Ising model using a classical computer and add the new solution instance to the instance pool, and (f) select from the instance pool the solution instance that minimizes the energy of the Ising model as the best solution.

The computational system of the present invention is a computational system for solving an Ising model having a predetermined number of variables, and includes a classical computer with a processor that generates multiple solution instances, which are multiple quasi-base solutions of the Ising model, and registers them in an instance pool; calculates the variability of the values of the multiple variables in the multiple solution instances; extracts from the multiple variables a number of variables that can be processed by the Ising machine in descending order of variability; and uses one solution instance randomly selected from the multiple solution instances as a tentative solution of the Ising model to construct a partial Ising model consisting only of the extracted variables; and an Ising machine that finds a base solution for the partial Ising model. The processor finds a new solution instance by incorporating the base solution into the tentative solution of the Ising model, adds the new solution instance to the instance pool, and selects from the instance pool the solution instance that minimizes the energy of the Ising model as the best solution.

The program of the present invention is a program for causing a classical computer to execute, in conjunction with an Ising machine, a calculation method for solving an Ising model having a predetermined number of variables, and executes the following processes: (a) generating multiple solution instances that are multiple quasi-base solutions of the Ising model and registering them in an instance pool; (b) calculating the variability of the values of the multiple variables in the multiple solution instances; (c) extracting from the multiple variables a number of variables that can be processed by the Ising machine in descending order of variability; constructing a partial Ising model consisting only of the extracted variables using one solution instance randomly selected from the multiple solution instances as a tentative solution of the Ising model; (d) obtaining a new solution instance by incorporating the base solutions obtained using the Ising machine for the constructed partial Ising model into the tentative solution of the Ising model; (e) adding the new solution instance to the instance pool; and (f) selecting from the instance pool the solution instance that minimizes the energy of the Ising model as the best solution.

According to the present invention, by constructing a partial Ising model from multiple solution instances of the Ising model based on theoretical evidence, it is possible to efficiently obtain an optimal solution for the Ising model globally.

FIG. 1 illustrates a general hybrid annealing algorithm. FIG. 1 is a schematic diagram illustrating an example of a QUBO model. FIG. 3 is a schematic diagram showing an example of a provisional solution of the QUBO model of FIG. 2. FIG. 4 is a schematic diagram showing an example of extracting a subQUBO model from the QUBO model of FIG. 3 . FIG. 4B is a schematic diagram showing a basic solution obtained by optimizing the subQUBO model of FIG. 4A using an Ising machine. 4B is a schematic diagram showing a new tentative solution obtained by incorporating the basic solution of the subQUBO model shown in FIG. 4B into the tentative solution of FIG. 3 . FIG. 4 is a schematic diagram showing an example of extracting another subQUBO model from the QUBO model of FIG. 3 . FIG. 5B is a schematic diagram showing the base solution (optimal solution) of the original QUBO model obtained through optimization of the subQUBO model of FIG. 5A. 1 is a block diagram showing the configuration of a hybrid computing system according to an embodiment of the present invention. FIG. 7 is a block diagram showing the hardware configuration of the classical computer shown in FIG. 6. FIG. 1 is a diagram showing an algorithm of a calculation method (hybrid annealing) according to the present embodiment. FIG. 1 is a schematic diagram illustrating the generation of N _I solution instances. 1 is a table showing an example of the variability of values for each binary variable across N _S solution instances (N _S <N _I ).

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

<QUBO model>
First, the QUBO model will be described. When the Ising model is expressed by an energy function up to a quadratic expression using binary variables that take two values, 0 and 1, it is called a QUBO model. The energy function (Hamiltonian) f(X) of the QUBO model is expressed as in Equation (1) using binary variables x _i (x _i = 0 or x _i = 1).
Here, X = {x ₁ , x ₂ , ...} is a set of binary variables, a _i is an external magnetic field coefficient representing the force acting on the binary variable x _i , and b _ij is an interaction coefficient representing the weight of the connection between x _i and x _j .

The QUBO model is stable in the lowest energy state (ground state). A solution to the QUBO model is one combination of binary variables, and the base solution of the QUBO model is the combination of binary variables that minimizes f(X). The value of f(X) for a given combination of binary variables is called the objective value.

In general, combinatorial optimization problems can be mapped to the problem of finding a combination of binary variables that minimizes f(X) in equation (1).

<General method>
Next, with reference to the algorithm shown in FIG. 1, a general method (hybrid annealing) for searching for a ground state or a quasi-ground state of a QUBO model having a size larger than the hardware of an Ising machine will be described.

In the QUBO model expressed by equation (1), X = { _x1 , _x2 , ..., _xn } is a set of binary variables. The set X includes n binary variables, and the size of this QUBO model is n. The number of binary variables that can be processed by the Ising machine (the hardware size of the Ising machine) is m (<n).

First, X is initialized by randomly setting each binary variable of X to 0 or 1 (line 2 in Figure 1), and the initialized X is designated as the tentative solution (X _best ) (line 3). Next, using this tentative solution, m binary variables are extracted from the n binary variables of the QUBO model to construct a subQUBO model (partial Ising model) (line 5). At this time, as described below, the interaction coefficients between the binary variables of the subset S (⊂ X) extracted as the subQUBO model and the binary variables of the difference set X-S are incorporated into the external magnetic field coefficients of the subQUBO model.

Next, the Ising machine optimizes the subQUBO model to obtain a base solution (m binary variables), and this base solution is incorporated into the current tentative solution of the original QUBO model to obtain a quasi-base solution X of the original QUBO model (line 6). This quasi-base solution X is designated as a new tentative solution _Xbest (line 7). At this time, the (n-m) binary variables in the difference set X-S are fixed to the values of the tentative solution. The process on lines 4 to 6 is repeated until _Xbest converges. In this way, by repeatedly obtaining the base solution of a subQUBO model of size m using an Ising machine, the base solution of the original QUBO model of size n can be obtained. Note that in FIG. 1, processes other than the optimization on line 6 are executed by a classical computer such as a personal computer.

If the set of binary variables of the QUBO model is X = { _x1 , _x2 , ..., _xn }, the tentative solution is _Xt = { _x1 ', _x2 ', ..., _xn '}, and the subset extracted as the subQUBO model is S(⊂X), the Hamiltonian f(X) of the QUBO model shown in equation (1) can be rewritten as the Hamiltonian _fs (S) of the subQUBO model as shown in equation (2).

The first term c _i on the right-hand side of equation (2) is defined as in equation (3). In equation (3), a _i and _bij are constants, and x _j ' is fixed as the value of the provisional solution in the difference set X-S, so c _i is a constant and can be considered as the external magnetic field coefficient of the subQUBO model. In this way, using the provisional solution x _j ' in the difference set X-S, the interaction coefficient bij between the binary variables of subset S and the binary variables of the difference set X- _S is incorporated into the external magnetic field coefficient c _i of the subQUBO model.

The third term const on the right side of equation (2) is a constant term defined as in equation (4).

Next, a specific example of the algorithm in Figure 1 will be described. Figure 2 shows an example of a QUBO model of size n. The set of binary variables in the QUBO model is X = { _x1 , _x2 , ..., _x5 }, the tentative solution is _Xt = { _x1 ', _x2 ', ..., _x5 '}, and the hardware size m of the Ising machine is 3. The QUBO model in Figure 2 has _a1 = -3, _a2 = -4, _a3 = 1, _a4 = 4, _a5 = -4, _b12 = -1, _b13 = -2, _b14 = 0, _b15 = 2, _b23 = 2, _b24 = -2, _b25 = -1, _b34 = -5, _b35 = 2, and _b45 = -3.

An example of a provisional solution for the QUBO model in Figure 2 is shown in Figure 3. The provisional solution shown in Figure 3 is _x1 ' = _x2 ' = _x3 ' = 1, _x4 ' = _x5 ' = 0, and the target value is -7. As shown in Figure 4A, when the subset S = { _x1 , _x3 , _x5 } is extracted as a subQUBO model from the QUBO model in Figure 3, the external magnetic field coefficients _c1 , _c3 , and _c5 of the subQUBO model are -4, 3, and -5, respectively, according to equation (3). In this case, each binary variable in the difference set X-S = { _x2 , _x4 } takes a fixed value given by the provisional solution, with _x2 = _x2 ' = 1 and _x4 = _x4 ' = 0.

When the subQUBO model shown in Fig. 4A is optimized using an Ising machine, a base solution ( _x1 = 1, _x3 = 0, _x5 = 1) of the subQUBO model is obtained as shown in Fig. 4B. By incorporating the base solution of the subQUBO model (Fig. 4B) into the current tentative solution of the original QUBO model (Fig. 3), a new tentative solution of the original QUBO model can be obtained as shown in Fig. 4C.

<Theoretical background of the calculation method of this embodiment>
Next, the theoretical background of the calculation method of this embodiment will be described. The provisional solution shown in FIG. 4C gives a target value of -11, but is not the base solution of the QUBO model in FIG. 2. The QUBO model in FIG. 2 becomes the base solution when all binary variables have a value of 1, and its target value is -14. In order to efficiently obtain the base solution of the original QUBO model, it is important how to extract a subQUBO model from the original QUBO model.

For example, as shown in Figure 5A, when a subset S = { _x3 , _x4 , _x5 } is extracted as a subQUBO model from the QUBO model that provides the provisional solution of Figure 3, the base solution of this subQUBO model is _x3 = _x4 = _x5 = 1. As a result, as shown in Figure 5B, the base solution of the original QUBO model ( _x1 = _x2 = _x3 = _x4 = _x5 = 1) can be obtained. Similarly, when a subset S = { _x2 , _x4 , _x5 } is extracted as a subQUBO model, the base solution of the original QUBO model can be obtained. Here, among the binary variables that make up the provisional solution of Figure 3, the binary variables that differ from the base solution of Figure 5B are _x4 and _x5 . Therefore, if the subset S extracted as the subQUBO model contains binary variables x ₄ and x ₅ that are different from the base solution, it can be inferred that the base solution of the original QUBO model can be obtained.

From the above example, the following theorem can be derived: "When all binary variables that make up a QUBO model have values that differ from the base solutions of the QUBO model and are extracted as subQUBO models, the base solutions of the extracted subQUBO model provide the base solutions of the original QUBO model."

To generalize this theorem, let X = { _xi } be the set of binary variables in the QUBO model, S(⊂X) be the subset extracted as the subQUBO model, _Xt = { _xi '} be the tentative solution of the original QUBO model, X ^* = { _xi ^* } be the base solution of the original QUBO model, _Xs ^* = { _si ^* } be the base solution of the subQUBO model for _xiεS , and N be the set of binary variables that have values different from the base solutions of the QUBO model. In this case, the above theorem can be generalized as follows: when S⊇N, _fs ( _Xs ^* ) = f(X ^* ).

Next, we will prove the above theorem. From equation (2), the target value f _s (X _s ^* ) of the ground state of the subQUBO model is expressed as equation (5).

Similarly, from equation (1), the target value f(X ^* ) of the ground state of the QUBO model is expressed as equation (6).

Since S ⊇ N, when x _i '∈X-S, x _i '∈X-N. When _{x i} '∈X-N, x _i ' = x _i ^* . In other words, when the binary variable (provisional variable) x _i ' of the provisional solution belongs to the difference set X-N, the value of the provisional variable x _i ' matches the value of the binary variable x _i ^* of the base solution of the QUBO model. Therefore, the following equations (7) to (9) hold.

Therefore, the target value f _s (X _s ^* ) of the ground state of the subQUBO model is expressed by equation (10).

From equations (6) and (10), if _fs ( _Xs ^* )>f(X ^* ), then _Xs ^* = { _si ^* } does not provide a basic solution of the subQUBO model, which contradicts the assumption that _Xs ^* is a basic solution of the subQUBO model. If _fs ( _Xs ^* )<f(X ^* ), then X ^* = { _xi ^* } does not provide a basic solution of the QUBO model, which contradicts the assumption that X ^* is a basic solution of the QUBO model. Therefore, _fs ( _Xs ^* ) = f(X ^* ). □

<Outline of the method for extracting subQUBO models>
Next, we will explain the flow of the subQUBO model extraction method. To extract a subQUBO model based on the above theorem, N _I (≧3) quasi-basis solutions (hereinafter referred to as solution instances) of the QUBO model are generated. These solution instances can be obtained by running any QUBO solver on a classical computer. Once N _I solution instances are obtained, the following two steps are performed.

Step 1: Focus on a specific binary variable x _i among the n binary variables x _i (x _i = 0 or x _i = 1) of the QUBO model, and count the number of solution instances where x _i = 1 among the N _I solution instances. This counting is performed for each binary variable of the original QUBO model.

Step 2: When the count of a binary variable x _i is N _I /2, the value of that binary variable x _i has the same number of 0s and 1s and has the maximum variation. When the count of a binary variable x _i is N _I or 0, the binary variable has N _I 1s or N _I 0s and has no variation. Then, the n binary variables of the QUBO model are sorted in descending order of value variation, and a number (m) of binary variables in descending order of variation that does not exceed the hardware size of the Ising machine are extracted to construct a subQUBO model.

In this way, if the value of a specific binary variable x _i is fixed to 0 (or 1) in many solution instances, it can be inferred that the value of the binary variable x _i of the base solution of the QUBO model is also 0 (or 1). On the other hand, if the value of a specific binary variable x _i is not fixed to 0 (or 1) in many solution instances (if it varies), it can be inferred that the value of the binary variable x _i is a value different from the base solution of the QUBO model. Therefore, it is thought that a set including all binary variables that are expected to take values different from the base solution of the QUBO model should be extracted as a subQUBO model.

However, the above-mentioned method always extracts a subQUBO model using all solution instances, resulting in only one fixed subQUBO model. Therefore, in this embodiment, the process of randomly selecting N _S solution instances (2≦N _S <N _I ) from the N _I solution instances and extracting a subQUBO model is repeated multiple times (N _E times) to fully utilize all solution instances. This allows N _E various subQUBO models to be extracted, resulting in a better quasi-basis solution (quasi-optimal solution) of the original QUBO model.

Details of the calculation method for searching the ground state of the original QUBO model based on this subQUBO model extraction method will be described later (see Figures 8 to 10).

<Computing system of this embodiment>
Next, the configuration of a hybrid computing system that executes the computing method of this embodiment will be described. As shown in Fig. 6, the hybrid computing system 10 of this embodiment includes a classical computer 20 and an Ising machine 30 connected to the classical computer 20. The classical computer 20 is a conventional computer such as a personal computer. Note that multiple Ising machines 30 may be connected to the classical computer 20.

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

As shown in FIG. 7, 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 executes various processes according to programs stored in the memory 204 and storage device 206. Details of the calculation methods executed by the processor 202 will be described later (see Figures 8 to 10).

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

Memory 204 includes read-only memory (ROM) and random access memory (RAM). ROM stores boot programs such as the BIOS. When processor 202 reads a program stored in ROM or a program stored in storage device 206, the program is loaded into RAM.

The storage device 206 has a non-transitory computer-readable storage medium and stores a program for executing the calculation method of this embodiment, data necessary for executing the program, etc. Examples of computer-readable storage media include a hard disk drive (HDD), a solid state drive (SSD), an optical disk, etc.

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

The input unit 208 includes 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), a wide area network (WAN), and/or the Internet.

<Calculation method of this embodiment>
Next, a calculation method (hybrid annealing) executed by the hybrid calculation system 10 will be described with reference to the algorithm shown in Fig. 8. In the following calculation method, the size of the QUBO model is set to n, and the size of the subQUBO model that can be processed by the Ising machine 30 is set to m (<n).

First, as shown in Fig. 9, by executing an arbitrary QUBO solver on the classical computer 20, N _I (≥ 3) solution instances X _i (i = 1, ..., N _I ) of the QUBO model are generated and registered in the instance pool (lines 2 to 4 in Fig. 8). Next, the classical computer 20 selects the solution instance that gives the smallest target value from among the solution instances in the instance pool as the provisional best solution X _best (line 5). The subsequent process (lines 6 to 19) is repeated until X _best converges.

Next, an arbitrary QUBO solver is executed on the classical computer 20 to optimize the solution instances in the instance pool and find a quasi-basis solution (lines 7-8). At this time, the solution instance obtained immediately before is input to the QUBO solver. Because the Ising machine 30 cannot process a QUBO model with n binary variables, the classical computer 20 is used in this process.

Next, the hybrid computing system 10 uses the above-described method for extracting subQUBO models to extract N _E subQUBO models as follows (lines 9 to 17).

To extract a subQUBO model, the classical computer 20 first randomly selects N _S (2≦N _S <N _I ) solution instances X _i (i=1, ..., N _S ) from the instance pool (line 10). Let x _k,j be the j th binary variable (1≦j≦n) in the k th solution instance (1≦k≦N _S ). The classical computer 20 focuses on the j th binary variable in the selected N _S solution instances, counts the number of instances where x _k,j = 1, and calculates the absolute value |c _j -N _S /2| of the difference between the obtained count c _j and N _S /2 as the index d _j (lines 11 to 14). Figure 10 shows an example of the count c _j and index d _j for each of the n binary variables in the QUBO model.

Next, the classical computer 20 sorts the n binary variables _x1 , ..., _xn in ascending order of index _dj (in descending order of variance), extracts a set of m binary variables starting from the smallest index _dj , and constructs a subQUBO model consisting only of the extracted m binary variables using one solution instance _Xt randomly selected from the N _S solution instances as a tentative solution of the original QUBO model (see line 15, Figure 4A). When constructing the subQUBO model, the classical computer 20 calculates each external magnetic field coefficient of the subQUBO model using equation (3).

Next, the Ising machine 30 optimizes the extracted subQUBO model to obtain a base solution (see FIG. 4B). Subsequently, the classical computer 20 obtains a quasi-base solution X' of the original QUBO model by incorporating the base solution of the subQUBO model into the current tentative solution _Xt (see FIG. 4C) (line 16). The classical computer 20 adds the quasi-base solution X' to the instance pool as a new solution instance (line 17).

The hybrid computing system 10 executes the process on lines 9 to 17 (the process of randomly selecting N _S solution instances and extracting subQUBO models) N _E times to construct N _E subQUBO models and add the obtained quasi-basis solution X′ to the instance pool.

After the process on lines 9 to 17, the classical computer 20 selects the solution instance that provides the smallest objective value from among the solution instances in the current instance pool as the best solution X _best (line 18).The classical computer 20 then redefines the top N _I solution instances in the instance pool (N _I solution instances in order of smallest objective value) as the solution instances in the instance pool (line 19).The hybrid computing system 10 then repeats the process on lines 6 to 19 until the best solution X _best converges.

As such, in the algorithm shown in Figure 8, the optimization of the subQUBO model on line 16 is performed by the Ising machine 30, and the other processes are performed by the classical computer 20.

In addition, in the hybrid computing system 10, when N _E Ising machines 30 are connected to the classical computer 20, the N _E Ising machines 30 can simultaneously obtain N _E basis solutions of the subQUBO model (line 16).

To evaluate the solution accuracy of the calculation method of this embodiment (the algorithm of FIG. 8), three QAPs (tai20a, tho30, tho40) in the Quadratic Assignment Problem Library (QAPLIB), which are benchmark problems for quadratic assignment problems (QAPs), were converted into QUBO models and solved using a D-Wave 2000Q machine as an Ising machine. The variable sizes (number of variables) of the QUBO models corresponding to tai20a, tho30, and tho40 were 400, 900, and 1600, respectively, which are larger than the maximum variable size of the D-Wave 2000Q machine. In addition, the three parameters (N _I , N _E , and N _S ) mentioned above were set to N _I = 20, N _E = 10, and N _S = 5, respectively.

The obtained solution is defined as X, the base solution obtained from QAPLIB is defined as X ^* , and the solution accuracy is defined as f(X)/f(X ^* ). The average values of the solution accuracy at tai20a, tho30, and tho40 obtained by the calculation method of this embodiment were 0.958, 0.955, and 0.963, respectively. For comparison, the average values of the solution accuracy at three QAPs obtained by the qbsolv method disclosed in Non-Patent Document 1 were 0.951, 0.943, and 0.935, respectively. In other words, it was found that the calculation method of this embodiment had higher solution accuracy than the qbsolv method for all QAPs.

We also found that the solution accuracy increases as the number of solution instances (N _I ) increases, and also increases as the number of subQUBO models (N _E ) increases. On the other hand, we also found that the value of the parameter N _S has almost no effect on the solution accuracy.

As described above, according to this embodiment, by optimizing an Ising model that is larger than the size that an Ising machine can process, it is possible to efficiently obtain an optimal solution for the Ising model globally, based on theoretical support provided by the theorem.

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

10 Hybrid computing system 20 Classical computer 30 Ising machine 202 Processor 204 Memory 206 Storage device 208 Input unit 210 Display 212 I/F

Claims (6)

1. A computational method for solving an Ising model having a predetermined number of variables, comprising:
With classical computers,
(a) generating a plurality of solution instances that are a plurality of quasi-basis solutions of the Ising model and registering them in an instance pool;
(b) calculating a variance in the values of each of the plurality of variables across the plurality of solution instances;
(c) extracting a number of variables that can be processed by an Ising machine from the plurality of variables in descending order of the variation, and constructing a partial Ising model consisting only of the extracted variables by using one solution instance randomly selected from the plurality of solution instances as a provisional solution of the Ising model;
The Ising machine
(d) determining a basis solution of the partial Ising model;
The classical computer
(e) obtaining a new solution instance by incorporating the base solution into the tentative solution of the Ising model, and adding the new solution instance to the instance pool;
(f) A calculation method in which a solution instance that minimizes the energy of the Ising model is selected from the instance pool as a best solution. The calculation method described in claim 1, wherein processes (b) to (f) are repeated until the value of the best solution converges. The calculation method described in claim 1, wherein in process (c), the partial Ising model is constructed by incorporating interaction coefficients between variables of the partial Ising model and variables not included in the partial Ising model, among the plurality of variables of the Ising model, into the external magnetic field coefficients of the partial Ising model. The calculation method described in claim 1, wherein processes (b) to (d) are performed multiple times to obtain multiple base solutions of the partial Ising model. 1. A computational system for solving an Ising model having a predetermined number of variables, comprising:
a classical computer having a processor that generates a plurality of solution instances that are a plurality of quasi-basis solutions of the Ising model and registers them in an instance pool, calculates a variation in the value of each of the plurality of variables in the plurality of solution instances, extracts a number of variables that can be processed by an Ising machine from the plurality of variables in descending order of the variation, and uses one solution instance randomly selected from the plurality of solution instances as a tentative solution of the Ising model to construct a partial Ising model consisting only of the extracted variables;
an Ising machine that finds a basis solution of the partial Ising model;
Equipped with
The processor:
a computational system that obtains a new solution instance by incorporating the base solution into the tentative solution of the Ising model, adds the new solution instance to the instance pool, and selects, from the instance pool, a solution instance that minimizes the energy of the Ising model as a best solution. A program for causing a classical computer to execute a calculation method for solving an Ising model having a predetermined number of variables in combination with an Ising machine,
(a) generating a plurality of solution instances that are a plurality of quasi-basis solutions of the Ising model and registering them in an instance pool;
(b) calculating a variance in the values of each of the plurality of variables across the plurality of solution instances;
(c) extracting a number of variables that can be processed by an Ising machine from the plurality of variables in descending order of the variation, and constructing a partial Ising model consisting only of the extracted variables by using one solution instance randomly selected from the plurality of solution instances as a provisional solution of the Ising model;
(d) obtaining a new solution instance by incorporating the basic solution obtained using the Ising machine for the constructed partial Ising model into the tentative solution of the Ising model;
(e) adding the new solution instance to the instance pool;
(f) A program for executing a process of selecting, from the instance pool, a solution instance that minimizes the energy of the Ising model as a best solution.