DATA PROCESSING APPARATUS, COMPUTER-READABLE RECORDING MEDIUM STORING PROGRAM OF PROCESSING DATA, AND METHOD OF PROCESSING DATA

Abstract

A computer of searching for a combination of state variables with which an evaluation function including the state variables becomes a local minimum or maximum, the computer including: a memory storing a first coefficient indicating a magnitude of interaction between k state variables in a kth order term of the evaluation function; and a processor that performs: calculating a first local field indicating a change amount of the kth order term when a first state variable among the k state variables changes by the first coefficient and a first variable obtained by the k state variables and second coefficients; and determining whether to allow a change in the first state variable based on a result of comparison between a predetermined value and a product of a sum of the first local field and a second local field indicating a change amount of quadratic and lower-order terms of the evaluation function.

Claims

1. A data processing apparatus of searching for a combination of values of a plurality of state variables with which a value of an evaluation function which includes the plurality of state variables becomes a local minimum or a local maximum, the data processing apparatus comprising: a storage device configured to store a first coefficient indicating a magnitude of interaction between k state variables (k is an integer of greater than or equal to three) out of the plurality of state variables included in a kth order term of the evaluation function; and a processor configured to perform processing including: calculating a first local field indicative of a change amount of the kth order term in a case where a value of a first state variable out of the k state variables changes based on a value of a first variable and the first coefficient read from the storage device, the value of the first variable being a value obtained based on values of the k state variables and a plurality of second coefficients respectively representative of influences of the k state variables on the first variable; and determining, based on a result of comparison, whether to allow a change in the value of the first state variable, the result of the comparison being obtained by comparing between a predetermined value and a product of a sum of the first local field and a second local field indicative of a change amount of quadratic and lower-order terms of the evaluation function in the case where the value of the first state variable changes and a change amount of the first state variable.

2. The data processing apparatus according to claim 1, wherein the plurality of second coefficients are −1 or 1.

3. The data processing apparatus according to claim 1, wherein the value of the first variable is determined for each of the k state variables, and wherein the value of the first variable determined for the first state variable is determined based on a total sum of products of values of second state variables, out of the k state variables, other than the first state variable and second coefficients related to the second state variables out of the plurality of second coefficients.

4. The data processing apparatus according to claim 3, wherein the first local field is a product of a third coefficient, out of the plurality of second coefficients, related to the first state variable, the value of the first variable determined for the first state variable, and the first coefficient.

5. The data processing apparatus according to claim 1, wherein a value of the first variable common to the k state variables is determined, wherein it is determined that the value of the first variable determined for the first state variable is 2 when a sum of k literals with the k state variables is k, it is determined that the value of the first variable determined for the first state variable is 1 when the sum of the k literals with the k state variables is k−1, and it is determined that the value of the first variable determined for the first state variable is 0 when the sum of the k literals with the k state variables is smaller than or equal to k−2, and wherein the processing unit sets the first local field as the first coefficient when the value of the first variable is 2, the processing unit sets the first local field as the first coefficient when the value of the first variable is 1 and a literal with the first state variable is 0, the processing unit sets the first local field to 0 when the value of the first variable is 1 and the literal with the first state variable is 1, and the processing unit sets the first local field to 0 when the value of the first variable is 0.

6. The data processing apparatus according to claim 1, wherein each of the plurality of state variables has a value of −1 or 1, and the first variable has a value of −1 or 1, wherein the processing unit determines the value of the first variable for each of the k state variables, and wherein the first local field for the first state variable is a product of an infinite product of the values of the second state variables, out of the k state variables, other than the first state variable, the first coefficient, and the first variable.

7. The data processing apparatus according to claim 1, wherein each of the plurality of state variables has a value of −1 or 1, and the first variable has a value of −1 or 1, and wherein the processing unit calculates the value of the first variable common to the k state variables with an infinite product of the values of the k state variables and the first local field for the first state variable with a product of the value of the first variable, the first coefficient, and the value of the first state variable.

8. A non-transitory computer-readable recording medium storing a program of searching for a combination of values of a plurality of state variables with which a value of an evaluation function which includes the plurality of state variables becomes a local minimum or a local maximum, the program including instructions which, when the program is executed by a computer, cause the computer to execute processing, the processing comprising: obtaining a first coefficient from a storage device that stores the first coefficient representative of a magnitude of interaction between k state variables (k is an integer of greater than or equal to three) out of the plurality of state variables included in a kth order term of the evaluation function; calculating a first local field indicative of a change amount of the kth order term in a case where a value of a first state variable out of the k state variables changes based on a value of a first variable and the first coefficient read from the storage device, the value of the first variable being a value obtained based on values of the k state variables and a plurality of second coefficients respectively representative of influences of the k state variables on the first variable; and determining, based on a result of comparison, whether to allow a change in the value of the first state variable, the result of the comparison being obtained by comparing between a predetermined value and a product of a sum of the first local field and a second local field indicative of a change amount of quadratic and lower-order terms of the evaluation function in the case where the value of the first state variable changes and a change amount of the first state variable.

9. A computer-implemented method of searching for a combination of values of a plurality of state variables with which a value of an evaluation function which includes the plurality of state variables becomes a local minimum or a local maximum, the method comprising: obtaining a first coefficient from a storage device that stores the first coefficient representative of a magnitude of interaction between k state variables (k is an integer of greater than or equal to three) out of the plurality of state variables included in a kth order term of the evaluation function; calculating a first local field indicative of a change amount of the kth order term in a case where a value of a first state variable out of the k state variables changes based on a value of a first variable and the first coefficient read from the storage device, the value of the first variable being a value obtained based on values of the k state variables and a plurality of second coefficients respectively representative of influences of the k state variables on the first variable; and determining, based on a result of comparison, whether to allow a change in the value of the first state variable, the result of the comparison being obtained by comparing between a predetermined value and a product of a sum of the first local field and a second local field indicative of a change amount of quadratic and lower-order terms of the evaluation function in the case where the value of the first state variable changes and a change amount of the first state variable.

Description

BRIEF DESCRIPTION OF DRAWINGS

[0018] FIG. 1 illustrates an example of a data processing apparatus and a method of processing data according to a first embodiment;

[0019] FIG. 2 illustrates an example of k auxiliary variables used corresponding to k state variables;

[0020] FIG. 3 illustrates the relationship between y.sub.jn and q.sub.jn;

[0021] FIG. 4 is a block diagram illustrating a hardware example of a data processing apparatus according to a second embodiment;

[0022] FIG. 5 is a block diagram illustrating a functional example of the data processing apparatus;

[0023] FIG. 6 illustrates an example of matrix information stored in a storage unit;

[0024] FIG. 7 is a flowchart illustrating a flow of an example of the method of processing data;

[0025] FIG. 8 is a flowchart illustrating a flow of an example of a procedure of the initialization process;

[0026] FIG. 9 is a flowchart illustrating a flow of an example of a procedure of an updating process;

[0027] FIG. 10 illustrates an example of a data processing apparatus according to a third embodiment;

[0028] FIG. 11 illustrates a configuration an example of a field-programmable gate array (FPGA);

[0029] FIG. 12 illustrates an example in which an auxiliary variable having a value of two bits is used;

[0030] FIG. 13 illustrates an example in which spin variables are used as the state variables;

[0031] FIG. 14 illustrates an example in which the number of the auxiliary variables used for the state variables that are k spin variables included in the kth term is one;

[0032] FIG. 15 illustrates an example in which a plurality of auxiliary variables are used in a plurality of layers; and

[0033] FIG. 16 illustrates an example of calculation results.

DESCRIPTION OF EMBODIMENTS

[0034] With the related-art technique in which the independent variable is added and the higher-order evaluation function is converted into the quadratic evaluation function, the number of independent variables increases as the degree of higher-order terms increases. When the number of independent variables increases, the size of the solvable problem decreases, and the solution space increases. Consequently, it may be difficult to solve a problem.

[0035] In one aspect, an object of the present disclosure is to provide a data processing apparatus, a program, and a method of processing data with which a discrete optimization problem represented by a higher-order evaluation function may be calculated without increasing the number of independent variables.

[0036] Hereinafter, the embodiments of the present disclosure will be described with reference to the drawings.

First Embodiment

[0037] FIG. 1 illustrates an example of a data processing apparatus and a method of processing data according to a first embodiment.

[0038] A data processing apparatus 10 according to the first embodiment is an apparatus that searches for a combination of values of a plurality of state variables with which a value of a higher-order evaluation function as described above becomes a local minimum or a local maximum.

[0039] In the case where a constraint condition to be satisfied by a problem is given by a complex desired combination of various conditions, the constraint condition may be given in a satisfiability problem (SAT). In this case, for example, it is desirable that the number of logical clauses unable to be satisfied by the SAT become the minimum value. Although all SATs may be converted into a 3-SAT in which the number of literals is three, the related-art Ising machine which is only able to handle an evaluation function of the quadratic form is able to directly solve only up to a 2-SAT. As described below, the data processing apparatus 10 according to the present embodiment calculates a local field representative of a change amount (the energy change amount) of a higher-order term due to a change in values of the state variables included in the higher-order term by using an auxiliary variable. With this technique, the data processing apparatus 10 enables calculation of a problem equal to or higher than the 3-SAT, for example.

