JP7613562B2 - Polynomial conversion device, polynomial conversion method, and program - Google Patents

Description

The present invention relates to a technique for replacing variables in a multivariate polynomial with other variables.

It is said that it is difficult for the currently widely used von Neumann computers to efficiently solve combinatorial optimization problems. In recent years, therefore, research and development has been progressing on quantum annealing machines and Ising machines, which are computers that can solve combinatorial optimization problems more efficiently than von Neumann computers.

These new computers take as input the objective function of the combinatorial optimization problem in question, which is a QUBO (Quadratic Unconstrained Binary Optimization) objective function or an optimization function expressed as an equivalent Ising Hamiltonian, and can quickly calculate the solution to the problem.

The QUBO objective function and its equivalent Ising Hamiltonian are multivariate quadratic polynomials for binary variables (0-1 variables) that take the value 0 or 1, but there are methods to convert multivariate polynomials of any degree for 0-1 variables into the QUBO objective function or its equivalent Ising Hamiltonian (see, for example, non-patent documents 1 and 2).

Nike Dattani, “Quadratization in Discrete Optimization and Quantum Mechanics”, [online], arXiv:1901.04405v2 [quant-ph] 23 Sep 2019, [Retrieved March 30, 2021], Internet <https://arxiv.org/pdf/1901.04405.pdf> Endre Boros, Yves Crama, Elisabeth Rodriguez-Heck, “Quadratizations of symmetric pseudo-Boolean functions: sub-linear bounds on the number of auxiliary variables”, [online], International Symposium on Artificial Intelligence and Mathematics (ISAIM 2018), 4-Jan-2018, [Retrieved March 30, 2021], Internet: https://orbi.uliege.be/handle/2268/220766

In the conventional method of converting a multivariate polynomial of any degree related to 0-1 variables into a QUBO objective function or its equivalent Ising Hamiltonian, each term (monomial) of degree 3 or higher is individually replaced with a quadratic polynomial. Therefore, one or more additional variables are required for each monomial of degree 3 or higher.

However, for example, if a multivariate polynomial is obtained by multiplying multiple polynomials, the number of monomials obtained by expanding this multivariate polynomial increases combinatorially, and a large number of additional variables are required.

Currently available quantum annealing machines and Ising machines have a limited number of variables that can be input, so an explosive increase in additional variables would make it impossible to run on these quantum annealing or Ising machines.

Such problems are common not only when generating optimization functions to solve combinatorial optimization problems using a quantum computer, but also when converting the variables of a multivariate polynomial of any degree into a multivariate polynomial of a lower degree.

The present invention has been made in consideration of these points, and aims to provide a technology that can convert the variables of a multivariate polynomial of any degree into a multivariate polynomial of a lower degree using a smaller number of variables than conventional methods.

A multivariate polynomial f(x ₀ , ..., x _N- 1 ) for N variables x ₀ , ..., x _N-1 is input, and multivariate polynomial g(x ₀ , ..., x _N-1 , a 0 , ..., a J-1 ) is obtained by replacing the divisors x _z(j,0) ... x z( _{j ,M(j)-1)} common to multiple terms in multivariate polynomial f(x ₀ , ..., x _N-1 ) with the same additional variable a _j to obtain multivariate polynomial g( _{x 0 , ..., x N-1 , a 0 ,} ..., a _{J-1 )} and a constraint equation s(a _j , x _z(j,0) , ..., x _z(j,M(j)-1) ) which takes the minimum value when a j = x _z (j,0) ... x _z( j,M( _j )-1). _J-1 ) = g(x ₀ , ..., x _N-1 , a ₀ , ..., a _J-1 ) + s(a ₀ , x _z(0,0) , ..., x _z(0,M(0)-1) ) + ... + s(a _J-1 , x _z(J-1,0) , ..., x _{z(J-1,M(J-1))} ) is obtained and output. Here, J is a positive integer, N, M(j) are integers equal to or greater than 2, j = 0, ..., J-1, m = 0, ..., M(j)-1, and z(j,m) ∈ {0, ..., N-1} is the function value for (j,m).

As described above, in the present invention, since the divisors common to multiple terms are replaced with the same additional variables, it is possible to convert the variables of a multivariate polynomial of any degree into a multivariate polynomial of a lower degree using fewer variables than in the past. In addition, the addition of a constraint equation ensures that the divisors before the replacement and the additional variables are identical.

FIG. 1 is a block diagram illustrating the functional configuration of a polynomial conversion device according to an embodiment. FIG. 2 is a flow chart illustrating the process of the polynomial conversion device of the embodiment. FIG. 13 is a diagram illustrating a procedure for selecting a summary term by heuristic search. FIG. 13 is a diagram illustrating a procedure for selecting a summary term by heuristic search. FIG. 5 is a graph showing the experimental results showing the effect of reducing the number of added variables. FIG. 6 is a block diagram illustrating a hardware configuration of the polynomial transformation device according to the embodiment.

