Patent Publication Number: US-2022222042-A1

Title: Computer-readable recording medium storing information processing program, information processing method, and information processing device

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
     This application is based upon and claims the benefit of priority of the prior Japanese Patent Application No. 2021-4448, filed on Jan. 14, 2021, the entire contents of which are incorporated herein by reference. 
     FIELD 
     The embodiment discussed herein is related to a non-transitory computer-readable storage medium storing an information processing program, an information processing method, and an information processing device. 
     BACKGROUND 
     In the past, there has been an approach called annealing calculation for working out an optimum solution of a combination problem. The optimum solution is, for example, the minimum value. In this approach, the minimum value of a target evaluation function is worked out by transitioning an evaluation function whose minimum value is known to the target evaluation function for which the minimum value is to be worked out. The target evaluation function is, for example, the Hamiltonian. In this approach, a search is stochastically performed in order to work out the minimum value except the local minimal value. 
     In an example of prior art, each integer variable of a polynomial is rewritten into a first-degree function with a binary variable. Furthermore, for example, there is a technique of setting high-order energy that is a four or higher-degree polynomial, using a binary variable corresponding to a binary label allocated to each pixel of image data. In addition, for example, there is a technique of registering information indicating which arithmetic algorithm the arithmetic program is to follow in relation to the degree of a polynomial when used to be advantageous in shortening the arithmetic time of polynomial multiplication. Besides, for example, there is a technique of recalculating each integer variable as a linear function with a binary variable, replacing the recalculated each integer variable with an equivalent binary representation, and executing a degree reduction on the equivalent binary representation. 
     Examples of the related art include as follows: Japanese National Publication of International Patent Application No. 2019-526090; Japanese Laid-open Patent Publication No. 2012-27755; Japanese Laid-open Patent Publication No. 2000-298665; and U.S. Patent Application Publication No. 2017/0344898. 
     SUMMARY 
     According to an aspect of the embodiments, a computer-implemented method includes: acquiring an evaluation function represented by a product of high-degree polynomials; generating a quadratic polynomial equivalent to the evaluation function by applying a degree reduction one or more times to each of the high-degree polynomials that represent the acquired evaluation function without expanding the evaluation function; and performing annealing calculation on the generated quadratic polynomial. 
     The object and advantages of the invention will be realized and attained by means of the elements and combinations particularly pointed out in the claims. 
     It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory and are not restrictive of the invention. 
    
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         FIG. 1  is an explanatory diagram illustrating an example of an information processing method according to an embodiment; 
         FIG. 2  is an explanatory diagram illustrating an example of an information processing system  200 ; 
         FIG. 3  is a block diagram illustrating a hardware configuration example of an information processing device  100 ; 
         FIG. 4  is a block diagram illustrating a functional configuration example of the information processing device  100 ; 
         FIG. 5  is an explanatory diagram illustrating a flow of an action of the information processing device  100 ; 
         FIG. 6  is an explanatory diagram (part 1) illustrating a first action example of the information processing device  100 ; 
         FIG. 7  is an explanatory diagram (part 2) illustrating a first action example of the information processing device  100 ; 
         FIG. 8  is an explanatory diagram illustrating a second action example of the information processing device  100 ; 
         FIG. 9  is an explanatory diagram illustrating a usage example of the information processing device  100 ; and 
         FIG. 10  is a flowchart illustrating an example of an overall processing procedure. 
     
    
    
     DESCRIPTION OF EMBODIMENTS 
     However, with the past techniques, it is difficult to efficiently perform the annealing calculation. For example, when the target evaluation function is cubic or of a higher degree, it is supposed that the target evaluation function is transformed into a quadratic format, and then the annealing calculation is performed. However, the greater the number of variables contained in the target evaluation function after the transformation, the less efficient the annealing calculation tends to be. 
     In one aspect, the present embodiment aims to improve the efficiency of the annealing calculation. 
     Hereinafter, embodiments of an information processing program, an information processing method, and an information processing device will be described in detail with reference to the drawings. 
     (Example of Information Processing Method According to Embodiment) 
       FIG. 1  is an explanatory diagram illustrating an example of an information processing method according to an embodiment. The information processing device  100  is a computer for generating a quadratic polynomial equivalent to an evaluation function. 
     The evaluation function is a high-degree polynomial. The evaluation function is represented by, for example, the product of high-degree polynomials. The evaluation function is employed as a target of the annealing calculation. The evaluation function is, for example, the Hamiltonian. For example, the information processing device  100  is a server, a personal computer (PC), or the like. 
     It is desirable that the target of the annealing calculation be a quadratic polynomial. Therefore, when the evaluation function is cubic or of a higher degree, the evaluation function is supposed to be converted into a quadratic polynomial by applying a degree reduction one or more times to the evaluation function. As an approach of applying the degree reduction, for example, an approach called higher order binary optimization (HOBO) 2 quadratic unconstrained binary optimization (QUBO) is conceivable. 
     Every time the degree reduction is applied, the number of variables contained in the finally converted quadratic polynomial increments by one. The number of variables denotes, for example, the number of variables in a case where variables different from each other are counted. The number of variables does not denote, for example, the number of variables in a case where the identical variables are counted separately when the identical variables appear a plurality of times. 
     Here, the smaller the number of variables contained in the converted quadratic polynomial, the more efficiently the annealing calculation tends to be allowed to be performed. However, in the past, it has been difficult to efficiently perform the annealing calculation. For example, in the past, the number of variables contained in the transformed quadratic polynomial has been prone to increase, and the efficiency of the annealing calculation has been prone to deteriorate. 
     For example, an approach 1 of converting the evaluation function into a quadratic polynomial by applying a degree reduction one or more times to each of cubic or higher-degree terms in the evaluation function in order from the beginning is conceivable. For example, in the approach 1, if the evaluation function is H=acd+bcd, the evaluation function is converted into a quadratic polynomial by applying a degree reduction to ac of the cubic or higher-degree term acd and applying a degree reduction to be of the cubic or higher-degree term bcd in the evaluation function. In the approach 1, the number of variables contained in the quadratic polynomial is prone to increase, and the efficiency of the annealing calculation is prone to deteriorate. 
     Furthermore, for example, an approach 2 of converting the evaluation function into a quadratic polynomial by specifying a common term in the evaluation function and applying a degree reduction to the common term is conceivable. For example, in the approach 2, if the evaluation function is H=acd+bcd, the evaluation function is converted into a quadratic polynomial by specifying a common term cd, converting the evaluation function into H=cd(a+b), and applying a degree reduction to cd. In the approach 2, the number of variables contained in the quadratic polynomial is prone to increase, and the efficiency of the annealing calculation is prone to deteriorate. 
     Thus, in the present embodiment, a description will be made of an information processing method that may achieve a decrease in the number of variables contained in a quadratic polynomial obtained by applying a degree reduction one or more times to an evaluation function and may improve the efficiency of annealing calculation. 
     In  FIG. 1 , (1-1) an information processing device  100  acquires an evaluation function represented by the product of high-degree polynomials. Here, the evaluation function is not expanded. The evaluation function is, for example, (first-degree polynomial)×(high-degree polynomial). The evaluation function is, for example, (high-degree polynomial)×(high-degree polynomial). For example, the evaluation function is (a+b+1)×(cd−2) or the like. The information processing device  100  acquires the evaluation function by accepting the input of the evaluation function based on an operation input by a user, for example. 
     (1-2) The information processing device  100  applies a degree reduction one or more times to each of high-degree polynomials representing the acquired evaluation function without expanding the evaluation function, thereby generating a quadratic polynomial equivalent to the evaluation function. For example, the information processing device  100  applies a degree reduction one or more times to each of the high-degree polynomials representing the evaluation function and converts each of the high-degree polynomials into a first-degree polynomial. This allows the information processing device  100  to generate a quadratic polynomial=(first-degree polynomial)×(first-degree polynomial) equivalent to the evaluation function. At this time, since the information processing device  100  applies the degree reduction one or more times to each of the high-degree polynomials representing the evaluation function without expanding the evaluation function, a decrease in the number of variables contained in the generated quadratic polynomial may be achieved. 
     (1-3) The information processing device  100  performs the annealing calculation on the generated quadratic polynomial. This allows the information processing device  100  to efficiently perform the annealing calculation. Since a relatively small number of variables are contained in the quadratic polynomial, for example, the information processing device  100  may perform the annealing calculation efficiently when performing the annealing calculation on the quadratic polynomial. 
     Here, a case where the information processing device  100  makes actions independently has been described. However, the information processing device  100  is not limited to this case. For example, there may be a case where the information processing device  100  cooperates with another computer. For example, there may be a case where the information processing device  100  acquires the evaluation function by receiving the evaluation function from another computer. In this case, the information processing device  100  generates a quadratic polynomial equivalent to the evaluation function and transmits the result of performing the annealing calculation to the other computer. 
     Furthermore, for example, there may be a case where the information processing device  100  acquires the evaluation function by receiving the evaluation function from another computer capable of performing the annealing calculation. In this case, the information processing device  100  generates a quadratic polynomial equivalent to the evaluation function and transmits the generated quadratic polynomial to the other computer capable of performing the annealing calculation. An example of an information processing system  200  including the information processing device  100  and another computer in this case will be described later precisely with reference to  FIG. 2 . 
     (Example of Information Processing System  200 ) 
     Next, an example of the information processing system  200  to which the information processing device  100  illustrated in  FIG. 1  is applied will be described with reference to  FIG. 2 . 
       FIG. 2  is an explanatory diagram illustrating an example of the information processing system  200 . In  FIG. 2 , the information processing system  200  includes the information processing device  100  and one or more client devices  201 . 
     In the information processing system  200 , the information processing device  100  and the client devices  201  are connected via a wired or wireless network  210 . For example, the network  210  is a local area network (LAN), a wide area network (WAN), the Internet, or the like. 
     The information processing device  100  receives the evaluation function from the client device  201 . The information processing device  100  applies a degree reduction one or more times to each of high-degree polynomials representing the received evaluation function without expanding the evaluation function, thereby generating a quadratic polynomial equivalent to the evaluation function. The information processing device  100  transmits the generated quadratic polynomial to the client device  201 . 
     The client device  201  acquires the evaluation function as a target to be subjected to the annealing calculation, based on an operation input by a user. The client device  201  receives the quadratic polynomial equivalent to the evaluation function from the information processing device  100 . The client device  201  performs the annealing calculation on the quadratic polynomial. The client device  201  outputs the result of performing the annealing calculation in a manner that allows the user to refer to the result. For example, the client device  201  is a server, a PC, or the like. 
     (Hardware Configuration Example of Information Processing Device  100 ) 
     Next, a hardware configuration example of the information processing device  100  will be described with reference to  FIG. 3 . 
       FIG. 3  is a block diagram illustrating a hardware configuration example of the information processing device  100 . In  FIG. 3 , the information processing device  100  includes a central processing unit (CPU)  301 , a memory  302 , a network interface (I/F)  303 , a recording medium I/F  304 , and a recording medium  305 . Furthermore, the individual components are connected to each other by a bus  300 . 
     Here, the CPU  301  is in charge of overall control of the information processing device  100 . For example, the memory  302  includes a read only memory (ROM), a random access memory (RAM), a flash ROM, and the like. Precisely, for example, the flash ROM or the ROM stores various programs, and the RAM is used as a work area for the CPU  301 . The programs stored in the memory  302  are loaded into the CPU  301  to cause the CPU  301  to execute coded processing. 
     The network I/F  303  is connected to the network  210  through a communication line and is connected to another computer via the network  210 . Then, the network I/F  303  is in charge of an interface between the network  210  and the inside and controls input and output of data to and from another computer. For example, the network I/F  303  is a modem, a LAN adapter, or the like. 
     The recording medium I/F  304  controls reading and writing of data from and to the recording medium  305  under the control of the CPU  301 . For example, the recording medium I/F  304  is a disk drive, a solid state drive (SSD), a universal serial bus (USB) port, or the like. The recording medium  305  is a nonvolatile memory that stores data written under the control of the recording medium I/F  304 . For example, the recording medium  305  is a disk, a semiconductor memory, a USB memory, or the like. The recording medium  305  may be attachable to and detachable from the information processing device  100 . 
     For example, the information processing device  100  may include a keyboard, a mouse, a display, a printer, a scanner, a microphone, a speaker, or the like in addition to the components described above. Furthermore, the information processing device  100  may include a plurality of the recording medium I/Fs  304  and the recording media  305 . In addition, the information processing device  100  does not need to include the recording medium I/F  304  and the recording medium  305 . 
     (Hardware Configuration Example of Client Device  201 ) 
     Precisely, since the hardware configuration example of the client device  201  is similar to the hardware configuration example of the information processing device  100  illustrated in  FIG. 3 , the description thereof will be omitted. 
     (Functional Configuration Example of Information Processing Device  100 ) 
     Next, a functional configuration example of the information processing device  100  will be described with reference to  FIG. 4 . 
       FIG. 4  is a block diagram illustrating a functional configuration example of the information processing device  100 . The information processing device  100  includes a storage unit  400 , an acquisition unit  401 , a generation unit  402 , an analysis unit  403 , and an output unit  404 . 
     The storage unit  400  is implemented by a storage area of the memory  302 , the recording medium  305 , or the like illustrated in  FIG. 3 , for example. Hereinafter, a case where the storage unit  400  is included in the information processing device  100  will be described. However, the storage unit  400  is not limited to this case. For example, there may be a case where the storage unit  400  is included in a device different from the information processing device  100 , and the information processing device  100  is allowed to refer to the stored contents of the storage unit  400 . 
     The acquisition unit  401  to the output unit  404  function as an example of a control unit. Precisely, for example, the acquisition unit  401  to the output unit  404  implement functions thereof by causing the CPU  301  to execute a program stored in the storage area of the memory  302 , the recording medium  305 , or the like or by the network I/F  303  illustrated in  FIG. 3 . A processing result of each functional unit is stored in the storage area of the memory  302 , the recording medium  305 , or the like illustrated in  FIG. 3 , for example. 
     The storage unit  400  stores various sorts of information to be referred to or updated in the processing of each functional unit. The storage unit  400  stores, for example, the evaluation function. The evaluation function is a high-degree polynomial. The evaluation function is unarranged. Being unarranged means not being expanded. Being unarranged means, for example, that at least one of multiplication points including the high-degree polynomial in the evaluation function is not expanded. The evaluation function is represented by, for example, the product of high-degree polynomials. For example, the evaluation function is represented by the product of a first-degree polynomial and a high-degree polynomial in some cases. For example, the evaluation function is represented by the product of a first high-degree polynomial and a second high-degree polynomial in some cases. The evaluation function is employed as a target of the annealing calculation. The evaluation function is, for example, the Hamiltonian. The Hamiltonian represents energy in a certain system. 
     The acquisition unit  401  acquires various sorts of information to be used for the processing of each functional unit. The acquisition unit  401  stores the acquired various sorts of information in the storage unit  400  or outputs the acquired various sorts of information to each functional unit. Furthermore, the acquisition unit  401  may output the various sorts of information stored in the storage unit  400  to each functional unit. The acquisition unit  401  acquires the various sorts of information based on, for example, an operation input by a user. The acquisition unit  401  may receive the various sorts of information from a device different from the information processing device  100 , for example. 
     The acquisition unit  401  acquires, for example, the evaluation function. For example, the acquisition unit  401  acquires the evaluation function by accepting the input of the evaluation function based on an operation input by the user. For example, the acquisition unit  401  acquires the evaluation function by receiving the evaluation function from the client device  201 . For example, the acquisition unit  401  acquires the evaluation function by reading the evaluation function from the attachable/detachable recording medium  305 . 
     The acquisition unit  401  may accept a start trigger to start the processing of any one of the functional units. The start trigger is, for example, a predetermined operation input made by the user. The start trigger may be, for example, the receipt of predetermined information from another computer. The start trigger may be, for example, the output of predetermined information by any one of the functional units. The acquisition unit  401  accepts, for example, the acquisition of the evaluation function as a start trigger to start the processing of the generation unit  402  and the analysis unit  403 . 
     The generation unit  402  generates a quadratic polynomial equivalent to the evaluation function. For example, the generation unit  402  applies a degree reduction one or more times to each of high-degree polynomials representing the acquired evaluation function without expanding the evaluation function, thereby generating a quadratic polynomial equivalent to the evaluation function. 
     For example, a case where the evaluation function is represented by the product of a first-degree polynomial and a high-degree polynomial is conceivable. In this case, for example, the generation unit  402  generates a quadratic polynomial equivalent to the evaluation function using the product of the first-degree polynomial representing the evaluation function and a first-degree polynomial obtained by applying a degree reduction one or more times to the high-degree polynomial representing the evaluation function. 
     More precisely, the generation unit  402  adds a penalty term to the product of the first-degree polynomial representing the evaluation function and a first-degree polynomial obtained by applying a degree reduction one or more times to the high-degree polynomial representing the evaluation function to generate a quadratic polynomial equivalent to the evaluation function. The penalty term is a term that is added to the evaluation function at the time of the degree reduction in order to ensure the identity of the evaluation function between before and after the application of the degree reduction. This allows the generation unit  402  to generate a quadratic polynomial equivalent to the evaluation function such that the number of variables contained in the quadratic polynomial to be generated becomes relatively small. 
     Furthermore, for example, a case where the evaluation function is represented by the product of the first high-degree polynomial and the second high-degree polynomial is conceivable. In this case, for example, the generation unit  402  applies a degree reduction one or more times to the first high-degree polynomial to generate a first first-degree polynomial. In addition, for example, the generation unit  402  applies a degree reduction one or more times to the second high-degree polynomial to generate a second first-degree polynomial. Then, for example, the generation unit  402  generates a quadratic polynomial equivalent to the evaluation function using the product of the first first-degree polynomial and the second first-degree polynomial. 
     More precisely, the generation unit  402  adds the penalty term to the product of the first first-degree polynomial and the second first-degree polynomial to generate a quadratic polynomial equivalent to the evaluation function. This allows the generation unit  402  to generate a quadratic polynomial equivalent to the evaluation function such that the number of variables contained in the quadratic polynomial to be generated becomes relatively small. 
     In this case, when generating a quadratic polynomial equivalent to the evaluation function, the generation unit  402  uses the same variable to apply a degree reduction to a part common to the first high-degree polynomial and the second high-degree polynomial. This allows the generation unit  402  to generate a quadratic polynomial equivalent to the evaluation function such that the number of variables contained in the quadratic polynomial to be generated further becomes smaller. 
     For example, the generation unit  402  determines whether to generate a quadratic polynomial equivalent to the evaluation function without expanding the evaluation function or to generate a quadratic polynomial equivalent to the evaluation function after expanding the evaluation function. For example, the generation unit  402  specifies a first number of times the degree reduction is applied when applying the degree reduction one or more times without expanding the evaluation function to generate a quadratic polynomial equivalent to the evaluation function. Furthermore, for example, the generation unit  402  specifies a second number of times the degree reduction is applied when applying the degree reduction one or more times after expanding the evaluation function to generate a quadratic polynomial equivalent to the evaluation function. 
     Then, for example, the generation unit  402  compares the first number of times and the second number of times. Here, for example, as a result of the comparison, if the first number of times is equal to or less than the second number of times, the generation unit  402  generates a quadratic polynomial equivalent to the evaluation function by applying a degree reduction one or more times to each of the high-degree polynomials representing the evaluation function without expanding the evaluation function. This allows the generation unit  402  to generate a quadratic polynomial equivalent to the evaluation function based on the first number of times and the second number of times such that the number of variables contained in the quadratic polynomial to be generated becomes relatively small. 
     As a result of the comparison, if the first number of times is greater than the second number of times, the generation unit  402  generates a quadratic polynomial equivalent to the evaluation function by applying a degree reduction one or more times after expanding the evaluation function. This allows the generation unit  402  to generate a quadratic polynomial equivalent to the evaluation function based on the first number of times and the second number of times such that the number of variables contained in the quadratic polynomial to be generated becomes relatively small. 
     The analysis unit  403  performs the annealing calculation on the generated quadratic polynomial. This allows the analysis unit  403  to efficiently perform the annealing calculation. Since a relatively small number of variables are contained in the quadratic polynomial, for example, the analysis unit  403  may perform the annealing calculation efficiently when performing the annealing calculation on the quadratic polynomial. 
     The output unit  404  outputs a processing result of at least any one of the functional units. An output format is, for example, display on a display, print output to a printer, transmission to an external device by the network I/F  303 , or storage in the storage area of the memory  302 , the recording medium  305 , or the like. This allows the output unit  404  to notify the user of the processing result of at least any one of the functional units, and the enhancement of convenience of the information processing device  100  may be achieved. 
     The output unit  404  outputs, for example, a quadratic polynomial equivalent to the evaluation function. For example, the output unit  404  outputs a quadratic polynomial equivalent to the evaluation function in a manner that allows the user to refer to the quadratic polynomial. This allows the output unit  404  to make it possible for the user to efficiently perform the annealing calculation. For example, the output unit  404  transmits the quadratic polynomial equivalent to the evaluation function to an external computer. The external computer is, for example, the client device  201 . This allows the output unit  404  to make it possible to efficiently perform the annealing calculation on the external computer. 
     The output unit  404  outputs, for example, the result of performing the annealing calculation on the quadratic polynomial. For example, the output unit  404  outputs the result of performing the annealing calculation on the quadratic polynomial in a manner that allows the user to refer to the result. This allows the output unit  404  to make the result of performing the annealing calculation on the quadratic polynomial available to the user. For example, the output unit  404  transmits the result of performing the annealing calculation on the quadratic polynomial to an external computer. This allows the output unit  404  to make the result of performing the annealing calculation on the quadratic polynomial available on the external computer. 
     Here, a case where the information processing device  100  includes the analysis unit  403  has been described. However, the information processing device  100  is not limited to this case. For example, there may be a case where the information processing device  100  does not make actions independently and is able to communicate with the client device  201  capable of performing the annealing calculation instead of including the analysis unit  403 . In this case, the client device  201  is supposed to include the analysis unit  403 . 
     In the following, a case where the information processing device  100  makes actions independently as illustrated in  FIG. 1  will be described. 
     (Flow of Action of Information Processing Device  100 ) 
     Next, a flow of an action of the information processing device  100  will be described with reference to  FIG. 5 . 
       FIG. 5  is an explanatory diagram illustrating a flow of an action of the information processing device  100 . In  FIG. 5 , the information processing device  100  accepts the input of an unarranged Hamiltonian H, based on an operation input by the user. Being unarranged means not being expanded. The information processing device  100  can perform approaches 1 and 2 of arranging the Hamiltonian H and then converting the Hamiltonian H after the arrangement into a quadratic polynomial. 
     For example, the approach 1 converts the Hamiltonian H into a quadratic polynomial by applying a degree reduction one or more times to each of cubic or higher-degree terms in the Hamiltonian H in order from the beginning. In addition, for example, the approach 2 converts the Hamiltonian H into a quadratic polynomial by specifying a common term in the Hamiltonian H and applying a degree reduction to the common term. 
     Furthermore, the information processing device  100  can perform an approach 3 of converting the Hamiltonian H into a quadratic polynomial without arranging the Hamiltonian H. For example, the approach 3 converts the Hamiltonian H into a quadratic polynomial by applying a degree reduction one or more times to each of high-degree polynomials representing the Hamiltonian H without arranging the Hamiltonian H. 
     (5-1) By the approach 1, the information processing device  100  arranges the Hamiltonian H and specifies a number of times a the degree reduction is applied to the Hamiltonian H after the arrangement when converting the Hamiltonian H after the arrangement into a quadratic polynomial. For example, the information processing device  100  arranges the Hamiltonian H and specifies the number of times a the degree reduction is applied to the Hamiltonian H after the arrangement by performing the approach 1. 
     Furthermore, by the approach 2, the information processing device  100  arranges the Hamiltonian H and specifies a number of times β the degree reduction is applied to the Hamiltonian H after the arrangement when converting the Hamiltonian H after the arrangement into a quadratic polynomial. For example, the information processing device  100  arranges the Hamiltonian H and specifies the number of times β the degree reduction is applied to the Hamiltonian H after the arrangement by performing the approach 2. This allows the information processing device  100  to obtain a guideline for evaluating how great the number of variables contained in the quadratic polynomial generated by each of the approaches 1 and 2 is to be. For example, the information processing device  100  can obtain a guideline for evaluating how good the efficiency of the annealing calculation is to be when the annealing calculation is performed on the quadratic polynomial generated by each of the approaches 1 and 2. 
     (5-2) By the approach 3, the information processing device  100  specifies a number of times γ the degree reduction is applied to the Hamiltonian H when converting the Hamiltonian H into a quadratic polynomial without arranging the Hamiltonian H. For example, the information processing device  100  specifies the number of times γ the degree reduction is applied to the Hamiltonian H by performing the approach 3 without arranging the Hamiltonian. This allows the information processing device  100  to obtain a guideline for evaluating how great the number of variables contained in the quadratic polynomial generated by converting the Hamiltonian H without arranging the Hamiltonian H is to be. For example, the information processing device  100  can obtain a guideline for evaluating how good the efficiency of the annealing calculation is to be when the annealing calculation is performed on the quadratic polynomial generated by converting the Hamiltonian H without arranging the Hamiltonian H. 
     (5-3) The information processing device  100  acquires a quadratic polynomial when the Hamiltonian H is converted into a quadratic polynomial by an approach corresponding to the minimum number of times among the specified number of times α, number of times β, and number of times γ. This allows the information processing device  100  to convert the Hamiltonian H into a quadratic polynomial by a relatively appropriate approach among different approaches such that the annealing calculation can be performed efficiently. Therefore, the information processing device  100  can improve the efficiency of the annealing calculation. 
     (First Action Example of Information Processing Device  100 ) 
     Next, a first action example of the information processing device  100  will be described with reference to  FIGS. 6 and 7 . The first action example is an action example indicating how the information processing device  100  converts the Hamiltonian H into a quadratic polynomial by the above approach 3 when the Hamiltonian H is represented by the square of a certain high-degree polynomial. 
       FIGS. 6 and 7  are explanatory diagrams illustrating the first action example of the information processing device  100 . In  FIG. 6 , the information processing device  100  accepts the input of H=(x 1 x 3 (x 2 +x 7 +x 2 x 4 )+x 2 x 5 (x 1 +x 8 +x 1 x 6 )) 2 . 
     (6-A) The information processing device  100  extracts unarranged parts f and g of H. The unarranged part is a high-degree polynomial. The unarranged part is, for example, a high-degree polynomial that is defined in parentheses and to be multiplied by another polynomial. The information processing device  100  extracts, for example, f=g=x 1 x 3 (x 2 +x 7 +x 2 x 4 )+x 2 x 5 (x 1 +x 8 +x 1 x 6 ). 
     (6-B) If f is a high-degree polynomial, the information processing device  100  applies a degree reduction one or more times to f to generate a first-degree polynomial f′. For example, the information processing device  100  applies a degree reduction one or more times to f to generate a first-degree polynomial f′=x 11 +x 13 +x 14 +x 12 +x 15 +x 16 . A specific example in which the information processing device  100  generates the first-degree polynomial f′ will be described later with reference to  FIG. 7 . 
     The information processing device  100  adds a penalty term produced by the degree reduction to H. The information processing device  100  sets, for example, H←H +X 1,3 P(x 1 , x 3 , x 9 )+ . . . +X 8,10 P(x 8 , x 10 , x 16 ). In the example in  FIG. 6 , eight penalty terms are produced. 
     When applying the degree reduction to f using a certain variable, the information processing device  100  applies the degree reduction also to g using the same variable if the degree reduction can be applied to g using the same variable similarly to f. Therefore, the information processing device  100  is deemed to have already converted g into the first-degree polynomial g=x 11 +x 13 +x 14 +x 12 +x 15 +x 16 . 
     (6-C) If g is a high-degree polynomial, the information processing device  100  applies a degree reduction one or more times to g to generate a first-degree polynomial g′. Since g is already a first-degree polynomial, the information processing device  100  sets g′=g=x 11 +x 13 +x 14 +x 12 +x 15 +x 16 . 
     (6-D) The information processing device  100  converts H into a quadratic polynomial by replacing f and g in H with f′ and g′. The information processing device  100  generates, for example, H=f′g′+X 1,3 P(x 1 , x 3 , x 9 )+ . . . +X 8,10 P(x 8 , x 10 , x 16 ). X (i,j)  denotes a relatively great integer value. X (i,j)  is, for example, all 100. 
     The information processing device  100  outputs H. The information processing device  100  outputs H, for example, in a manner that allows the user to refer to H. The information processing device  100  outputs H, for example, to a functional unit that performs the annealing calculation. This allows the information processing device  100  to make a quadratic polynomial equivalent to H available, which allows to perform the annealing calculation efficiently. 
     Here, in the above approach 2, since the number of times the degree reduction is applied is ten, when H is converted into a quadratic polynomial, the number of variables contained in the quadratic polynomial equivalent to original H will increase by ten compared with the number of variables contained in original H. Furthermore, in the above approach 1, since the number of times the degree reduction is applied is ten or more, when H is converted into a quadratic polynomial, the number of variables contained in the quadratic polynomial equivalent to original H will increase by ten or more compared with the number of variables contained in original H. 
     On the other hand, in the above approach 3, since the number of times the degree reduction is applied is eight, when H is converted into a quadratic polynomial, the number of variables contained in the quadratic polynomial equivalent to original H will increase by eight compared with the number of variables contained in original H. This means that the approach 3 may generate a quadratic polynomial that is more suitable for the annealing calculation than in the case of the approaches 1 and 2. 
     It is conceivable that the efficiency of the annealing calculation will be enhanced twice at the maximum each time the number of variables contained in the quadratic polynomial is lessened by one. Accordingly, the information processing device  100  may allow to efficiently perform the annealing calculation by achieving a decrease in the number of variables contained in the quadratic polynomial. Next, description of  FIG. 7  will be made. 
     In  FIG. 7 , (7-1) the information processing device  100  applies a degree reduction to x 1 x 3  in f to replace x 1 x 3  with x 9  and also adds a penalty term X 1,3 P(x 1 , x 3 , x 9 ) to H. 
     (7-2) The information processing device  100  applies a degree reduction to x 2 x 5  in f to replace x 2 x 5  with x 10  and also adds a penalty term X 2,5 P(x 2 , x 5 , x 10 ) to H. Here, f has become x 2 x 9 (1+x 4 )+x 7 x 9 +x 1 x 10 (1+x 6 )+x 8 x 10 . 
     (7-3) The information processing device  100  applies a degree reduction to x 2 x 9  in f to replace x 2 x 9  with xii and also adds a penalty term X 2,9 P(x 2 , x 9 , x 11 ) to H. 
     (7-4) The information processing device  100  applies a degree reduction to x 1 x 10  in f to replace x 1 x 10  with x 12  and also adds a penalty term X 1,10 P(x 1 , x 10 , x 12 ) to H. Here, f has become x 11 +x 4 x 11 +x 7 x 9 +x 12 +x 6 x 12 +x 8 x 10 . 
     (7-5) The information processing device  100  applies a degree reduction to x 4 x 11  in f to replace x 4 x 11  with x 13  and also adds a penalty term X 4,11 P(x 4 , X 11 , x 13 ) to H. 
     (7-6) The information processing device  100  applies a degree reduction to x 7 x 9  in f to replace x 7 x 9  with x 14  and also adds a penalty term X 7,9 P(x 7 , x 9 , x 14 ) to H. 
     (7-7) The information processing device  100  applies a degree reduction to x 6 x 12  in f to replace x 6 x 12  with xis and also adds a penalty term X 6,12 P(x 6 , x 12 , x 15 ) to H. 
     (7-8) The information processing device  100  applies a degree reduction to x 8 x 10  in f to replace x 8 x 10  with x 16  and also adds a penalty term X 8,10 P(x 8 , x 10 , x 16 ) to H. Here, f has become a first-degree polynomial x 11 +x 13 +x 14 +x 12 +x 15 +x 16 . Therefore, f 2 =fg is put into a format suitable for the annealing calculation because f 2 =fg is a quadratic polynomial and does not become a high-degree polynomial of a cubic or higher degree. Furthermore, the number of variables of f has increased by eight compared with the original state because the degree reduction has been applied eight times. 
     (Second Action Example of Information Processing Device  100 ) 
     Next, a second action example of the information processing device  100  will be described with reference to  FIG. 8 . The second action example is an action example indicating how the information processing device  100  converts the Hamiltonian H into a quadratic polynomial by the above approach 3 when the Hamiltonian H is represented by the cube of a certain high-degree polynomial. 
       FIG. 8  is an explanatory diagram illustrating a second action example of the information processing device  100 . In  FIG. 8 , the information processing device  100  accepts the input of H=(x 1 x 3 (x 2 +x 7 +x 2 x 4 )+x 2 x 5 (x 1 +x 8 +x 1 x 6 )) 3 . 
     (8-A) The information processing device  100  extracts unarranged parts f and g of H. The information processing device  100  extracts, for example, f=(x 1 x 3 (x 2 +x 7 +x 2 x 4 )+x 2 x 5 (x 1 +x 8 +x 1 x 6 )) 2  and g=x 1 x 3 (x 2 +x 7 +x 2 x 4 )+x 2 x 5 (x 1 +x 8 +x 1 x 6 ). 
     (8-B) If f is a high-degree polynomial, the information processing device  100  applies a degree reduction one or more times to f to generate a first-degree polynomial f′. The information processing device  100  generates the first-degree polynomial f′ by, for example, expanding f and then applying a degree reduction one or more times. For example, the information processing device  100  may generate the first-degree polynomial f′ by converting f into a quadratic polynomial and then additionally applying a degree reduction one or more times to the converted quadratic polynomial, as in  FIG. 6 . 
     The information processing device  100  adds a penalty term produced by the degree reduction to H. At this time, when applying the degree reduction to f using a certain variable, the information processing device  100  applies the degree reduction also to g using the same variable if the degree reduction can be applied to g using the same variable similarly to f. 
     (8-C) If g is a high-degree polynomial, the information processing device  100  applies a degree reduction one or more times to g to generate a first-degree polynomial g′. 
     (8-D) The information processing device  100  converts H into a quadratic polynomial by replacing f and g in H with f′ and g′. The information processing device  100  generates, for example, H=f′g′+P. P is a symbol indicating a penalty term. 
     The information processing device  100  outputs H. The information processing device  100  outputs H, for example, in a manner that allows the user to refer to H. The information processing device  100  outputs H, for example, to a functional unit that performs the annealing calculation. This allows the information processing device  100  to make a quadratic polynomial available, which allows to perform the annealing calculation efficiently. 
     (Usage Example of Information Processing Device  100 ) 
     Next, a usage example of the information processing device  100  will be described with reference to  FIG. 9 . 
       FIG. 9  is an explanatory diagram illustrating a usage example of the information processing device  100 . In  FIG. 9 , the information processing device  100  has a function as a quantum annealing calculator. The information processing device  100  converts an evaluation function as an input into a quadratic polynomial and performs a quantum annealing calculation, thereby specifying a minimum value of the evaluation function and specifying a variable value of the evaluation function that implements the minimum value. The information processing device  100  outputs the specified minimum value and the variable value of the evaluation function that implements the specified minimum value in a manner that allows the user to refer to the output minimum value and variable value. 
     (Overall Processing Procedure) 
     Next, an example of an overall processing procedure executed by the information processing device  100  will be described with reference to  FIG. 10 . The overall processing is implemented by, for example, the CPU  301 , the storage area of the memory  302 , the recording medium  305 , or the like, and the network I/F  303  illustrated in  FIG. 3 . 
       FIG. 10  is a flowchart illustrating an example of an overall processing procedure. In  FIG. 10 , the information processing device  100  acquires an unarranged Hamiltonian H=fg+h (step S 1001 ). Here, elements f, g, and h denote polynomials. Either the element f or g denotes a high-degree polynomial. The element h denotes a quadratic or lower-degree polynomial. Then, the information processing device  100  extracts unarranged parts f and g of the Hamiltonian H (step S 1002 ). 
     Next, the information processing device  100  converts extracted f into a first-degree polynomial f′ by applying a degree reduction to extracted f (step S 1003 ). Then, the information processing device  100  adds a penalty term produced by the degree reduction to the Hamiltonian H (step S 1004 ). 
     Next, the information processing device  100  converts extracted g into a first-degree polynomial g′ by applying a degree reduction to extracted g (step S 1005 ). Then, the information processing device  100  adds a penalty term produced by the degree reduction to the Hamiltonian H (step S 1006 ). 
     Next, the information processing device  100  outputs the Hamiltonian H=f′g′+h+P (step S 1007 ). P denotes a penalty term. Then, the information processing device  100  ends the overall processing. This allows the information processing device  100  to convert the Hamiltonian H into a quadratic polynomial such that the annealing calculation can be performed efficiently. 
     Here, the information processing device  100  may exchange some steps in the processing order in  FIG. 10  to execute. For example, the places of the processing in steps S 1003  and S 1004  and the places of the processing in steps S 1005  and S 1006  can be exchanged in the order. Furthermore, the information processing device  100  may omit the processing in some steps in  FIG. 10 . For example, if f=g holds, the processing in steps S 1005  and S 1006  can be omitted. 
     As described above, according to the information processing device  100 , an evaluation function represented by the product of high-degree polynomials may be acquired. According to the information processing device  100 , a quadratic polynomial equivalent to the evaluation function may be generated by applying a degree reduction one or more times to each of the high-degree polynomials representing the acquired evaluation function without expanding the evaluation function. According to the information processing device  100 , the annealing calculation may be performed on the generated quadratic polynomial. This allows the information processing device  100  to make it easier to perform the annealing calculation efficiently. 
     According to the information processing device  100 , a first number of times the degree reduction is applied when the degree reduction is applied one or more times without expanding the evaluation function to generate a quadratic polynomial equivalent to the evaluation function may be specified. According to the information processing device  100 , a second number of times the degree reduction is applied when the degree reduction is applied one or more times after expanding the evaluation function to generate a quadratic polynomial equivalent to the evaluation function may be specified. According to the information processing device  100 , the first number of times and the second number of times may be compared. According to the information processing device  100 , as a result of the comparison, if the first number of times is equal to or less than the second number of times, a quadratic polynomial equivalent to the evaluation function may be generated by applying a degree reduction one or more times to each of the high-degree polynomials representing the evaluation function without expanding the evaluation function. This allows the information processing device  100  to generate a quadratic polynomial equivalent to the evaluation function by an appropriate approach based on the first number of times and the second number of times such that the number of variables contained in the quadratic polynomial to be generated becomes relatively small. 
     According to the information processing device  100 , as a result of the comparison, if the first number of times is greater than the second number of times, a quadratic polynomial equivalent to the evaluation function may be generated by applying a degree reduction one or more times after expanding the evaluation function. This allows the information processing device  100  to generate a quadratic polynomial equivalent to the evaluation function by an appropriate approach based on the first number of times and the second number of times such that the number of variables contained in the quadratic polynomial to be generated becomes relatively small. 
     According to the information processing device  100 , an evaluation function represented by the product of the first high-degree polynomial and the second high-degree polynomial may be acquired. According to the information processing device  100 , a first-degree polynomial may be generated by applying a degree reduction one or more times to the first high-degree polynomial without expanding the evaluation function. According to the information processing device  100 , a first-degree polynomial may be generated by applying a degree reduction one or more times to the second high-degree polynomial without expanding the evaluation function. According to the information processing device  100 , the product of the generated first-degree polynomials may be used to generate a quadratic polynomial equivalent to the evaluation function. This allows the information processing device  100  to efficiently generate a quadratic polynomial equivalent to an evaluation function represented by the product of the first high-degree polynomial and the second high-degree polynomial. 
     According to the information processing device  100 , an evaluation function represented by a product of the first high-degree polynomial and a second high-degree polynomial may be acquired. According to the information processing device  100 , the same variable may be used to apply a degree reduction to a part common to the first high-degree polynomial and the second high-degree polynomial. This allows the information processing device  100  to generate a quadratic polynomial equivalent to the evaluation function such that the number of variables contained in the quadratic polynomial to be generated further becomes smaller. Therefore, the information processing device  100  may make it possible to perform the annealing calculation more efficiently. 
     According to the information processing device  100 , an evaluation function represented by the product of a first-degree polynomial and a high-degree polynomial may be acquired. This allows the information processing device  100  to be applied when the annealing calculation is performed on an evaluation function represented by the product of the first-degree polynomial and the high-degree polynomial. 
     According to the information processing device  100 , the evaluation function that is a Hamiltonian may be acquired. This allows the information processing device  100  to be applied when the annealing calculation is performed on an evaluation function that represents energy in a certain system. 
     Note that the information processing method described in the present embodiment may be implemented by executing a prepared program on a computer such as a PC or a workstation. The information processing program described in the present embodiment is executed by being recorded on a computer-readable recording medium and being read from the recording medium by the computer. The recording medium is a hard disk, a flexible disk, a compact disc (CD)-ROM, a magneto-optical disc (MO), a digital versatile disc (DVD), or the like. Furthermore, the information processing program described in the present embodiment may be distributed via a network such as the Internet. 
     All examples and conditional language provided herein are intended for the pedagogical purposes of aiding the reader in understanding the invention and the concepts contributed by the inventor to further the art, and are not to be construed as limitations to such specifically recited examples and conditions, nor does the organization of such examples in the specification relate to a showing of the superiority and inferiority of the invention. Although one or more embodiments of the present invention have been described in detail, it should be understood that the various changes, substitutions, and alterations could be made hereto without departing from the spirit and scope of the invention.