[0040] A higher-order evaluation function may be represented by, for example, the following Expression (3).

[00003]$\begin{array}{cc}E=-\underset{.Math.j1.Math.\mathrm{jk}.Math.}{.Math.}{Z}_{.Math.j1.Math.\mathrm{jk}.Math.}{x}_{j1}.Math.x_{\mathrm{jk}}-\underset{.Math.\mathrm{ij}.Math.}{.Math.}{W}_{\mathrm{ij}}{x}_i{x}_j-\underset{i}{.Math.}{b}_i{x}_i+E_0& \left(3\right)\end{array}$

[0041] On the right side, the first term is a kth (k≥3) term (higher-order term), and the second and subsequent terms are quadratic and lower-order terms. Out of N state variables, x.sub.j1 to x.sub.jk are state variables that are included in the kth term and forms a k-field combination. In Expression (3), Z<.sub.j1 . . . jk> is a coefficient representative of the magnitude of interaction between x.sub.j1 to x.sub.jk (for example, it may also be said to be a coefficient representative of the strength of combination of the k-field combination).

[0042] In the case where the constraint condition of the SAT type discrete optimization problem is handled, in the higher-order term, the part representative of the product of x.sub.j1 to x.sub.jk may be the product of positive and negative literals. For example, in the case where k=4 and x.sub.j1=x.sub.1, x.sub.j2=x.sub.2, x.sub.j3=x.sub.3, x.sub.j4=x.sub.4, the product such as Expression (4) below may also be handled as a higher-order term.

x.sub.1x.sub.2x.sub.3x.sub.4=(1−x.sub.1)x.sub.2(1−x.sub.3)x.sub.4  (4)

[0043] IN Expression (4), state variables (x.sub.1, x.sub.3) with a bar are negative literals. In the case of such a higher-order term, when the logical clause of Expression (5) below is not satisfied, for example, in the case of Expression (6) below, Z.sub.<j1 . . . jk> contributes to E (energy) (cost is generated).

x.sub.1∨x.sub.2∨x.sub.3∨x.sub.4  (5)

x.sub.1∧x.sub.2∧x.sub.3∧x.sub.4=1  (6)

[0044] It is assumed that, in the case where the logical clause of Expression (5) is not satisfied, Z.sub.1234 is generated as Z.sub.<j1 . . . jk>. A biquadratic term that generates such Z.sub.1234 may be represented as Z.sub.1234(1−x.sub.1)x.sub.2(1−x.sub.3)x.sub.4. In the case where the value of each of x.sub.1 to x.sub.4 changes, a corresponding local field (h.sub.1.sup.XY to h.sub.4.sup.XY) indicative of a change amount of the above biquadratic term may be represented as follows by using a corresponding auxiliary variable (y.sub.1 to y.sub.4).

[0045] For example, the change amount of the biquadratic term in the case where the value of x.sub.1 changes indicated by h.sub.1.sup.XY may be represented as h.sub.1.sup.XY=−Z.sub.1234y.sub.1 by using y.sub.1 that is y.sub.1=x.sub.2(1−x.sub.3)x.sub.4. The change amount of the biquadratic term in the case where the value of x.sub.2 changes indicated by h.sub.2.sup.XY, may be represented as h.sub.2.sup.XY=+Z.sub.1234y.sub.2 by using y.sub.2 that is y.sub.2=(1−x.sub.1)(1−x.sub.3)x.sub.4. The change amount of the biquadratic term in the case where the value of x.sub.3 changes indicated by h.sub.3.sup.XY may be represented as h.sub.3.sup.XY=−Z.sub.1234y.sub.3 by using y.sub.3 that is y.sub.3=(1−x.sub.1)x.sub.2x.sub.4. The change amount of the biquadratic term in the case where the value of x.sub.4 changes indicated by h.sub.4.sup.XY may be represented as h.sub.4.sup.XY=+Z.sub.1234y.sub.4 by using y.sub.4 that is y.sub.4=(1−x.sub.1)x.sub.2(1−x.sub.3).

[0046] A value obtained by multiplying h.sub.i.sup.XY by −Δx.sub.i is an increase in energy with the biquadratic term in the case where y.sub.i=1.

[0047] As described above, when all the literals other than x.sub.1 generating h.sub.i.sup.XY out of the literals of k state variables included in the kth term are 1, h.sub.i.sup.XY is a value obtained by adding an appropriate sign to Z<.sub.j1 . . . jk>. In contrast, when even one of the literals other than x.sub.i is false (0), h.sub.i.sup.XY is 0.

[0048] A value to which an appropriate sign is added means that a positive sign is added in the case where x.sub.i that generates h.sub.i.sup.XY is a positive literal in the kth order term and a negative sign is added in the case where x.sub.i that generates h.sub.i.sup.XY is a negative literal in the kth term.

[0049] Using the auxiliary variables as described above allows calculation of h.sub.i.sup.XY that is the local field indicative of the change amount of the kth term in the case where the values of the state variables included in the kth term change.

[0050] Since the auxiliary variables are obtained from the values of the state variables, the auxiliary variables are not independent variables and do not increase a solution searching space.

[0051] The data processing apparatus 10 illustrated in FIG. 1 calculates, by using three types of local fields (h.sub.i.sup.XX, h.sub.i.sup.XY, h.sub.j.sup.YX) including the above-described h.sub.i.sup.XY and the auxiliary variables as described above, a change amount (ΔE) of the value of the evaluation function of Expression (3) in the case where the value of x.sub.i changes and determines whether to allow a change in a value of x.sub.i.

[0052] The data processing apparatus 10 according to the first embodiment includes a storage unit 11 and a processing unit 12.

[0053] The storage unit 11 is, for example, a volatile storage device including an electronic circuit such as a dynamic random-access memory (DRAM) or a non-volatile storage device including an electronic circuit such as a hard disk drive (HDD) or a flash memory. The storage unit 11 may include an electronic circuit such as a register.

[0054] The storage unit 11 stores problem information of the discrete optimization problem, values of a plurality of (hereafter, N) state variables included in the evaluation function of Expression (3), and values of h.sub.i.sup.XX, h.sub.i.sup.XY, h.sub.j.sup.YX.

[0055] The problem information includes, for example, a coefficient (d.sub.j), which will be described later, other than Z.sub.<j1 . . . jk> (simply represented as Z in FIG. 1), W.sub.ij, and b.sub.i represented in Expression (3).

[0056] The local field h.sub.i.sup.XX is a local field representative of the change amount of the quadratic and lower-order terms of the value of the evaluation function of Expression (3) in the case where the value of x.sub.i changes and corresponds to h.sub.i of Expression (2). For example, h.sub.i.sup.XX may be represented by Expression (7) below.

[00004]$\begin{array}{cc}{h}_i^{\mathrm{XX}}=\underset{l=1}{\overset{N}{.Math.}}{W}_{\mathrm{il}}{x}_l+b_i& \left(7\right)\end{array}$

[0057] The local field h.sub.j.sup.YX is a first local field for the kth term and indicates a local field that N state variables generate for the auxiliary variable. The local field H.sub.j.sup.YX may be represented by Expression (8) below.

[00005]$\begin{array}{cc}{h}_j^{\mathrm{YX}}=\underset{l=1}{\overset{N}{.Math.}}{C}_{\mathrm{jl}}{x}_l+d_j& \left(8\right)\end{array}$

[0058] In Expression (8), C.sub.jl is a coefficient representative of the influence of the x.sub.l on the jth auxiliary variable. Assuming that the state variables not included in the kth term do not influence the auxiliary variable used for this kth term, C.sub.jl related to these state variables is 0.

[0059] As described above, in the case where the kth term is represented by the product of positive and negative literals, the C.sub.jn,j1 to C.sub.jn,jk representative of the influence of the x.sub.j1 to x.sub.jk included in the kth term on y.sub.jn may be represented by σ.sub.j1 to σ.sub.jk being appropriate signs described above. For example, in the case where is included in the above product as a positive literal, σ.sub.jn=+1, and in the case where x.sub.jn is included in the above product as a negative literal (1−x.sub.jn), σ.sub.jn=−1.

[0060] In Expression (8), d.sub.j is, for example, a predetermined constant such as −(k−(3/2)) (see FIG. 3).

[0061] An updated value of H.sub.j.sup.YX due to the change in the value of x.sub.i may be represented as h.sub.j.sup.YX=h.sub.j.sup.YX+C.sub.jiΔx.sub.i.

[0062] The local field h.sub.i.sup.XY is a second local field for the kth term and, as described above, indicates the change amount of the kth term in the case where the values of the state variables included in the kth term change. According to the first embodiment, h.sub.i.sup.XY indicates a local field that a certain auxiliary variable generates for x.sub.i. Expression (9) below may represent h.sub.i.sup.XY.