Hereinafter, an embodiment of the present invention will be described with reference to the drawings.
First, the principle of the embodiment will be described.
In an embodiment, a common divisor (summary term) of multiple monomials in the target multivariate polynomial is found, and this summary term is replaced with an additional variable (also called an "auxiliary variable"), and a constraint is added that requires the summary term and the additional variable to have the same value so that the meaning of the target multivariate polynomial does not change. That is, the conversion unit receives as input a multivariate polynomial f(x ₀ , ..., x _{N-1 ) for N variables x 0 , ..., x N-1 , and} converts the multivariate polynomial g(x ₀ , ..., x _{N-1 ,} a 0 , ..., a J-1 ) obtained by replacing divisors (summarize terms) _xz(j,0) ... _xz(j,M(j)-1) common to a plurality of terms (monomials ₎ in the multivariate polynomial f(x ₀ , ..., x _N-1 ) with the same additional variable a j , and a constraint equation s(a _j , _{xz(j,0) , ...} , _xz(j,M(j)-1) which is a function (Summarize Divisor) that takes the minimum value when a _{j =xz(j,0)} ... _{xz(j,M(j)-1).} ), and obtain and output the multivariate polynomial h(x ₀ , ..., x _N-1 , a ₀ , ..., a _J-1 ) = g(x ₀ , ..., x _N-1 , a ₀ , ..., a _J-1 ) + s(a ₀ , x _z(0,0) , ..., x _z(0,M(0)-1) ) + ... + s(a _J-1 , x _z(J-1,0) , ..., x _{z(J-1,M(J-1))} ). Here, J is a positive integer representing the number of summary terms, N is an integer of 2 or more representing the number of types of variables, M(j) is an integer of 2 or more representing the number of variables constituting the j-th summary term, and satisfies 2≦M(j)≦N, j=0,...,J-1, m=0,...,M(j)-1, and z(j,m)∈{0,...,N-1} is the function value for (j,m). For all j=0,...,J-1, the value of M(j) may be the same (e.g., M(0)=M(1)=...=M(J-1)=2), or may not be the same (e.g., M(0)=3, M(1)=2,...,M(J-1)=2). The variables x ₀ , ..., x _N-1 may be any variables, but for example, each of the variables x ₀ , ..., x _N-1 may be a binary variable x _i ∈{b ₀ , b ₁ }, where b ₀ ≠ b _1. However, i=0, ..., N-1. In particular, when the binary variable x _i is a 0-1 variable, b ₀ =0 and b ₁ =1. The possible values for each variable x _i may be set individually for each i. For example, each of the variables x ₁ , ..., x _N may be a binary variable x _i ∈{b _0,i , b _1,i }, where each {b _0,i , b _1,i } may be different depending on i. In particular, when the binary variable x _i is a 0-1 variable, (b _0,i , b _1,i )=(0,1) or (b _0,i , b _1,i )=(1,0) may differ depending on i. There is no limitation on the input multivariate polynomial f(x ₀ , ..., x _N-1 ). For example, the multivariate polynomial f(x ₀ , ..., x _N-1 ) is some objective function to be minimized or a function equivalent to the objective function. One example of the multivariate polynomial f(x ₀ , ..., x _N-1 ) is a multivariate polynomial for 0-1 variables that represents the objective function of a combinatorial optimization problem or a function equivalent thereto (for example, the Ising Hamiltonian). Moreover, the output multivariate polynomial g( _x0 ,..., _xN-1 , _a0 ,..., _aJ-1 ) is obtained by replacing the summary terms _xz(j,0) ... _xz(j,M(j)-1) common to a plurality of terms with the same additional variable _{aj for j=0,...,J-1. The multivariate polynomial h is obtained by adding the constraint equation s(aj,xz(j,0),...,xz(j,M(j)-1)) for j = 0 , ...} ,J-1 to the multivariate polynomial g(x0,...,xN _-1 , _a0 ,..., _aJ-1 ).

In this way, since the summary terms _xz(j,0) ... _xz(j,M(j)-1) common to multiple terms are replaced with the same additional variable _aj , the variables of a multivariate polynomial f( _x0 , ...,xN _-1 ) of any degree can be converted into a multivariate polynomial h( _x0 , ...,xN _-1 , _a0 , ..., _aJ-1 ) of a lower degree with fewer variables than before. For example, a multivariate polynomial of any degree regarding 0-1 variables can be converted into a QUBO objective function or an Ising Hamiltonian equivalent thereto with fewer additional variables than before. In addition, the constraint equation s( _aj , _xz(j,0) , ...,xz _(j,M(j)-1) is added, thereby ensuring the identity of the summary terms _xz(j,0) ... _xz(j,M(j)-1) before replacement and the additional variable _aj .

For example, the multivariate polynomial g(x ₀ , ..., x _N-1 , a ₀ , ..., a _J-1 ) may include terms replaced by the product of multiple additional variables. That is, the multivariate polynomial g(x ₀ , ..., x _N-1 , a ₀ , ..., a _J-1 ) may have terms obtained by replacing some or all of certain terms of the multivariate polynomial f(x ₀ , ..., x _N-1 ) by the product a _{j(0 )} ... a j( _R-1) of R additional variables a j(0) ... a _j(R-1) . Here, R is an integer equal to or greater than 2, r = 0, ..., R-1, j(r) is a function value of r, and {j(0), ..., j(R-1)} ⊂ {0, ..., J-1}. This allows the degree of the terms to be efficiently reduced.

For example, the multivariate polynomial g(x ₀ , ..., x _N-1 , a ₀ , ..., a _J-1 ) may have a plurality of terms replaced by the product of a plurality of additional variables, and only some of the additional variables of the plurality of terms may be identical to one another. In other words, the multivariate polynomial g _{(x 0 ,} ..., x _N-1 , a ₀ , ..., a _{J-1 )} may further have a term obtained by replacing some or all of a certain term of the multivariate polynomial f(x ₀ , ..., x _N-1 ) by the product a j _'(0) ...a _j'(R'-1) of R' additional variables a _j'(0) ...a j'(R'-1), and only some of the R additional variables a j(0) ...a _j(R-1) may be included in the set of the R' additional variables a _j'(0) ...a _j'(R'-1) . where R' is an integer equal to or greater than 2, r' = 0, ..., R'-1, j(r') is a function value of r', and {j'(0), ..., j'(R'-1)} ⊂ {0, ..., J-1}. This allows for an efficient reduction in the order of terms.

For example, at least some of the terms of the multivariate polynomial f(x ₀ , ..., x _N-1 ) are monomials of degree 3 or higher, and the terms of the multivariate polynomial g(x ₀ , ..., x _N-1 , a ₀ , ..., a _J-1 ) are monomials of degree 2 or lower. For example, all of the terms of the multivariate polynomial g(x ₀ , ..., x _N-1 , a ₀ , ..., a _J-1 ) are monomials of degree 2 or lower. For example, the target multivariate polynomial is made into a quadratic expression by selecting divisors such that at least some of the monomials are expressed as a product of two additional variables.

ここで、Ａ_ｍは変数（追加変数）であり、

である。なお、＃（Ａ）は

ビットで表現できる２進数表記された値を表している。 In addition, there is no limitation to the constraint equation s(a _j , x _z(j,0) , ..., x _z(j,M(j)-1) ). For example, when each of variables x ₀ , ..., x _N-1 is a 0-1 variable x _i ∈{0,1}, the following equation (1) can be the constraint equation s(a _j , x _z(j,0) , ..., x _z(j,M(j)-1) ).

where A _m is a variable (additional variable),

In addition, #(A) is

It represents a binary value that can be expressed by bits.

Here, the first term on the right hand side of equation (1) is minimized when the number of 1s, x ₀ +...+x _M(j), contained in x ₀ ,...,x _M(j) ∈{0,1} is equal to #(A)+a _j (Fact 1). On the other hand, the second term on the right hand side of equation (1) is minimized when a _j is 0 if one or more of A _m are 0. Therefore, the second term on the right hand side of equation (1) is minimized when all A _m are 1 if a _j is 1. From equation (2), "all A _m are 1" and "#(A)=M(j)-1" are equivalent. Therefore, if a _j is 1, the second term on the right hand side of equation (1) is minimized when #(A)=M(j)-1. In other words, if a _j =1, the second term on the right hand side of equation (1) is minimized when #(A)+a _j =M(j). In other words, the second term on the right-hand side of equation (1) is minimized when #(A) + _aj = M(j) _aj = 1 (Fact 2). From facts 1 and 2, equation (1) is minimized when the number of 1s contained in _x0 , ..., xM _(j) ∈ {0, 1} is _x0 + ... + xM _(j) = M(j) _aj = 1. Therefore, equation (1) is minimized when _x0 , ..., _xM(j) are all 1 _aj = 1. Therefore, equation (1) is minimized when _aj = _x0 ... _xM(j) .

[First embodiment]
Next, a first embodiment will be described. Hereinafter, the same symbols will be used for matters that have already been described and the description will be omitted.
<Configuration>
As illustrated in Fig. 1, the polynomial conversion device 1 of this embodiment has a conversion unit 10, a storage unit 13, and a control unit 14. Here, the conversion unit 10 illustrated in this embodiment has a summary term selection unit 11 and a summary term conversion unit 12. However, these do not limit the present invention, and at least some functions of multiple processing units may be integrated. Furthermore, each process is executed under the control of the control unit 14, and data obtained in each process is stored in the storage unit 13 and is read out and used in other processes as necessary.

<Processing>
The polynomial conversion process of this embodiment will be illustrated.
A multivariate polynomial f(x ₀ , ..., x _N-1 ) to be converted is input to the conversion unit 10 of the polynomial conversion device 1. There is no limitation on the multivariate polynomial f(x ₀ , ..., x _N-1 ), but for example, a multivariate polynomial f(x ₀ , ..., x _N-1 ) with respect to 0-1 variables that represents an objective function of a combinatorial optimization problem or a function equivalent thereto (for example, an Ising Hamiltonian) is input.

The conversion unit 10 converts a multivariate polynomial g(x ₀ , ..., x _{N-1 , a 0 ,} ..., a J-1 ) obtained by replacing the divisors (summary terms) _xz(j,0) ... _xz(j,M(j)-1) common to a plurality of terms in the input multivariate polynomial f(x 0 , ..., x N-1 ) with the same additional variable a _j to obtain a multivariate polynomial g(x ₀ , ..., x _N-1 , a ₀ , ..., a _J-1 ) and a constraint equation s(a _{j , xz(j,0)} , ..., _{xz(j,M(j)-1) )} which takes the minimum value when a _j = _xz(j,0) ... xz(j,M(j)-1). The conversion unit 10 converts a multivariate polynomial g(x ₀ , ..., x _N-1 , a ₀ , ..., a J-1 ) obtained by adding the constraint equation s(a j , _{xz(j,0) , ..., xz(j,M} ( _j)-1 ) ) which takes the _minimum value when a j = xz(j,0) ... xz(j,M _(j )-1) _{. J-1} ) + s(a ₀ , x _z(0,0) , ..., x _z(0,M(0)-1) ) + ... + s(a _J-1 , x _z(J-1,0) , ..., x _{z(J-1,M(J-1))} ) is obtained and output.

The function conversion process of this embodiment will be illustrated with reference to FIG.
A multivariate polynomial f(x ₀ , ..., x _N-1 ) is input to the summary term selection unit 11 of the conversion unit 10. The summary term selection unit 11 selects and outputs summary terms xz(j,0) ... _xz(j,M(j)-1) that are common to multiple terms of the multivariate polynomial f( _{x 0 ,} ..., x _N-1 ) for j=0, ...,J-1. There is no limitation on the method of selecting the summary terms _xz(j,0) ... _xz(j,M(j)-1) , but for example, the summary terms _xz(j,0) ... xz _(j,M(j)-1) may be selected by heuristic search. This will be described in detail later (step S11).

The multivariate polynomial f(x ₀ , ..., x _N-1 ) and the summary terms x z(j _{,0) ... x z( j,M(j)-1)} for =0, ...,J-1 output from the summary term selection unit 11 are input to the summary term conversion unit 12 of the conversion unit 10. The summary term conversion unit 12 obtains and outputs a multivariate polynomial h( _x0 , ..., xN-1 _{, a0,} ... _{, aJ -1} ) by adding a multivariate polynomial g( _x0 , ..., xN _-1 , _a0 , ..., _aJ-1 ) obtained by replacing the summary term _xz (j,0) ... _{xz(j, M(j)-1) in the multivariate polynomial f(x0, ..., xN-1) with an additional variable aj and a constraint equation s(aj, xz(j,0), ..., xz(j, M(j)-1) ) ( step S12 ) .}

<Summary Term Selection by Heuristic Search>
When selecting J summary terms from N types of variables x ₀ , ..., x _N-1, there are O(2 ^{N^J} ) candidates, so it is difficult to select the optimal summary term by exhaustive search. Therefore, summary terms may be selected by heuristic search. Figures 3 and 4 show an example of a procedure for selecting summary terms by heuristic search.

As shown in Fig. 3, the summary term selection unit 11 stores in half_term those monomials (terms) constituting the multivariate polynomial f( _x0 , ..., _xN-1 ) that have summary term candidates (divisor candidates) for converting them into quadratic monomials (step S111). Next, the following steps S112 to S119 are repeated until both terms and half_term are empty. The summary term selection unit 11 replaces partial monomials (summary term candidates) with the maximum heuristic evaluation score (score(terms, half_terms, candidate)) with summary terms (summarized_term) first (step S112). The evaluation score (score(terms, half_terms, candidate)) is determined according to Fig. 4 (steps S1121 to S1124). That is, the summary term selection unit 11 adds a score of +2 when it completes replacing one unreplaced monomial from terms in one go (increases the evaluation score by 2) (step S1121), adds a score of +1 when it moves one unreplaced monomial from terms to half_terms (increases the evaluation score by 1) (step S1122), adds a score of +1 when it completes replacing one unreplaced monomial from half_terms in combination with any of x ₀ , ..., x _N-1 (step S1123), and adds a score of +1 when it completes replacing one unreplaced monomial from half_terms in combination with any of the replaced summary terms (step S1124).

As shown in FIG. 3, the summary term selection unit 11 repeats steps S113 to S116 for the terms stored in half_term. That is, the summary term selection unit 11 targets only monomials whose summary terms are partial monomials (step S113), and if the target monomial (term) is the summary term itself or a summary term x an existing variable, the replacement is completed (step S114), if the target monomial (term) is the product of the selected summary term and an already registered (replaced) summary term, the replacement is completed (step S115), and if the target monomial (term) cannot be removed (replaced), the monomial (term) is added to the summary term candidates (candidates) (step S116). In step S115, the selected summary term and the already registered summary term may contain overlapping variables.

Next, the summary term selection unit 11 repeats steps S117 to S119 for the term stored in term. That is, the summary term selection unit 11 targets only monomials whose summary term is a partial monomial (step S117), and if term is the summary term itself or summary term × existing variable, the replacement is completed (step S118), and otherwise moves the target monomial to half_terms (step S119).

<Specific examples>
An example in which a multivariate polynomial f(x ₀ , . . . , x ₄ ) regarding five 0-1 variables x ₀ , . . . , x ₄ is the conversion target is shown below.
A multivariate polynomial to transform:
f( _x0 ,..., _x4 )
=A ₀ x ₀ x ₁ x ₂ x ₃ +A ₁ x ₀ x ₁ x ₂ x ₄ +A ₂ x ₀ x ₁ x ₂ +A ₃ x ₀ x ₁ x ₃ x ₄ +A ₄ x ₀ x ₁ x ₃ +
A ₅ x ₀ x ₁ x ₄ +A ₆ x ₀ x ₂ x ₃ x ₄ +A ₇ x ₀ x ₂ x ₃ +A ₈ x ₀ x ₂ x ₄ +A ₉ x ₀ x ₃ x ₄ +
A ₁₀ x ₁ x ₂ x ₃ x ₄ +A ₁₁ x ₁ x ₂ x ₃ +A ₁₂ x ₁ x ₂ x ₄ +A ₁₃ x ₁ x ₃ x ₄ +A ₁₄ x ₂ x ₃ x ₄

Summary section:
a ₀ = x ₀ x ₁ x _4
a1 = _{x0 x1
a2} = _{x0 x4
a3} = _{x1 x4
a4} = _{x2 x3}

Multivariate polynomials:
g( _x0 ,..., _x4 )
= A ₀ a ₁ a ₄ + A ₁ a ₀ x ₂ + A ₂ a ₁ x ₂ + A ₃ a ₀ x ₃ + A ₄ a ₁ x ₃ +
A ₅ a ₀ x ₄ + A ₆ a ₂ a ₄ + A ₇ x ₀ a ₄ + A ₈ a ₂ x ₂ + A ₉ a ₂ x ₃ +
A ₁₀ x ₁ a ₄ x ₄ +A ₁₁ x ₁ a ₄ +A ₁₂ a ₃ x ₂ +A ₁₃ a ₃ x ₃ +A ₁₄ a ₄ x ₄

Constraint formula:
s(a ₀ , x ₀ , x ₁ , x ₄ )
s(a ₁ , x ₀ , x ₁ )
s(a ₂ , x ₀ , x ₄ )
s(a ₃ , x ₁ , x ₄ )
s(a ₄ , x ₂ , x ₃ )

The output multivariate polynomial:
h( _x0 ,..., _x4 )
= A ₀ a ₁ a ₄ + A ₁ a ₀ x ₂ + A ₂ a ₁ x ₂ + A ₃ a ₀ x ₃ + A ₄ a ₁ x ₃ +
A ₅ a ₀ x ₄ + A ₆ a ₂ a ₄ + A ₇ x ₀ a ₄ + A ₈ a ₂ x ₂ + A ₉ a ₂ x ₃ +
A ₁₀ x ₁ a ₄ x ₄ +A ₁₁ x ₁ a ₄ +A ₁₂ a ₃ x ₂ +A ₁₃ a ₃ x ₃ +A ₁₄ a ₄ x ₄ +
s(a ₀ , x ₀ , x ₁ , x ₄ )+
s(a ₁ , x ₀ , x ₁ )+
s(a ₂ , x ₀ , x ₄ )+
s(a ₃ , x ₁ , x ₄ )+
s(a ₄ , x ₂ , x ₃ )

<Experimental Results>
FIG. 5 shows the results of an experiment to demonstrate the effect of this embodiment. In this experiment, a multivariate polynomial f(x ₀ , . . . , x _{N- 1} ) obtained by adding up all the cubic monomials related to N 0-1 variables x ₀ , . . . , x N-1 was used as the conversion target, and the extent to which the number of added variables was reduced by this embodiment was confirmed. The horizontal axis of FIG. 5 represents the number of types of variables N, and the vertical axis represents the number of added variables. The solid line illustrates the experimental results when the monomial substitution of this embodiment is performed, and the dashed line illustrates the experimental results when the monomial substitution of this embodiment is not performed (in the case of the conventional method). As illustrated in FIG. 5, the number of added variables is reduced by performing the monomial substitution of this embodiment, and the effect is greater as N is larger.

[Second embodiment]
A function transformation device (not shown) may transform a multivariable function F(x ₀ , ..., x _N-1 ) of any degree related to N input variables x ₀ , ..., x N _-1 into a multivariable polynomial f(x ₀ , ..., x N-1 ) related to variables x ₀ , ..., x _{N -1} as follows, and the polynomial transformation device 1 (FIG. 1) of the first embodiment may transform the multivariable polynomial f(x ₀ , ..., x _N-1 ) into a multivariable polynomial h(x ₀ , ..., x _N-1 , a ₀ , ..., a _J-1 ) as described above and output it.

あるいは、関数変換装置は、すべての組（ｓ_０，…，ｓ_Ｎ－１）∈ｕ_ｘについてＦ（ｓ_０，…，ｓ_Ｎ－１）Ｐ（ｓ_０，…，ｓ_Ｎ－１，ｘ_０，…，ｘ_Ｎ－１）を足し合わせた多変数多項式ｆ（ｘ_０，…，ｘ_Ｎ－１）を得て出力してもよい。

This function transformation device, for example, takes as input a multivariate function F(x ₀ , ..., x _N-1 ) and derives and outputs a multivariate polynomial f(x ₀ , ..., x _N-1 ) by adding F(s ₀ , ..., s _N-1 )P(s ₀ , ..., s _N-1 , x ₀ , ..., x _{N-1 )} for at least some of the pairs (s ₀ , ..., s N-1 ). For example, the function transformation device obtains and outputs a _multivariate polynomial f(x ₀ , ..., x _N-1 ) by adding F(s ₀ , ..., s _{N-1 )} P(s ₀ , ..., s _N-1 , x ₀ , ..., x _N-1 ) for _a set (s _{0 , ..., s N-1 ) ∈ d x that belongs to a domain d x of the set (x 0 ,} ..., x _N-1 ).

Alternatively, the function transformation device may obtain and output a multivariate polynomial _f (x ₀ , ..., x _N-1 ) by adding up F(s ₀ , ..., s _N-1 )P(s ₀ , ..., s _N-1 , x ₀ , ..., x _N-1 ) for all pairs (s ₀ , ..., s _N-1 ) ∈ u x.

Here, the N s ₀ , ..., s _N-1 are variables, and when (s ₀ , ..., s _N-1 ) = (x ₀ , ..., x _N-1 ), P(s ₀ , ..., s _N-1 , x ₀ , ..., x _N-1 ) = 1, and when (s ₀ , ..., s _N-1 ) ≠ (x ₀ , ..., x _N-1 ), P(s ₀ , ..., s _N-1 , x ₀ , ..., x _N-1 ) = 0. For example, each of the variables x ₀ , ..., x _N-1 is a binary variable x _i ∈{0,1}, each of the variables s ₀ , ..., s _N-1 is a binary variable s _i ∈{0,1}, i = 0, ..., N-1, x _i ^- = 1 - x _i , when s _i = 1, x _i (+)s _i = x _i , when s _i = 0, x _i (+)s _i = x _i ^- , and P(s ₀ , ..., s _N-1 , x ₀ , ..., x _N-1 ) = Π _0≦i≦N-1 (x _i (+)s _i ).

For example, the function transformation device may have a multivariable function value generation unit that receives a multivariable function F(x ₀ , ..., x _N-1 ) as input and obtains a multivariable function value F(s ₀ , ..., s _{N-1 )} for at least some of the sets (s ₀ , ..., s _N-1 ), and a multivariable polynomial generation unit that receives the multivariable function value F(s ₀ , ..., s _N-1 ) as input and obtains and outputs a multivariable polynomial f(x ₀ , ..., x _{N-1 ) by adding F(s 0 , ..., s N-1 )} P(s ₀ , ..., s N-1 _, x ₀ , ..., x N- ₁ ) for at least some of the sets (s ₀ , ..., s _N-1 ).

[Third embodiment]
When a multivariate function F(x ₀ , ..., x _N-1 ) is a multivariate function with constraints, (x ₀ , ..., x _N-1 ) that satisfies a specific constraint is valid, but (x ₀ , ..., x _N-1 ) that does not satisfy the constraint is invalid. For example, the objective function of a combinatorial optimization problem and the corresponding objective function or Ising Hamiltonian of a QUBO are the sum of a constraint function for expressing a valid solution as a combinatorial optimization problem and a cost function for expressing a more suitable solution among the valid solutions. For example, the constraint function is zero for a valid solution ((x ₀ , ..., x _N-1 ) that satisfies the constraint) and takes a large value for an invalid solution ((x ₀ , ..., x _N-1 ) that does not satisfy the constraint), and the cost function represents the evaluation of the solution with a value smaller than that of the constraint function. A solution to a combinatorial optimization problem is found by minimizing such an objective function or Ising Hamiltonian. In this case, the value of the constraint function for an invalid solution ((x ₀ , ..., x _N-1 ) that does not satisfy the constraints) becomes large, and the value of the cost function becomes meaningless. The value of the constrained multivariable function F(x ₀ , ..., x _N-1 ) for (x ₀ , ..., x _N-1 ) that does not satisfy the constraints becomes meaningless, and there is no practical problem no matter what value is set for such a constrained multivariable function F(x ₀ , ..., x _{N-1 ). Therefore, the value of the multivariable function F(x 0 , ..., x N-1 ) that} does not cause any practical problem may be changed, and the number of terms (the total number of terms related to x _i and constant terms) when the multivariable polynomial f(x ₀ , ..., x _N-1 ) is expanded may be reduced.

That is, a function transformation device (not shown) may transform a constrained multivariable function F(x ₀ , ..., x _N-1 ) of any degree for input N variables x ₀ , ..., x N-1 into a multivariable polynomial f(x 0 , ..., x _N-1 ) for variables x ₀ , ..., x _N-1 as follows, and the polynomial transformation device 1 of the first embodiment (FIG. ₁ ) may transform the multivariable polynomial f(x ₀ , ..., x _N-1 ) into a multivariable polynomial h(x ₀ , ..., x _N-1 , a ₀ , ..., a _J-1 ) as described above and output _it .

This function transformation device, for example, receives a constrained multivariable function F(x ₀ , ..., x _N-1 ), determines the multivariable function value F'(s ₀ , ..., s _N-1 ) for (s ₀ , ..., s _N-1 ) that is the same as the set (x ₀ , ..., x N _-1 ) that satisfies the constraint as F(s ₀ , ..., s _N-1 ), determines the multivariable function value F'(s ₀ , ..., s _N-1 ) for (s ₀ , ..., s _{N-1 )} that is the same as the set (x ₀ , ..., x _N- 1 ) that does not satisfy the constraint as F"(s ₀ , ..., s N-1 ), and calculates F'(s ₀ , ..., s _{N-1 )} P( _{s 0 ,} ..., s _N-1 , x ₀ , ..., x _N-1 ), and obtains and outputs a multivariate polynomial f(x ₀ , ..., x _N-1 ). However, the number of terms in the obtained multivariate polynomial f(x ₀ , ..., x _N-1 ) is less than the number of terms in the multivariate polynomial G(x ₀ , ..., x _N-1 ) obtained by adding F(s ₀ , ..., s _N-1 )P(s ₀ , ..., s _N-1 , x ₀ , ..., x N- ₁ ) for at least some of the pairs (s ₀ , ..., s _N-1 ).

For example, the function transformation device obtains and outputs a _multivariate polynomial f(x ₀ , ..., x _N-1 ) by adding F'(s ₀ , ..., s _{N -1} )P(s ₀ , ..., s _N-1 , x ₀ , ..., x _N-1 ) for _a set (s ₀ , ..., s N-1 ) ∈ d x that belongs to a domain d x of the set (x ₀ , ..., x _N-1 ). In this case, the number of terms of the multivariate polynomial f( _x0 ,..., _xN-1 ) is less than the number of terms of the multivariate polynomial _G ( _x0 ,...,xN _-1 ) obtained by adding up _F '( _s0 ,..., _sN-1 )P( _s0 ,...,sN _{-1 , x0} ,...,xN _{-1) for sets (s0,...,sN-1 )} ∈dx belonging to the domain _dx . Alternatively, the function transformation device may obtain and output the multivariate polynomial f( _x0 ,..., _xN-1 ) obtained by adding up F'( _s0 ,...,sN _-1 )P( _s0 ,...,sN _-1 , _x0 ,..., _xN-1 ) for all sets ( _s0 ,..., _sN-1 )∈ux. In this case, the number of terms in the multivariate polynomial f(x ₀ , ..., x _N-1 ) is less than the number _of terms in the multivariate polynomial G(x ₀ , ..., x _N-1 ) obtained by adding up F'(s ₀ , ..., s N _-1 )P(s ₀ , ..., s _N -1 , x ₀ , ..., x _{N -1} ) for all pairs (s ₀ , ..., s N-1 )∈u x.

である、 There is no limitation on F"(s ₀ , ..., s _N-1 ) but, for example, if variables x ₀ , ..., x _N-1 ∈{0,1} are binary variables, variables s ₀ , ..., s _N-1 ∈{0,1} are binary variables, N variables k ₀ , ..., k _N-1 ∈{0,1} are binary variables, i=0, ..., N-1, x _i ^- =1-x _i , when s _i =1, x _i (+)s _i =x _i , when s _i =0, x _i (+)s _i =x _i ^- , and P(s ₀ , ..., s _N-1 , x ₀ , ..., x _N-1 )=Π _0≦i≦N-1 (x _i (+)s _i ), then F"(s ₀ , . . . , s _N−1 ) are defined recursively as follows:

That is,

For example, the function transformation device has a multivariable function value generation unit that receives a constrained multivariable function F(x ₀ , ..., x _N-1 ) as input and obtains a multivariable function value F'(s ₀ , ..., s _N-1 ) for at least some of the sets (s ₀ , ..., s _N-1 ), and a multivariable polynomial generation unit that receives the multivariable function value F'(s ₀ , ..., s _{N-1 ) as input and obtains and outputs a multivariable polynomial f(x 0 , ..., x N-1 ) by} adding F'(s ₀ , ..., s N-1 )P(s ₀ , ..., s _N-1 , x ₀ , ..., x _N -1 ) for at least some of the sets (s ₀ , ..., s _N-1 ).

[Hardware configuration]
The polynomial conversion device 1 in each embodiment is a device configured by a general-purpose or dedicated computer having a processor (hardware processor) such as a CPU (central processing unit) and memories such as a RAM (random-access memory) and a ROM (read-only memory) executing a predetermined program. That is, the polynomial conversion device 1 in each embodiment has, for example, a processing circuit configured to implement each unit. This computer may have one processor and memory, or may have multiple processors and memories. This program may be installed in the computer, or may be recorded in a ROM or the like in advance. In addition, some or all of the processing units may be configured using electronic circuits that realize processing functions independently, rather than electronic circuits that realize functional configurations by reading programs like a CPU. In addition, an electronic circuit that configures one device may include multiple CPUs.

Figure 6 is a block diagram illustrating the hardware configuration of the polynomial conversion device 1 in each embodiment. As illustrated in Figure 6, the polynomial conversion device 1 in this example has a CPU (Central Processing Unit) 10a, an input unit 10b, an output unit 10c, a RAM (Random Access Memory) 10d, a ROM (Read Only Memory) 10e, an auxiliary storage device 10f, and a bus 10g. The CPU 10a in this example has a control unit 10aa, a calculation unit 10ab, and a register 10ac, and executes various calculation processes according to various programs loaded into the register 10ac. The input unit 10b is an input terminal to which data is input, a keyboard, a mouse, a touch panel, etc. The output unit 10c is an output terminal to which data is output, a display, a LAN card controlled by the CPU 10a that has loaded a specific program, etc. The RAM 10d is a static random access memory (SRAM), a dynamic random access memory (DRAM), or the like, and has a program area 10da in which a predetermined program is stored and a data area 10db in which various data is stored. The auxiliary storage device 10f is, for example, a hard disk, a magneto-optical disc (MO), a semiconductor memory, or the like, and has a program area 10fa in which a predetermined program is stored and a data area 10fb in which various data is stored. The bus 10g connects the CPU 10a, the input unit 10b, the output unit 10c, the RAM 10d, the ROM 10e, and the auxiliary storage device 10f so that information can be exchanged. The CPU 10a writes the program stored in the program area 10fa of the auxiliary storage device 10f to the program area 10da of the RAM 10d according to the loaded OS (Operating System) program. Similarly, the CPU 10a writes various data stored in the data area 10fb of the auxiliary storage device 10f to the data area 10db of the RAM 10d. The addresses on the RAM 10d to which the programs and data are written are then stored in the register 10ac of the CPU 10a. The control unit 10aa of the CPU 10a sequentially reads out these addresses stored in the register 10ac, reads out the programs and data from the areas on the RAM 10d indicated by the read addresses, causes the calculation unit 10ab to sequentially execute the calculations indicated by the programs, and stores the results of the calculations in the register 10ac. With this configuration, the functional configuration of the polynomial conversion device 1 is realized.

The above-mentioned program can be recorded on a computer-readable recording medium. An example of a computer-readable recording medium is a non-transitory recording medium. Examples of such recording media include magnetic recording devices, optical disks, magneto-optical recording media, semiconductor memories, etc.

The distribution of this program is, for example, by selling, transferring, lending, etc., portable recording media such as DVDs and CD-ROMs on which the program is recorded. Furthermore, the program may be distributed by storing the program in a storage device of a server computer and transferring the program from the server computer to other computers via a network. As described above, a computer that executes such a program, for example, first stores in its own storage device the program recorded in the portable recording medium or the program transferred from the server computer. Then, when executing the process, the computer reads the program stored in its own storage device and executes the process according to the read program. In addition, as another execution form of this program, the computer may read the program directly from the portable recording medium and execute the process according to the program, or, further, each time the program is transferred from the server computer to this computer, the computer may execute the process according to the received program. In addition, the server computer may not transfer the program to this computer, but may execute the above-mentioned process by a so-called ASP (Application Service Provider) type service that realizes the processing function only by issuing an execution instruction and obtaining the results. In this embodiment, the program includes information used for processing by an electronic computer and equivalent to a program (such as data that is not a direct instruction to a computer but has the nature of defining computer processing).

In each embodiment, the device is configured by executing a specific program on a computer, but at least a portion of the processing content may be realized in hardware.

The present invention is not limited to the above-described embodiments. For example, the various processes described above may not only be executed in chronological order as described, but may also be executed in parallel or individually depending on the processing capacity of the device executing the processes or as necessary. Needless to say, other modifications may be made as appropriate without departing from the spirit of the present invention.

The present invention can be used, for example, when solving combinatorial optimization problems using a quantum annealing machine or an Ising machine. For example, the present invention can convert the objective function of a combinatorial optimization problem or its equivalent multivariate polynomial f(x ₁ , ..., x _N ) with respect to 0-1 variables into a QUBO objective function or its equivalent Ising Hamiltonian with a small number of additional variables. By inputting the QUBO objective function or Ising Hamiltonian thus obtained into a quantum annealing machine or an Ising machine, the combinatorial optimization problem can be solved at high speed.

1 Polynomial conversion device 10 Conversion unit 11 Summary term selection unit 12 Summary term conversion unit

Claims (9)

J is a positive integer, N, M(j) are integers equal to or greater than 2, j = 0, ..., J-1, m = 0, ..., M(j)-1, and z(j,m) ∈ {0, ..., N-1} is a function value for (j,m),
A multivariate polynomial f(x ₀ , ..., x _{N- 1} ) for N variables x ₀ , ..., x N-1 is input, and multivariate polynomial g(x ₀ , ..., x _N-1 , a 0 , ..., a J-1 ) is obtained by replacing the divisors x _z(j,0) ... x _z(j,M(j)-1) common to a plurality of terms in the multivariate polynomial f(x ₀ , ..., x _{N-1 )} with the same additional variable a _j , and a constraint equation s(a _j , x _z (j, ₀ ) , ..., x z _{(j,M(j)-1) )} which takes the minimum value when a _j = x _z(j,0) ... x _z(j,M(j)-1 ) is obtained by adding a multivariate polynomial h(x ₀ , ..., x _N-1 , a ₀ , ..., a _a conversion unit that obtains and outputs g(x ₀ , ..., x _N-1 , a ₀ , ..., a _J-1 ) + s(a ₀ , x _z(0,0) , ..., x _z(0,M(0)-1) ) + ... + s(a _J-1 , x _z(J-1,0) , ..., x _{z(J-1,M(J-1))} );
R is an integer equal to or greater than 1, r=0,...,R-1, j(r) is a function value of r, and {j(0),...,j(R-1)} ⊂ {0,...,J-1};
the multivariate polynomial g(x ₀ , ..., x _N-1 , a ₀ , ..., a _J-1 ) has terms obtained by replacing a part or all of certain terms of the multivariate polynomial f(x ₀ , ..., _{x N-1 ) by} a product a _{j (0)} ... a _j(R-1) of R additional variables a j(0) ... a j(R-1);
A polynomial transformation device, wherein each of the additional variables a _j(0) , ..., a _j(R-1) is the additional variable a _j in jε{j(0), ..., j(R-1)}. J is a positive integer, N, M(j) are integers equal to or greater than 2, j = 0, ..., J-1, m = 0, ..., M(j)-1, and z(j,m) ∈ {0, ..., N-1} is a function value for (j,m),
A multivariate polynomial f(x ₀ , ..., x _{N- 1} ) for N variables x ₀ , ..., x N-1 is input, and multivariate polynomial g(x ₀ , ..., x _N-1 , a 0 , ..., a J-1 ) is obtained by replacing the divisors x _z(j,0) ... x _z(j,M(j)-1) common to a plurality of terms in the multivariate polynomial f(x ₀ , ..., x _{N-1 )} with the same additional variable a _j , and a constraint equation s(a _j , x _z (j, ₀ ) , ..., x z _{(j,M(j)-1) )} which takes the minimum value when a _j = x _z(j,0) ... x _z(j,M(j)-1 ) is obtained by adding a multivariate polynomial h(x ₀ , ..., x _N-1 , a ₀ , ..., a _a conversion unit that obtains and outputs g(x ₀ , ..., x _N-1 , a ₀ , ..., a _J-1 ) + s(a ₀ , x _z(0,0) , ..., x _z(0,M(0)-1) ) + ... + s(a _J-1 , x _z(J-1,0) , ..., x _{z(J-1,M(J-1))} );
R is an integer equal to or greater than 1, r=0,...,R-1, j(r) is a function value of r, and {j(0),...,j(R-1)} ⊂ {0,...,J-1};
the multivariate polynomial g(x ₀ , ..., x _N-1 , a ₀ , ..., a _J-1 ) has terms obtained by replacing a part or all of certain terms of the multivariate polynomial f(x ₀ , ..., _{x N-1 ) by} a product a _{j (0)} ... a _j(R-1) of R additional variables a j(0) ... a j(R-1);
R' is an integer equal to or greater than 2, r' = 0, ..., R'-1, j(r') is a function value of r', and {j'(0), ..., j'(R'-1)} ⊂ {0, ..., J-1};
the multivariate polynomial g(x ₀ , ..., x _N-1 , a ₀ , ..., a _J-1 ) further has a term obtained by replacing a part or all of a certain term of the multivariate polynomial f( _{x 0} , ..., _{x N -1} ) with a product a _j'(0) ...a j'(R'-1) of R' additional variables a j'( ₀ ) ...a _j'(R'-1) ;
A polynomial transformation device, wherein only a portion of the R additional variables a _j(0) , . . . , a _j(R-1) is included in a set of the R' additional variables a _j'(0) , . . . , a _j'(R'-1) . J is a positive integer, N, M(j) are integers equal to or greater than 2, j = 0, ..., J-1, m = 0, ..., M(j)-1, and z(j,m) ∈ {0, ..., N-1} is a function value for (j,m),
A multivariate polynomial f(x ₀ , ..., x _{N- 1} ) for N variables x ₀ , ..., x N-1 is input, and multivariate polynomial g(x ₀ , ..., x _N-1 , a 0 , ..., a J-1 ) is obtained by replacing the divisors x _z(j,0) ... x _z(j,M(j)-1) common to a plurality of terms in the multivariate polynomial f(x ₀ , ..., x _{N-1 )} with the same additional variable a _j , and a constraint equation s(a _j , x _z (j, ₀ ) , ..., x z _{(j,M(j)-1) )} which takes the minimum value when a _j = x _z(j,0) ... x _z(j,M(j)-1 ) is obtained by adding a multivariate polynomial h(x ₀ , ..., x _N-1 , a ₀ , ..., a _a conversion unit that obtains and outputs g(x ₀ , ..., x _N-1 , a ₀ , ..., a _J-1 ) + s(a ₀ , x _z(0,0) , ..., x _z(0,M(0)-1) ) + ... + s(a _J-1 , x _z(J-1,0) , ..., x _{z(J-1,M(J-1))} );

and A _m is an additional variable,

A polynomial conversion device. 4. The polynomial conversion device according to claim 1,
The conversion unit is
a summary term selection unit which receives the multivariate polynomial f(x ₀ , . . . , x _N−1 ) as an input and selects divisors x _{z(j, 0)} . . . x _{z(j, M(j)−1)} common to the multiple terms;
a summary term conversion unit which obtains and outputs the multivariate polynomial h( _x0 ,..., _xN-1,a0 , _{...,aJ -1} ) obtained by adding the multivariate polynomial g(x0,...,xN _-1 , _a0 ,...,aJ _-1 ) obtained by substituting the divisors _{xz (j,0)} ...xz(j,M(j)-1) in the multivariate polynomial f( _x0 ,...,xN-1) with the additional variable aj, and the constraint equation s( _aj ,xz _{(j, 0} ),..., _{xz (j,M(j)-1) )} ;
A polynomial conversion device having the following structure. 5. The polynomial conversion device according to claim 1,
At least one term of the multivariate polynomial f(x ₀ , . . . , x _N−1 ) is a monomial of third or higher degree,
In the polynomial transformation device, the terms of the multivariate polynomial g(x ₀ , . . . , x _N-1 , a ₀ , . . . , a _J-1 ) are monomials of degree two or less. A polynomial conversion method for a polynomial conversion device, comprising:
J is a positive integer, N, M(j) are integers equal to or greater than 2, j = 0, ..., J-1, m = 0, ..., M(j)-1, and z(j,m) ∈ {0, ..., N-1} is a function value for (j,m),
A conversion unit of the polynomial conversion device receives as input a multivariate polynomial f(x ₀ , ..., x _{N -1} ) relating to N variables x ₀ , ..., x N-1, and converts the multivariate polynomial g(x ₀ , ..., x _{N-1 ,} a 0 , ..., a J-1 ) obtained by replacing divisors x _z(j,0) ... x _z(j,M(j)-1) common to a plurality of terms in the multivariate polynomial f(x ₀ , ..., x _N-1 ) with the same additional variable a _j to obtain a multivariate polynomial _h (x ₀ , _... , x _N- 1 ) obtained by adding a constraint equation s(a _j , x _z(j,0) , ..., x _z(j,M( j)-1) ) which takes a minimum value when a j = x _z (j,0) ... x z _{(j,M(j) -1} ). , a ₀ , ..., a _J-1 )=g(x ₀ , ..., x _N-1 , a ₀ , ..., a _J-1 )+s(a ₀ , x _z(0,0) , ..., x _z(0,M(0)-1) )+ ...+s(a _J-1 , x _z(J-1,0) , ..., x _{z(J-1,M(J-1))} ) is obtained and output;
R is an integer equal to or greater than 1, r=0,...,R-1, j(r) is a function value of r, and {j(0),...,j(R-1)}⊂{0,...,J-1};
the multivariate polynomial g(x ₀ , ..., x _N-1 , a ₀ , ..., a _J-1 ) has terms obtained by replacing a part or all of certain terms of the multivariate polynomial f(x ₀ , ..., _{x N-1 ) by} a product a _{j (0)} ... a _j(R-1) of R additional variables a j(0) ... a j(R-1);
A method for polynomial transformation, wherein each of the additional variables a _j(0) , ..., a _j(R-1) is the additional variable a _j for jε{j(0), ..., j(R-1)}. A polynomial conversion method for a polynomial conversion device, comprising:
J is a positive integer, N, M(j) are integers equal to or greater than 2, j = 0, ..., J-1, m = 0, ..., M(j)-1, and z(j,m) ∈ {0, ..., N-1} is a function value for (j,m),
A conversion unit of the polynomial conversion device receives as input a multivariate polynomial f(x ₀ , ..., x _{N -1} ) relating to N variables x ₀ , ..., x N-1, and converts the multivariate polynomial g(x ₀ , ..., x _{N-1 ,} a 0 , ..., a J-1 ) obtained by replacing divisors x _z(j,0) ... x _z(j,M(j)-1) common to a plurality of terms in the multivariate polynomial f(x ₀ , ..., x _N-1 ) with the same additional variable a _j to obtain a multivariate polynomial _h (x ₀ , _... , x _N- 1 ) obtained by adding a constraint equation s(a _j , x _z(j,0) , ..., x _z(j,M( j)-1) ) which takes a minimum value when a j = x _z (j,0) ... x z _{(j,M(j) -1} ). , a ₀ , ..., a _J-1 )=g(x ₀ , ..., x _N-1 , a ₀ , ..., a _J-1 )+s(a ₀ , x _z(0,0) , ..., x _z(0,M(0)-1) )+...+s(a _J-1 , x _z(J-1,0) , ..., x _{z(J-1,M(J-1))} ) is obtained and output;
R is an integer equal to or greater than 1, r=0,...,R-1, j(r) is a function value of r, and {j(0),...,j(R-1)}⊂{0,...,J-1};
the multivariate polynomial g(x ₀ , ..., x _N-1 , a ₀ , ..., a _J-1 ) has terms obtained by replacing a part or all of certain terms of the multivariate polynomial f(x ₀ , ..., _{x N-1 ) by} a product a _{j (0)} ... a _j(R-1) of R additional variables a j(0) ... a j(R-1);
R' is an integer equal to or greater than 2, r' = 0, ..., R'-1, j(r') is a function value of r', and {j'(0), ..., j'(R'-1)} ⊂ {0, ..., J-1};
the multivariate polynomial g(x ₀ , ..., x _N-1 , a ₀ , ..., a _J-1 ) further has a term obtained by replacing a part or all of a certain term of the multivariate polynomial f( _{x 0} , ..., _{x N -1} ) by a product a _j'(0) ...a j'(R'-1) of R' additional variables a j'( ₀ ) ...a _j '(R'-1);
A method for polynomial transformation, wherein only a portion of the R additional variables a _j(0) , . . . , a _j(R-1) is included in the set of the R' additional variables a _j'(0) , . . . , a _j'(R'-1) . A polynomial conversion method for a polynomial conversion device, comprising:
J is a positive integer, N, M(j) are integers equal to or greater than 2, j = 0, ..., J-1, m = 0, ..., M(j)-1, and z(j,m) ∈ {0, ..., N-1} is a function value for (j,m),
A conversion unit of the polynomial conversion device receives as input a multivariate polynomial f(x ₀ , ..., x _{N -1} ) relating to N variables x ₀ , ..., x N-1, and converts the multivariate polynomial g(x ₀ , ..., x _{N-1 ,} a 0 , ..., a J-1 ) obtained by replacing divisors x _z(j,0) ... x _z(j,M(j)-1) common to a plurality of terms in the multivariate polynomial f(x ₀ , ..., x _N-1 ) with the same additional variable a _j to obtain a multivariate polynomial _h (x ₀ , _... , x _N- 1 ) obtained by adding a constraint equation s(a _j , x _z(j,0) , ..., x _z(j,M( j)-1) ) which takes a minimum value when a j = x _z (j,0) ... x z _{(j,M(j) -1} ). , a ₀ , ..., a _J-1 )=g(x ₀ , ..., x _N-1 , a ₀ , ..., a _J-1 )+s(a ₀ , x _z(0,0) , ..., x _z(0,M(0)-1) )+...+s(a _J-1 , x _z(J-1,0) , ..., x _{z(J-1,M(J-1))} ) is obtained and output;

and A _m is an additional variable,

,Polynomial transformation method . A program for causing a computer to function as a polynomial conversion device according to any one of claims 1 to 5.

Images