[00006]$\begin{array}{cc}{h}_i^{\mathrm{XY}}=\underset{j=1}{\overset{M}{.Math.}}{F}_{\mathrm{ij}}{y}_j& \left(9\right)\end{array}$

[0063] In Expression (9), y.sub.j is a jth auxiliary variable out of M auxiliary variables and may be represented as y.sub.j=f(h.sub.j.sup.YX). In this expression, f is a function representative of the input and output relationship of y.sub.j.

[0064] In this expression, F.sub.ij indicates the strength of the influence of the jth auxiliary variable on the x.sub.i. For example, the product of Z.sub.<j1 . . . jk> indicated in Expression (3) above and a coefficient (C.sub.jl) representative of the influence of x.sub.i on the jth auxiliary variable is used as F.sub.ij.

[0065] According to the first embodiment, k auxiliary variables that are values of a single bit of 0 or 1 are used corresponding to the number of k state variables (x.sub.j1 to x.sub.jk) included in the kth term. The auxiliary variables may be variables having a value of two or more bits. In this case, the number of the auxiliary variables may be one for k state variables (see a fourth embodiment (FIG. 12) to be described later).

[0066] FIG. 2 illustrates an example of k auxiliary variables used corresponding to k state variables.

[0067] Each of the k auxiliary variables (y.sub.j1 to y.sub.jk) generates the local field (h.sub.j1.sup.XY to h.sub.jk.sup.XY) for one of x.sub.j1 to x.sub.jk. Each of y.sub.j1 to y.sub.jk is determined based on a total sum of the products of the values of the state variables out of x.sub.j1 to x.sub.jk other than the state variable for which the local field is generated and a subset of σ.sub.j1 to σ.sub.jk described above related to the state variables other than the state variable for which the local field is generated.

[0068] In FIG. 1, for simplicity of explanation, one of the auxiliary variables (y.sub.jn) is illustrated. For x.sub.jn, y.sub.jn generates a local field (h.sub.jn.sup.XY).

[0069] The local field (h.sub.jn.sup.XY) that y.sub.jn generates for x.sub.jn may be represented as h.sub.jn.sup.XY=σ.sub.jnZy.sub.jn by using σ.sub.jn and Z described above.

[0070] A function f(h.sub.jn.sup.YX) that determines y.sub.jn is a function that determines a value of y.sub.jn in accordance with a value of q.sub.jn represented by Expression (10) below.

[00007]$\begin{array}{cc}{q}_{\mathrm{jn}}=\underset{l=1,l\ne n}{\overset{k}{.Math.}}{\sigma }_{\mathrm{jl}}{x}_{\mathrm{jl}}+N_{\mathrm{negative}}& \left(10\right)\end{array}$

[0071] The first term on the right side of Expression (10) is a value obtained by subtracting σ.sub.jnx.sub.jn and d.sub.j from h.sub.jn.sup.YX obtained based on Expression (8). The second term, N.sub.negative on the right side of Expression (10) is the number of state variables included in the above-described product as negative literals in the x.sub.jl (l=1 to k, l≠jn).

[0072] FIG. 3 illustrates the relationship between y.sub.jn and q.sub.jn. The horizontal axis represents q.sub.jn and the vertical axis represents y.sub.jn.

[0073] In the case of k−1 at which the q.sub.jn is the maximum, y.sub.jn is 1, and in the case of smaller than k−1 (in the case of k−2 or smaller) y.sub.jn is 0. As a threshold for such determination, the indicated in Expression (8) is used.

[0074] In this way, h.sub.jn.sup.XY representative of the change amount of the kth term in the case where the value of x.sub.jn changes may be obtained.

[0075] For example, as described above, the biquadratic term that generates Z.sub.1234 in the case where the logical clause of Expression (5) is not satisfied may be represented as Z.sub.1234(1−x.sub.1)x.sub.2(1−x.sub.3)x.sub.4. In the case of jn=1, it may be determined that y.sub.1 used for calculation of h.sub.1.sup.XY generated for x.sub.1 is 1 or 0 depending on whether q.sub.1=x.sub.2−x.sub.3+x .sub.4+1 is equal to or greater than (k−(3/2))=2.5. Thus, y.sub.1=f(h.sub.1.sup.YX) is the same expression as y.sub.1=x.sub.2(1−x.sub.3)x.sub.4 described above. For example, in the case where x.sub.2=1, x.sub.3=0, and x.sub.4=1, q.sub.1=3 and q.sub.1 is k−1. Thus, y.sub.1=1.

[0076] The storage unit 11 illustrated in FIG. 1 may store σ.sub.j1 to σ.sub.jk used in the above-described calculation.

[0077] The storage unit 11 may store various types of data such as calculation conditions used when the processing unit 12 executes the method of processing data, which will be described later (for example, the number of replicas, a value of a temperature parameter set for each of the replicas, a replica exchange cycle, and a calculation end condition in the case where a replica exchange method is executed). In the case where the processing unit 12 executes part or the entirety of processing of the method of processing data, which will be described later, by using software, a program for executing the processing is stored in the storage unit 11.

[0078] For example, the processing unit 12 may be realized by using a processor that is hardware such as a central processing unit (CPU), a graphics processing unit, (GPU) or a digital signal processor (DSP). Instead, the processing unit 12 may be realized by using an electronic circuit such as an application-specific integrated circuit (ASIC) or a field-programmable gate array (FPGA).

[0079] For example, the processing unit 12 searches for a state in which the value of the evaluation function (energy) represented by Expression (3) becomes the local minimum. The optimal solution is a state having the minimum value among the local minimums of the evaluation function. By changing the sign of the evaluation function represented by Expression (3), the processing unit 12 may search for a state in which the value of the evaluation function becomes the local maximum (in this case, a state having the maximum value is the optimal solution).

[0080] FIG. 1 illustrates a flow of an example of part of processing performed by the processing unit 12.

[0081] Here, it is assumed that values based on the initial values of x.sub.1 to x.sub.N are stored in the storage unit 11 as h.sub.i.sup.XX, h.sub.i.sup.XY, h.sub.j.sup.YX, y.sub.j, and E.

[0082] The processing unit 12 selects, out of x.sub.1 to x.sub.N, a candidate state variable the value of which is to be changed (hereafter referred to as a flip candidate) (step S1). For example, the processing unit 12 selects a flip candidate state variable randomly or in a predetermined order. A case where x.sub.jn included in the kth term is selected is described below.

[0083] In the case where the value of x.sub.jn changes, the processing unit 12 calculates (or updates) h.sub.jn.sup.XY based on the updated value of h.sub.j.sup.YX (=h.sub.jn.sup.YX) by using the above-described method (step S2).

[0084] The processing unit 12 calculates the change amount (ΔE) of the value of the evaluation function in the case where the value of x.sub.jn changes by using the product of −Δx.sub.jn and the sum of h.sub.jn.sup.XY and h.sub.i.sup.XX(=h.sub.jn.sup.XX) obtained based on Expression (7) (step S3).

[0085] Based on a result of comparison between ΔE and a predetermined value, the processing unit 12 determines whether to allow a change in the value of x.sub.jn (whether to enable or disable the flipping) (step S4). Hereinafter, this determination process is referred to as a flip determination process.

[0086] The predetermined value is, for example, a noise value obtained based on a random number and the value of a temperature parameter. The processing unit 12 determines that the change in the value of x.sub.jn is allowed in the case where, for example, ΔE is smaller than log (rand)×T which is an example of the noise value obtained based on a uniform random number (rand) of greater than or equal to 0 and smaller than or equal to 1 and the temperature parameter (T).

[0087] In the case where it is determined that the flip is enabled, the processing unit 12 updates the state stored in the storage unit 11 by changing the value of x.sub.jn and performs an updating process that updates h.sub.i.sup.XX, h.sub.i.sup.XY, h.sub.j.sup.YX, and y due to the change (step S5).

[0088] For example, updating of h.sub.i.sup.XX (i=1 to N) due to the change in the value of x.sub.jn may be performed by using the following expression: h.sub.i.sup.XX=h.sub.i.sup.XX+W.sub.i,jnΔx.sub.jn. For example, it is sufficient that the processing unit 12 read weight values in a jn column in a matrix W of N×N weight values.

[0089] Updating h.sub.j.sup.YX and h.sub.i.sup.XY may be performed by determining updated values obtained when h.sub.jn.sup.XY is calculated in the processing of step S2.

[0090] After the processing of step S5 or in the case where the flip is determined not to be enabled in the processing of step S4, the processing unit 12 repeatedly performs the processing from step S1 until a predetermined end condition is satisfied.

[0091] The order of the above-described processes is merely exemplary and may be changed as appropriate.

[0092] Although an example in which the processing of steps S2 to S4 is performed by selecting the flip candidate state variables one by one out of N state variables has been described in the above description, the processing of steps S2 to S4 may be performed in parallel for a plurality of (for example, all of N) state variables. In this case, when there are a plurality of state variables the values of which are allowed to be changed, the processing unit 12 selects the state variables the values of which are to be changed randomly or in accordance with a predetermined rule to perform the updating process of step S5. The parallel processing as described above increases the speed of the calculation.

[0093] In the case of performing a simulated annealing method, the processing unit 12 decreases the value of the above-described temperature parameter (T) according to a predetermined temperature parameter change schedule every time, for example, the flip determination process is repeatedly performed a predetermined number of times. The processing unit 12 outputs the state obtained in the case where the flip determination process has been repeatedly performed the predetermined number of times as a calculation result of the discrete optimization problem (for example, displays on a display device not illustrated). The processing unit 12 may update the value of the evaluation function (energy) represented by Expression (3) every time the change in the value of the state variable is generated and cause the storage unit 11 to hold the energy and the state in the case where the energy becomes the minimum energy up to that time. In this case, the processing unit 12 may output, as the calculation result, the state corresponding to the minimum energy stored after the flip determination process have been repeatedly performed the predetermined number of times.

[0094] In the case where the processing unit 12 performs the replica exchange method, the processing unit 12 performs the processing of steps S1 to S5 described above in a plurality of different replicas in which different values of the temperature parameter are set. Every time the flip determination process is repeatedly performed a predetermined number of times, the processing unit 12 performs a replica exchange. For example, the processing unit 12 randomly selects two replicas out of the plurality of replicas and exchanges the value of the temperature parameter or the state between the two selected replicas with a predetermined exchange probability based on an energy difference between the replicas and the difference in the value of the temperature parameter between the replicas. For example, the processing unit 12 updates the value of the evaluation function (energy) represented by Expression (3) every time the change in the value of the state variable is generated in each of the replicas and holds the energy and the state in the case where the energy becomes the minimum energy up to that time. The processing unit 12 outputs, as the calculation result, the state corresponding to the minimum energy in all the replicas out of the minimum energies stored after the above-described flip determination process has been repeatedly performed the predetermined number of times in each of the replicas.

[0095] With the data processing apparatus 10 and the method of processing data as described above, the change amount of the kth term in the case where the values of the state variables included in the kth term change is calculated by using the values of the auxiliary variables obtained based on the values of the state variables included in the kth term. Since the auxiliary variables are not independent variables or do not increase a solution searching space. Accordingly, the discrete optimization problem represented by a higher-order evaluation function may be calculated without increasing the number of independent variables.

[0096] Since the combination between the state variables and the auxiliary variables is represented by the coefficient (C.sub.jl of Expression (8) or F.sub.ij of Expression (9)) as described above, wiring or the like is not desired, and even when the number of auxiliary variables increases, a problem such as wiring jam does not occur.

Second Embodiment

[0097] FIG. 4 is a block diagram illustrating a hardware example of a data processing apparatus according to a second embodiment.

[0098] The data processing apparatus 20 is, for example, a computer and includes a CPU 21, a random-access memory (RAM) 22, an HDD 23, a GPU 24, an input interface 25, a medium reader 26, and a communication interface 27. The above-described devices are coupled to a bus.

[0099] The CPU 21 is a processor including an arithmetic circuit that executes program instructions. The CPU 21 loads at least a subset of programs and data stored in the HDD 23 into the RAM 22 and executes the programs. The CPU 21 may include a plurality of processor cores, or the data processing apparatus 20 may include a plurality of processors. Processes to be described below may be executed in parallel by using the plurality of processors or processor cores. A set of a plurality of processors (multiprocessor) may be referred to as a “processor”.

[0100] The RAM 22 is a volatile semiconductor memory that temporarily stores the programs executed by the CPU 21 or the data used for the arithmetic by the CPU 21. The data processing apparatus 20 may include a memory of a type other than the type of the RAM 22 and may include a plurality of memories.

[0101] The HDD 23 is a non-volatile storage device that stores the programs of software such as an operating system (OS), middleware, and application software, and data. Examples of the programs include a program for causing the data processing apparatus 20 to execute a process of searching for a solution to a discrete optimization problem. The data processing apparatus 20 may include another type of the storage device such as a flash memory or a solid-state drive (SSD) and may include a plurality of non-volatile storage devices.

[0102] The GPU 24 outputs images to a display 24a coupled to the data processing apparatus 20 in accordance with instructions from the CPU 21. As the display 24a, a cathode ray tube (CRT) display, a liquid crystal display (LCD), a plasma display panel (PDP), an organic electro-luminescence (OEL) display, or the like may be used.

[0103] The input interface 25 obtains an input signal from an input device 25a coupled to the data processing apparatus 20 and outputs the input signal to the CPU 21. As the input device 25a, a pointing device such as a mouse, a touch panel, a touchpad, and a trackball, as well as a keyboard, a remote controller, a button switch, or the like may be used. A plurality of types of input devices may be coupled to the data processing apparatus 20.

[0104] The medium reader 26 is a reading device that reads programs and data recorded in a recording medium 26a. As the recording medium 26a, for example, a magnetic disk, an optical disk, a magneto-optical (MO) disk, a semiconductor memory, or the like may be used. Examples of the magnetic disk include a flexible disk (FD) and an HDD. Examples of the optical disk include a compact disc (CD) and a Digital Versatile Disc (DVD).

[0105] For example, the medium reader 26 copies the programs or the data read from the recording medium 26a to another recording medium such as the RAM 22 or the HDD 23. For example, the read programs are executed by the CPU 21. The recording medium 26a may be a portable-type recording medium and, in some cases, is used to distribute the programs and the data. The recording medium 26a and the HDD 23 may be referred to as computer-readable recording media.

[0106] The communication interface 27 is an interface that is coupled to a network 27a and that communicates with another information processing apparatus via the network 27a. The communication interface 27 may be a wired communication interface coupled to a communication device such as a switch via a cable or a wireless communication interface coupled to a base station via a wireless link.

[0107] Next, the functions and a processing procedure of the data processing apparatus 20 are described.

[0108] FIG. 5 is a block diagram illustrating a functional example of the data processing apparatus.

[0109] The data processing apparatus 20 includes an input unit 30, a control unit 31, a storage unit 32, a search unit 33, and an output unit 34.

[0110] The input unit 30, the control unit 31, the search unit 33, and the output unit 34 have the function of the processing unit 12 of the data processing apparatus 10 according to the first embodiment. The input unit 30, the control unit 31, the search unit 33, and the output unit 34 may be implemented by using, for example, program modules executed by the CPU 21 or a storage area (a register or a cache memory) in the CPU 21. The storage unit 32 has the function of the storage unit 11 of the data processing apparatus 10 according to the first embodiment. The storage unit 32 may be implemented by using, for example, a storage area reserved in the RAM 22 or the HDD 23.

[0111] The input unit 30 accepts, for example, input of initial values of the state variables (x.sub.i to x .sub.N), the problem information, and calculation conditions. The problem information includes, for example, the coefficients (C.sub.jl, d.sub.j) indicated in Expression (8) in addition to Z.sub.<j1 . . . jk>, the weight value (W.sub.ij), and the bias coefficient (b.sub.i) indicated in Expression (3). The problem information may include F.sub.ij that is a value obtained by multiplying Z.sub.<j1 . . . jk> by π.sub.j1 to ϕ.sub.jk described above. Examples of the calculation conditions include, for example, the number of replicas, the replica exchange cycle, the value of the temperature parameter set for each of the replicas in the case where the replica exchange method is executed, and the temperature parameter change schedule, the calculation end condition, and so forth in the case where the simulated annealing method is performed.

[0112] These pieces of information may be input by a user operating the input device 25a or input via the recording medium 26a or the network 27a.

[0113] Based on the calculation conditions and the like, the control unit 31 controls the units in the data processing apparatus 20 to cause the units to execute processing to be described later.

[0114] The storage unit 32 stores the initial values of x.sub.1 to x.sub.N and the problem information. The storage unit 32 may store various types of information such as the calculation conditions.

[0115] The search unit 33 includes an initial value calculation unit 33a, an h&y updating and holding unit 33b, a flip candidate variable selection unit 33c, a Δx calculation unit 33d, a ΔE calculation unit 33e, and an E updating and holding unit 33f. The search unit 33 further includes a flip determination unit 33g, a state holding unit 33h, a transition destination state calculation unit 33i, and a state updating unit 33j.

[0116] The initial value calculation unit 33a reads the initial values of x.sub.1 to x.sub.N, b.sub.i, C.sub.jk, and d.sub.j stored in the storage unit 32 and, based on these values, calculates the initial values of h.sub.i.sup.XX and h.sub.j.sup.YX by using Expressions (7) and (8). Also, the initial value calculation unit 33a calculates the initial value of y.sub.j from the initial value of h.sub.j.sup.YX by using the following expression: y.sub.j=f(h.sub.j.sup.YX).

[0117] Furthermore, the initial value calculation unit 33a reads, for example, F.sub.ij stored in the storage unit 32 and calculates, based on the calculated initial value of y.sub.j and F.sub.ij, the initial value of h.sub.i.sup.XY by using Expression (6).

[0118] The h&y updating and holding unit 33b updates h.sub.i.sup.XX, h.sub.i.sup.YX, h.sub.j.sup.XY, and y.sub.j and holds values of these.

[0119] The updated value of h.sub.i.sup.XX due to the change in the value of x.sub.jn may be represented by the following expression: h.sub.i.sup.XX=h.sub.i.sup.XX+W.sub.i,jnΔx.sub.jn. The updated value of h.sub.j.sup.YX due to the change in the value of x.sub.jn may be represented by the following expression: h.sub.j.sup.YX=h.sub.j.sup.YX+C.sub.j,jnΔx.sub.jn. The updated value of h.sub.j.sup.XY due to the change in the value of x.sub.jn may be represented by the following expression: h.sub.i.sup.XY=h.sub.i.sup.XY+F.sub.ijΔy.sub.j. Calculation of Δy.sub.j is performed by using an expression Δy.sub.j=f(h.sub.j.sup.YX)−y.sub.j using the updated value of h.sub.j.sup.YX.

[0120] The flip candidate variable selection unit 33c selects a flip candidate state variable. For example, the flip candidate variable selection unit 33c selects a flip candidate state variable randomly or in a predetermined order. The flip candidate variable selection unit 33c outputs an identification number (1 to N) of the selected flip candidate state variable.

[0121] The Δx calculation unit 33d calculates the change amount of the value of the selected flip candidate state variable. For example, when the flip candidate state variable is x.sub.jn, Δx.sub.jn becomes −1 in the case where x.sub.jn changes from 1 to 0, and Δx.sub.jn becomes 1 in the case where the state variable x.sub.jn changes from 0 to 1.

[0122] The ΔE calculation unit 33e calculates, based on the product of the sum of two types of local fields and the change amount of the value of the flip candidate state variable, ΔE in the case where the value of the flip candidate state variable changes. For example, when the flip candidate state variable is x.sub.jn, ΔE is calculated by using the product of −Δx.sub.jn and the sum of h.sub.jn.sup.XY and h.sub.jn.sup.XX in the case where the value of x.sub.jn changes.

[0123] In the case where the change in the value of the flip candidate state variable is allowed by the flip determination unit 33g, the E updating and holding unit 33f updates E that is the value of the evaluation function indicated by Expression (3) based on ΔE calculated by the ΔE calculation unit 33e and holds E. The E updating and holding unit 33f may hold the smallest E out of Es having been obtained up to that time.

[0124] Based on the result of comparison between ΔE and a predetermined value, the flip determination unit 33g performs the flip determination process that determines whether to allow the change in the value of the flip candidate state variable. The predetermined value is, for example, a noise value obtained based on a random number and the value of the temperature parameter. The flip determination unit 33g determines that the change in the value of the flip candidate state variable is allowed in the case where, for example, ΔE is smaller than log (rand)×T which is an example of the noise value obtained based on a uniform random number (rand) greater than or equal to 0 and smaller than or equal to 1 and the temperature parameter (T).

[0125] The state holding unit 33h holds values of N state variables (x.sub.1 to x.sub.N).

[0126] The transition destination state calculation unit 33i calculates a transition destination state in which the value of the state variable of the identification number output by the flip candidate variable selection unit 33c out of the x.sub.1 to x.sub.N is changed.

[0127] In the case where the flip determination unit 33g determines that the change in the value of the state variable is allowed, the state updating unit 33j uses the transition destination state calculated by the transition destination state calculation unit 33i to update the state held by the state holding unit 33h.

[0128] Under the control of the control unit 31, the search unit 33 searches for a state in which the value of the evaluation function (energy) becomes the local minimum by repeatedly performing the flip determination process and the updating process of each parameter as described above.

[0129] The output unit 34 outputs a search result (calculation result) of the search unit 33. For example, in the case where the replica exchange method is performed, the output unit 34 outputs, as the calculation result, the state corresponding to the minimum energy in all the replicas out of the minimum energies stored after the above-described flip determination process has been repeatedly performed the predetermined number of times in each of the replicas.

[0130] For example, the output unit 34 may output and display the calculation result on the display 24a, transmit the calculation result to another information processing apparatus via the network 27a, or store the calculation result in an external storage device.

[0131] FIG. 6 illustrates an example of matrix information stored in the storage unit.

[0132] In the case where the number of the state variables and the number of the auxiliary variables included in the evaluation function of Expression (3) is N and M, respectively, W.sub.ij is an N×N matrix, C.sub.jl in Expression (8) is an M×N matrix, and F.sub.ij in Expression (9) is an N×M matrix. Here, W.sub.ij=W.sub.ji. According to the present embodiment, it is assumed that the weight values between the auxiliary variables is 0.

[0133] Hereinafter, the processing procedure (a method of processing data) of the data processing apparatus 20 will be described. An example in which search is performed by using the replica exchange method is described below.

[0134] FIG. 7 is a flowchart illustrating a flow of an example of the method of processing data.

[0135] Step S10: The input unit 30 accepts input of the initial values of x.sub.1 to x.sub.N, the above-described problem information, and the calculation conditions. For example, the initial values of x.sub.1 to x.sub.N and the problem information having been input are stored in the storage unit 32, and the calculation conditions having been input are supplied to the control unit 31.

[0136] Step S11: The initialization process is performed for each of the replicas. An example of a procedure of the initialization process will be described later.

[0137] For each of the replicas, the control unit 31 causes the search unit 33 to perform processing of steps S12 to S16 below.

[0138] Step S12: The flip candidate variable selection unit 33c of the search unit 33 selects a candidate state variable the value of which is to be changed (updated).

[0139] Step S13: The ΔE calculation unit 33e calculates ΔE. Based on the product of the sum of two types of local fields and the change amount of the value of the flip candidate state variable, ΔE in the case where the value of the flip candidate state variable changes is calculated. For example, when the flip candidate state variable is x.sub.jn, the ΔE calculation unit 33e calculates ΔE by using the product of −Δx.sub.jn and the sum of h.sub.jn.sup.XY and h.sub.jn.sup.XX in the case where the value of x.sub.jn changes.

[0140] Step S14: The flip determination unit 33g performs the flip determination based on the result of comparison between ΔE and a predetermined value. In the case where the flip determination unit 33g determines that the change in the value of the state variable is allowed, (in the case of “FLIP ENABLED”), processing of step S15 is performed. In the case where the flip determination unit 33g determines that the change in the value of the state variable is not allowed (in the case of “FLIP DISABLED”), processing of step S16 is performed.

[0141] Step S15: The updating process is performed. In the processing of step S15, the state is updated by the state updating unit 33j, h.sub.i.sup.XX, h.sub.j.sup.YX, h.sub.i.sup.XY, and y.sub.j are updated by the h&y updating and holding unit 33b, and E is updated by the E updating and holding unit 33f. An example of a procedure of the processing of step S15 will be described later.

[0142] Step S16: The control unit 31 determines whether the processing satisfies a predetermined end condition. For example, in the case where the number of times the search unit 33 performs the flip determination process has reached a maximum number of times of the flip determination, the control unit 31 determines that the end condition is satisfied. In the case where it is determined that the processing satisfies the predetermined end condition, processing of step S19 is performed. In the case where it is determined that the processing does not satisfy the predetermined end condition, processing of step S17 is performed.

[0143] Step S17: The control unit 31 determines whether the number of times of the flip determination indicates the replica exchange cycle. For example, in the case where a remainder of the number of times of the flip determination divided by a value indicative of the replica exchange cycle is 0, the control unit 31 determines that the number of times of the flip determination indicates the replica exchange cycle.

[0144] The control unit 31 performs processing of step S18 in the case where it is determined that the number of times of the flip determination indicates the replica exchange cycle. The control unit 31 causes the search unit 33 to repeat the processing from step S12 in the case where it is determined that the number of times of the flip determination does not indicate the replica exchange cycle.

[0145] Step S18: The control unit 31 performs a replica exchange process. For example, the control unit 31 randomly selects two replicas out of the plurality of replicas and exchanges the value of the set temperature parameter or the state between the two selected replicas with a predetermined exchange probability based on an energy difference between the replicas and the difference in the value of the temperature parameter between the replicas. After the processing of step S18, the control unit 31 causes the search unit 33 to repeat the processing from step S12.

[0146] Step S19: The output unit 34 outputs the calculation result. For example, the output unit 34 outputs, as the calculation result, the state corresponding to the minimum energy in all the replicas out of the minimum energies stored in the replicas. For example, the output unit 34 may output and display the calculation result on the display 24a, transmit the calculation result to another information processing apparatus via the network 27a, or store the calculation result in an external storage device.

[0147] Next, an example of the procedure of the initialization process of step S11 described above is described.

[0148] FIG. 8 is a flowchart illustrating a flow of the example of the procedure of the initialization process.

[0149] It is assumed that E is initialized to E.sub.0 of Expression (3) (for example, 0).

[0150] First, the initial value calculation unit 33a sets h.sub.i.sup.XX=b.sub.i, h.sub.i.sup.XY=0, and h.sub.j.sup.YX=d.sub.j for h.sub.i.sup.XX, h.sub.i.sup.XY, and h.sub.j.sup.YX, of every i from 1 to N and every j from 1 to M (step S20). As for example, a value of −(k−3/2) is used in the case where the auxiliary variable y.sub.j is an auxiliary variable for a k-field combined state variable (k≥3). The value y.sub.j is determined by using (see FIG. 3 described above).

[0151] The initial value calculation unit 33a calculates y.sub.j of every j from 1 to M by using an expression y.sub.j=f(h.sub.j.sup.YX) (step S21). After the processing of step S21, the initial value calculation unit 33a updates h.sub.i.sup.XY of every i from 1 to N by using F.sub.ijy.sub.j of every j from 1 to M and an expression h.sub.i.sup.XY=h.sub.i.sup.XY+F.sub.ijy.sub.j (step S22).

[0152] Then, the initial value calculation unit 33a sets k that is a variable representative of the identification number of the state variable to k=1 (step S23) and updates E by using the following expression: E=E−x.sub.k.sup.0(h.sub.k.sup.XX+h.sub.k.sup.XY) (step S24). Furthermore, the initial value calculation unit 33a updates h.sub.i.sup.XX of every i from 1 to N by using the following expression: h.sub.i.sup.XX=h.sub.i.sup.XX+w.sub.ikx.sub.k.sup.0 (step S25). Here, x.sub.k.sup.0 represents an initial value of the state variable with an identification number=k.

[0153] After the processing of step S25, the initial value calculation unit 33a determines whether k=N holds (step S26). In the case where it is determined that k=N does not hold, k=k+1 is set (step S27), and the processing from step S24 is repeated.

[0154] In the case where it is determined that k=N holds, the initial value calculation unit 33a sets the variable j indicative of the identification number of the auxiliary variable as j=1 (step S28). Hereinafter, it is assumed that the number of auxiliary variables is M.

[0155] By using an expression of h.sub.j.sup.YX=h.sub.j.sup.YX+C.sub.jkx.sub.k.sup.0, the initial value calculation unit 33a updates h.sub.j.sup.YX by using C.sub.jkx.sub.k.sup.0 of every k from 1 to N (step S29). For example, C.sub.jk related to a state variable not included in the kth term is 0, and C.sub.jk related to a state variable included in the kth term is +1 or −1 (σ.sub.j1 to σ.sub.jk in FIG. 1). Out of the state variables included in the kth term, C.sub.jk related to a state variable that is a positive literal is +1, and a C.sub.jk related to a state variable that is a negative literal is −1.

[0156] The initial value calculation unit 33a calculates Δy.sub.j by using an expression of Δy.sub.j=f(h.sub.j.sup.YX)−y.sub.j (step S30) and updates h.sub.i.sup.XY of every i from 1 to N by using an expression of h.sub.i.sup.XY=h.sub.i.sup.XY+F.sub.ijΔy.sub.j (step S31). The product of C.sub.ji and Z.sub.<j1 . . . jk> in Expression (3) represents F.sub.ij. Since C.sub.ji related to a state variable not included in the kth term is 0, F.sub.ij is also 0.

[0157] After the processing of step S31, the initial value calculation unit 33a determines whether j=M holds (step S32). In the case where it is determined that j=M does not hold, j=j+1 is set (step S33), and the processing from step S29 is repeated.

[0158] In the case where it is determined that j=M holds, the initial value calculation unit 33a ends the initialization process.

[0159] Next, an example of the procedure of the updating process of step S15 illustrated in FIG. 7 is described.

[0160] FIG. 9 is a flowchart illustrating a flow of the example of the procedure of the updating process. In FIG. 9, an example in the case where the change in the value of x.sub.jn is allowed is illustrated.

[0161] The state updating unit 33j uses the transition destination state calculated by the transition destination state calculation unit 33i to update the state held by the state holding unit 33h. The updated state is a state in which the value of x.sub.jn is changed so as to satisfy x.sub.jn=x.sub.jn+Δx.sub.jn. The E updating and holding unit 33f updates E by using the following expression: E=E−Δx.sub.jn(h.sub.jn.sup.XX+h.sub.jn.sup.XY) (step S40). Here, −Δx.sub.jn(h.sub.jn.sup.XX+h.sub.jn.sup.XY)=ΔE and is supplied from the ΔE calculation unit 33e.

[0162] The h&y updating and holding unit 33b updates h.sub.i.sup.XX of every i from 1 to N by using the following expression: h.sub.i.sup.XX=h.sub.i.sup.XX+W.sub.i,jnΔx.sub.jn (step S41). Also, the h&y updating and holding unit 33b sets j=1 (step S42) and updates h.sub.j.sup.YX with an updated value of h.sub.j.sup.YX (calculated when ΔE is calculated in step S13) represented by an expression of h.sub.j.sup.YX=h.sub.j.sup.YX+C.sub.j,jnΔx.sub.jn. Also, the h&y updating and holding unit 33b updates Δy.sub.j with an updated value of Δy.sub.j (calculated when ΔE is calculated in step S13) represented by an expression of Δy.sub.j=f(h.sub.j.sup.YX)−y.sub.j (step S43). By using h.sub.j.sup.YX before the updating, y.sub.j may be represented as y.sub.j=f(h.sub.j.sup.YX).

[0163] Then, the h&y updating and holding unit 33b calculates the updated value of h.sub.i.sup.XY of every i from 1 to N due to the change in the value of x.sub.jn by using the following expression: h.sub.i.sup.XY=h.sub.i.sup.XY+F.sub.ijΔy.sub.j (step S44).

[0164] After the processing of step S44, the h&y updating and holding unit 33b determines whether j=M holds (step S45). In the case where it is determined that j=M does not hold, j=j+1 is set (step S46), and the processing from step S43 is repeated.

[0165] In the case where it is determined that j=M, the updating process ends.

[0166] The order of the processes illustrated in FIGS. 7 to 9 is merely exemplary and may be changed as appropriate.

[0167] With the data processing apparatus 20 and the method of processing data as described above, similar effects to those of the data processing apparatus 10 and the method of processing data according to the first embodiment may be obtained. For example, the discrete optimization problem represented by a higher-order evaluation function may be calculated without increasing the number of independent variables.

[0168] As has been described, the processing content described above may be realized by causing the data processing apparatus 20 to execute a program.

[0169] The program may be recorded in a computer-readable recording medium (for example, the recording medium 26a). As the recording medium, for example, a magnetic disk, an optical disk, a magneto-optical disk, a semiconductor memory, or the like may be used. Examples of the magnetic disk include an FD and an HDD. Examples of the optical disk include a CD, a CD-recordable (R)/rewritable (RW), a DVD, and a DVD-R/RW. The program may be recorded in a portable-type recording medium to be distributed. In this case, the program may be copied from the portable-type recording medium to another recording medium (for example, the HDD 23) to be executed.

Third Embodiment

[0170] FIG. 10 illustrates an example of a data processing apparatus according to a third embodiment. In FIG. 10, the same elements as the elements illustrated in FIG. 4 are denoted by the same reference signs.

[0171] A data processing apparatus 40 according to the third embodiment includes an accelerator card 41 coupled to the bus.

[0172] The accelerator card 41 is a hardware accelerator that searches for a solution to a discrete optimization problem. The accelerator card 41 includes an FPGA 41a and a DRAM 41b.

[0173] In the data processing apparatus 40 according to the third embodiment, the FPGA 41a performs, for example, the processing of the control unit 31 and the search unit 33 illustrated in FIG. 5.

[0174] The DRAM 41b functions as the storage unit 32 illustrated in FIG. 5.

[0175] A plurality of accelerator cards 41 may be provided. In this case, for example, the processing (for example, the processing of steps S12 to S16 illustrated in FIG. 7) for the replicas may be performed in parallel.

[0176] FIG. 11 illustrates a configuration of an example of an FPGA.

[0177] The FPGA 41a includes a controller 50, a state updating and holding circuit 51, multipliers 52 and 53, an h.sup.XX updating and holding circuit 54, an h.sup.YX updating and holding circuit 55, a y calculating and holding circuit 56, an E updating and holding circuit 57, a multiplier 59, an h.sup.XY updating and holding circuit 60, and an addition circuit 61.

[0178] The controller 50 controls portions of the FPGA 41a. For example, as illustrated in FIG. 11, the controller 50 generates and outputs clock signals (clkx, clky) for determining operation timing of the state updating and holding circuit 51 and the y calculating and holding circuit 56.

[0179] The controller 50 has the function of selecting the flip candidate state variable and the function of determining whether to allow the change in the value of the flip candidate state variable based on a result of addition of two types of local fields output by the addition circuit 61. For example, in the case where x.sub.jn is selected as the flip candidate state variable, the controller 50 outputs the identification number=jn. Based on h.sub.jn.sup.XX+h.sub.jn.sup.XY which is the addition result output by the addition circuit 61 and Δx.sub.jn output by the state updating and holding circuit 51, the controller 50 calculates ΔE=−Δx.sub.jn(h.sub.jn.sup.XX+h.sub.jn.sup.XY). The controller 50 determines whether to allow the change in the value of x.sub.jn based on a result of comparison between ΔE and a noise value obtained based on a random number and the value of the temperature parameter.

[0180] The state updating and holding circuit 51 includes, for example, a register, a static random-access memory (SRAM), or the like and holds values of N state variables x.sub.i (i=1 to N). An initial value x.sub.i.sup.0 of N state variables x.sub.i is read from the DRAM 41b and held in the state updating and holding circuit 51.

[0181] The state updating and holding circuit 51 outputs the change amount in the case where the value of the flip candidate state variable designated by the controller 50 is changed. For example, in the case where jn is designated as the identification number of the state variable, the state updating and holding circuit 51 outputs Δx.sub.jn which is the change amount of x.sub.jn.

[0182] In the case where the state updating and holding circuit 51 receives, from the controller 50, a signal indicative of allowing the change in the value of the flip candidate state variable, the state updating and holding circuit 51 updates the state by changing the value of the state variable.

[0183] The multiplier 52 outputs the products of the change amount of the state variable and the weight values in a row or a column related to the flip candidate state variable out of the matrix W of N×N weight values W.sub.ij stored in the DRAM 41b. For example, in the case where the flip candidate state variable is x.sub.jn, N weight values (W.sub.i,jn) in the jn column out of the matrix W are read from the DRAM 41b, and the products of Δx.sub.jn and W.sub.i,jn are output.

[0184] The multiplier 53 outputs the products of the change amount of the state variable and the coefficients in a column related to the flip candidate state variable out of the matrix C of M×N coefficients C.sub.jk stored in the DRAM 41b. For example, in the case where the flip candidate state variable is x.sub.jn, M coefficients (C.sub.j,jn) in the jn column out of the matrix C are read from the DRAM 41b, and the products of Δx.sub.jn and C.sub.j,jn are output.

[0185] The h.sub.XX updating and holding circuit 54 includes, for example, a register, an SRAM, or the like, holds N local fields h.sub.i.sup.XX, and calculates updated values of N local fields h.sub.i.sup.XX by adding each of N products output by the multiplier 52 to corresponding h.sub.i.sup.XX out of N local fields h.sub.i.sup.XX. An initial value of N local fields h.sub.i.sup.XX, b.sub.i, is read from the DRAM 41b and held in the h.sub.XX updating and holding circuit 54.

[0186] For example, the h.sub.YX updating and holding circuit 55 includes a register, an SRAM, or the like and holds M local fields h.sub.j.sup.YX corresponding to the number of auxiliary variables. The h.sub.YX updating and holding circuit 55 calculates updated values of M local fields h.sub.j.sup.YX by adding each of the M products output by the multiplier 53 to the corresponding h.sub.j.sup.YX out of M local fields h.sub.j.sup.YX. An initial value of M local fields h.sub.j.sup.YX, d.sub.j, is read from the DRAM 41b and held in the h.sup.YX updating and holding circuit 55.

[0187] The y calculating and holding circuit 56 calculates y.sub.j which is M auxiliary variables and a difference (Δy.sub.j) from the previously calculated y.sub.j. As described above, y.sub.j is determined by using the expression of y.sub.j=f(h.sub.j.sup.YX). For example, the y calculating and holding circuit 56 outputs y.sub.jn that is a value of 0 or 1 in accordance with a result of comparison between the value of q.sub.jn represented by Expression (10) and −d.sub.j (for example, k−3/2 described above).

[0188] For example, the y calculating and holding circuit 56 includes a register, an SRAM, or the like and holds M auxiliary variables y.sub.j having been calculated.

[0189] For example, the E updating and holding circuit 57 includes a register, an SRAM, or the like, holds E that is the value of the evaluation function indicated in Expression (1), and calculates an updated value of E. For example, in the case where the change in the value of x.sub.jn is allowed, the updated value of E is obtained by using the following expression: E=E−(h.sub.jn.sup.XX+h.sub.jn.sup.XY)Δx.sub.jn. As an initial value of E, E.sub.0 of Expression (3) is set in the E updating and holding circuit 57.

[0190] The multiplier 59 outputs the product of Δy.sub.j and F.sub.ij read from the DRAM 41b.

[0191] The h.sub.XY updating and holding circuit 60 includes, for example, a register, an SRAM, or the like, holds N local fields h.sub.i.sup.XY, and calculates updated values of N local fields h.sub.i.sup.XY by adding F.sub.iiΔy.sub.j, for each j, output by the multiplier 59 to corresponding h.sub.i.sup.XY out of N local fields h.sub.i.sup.XY. As an initial value of N local fields h.sub.i.sup.XY, 0 is set in the h.sup.XY updating and holding circuit 60.

[0192] The addition circuit 61 outputs the addition result of the local field held by the h.sub.XX updating and holding circuit 54 and the local field held in the h.sup.XY updating and holding circuit 60. The addition result is used for the controller 50 and the E updating and holding circuit 57 to calculate ΔE. In the case where the value of x.sub.jn changes, the addition circuit 61 outputs h.sub.jn.sup.XX+h.sub.jn.sup.XY as illustrated in FIG. 1.

[0193] Also with the data processing apparatus 40 according to the third embodiment as described above, by using the FPGA 41a having the circuit configuration as illustrated in FIG. 11, the functions similar to those of the processing unit 12 of the data processing apparatus 10 according to the first embodiment are realized, and the effects similar to those of the data processing apparatus 10 according to the first embodiment are obtained.

Fourth Embodiment

[0194] According to the examples of the embodiments described above, it is assumed that, as illustrated in FIG. 2, k auxiliary variables that are values of a single bit of 0 or 1 are used corresponding to the number of k state variables (x.sub.j1 to x.sub.jk) included in the kth term. However, as described below, when the auxiliary variable is a variable having a value of two bits or more, it is sufficient that a single auxiliary variable be used for k state variables included in the kth term.

[0195] FIG. 12 illustrates an example in which an auxiliary variable having a value of two bits is used. In FIG. 12, the auxiliary variable having a two-bit value is denoted by q.sub.m.

[0196] It is determined that, when the sum of k literals of x.sub.j1 to x.sub.jk is k, q.sub.m is 2. It is determined that, when this sum is k−1, q.sub.m is 1. It is determined that, when this sum is k−2 or smaller, q.sub.m is 0. In the example illustrated in FIG. 12, k literals of x.sub.j1 to x.sub.jk are all positive literals.

[0197] For example, h.sub.j.sup.YX calculated as σ.sub.j1 to σ.sub.jk=1, d.sub.m=−(k−2) may be set as q.sub.m. For example, in this case, q.sub.m=f(h.sub.j.sup.YX)=h.sub.j.sup.YX.

[0198] The local fields (h.sub.j1.sup.XY to h.sub.jk.sup.XY) generated for x.sub.j1 to x.sub.jk by q.sub.m are converted from value of the q.sub.m by conversion units 70j1, 70jn, 70jk illustrated in FIG. 12.

[0199] For example, in the case where q.sub.m is 2, the constraint condition represented by the kth term is not satisfied, and accordingly, the conversion unit 70jn outputs Z.sub.<j1 . . . jk> as h.sub.jn.sup.XY. In the case where q.sub.m is 1, when the literal by x.sub.jn is 0, the constraint condition is not satisfied in the case where the value is changed, and accordingly, the conversion unit 70jn outputs Z.sub.<j1 . . . jk> as h.sub.jn.sup.XY. When the literal by x.sub.jn is 1, the constraint condition is satisfied in the case where the value is changed, and accordingly, the conversion unit 70jn outputs 0 as h.sub.jn.sup.XY. When the value of x.sub.jn is any value, in the case where q.sub.m is 0, the constraint condition is satisfied after the change, and accordingly, the conversion unit 70jn outputs 0 as h.sub.jn.sup.XY.

[0200] The conversion units 70j1 to 70jk as described above may be applied to the data processing apparatus 20 and 40 when, for example, the conversion units 70j1 to 70jk are incorporated into the h&y updating and holding unit 33b illustrated in FIG. 5 or incorporated as a logic circuit into the h.sup.XY updating and holding circuit 60 illustrated in FIG. 11.

[0201] When the technique as described above is used, the number of auxiliary variables may be decreased. For example, when the number of state variable groups forming a k-field combination is m.sub.k, the number of auxiliary variables may be m.sub.k.

Fifth Embodiment

[0202] Although it has been described that the state variables (x.sub.1 to x.sub.N) are binary variables having a value of 0 or 1 in the examples of the embodiments described above, the state variables (x.sub.1 to x.sub.N) may be spin variables having a value of −1 or 1.

[0203] FIG. 13 illustrates an example in which spin variables are used as the state variables.

[0204] The combination relationship between x.sub.j1 to x.sub.jk forming the k-field combination and y.sub.j1 to y.sub.jk as the auxiliary variables is the same as that illustrated in FIG. 2.

[0205] In the case where the spin variable is used as the state variable, when changing of Δx.sub.i is performed as Δx.sub.i=−x.sub.i−x.sub.i=−2x.sub.i, calculations at the time of updating the energy and h.sub.i.sup.XX similarly to those in the case where the binary variable is used (see steps S40 and S41 illustrated in FIG. 9) may be performed.

[0206] However, f(h.sub.j.sup.YX) for calculation of h.sub.i.sup.XY is different from that in the case where the binary variable is used. Since a sign is included in the spin variable, for example, h.sub.jn.sup.XY generated when y.sub.jn which is an auxiliary variable is 1 for x.sub.jn which is a state variable included in the kth term may be represented by Expression (11) below without using a coefficient representative of the sign (corresponding to σ.sub.j1 to σ.sub.jk=1).

[00008]$\begin{array}{cc}{Z}_{.Math.j1.Math.\mathrm{jk}.Math.}\stackrel{k}{\underset{l=1,l\ne n}{.Math.}}{x}_{\mathrm{jl}}& \left(11\right)\end{array}$

[0207] In Expression (11), −Z.sub.<j1 . . . jk> is used when the number of state variables having a value of −1 out of the state variables of x.sub.j1 to x.sub.jk except for x.sub.jn is an odd number and Z.sub.<j1 . . . jk> is used when this number is an even number. To generate such h.sub.jn.sup.XY, it is sufficient that Expression (12) below be used as h.sub.jn.sup.YX in y.sub.jn=f(h.sub.jn.sup.YX).

[00009]$\begin{array}{cc}{h}_{\mathrm{jn}}^{\mathrm{YX}}=\{\begin{array}{c}\frac{1}{2}{.Math.}_{l=1,l\ne n}^k{x}_{\mathrm{jl}}\mathrm{for}\mathrm{odd}k\\ \frac{1}{2}{.Math.}_{l=1,l\ne n}^k{x}_{\mathrm{jl}}-\frac{1}{2}\mathrm{for}\mathrm{even}k\end{array}& \left(12\right)\end{array}$

[0208] In the case where k is an odd number, an expression on the upper side of Expression (12) is used, and in the case where k is an even number, an expression on the lower side of Expression (12) is used. Regarding f(h.sub.jn.sup.YX), f(h.sub.jn.sup.YX) becomes a function that outputs −1 since, when h.sub.jn.sup.YX is an even number, the number of the state variables having a value of −1 out of x.sub.j1 to x.sub.jk except for x.sub.jn is an odd number and becomes a function that outputs +1 when h.sub.jn.sup.YX is an odd number.

[0209] When such y.sub.jn=f(h.sub.jn.sup.YX) is used, h.sub.jn.sup.XY may be represented as h.sub.jn.sup.XY=Z.sub.<j1 . . . jk>y.sub.jn.

[0210] When the method of calculating h.sub.jn.sup.XY and the like are changed as described above, the spin variables may be handled as the state variables. When the spin variables are able to be handled, for example, the following effects may be obtained.

[0211] In the case where a problem originally formulated by using the spin variable is converted into a problem using the binary variable, the number of coefficients may increase. For example, in the case where a cubic evaluation function by the spin variable is converted into an evaluation function by the binary variable, the number of coefficients may increase due to generation of quadratic and linear terms by the conversion.

[0212] Directly handling the spin variable may decrease an increase in coefficient due to the conversion and the memory capacity for storing the coefficient.

[0213] Examples of the problem formulated by using the spin variable include, for example, problems related to quantum chemistry calculation. In quantum chemical calculation, when a Hamiltonian of a ground state of an electron system is expanded with the spin variable, a form including a higher-order spin product is obtained.

Sixth Embodiment

[0214] As is the case with the fourth embodiment, even when the spin variable is used, the number of auxiliary variables used for k state variables included in the kth term may be one.

[0215] Since x.sub.jl is a spin variable in Expression (11) and x.sub.jl.sup.2=1, Expression (11) may be transformed as presented by Expression (13) below.

[00010]$\begin{array}{cc}{Z}_{.Math.j1.Math.\mathrm{jk}.Math.}\stackrel{k}{\underset{l=1,l\ne n}{.Math.}}{x}_{\mathrm{jl}}=Z_{.Math.j1.Math.\mathrm{jk}.Math.}{x}_{\mathrm{jn}}\stackrel{k}{\underset{l=1}{.Math.}}{x}_{\mathrm{jl}}=Z_{.Math.j1.Math.\mathrm{jk}.Math.}{x}_{\mathrm{jn}}{q}_m& \left(13\right)\end{array}$

[0216] For example, h.sub.jn.sup.XY for x.sub.jn may be calculated by generating q.sub.m which is one auxiliary variable and multiplying q.sub.m by Z.sub.<j1 . . . jk>x.sub.jn. After the initial value (+1 or −1) has been set, q.sub.m is updated by inverting the sign every time any of values of x.sub.j1 to x.sub.jk changes. When the value of x.sub.jn changes, h.sub.jn.sup.XY does not change, h.sub.j1.sup.XY to h.sub.jk.sup.XY for x.sub.j1 to x.sub.jk other than x.sub.jn change, and the changed part is Z.sub.<j1 . . . jk>x.sub.j1Δq.sub.m to Z.sub.<j1 . . . jk>x.sub.jkΔq.sub.m.

[0217] FIG. 14 illustrates an example in which the number of the auxiliary variables used for the state variables that are k spin variables included in the kth term is one.

[0218] The local fields (h.sub.j1.sup.XY to h.sub.jk.sup.XY) generated for the x.sub.j1 to x.sub.jk by q.sub.m are obtained by multiplying Z.sub.<j1 . . . jk>q.sub.m by the values of the x.sub.j1 to x.sub.jk by using multiplication units 80j1 , . . . , 80jn, . . . , 80jk illustrated in FIG. 14.

[0219] The multiplication units 80j1 to 80jk as described above may be applied to the data processing apparatus 20 and 40 when, for example, the multiplication units 80j1 to 80jk are incorporated into the h&y updating and holding unit 33b illustrated in FIG. 5 or incorporated as a logic circuit (multiplier) into the h.sub.XY updating and holding circuit 60 illustrated in FIG. 11.

[0220] When the technique as described above is used, the auxiliary variable may be generated as a neuron of multiple inputs and multiple outputs for one kth order combination. When a set of Z.sub.<j1 . . . jk> and the identification numbers (j1 to jk) of the state variables included in the kth term are read from the memory (for example, the storage unit 32 or the DRAM 41b) once, the local fields (h.sub.j1.sup.XY to h.sub.jk.sup.XY) for x.sub.j1 to x.sub.jk may be calculated.

Seventh Embodiment

[0221] Although it is assumed in the examples of the embodiments described above that the auxiliary variables (such as y.sub.j1 to y.sub.jk illustrated in FIG. 2) are used in a single layer and the weight values between the auxiliary variables is 0 as illustrated in FIG. 6, the auxiliary variables may be used in a plurality of layers as described below.

[0222] FIG. 15 illustrates an example in which a plurality of auxiliary variables are used in a plurality of layers. In the example illustrated in FIG. 15, the auxiliary variables of y.sub.1 to y.sub.M form a multilayer network.

[0223] By setting the initial value and the weight value, y.sub.1 to y.sub.M may also function as a single-layer auxiliary variable group (or a single auxiliary variable) that causes the state variables included in the above-described kth term to generate local fields related to the kth term.

[0224] Furthermore, as illustrated in FIG. 15, when y.sub.1 to y.sub.M is formed in a plurality of layers and the weight value between y.sub.1 to y.sub.M is set, not only a higher-order term but also a more usual cost function may be handled.

Calculation Example

[0225] FIG. 16 illustrates an example of calculation results.

[0226] FIG. 16 illustrates an example in which a SAT-type discrete optimization problem with a known solution (seven instances in FIG. 16) is calculated by using the data processing apparatus 20 as described in the second embodiment. In each of the instances, the number of state variables included in the evaluation function is different from the number of logical clauses of higher-order terms. According to the example of the calculation results illustrated in FIG. 16, all the logical clauses in all the seven instances are satisfied, and the solutions are obtained by the amounts of time indicated by “SOLUTION TIME (s)”.

[0227] Although aspects of the data processing apparatus, the program, and the method of processing data according to the present disclosure have been described above based on the embodiments, the embodiments are merely exemplary and not limited to the above description.

[0228] 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.