Testing Shift-Equivalence of Polynomials Using Quantum Machines

D. Grigoriev^{1}

Department of Computer Science & Department of Mathematics

Penn State University University Park, PA 16802 USA

email: dima@cse.psu.edu

The polynomials f, g ∈ F [X_{1}, …, X_{n}] are called shiftequivalent if there exists a shift (α_{1}, …, α_{n}) ∈ F^{n} such that f(X_{1} + α_{1}, …, X_{n} + α_{n}) = g. The algorithms in three different cases are designed which produce the set of all shiftequivalences of f, g in polynomial time, herewith in the case of a

1. zero-characteristics field F the designed algorithm is deterministic;

2. prime residue field F = F_{p} and a reduced polynomial f, i.e. deg_{X_{i}}(f) ≤ p − 1, 1 ≤ i ≤ n, the algorithm is randomized;

3. finite field F = F_{q} of the characteristic 2 the algorithm is quantum. For an arbitrary finite field F_{q} a quantum machine is designed which computes the group of all shift-self-equivalences of f, i.e. (β_{1}, …, β_{n}) ∈ F_{q}^{n} such that f(X_{1} + β_{1}, …, X_{n} + β_{n}) = f.

1 Introduction

In the paper we deal with the problem of testing, whether two given polynomials f, g ∈ F [X_{1}, …, X_{n}] are shift-equivalent, i.e. there exists a shift α_{1}, …, α_{n} such that f(X_{1}+α_{1}, …, X_{n}+ α_{n}) = g. The issue of considering polynomials up to the shifts appeared already in the context of the interpolation of shifted-sparse polynomials (see [8, 10, 7]), namely, the polynomials which become sparse after a suitable shift.

We present the algorithms for computing the group S_{f,f} of the shifts (β_{1}, …, β_{n}) such that f(X_{1} + β_{1}, …, X_{n} + β_{n}) = f and for testing, whether the set S_{f,g} of the shifts (α_{1}, …, α_{n}) for which f(X_{1} + α_{1}, …, X_{n} + α_{n}) = g is nonempty (in the latter case S_{f,g} = (α_{1}, …, α_{n}) + S_{f,f} and the algorithm yields a certain (α_{1}, …, α_{n}) ∈ S_{f,g}). The nature and the complexity of the algorithms drastically depends on the characteristic of the ground field F. For the characteristic zero we design in the section 2 a deterministic algorithm for testing shift-equivalence which has a polynomial time complexity, if the degree of f grows slower than n.

For the positive characteristic p when F = F_{p} is the field of residues mod p and the polynomial f is reduced, i.e. the degree with respect to each variable deg_{X_{i}}(f) ≤ p − 1, 1 ≤ i ≤ n, we design in the section 3 a randomized algorithm for testing shift-equivalence which has a polynomial runningtime, if p grows slower than a certain polynomial in n/d.

For an arbitrary finite ground field F and the degree of f we design in the section 4 a quantum machine (for this computational model and the background see e.g. [1, 13, 14, 16]) which computes the group S_{f,f}. Observe that the developed in the section 4 methods actually allow one to design a quantum machine which for a given action of an abelian group on a finite set, computes the stabilizator subgroup of a given element from the set (as the author recently learned, the problem of computing the stabilizator subgroup by a quantum machine was also solved in [17] with a better complexity bound). In [18] a quantum machine was constructed which allows one to test, whether a given function has a hidden linear structure, or to find the period of a periodic univariate function with small preimages (the latter result generalizes [13]). The method exhibited in the section 4 has a common point with [18] in applying the Fourier transform to the similar initial configurations (actually, this idea rises to [14]), but it is easier since it does not use the uniqueness of a hidden linear structure and estimations of the amplitudes as in [18], but rather exploites the duality of S_{f,f} with its group of characters.

When the characteristic of F is 2 we design a quantum machine which computes S_{f,g}. Moreover, if the abelian group being a direct product of cyclic groups each of the order 2 acts on a finite set, one can design a quantum machine, which tests, whether two elements from the set lie in the same orbit of the action of the group. It seems to be an open question, whether one could solve the latter problem by a quantum machine over a finite field of an arbitrary characteristics. The designed quantum machines run in polynomial time, if p grows slower than a certain polyno-

mial in the input size ( \begin{matrix}n + d \\ d \end{matrix} ) (being the number of the

coefficients of f).

Now we formulate the main result of the paper.

Theorem 1) Let f, g ∈ Q[X_{1}, …, X_{n}], deg(f), deg(g) ≤ d and the bit-size of the coefficients of f, g be less than M. A (deterministic) algorithm is designed which finds a basis (over C) v_{1}, …, v_{k} ∈ Q^{n} of the linear space S_{f,f} ⊂ C^{n} of all the shift-selfequivalences of f. Moreover, the algorithm tests, whether the set of all shift-equivalences S_{f,g} ⊂ C is nonempty and in the later case produces an element (α_{1}, …, α_{n}) ∈ S_{f,g} ∩ Q^{n}. The running time of the algorithm can be bounded by (M(dn)^{d})^{O(1)}.

1Supported by NSF grant CCR-9424358.

2) Let f, g ∈ F_{p}[X_{1}, …, X_{n}] for a prime p, the degrees deg(f), deg(g) ≤ d and deg_{X_{i}}(f), deg_{X_{i}}(g) ≤ p − 1, 1 ≤ i ≤ n. A randomized algorithm is designed which finds a basis over F_{p} of the linear space S_{f,f} ⊂ F_{p}^{n}. Moreover, the algorithm tests, whether S_{f,g} ≠ ∅ and in the latter case produces an element (α_{1}, …, α_{n}) ∈ S_{f,g}. The running time

of the algorithm does not exceed (p^{d} ( \begin{matrix}n + d \\ d \end{matrix} ))^{O(1)}.

3) Let f, g ∈ F_{p^{m}}[X_{1}, …, X_{n}], the degrees deg(f), deg(g) ≤ d. A quantum machine is designed which finds a basis over F_{p} of S_{f,f} ⊂ (F_{p^{m}})^{n}. Moreover, when the fields characteristics p = 2, a quantum machine is designed which computes S_{f,g} ⊂ (F_{2^{m}})^{n} in the form similar to 2). The running times

of the quantum machines are less than (pm ( \begin{matrix}n + d \\ d \end{matrix} ))^{O(1)}.

2 Testing shift-equivalence of polynomials over zero-characteristic field: deterministic algorithm

Let f, g ∈ Q[X_{1}, …, X_{n}] be two polynomials with deg(f), deg(g) ≤ d and with the size of rational coefficients less than M. Actually, one could consider the coefficients of f, g from a larger (say, algebraic number) field, but we stick with the rational coefficients just for simplifying the bounds on the size of the output data.

Denote by S_{f,g} ⊂ \overline{Q}^{n} (herewith the bar denotes the algebraic closure) the set of all shift-equivalence of f and g, i.e. (β_{1}, …, β_{n}) ∈ \overline{Q}^{n} such that f(X_{1} + β_{1}, …, X_{n} + β_{n}) = g(X_{1}, …, X_{n}). If S_{f,g} ≠ ∅ we say that f and g are shiftequivalent. In this section we design a deterministic algorithm which computes S_{f,g}. Observe that if (α_{1}, …, α_{n}) ∈ S_{f,f} then for any integer m we have (mα_{1}, …, mα_{n}) ∈ S_{f,f}. Hence (tα_{1}, …, tα_{n}) ∈ S_{f,f} holds for any t ∈ \overline{Q}. Thus, considering t as a new variable, we get that

0 = \frac{df(X_{1} + tα_{1}, …, X_{n} + tα_{n})}{dt}
= (α_{1} \frac{∂f}{∂X_{1}} + ⋯ + α_{n} \frac{∂f}{∂X_{n}} ) (X_{1} + tα_{1}, …, X_{n} + tα_{n})

Substituting t = 0 in the latter identity, we obtain that α_{1} \frac{∂f}{∂X_{1}} + ⋯ + α_{n} \frac{∂f}{∂X_{n}} = 0. Inversing this arguing, we conclude that S_{f,f} ⊂ \overline{Q}^{n} is a linear subspace. Therefore, S_{f,g} is a linear variety of the same dimension as S_{f,f} (if S_{f,g} is nonempty).

Observe that the variety S_{f,g} is defined over Q, therefore the subspace S_{f,f} has a basis from Q^{n} (one could obtain it from the system of linear equations α_{1} \frac{∂f}{∂X_{1}} +⋯+α_{n} \frac{∂f}{∂X_{n}} = 0 in the variables α_{1}, …, α_{n}). Furthermore, S_{f,g} contains a vector from Q^{n}, indeed, take any vector β ∈ S_{f,g} and all its conjugates β = δ_{1}(β), δ_{2}(β), …, δ_{N}(β) ∈ S_{f,g} over Q, then \frac{1}{N} ∑_{1≤j≤N}δ_{j}(β) ∈ S_{f,g} ∩ Q^{n}, thus S_{f,g} is definable by a linear

system over Q.

For brevity denote S^{(i)} = S_{∂f/∂X_{i},∂g/∂X_{i}}, 1 ≤ i ≤ n. Lemma 1 S_{f,g} = ∩_{1≤i≤n}S^{(i)} ∩ \{(α_{1}, …, α_{n}) ∈ \overline{Q}^{n} :

f(α_{1}, …, α_{n}) = g(0, …, 0)}.

Relying on lemma 1, the algorithm finds each S^{(i)}, 1 ≤ i ≤ n by a linear over Q system defining S^{(i)}, using the recursion on the degree. Then the algorithm finds a linear over Q system defining the intersection ∩_{1≤i≤n}S^{(i)} and substitutes the general (parametric) solution (A_{1}, …, A_{n}) = v+ λ_{1}v_{1} +⋯+λ_{k}v_{k} of the latter system (here λ_{1} …, λ_{k} are parameters, the vectors v, v_{1}, …, v_{k} ∈ Q^{n}, k = dim ∩_{1≤i≤n}S^{(i)}, and v_{1} …, v_{k} are linearly independent) into f. Due to lemma 1 the set of the vectors (A_{1}, …, A_{n}) satisfying the equation f(A_{1}, …, A_{n}) = g(0, …, 0), coincides with S_{f,g}.

Hence the equation f(A_{1}, …, A_{n}) = g(0, …, 0) determines a linear variety V in the space Λ ≃ \overline{Q}^{k} of parameters (λ_{1}, …, λ_{k}). There could occur one of the following three cases. In the first case V = ∅, i.e. S_{f,g} = ∅, this means that the polynomial f(A_{1}, …, A_{n}) − g(0, …, 0) ∈ Q[λ_{1}, …, λ_{k}] equals to a nonzero constant from Q. In the second case V = Λ, i.e. S_{f,g} = ∩_{1≤i≤n}S^{(i)}, it is equivalent to identical vanishing of the polynomial f(A_{1}, …, A_{n}) − g(0, …, 0). In the last case V is a hyperplane in Λ, given by a linear equation ∑_{1≤j≤k}c_{j}λ_{j} − c_{0} = 0 for suitable c_{j} ∈ Q. Therefore,

f(A_{1}, …, A_{n}) − g(0, …, 0) = c ( ∑_{1≤j≤k} c_{j}λ_{j} − c_{0})^{δ}

for an appropriate c ∈ Q, where δ = deg_{λ_{1},...,λ_{k}} f(A_{1}, …, A_{n}). Let us find all c_{j}. Checking, whether the polynomial f(A_{1}, …, A_{n})−g(0, …, 0) is homogeneous, we detect, whether c_{0} = 0. If c_{0} ≠ 0 we set c_{0} = 1 and for every 1 ≤ j ≤ k replace λ_{ℓ}, for all ℓ ≠ j by zeroes in f(A_{1}, …, A_{n}) − g(0, …, 0), as a result we obtain a univariate polynomial ψ_{j} = f(A_{1}, …, A_{n}) − g(0, …, 0)|_{λ_{ℓ}=0,ℓ≠j} = c(c_{j}λ_{j} − 1)^{δ}.

The algorithm finds c_{j} calculating GCD (ψ_{j}, \frac{d ψ_{j}}{d λ_{j}} ) = c_{j} λ_{j}− 1. If on the opposite c_{0} = 0, then for each pair 1 ≤ j_{1}, j_{2} ≤ k we make a substitution λ_{j_{1}} = 1 and λ_{ℓ} = 0 for all ℓ ≠ j_{1}, j_{2}, as a result the algorithm either finds the quotient c_{j_{2}}/c_{j_{1}} or returns c_{j_{1}} = 0 similar to the situation c_{0} = 1. This completes the description of the recursive algorithm which computes S_{f,g}.

In particular, this allows one to test, whether f and g are shift-equivalent.

Now we estimate the number of arithmetic operations in the described algorithm. The number of monomials in f, g and the number of taking the derivatives can be bounded by

( \begin{matrix}d + n \\ d \end{matrix} )^{O(1)}. At each step of recursion for constructing

the intersection ∩_{1≤i≤n}S^{(i)} the algorithm solves a linear system in n variables, it requires n^{O(1)} arithmetic operations. After that the calculating of the substitution f(A_{1}, …, A_{n})

needs ( \begin{matrix}d + n \\ d \end{matrix} )^{O(1)} operations, and finally computing c_{j}

takes n^{O(1)} operations. Thus, the number of arithmetic op-

erations of the algorithm does not exceed ( \begin{matrix}d + n \\ d \end{matrix} )^{O(1)},

i.e. is polynomial in the input size.

Now we estimate the bit-size of the occurring intermediate coefficients. The bit-size of the coefficients of any involved partial derivative is less than d(log n)M. Denote by M_{ℓ}, 0 ≤ b ≤ d the bit-size of the coefficients of the linear systems representing S_{f_{ℓ},g_{ℓ}} for intermediate in the recursion polynomials of degrees ℓ. Then at the current step of the recursion the size of the coefficients in a linear system representing ∩_{1≤i≤n}S^{(i)} can be bounded by n^{O(1)}M_{ℓ}, then the size of the coefficients c_{j} does not exceed (nd)^{O(1)}M_{ℓ} by the subresultant theorem [11]. Hence M_{ℓ+1} ≤ (nd)^{O(1)}M_{ℓ} and we conclude that M_{d} ≤ (nd)^{O(d)}M and the bit-size of all occurring coefficients is also less than M(nd)^{O(d)}. Therefore, the running time of the described algorithm does not exceed (M(nd)^{d})^{O(1)} which completes the proof of theorem

1). When d = n^{o(1)} then (nd)^{O(d)} ≤ ( \begin{matrix}d + n \\ n \end{matrix} )^{O(1)} and

the bit complexity of the described algorithm is polynomial. When d grows faster than, say, n^{2} it is more profitable for computing S_{f,g} to solve a system of polynomial equations f(X_{1} + α_{1}, …, X_{n} + α_{n}) = g(X_{1}, …, X_{n}) in n variables α_{1}, …, α_{n} with the running time (Md^{n^{2}})^{O(1)} [3].

3 Testing shift-equivalence of reduced polynomials over a prime residues field: randomized algorithm

Let the polynomials f, g ∈ F_{p}[X_{1}, …, X_{n}], deg(f), deg(g) ≤ d, where p is a prime, be reduced, namely deg_{X_{i}}(f), deg_{X_{i}}(g) ≤ p−1, 1 ≤ i ≤ n. In this section we design a polynomial-time randomized algorithm which computes S_{f,g} ⊂ F_{p}^{n}. Observe that S_{f,f} is a linear subspace over F_{p} and S_{f,g} = v + S_{f,f} for an arbitrary vector v ∈ S_{f,g} (if S_{f,g} ≠ ∅).

Notice that since f, g are reduced, lemma 1 from the section 2 holds for S_{f,g} also in the case under consideration.

Let q = p^{m}, a polynomial h ∈ F_{q}[X_{1}, …, X_{n}]. The following lemma 2 was told the author by R. Smolensky [15] and strengthens Schwartz’s lemma [12] for finite fields. Observe that when n ≤ q deg h and deg_{X_{i}}(h) ≤ q − 2, 1 ≤ i ≤ n, lemma 2 follows from [9] (for arbitrary h a weaker bound was proved in [5]).

Lemma 2 If h has a zero in F_{q}^{n} then h has at least q^{n−deg(h)} zeroes.

Now we describe a randomized algorithm which computes S_{f,g} ⊂ F_{p}^{n}. Similar to the section 2 the algorithm by recursion on the degree computes S^{(i)}, 1 ≤ i ≤ n representing each S^{(i)} by a linear system over F_{p}. Then the algorithm produces a linear system which represents the intersection ∩_{1≤i≤n}S^{(i)} yields the general (parametric) solution (A_{1}, …, A_{n}) = v + λ_{1}v_{1} + ⋯ + λ_{k}v_{k}, where v, v_{1}, …, v_{k} ∈ F_{p}^{n}, k = dim_{F_{p}} (∩_{1≤i≤n}S^{(i)}) of this linear system (cf. section 2). After that the algorithm substitutes (A_{1}, …, A_{n}) in f. Due to lemma 1 S_{f,g} is isomorphic to the set of the solutions of the polynomial over F_{p} equation f(A_{1}, …, A_{n}) = g(0, …, 0) in the parameters λ_{1}, …, λ_{k}, one could consider w.l.o.g. S_{f,g} as a linear over F_{p} variety in the space Λ ≃ F_{p}^{k} of the parameters. Lemma 2 implies that s = dim_{F_{p}} S_{f,g} ≥ k − deg f ≥ k − d (if S_{f,g} ≠ ∅).

In [8] it is proved that if in a set U to choose randomly independently N times elements u ∈ U then the number y of the times when a chosen u belongs to a fixed subset ∅ ≠ A ⊂ U, satisfies with the probability greater than 1 − δ the following inequalities: \frac{1}{2} \frac{#A}{#U} ≤ \frac{y}{N} ≤ \frac{3}{2} \frac{#A}{#U}, where

N = \frac{#U}{#A} · 16 · log_{2}(2/δ).

The randomized algorithm under description for computing S_{f,g} checks first, whether 0 ∈ S_{f,g}, if yes then we set the vector u_{0} = 0 ∈ S_{f,g}. If not then the algorithm chooses N times randomly independently elements from the set U = Λ,

herewith A = A_{0} = S_{f,g} and δ = (n ( \begin{matrix}n + d \\ d \end{matrix} ))^{−2}. Hence \frac{#U}{#A} ≤ p^{d}. Then with the probability greater than 1 − δ among the chosen N = O(p^{d}d log n) vectors there would be a vector u_{0} ∈ S_{f,g}, (one could easily check the membership to S_{f,g}), provided that S_{f,g} ≠ ∅. If none of the chosen N vectors belongs to S_{f,g}, the algorithm returns that S_{f,g} = ∅. After that the algorithm makes 2N independent choices of the elements from U. Among them with the probability greater than 1 − δ there is a vector u_{1} ∈ S_{f,g} such that u_{1} − u_{0} ≠ 0 (herewith we take A = A_{1} = S_{f,g}\{u_{0}}, obviously #A_{1} ≥ \frac{1}{2} #A_{0}). Thereupon making again 2N independent choices the algorithm with the probability greater than 1−δ finds a vector u_{2} ∈ S_{f,g} such that the vectors u_{2} − u_{0}, u_{1} − u_{0} are linearly independent. Herewith we take A = A_{2} = S_{f,g}\L {u_{0}, u_{1}} where L (u′_{0}, ⋯, u′_{ℓ}) denotes the minimal linear variety which contains the points u′_{0}, …, u′_{ℓ} (clearly L \{u_{0}, u_{1}\} is a line), obviously #A_{2} ≥ \frac{1}{2} #A_{0}. Continuing in this way, the algorithm makes at most s ≤ k rounds of 2N independent choices, while it is possible to find the vectors u_{0}, u_{1}, …, u_{s_{0}} ∈ S_{f,g}, s_{0} ≤ s such that the differences u_{1} − u_{0}, …, u_{s_{0}} − u_{0} are linearly independent. The algorithm returns that S_{f,g} = u_{0} + \overline{λ}_{1}(u_{1} − u_{0}) + ⋯ + \overline{λ}_{s_{0}}(u_{s_{0}} − u_{0}), where \overline{λ}_{1}, …, \overline{λ}_{s_{0}} are parameters from F_{p}.

The algorithm finds S_{f,g} correctly with the probability at

least (1 − δ)^{n( \begin{matrix}n + d \\ d \end{matrix} )} ≥ 1 − (n ( \begin{matrix}n + d \\ d \end{matrix} ))^{−1}, because

the algorithm calls recursively to itself at most ( \begin{matrix}n + d \\ d \end{matrix} )

times since the number of nonvanishing partial derivatives

of f does not exceed ( \begin{matrix}n + d \\ d \end{matrix} ), and at each recursive step

the algorithm makes at most n rounds of 2N independent choices as described above. Notice that if S_{f,g} = ∅, the algorithm always returns the correct answer.

Finally, estimate the running time of the algorithm. As

already mentioned, there are at most ( \begin{matrix}n + d \\ d \end{matrix} ) recursive

calls of the algorithm to itself. At each recursive step the algorithm first finds (deterministically) the intersection ∩_{1≤i≤n}S^{(i)}, by means of solving a linear over F_{p} system with at most n variables, that requires ((log p)n)^{O(1)} running time. Then the algorithm makes at most n rounds of choosing 2N vec-

tors from U = Λ, it takes (p^{d} ( \begin{matrix}n + d \\ d \end{matrix} ))^{O(1)}, which com-

pletes the proof of theorem 2).

Notice that the time bound of the algorithm is better than the time bound p^{n} of the trivial search in F_{p}^{n} when d = o(n). In this case the time bound of the algorithm is

polynomial in the input size log p · ( \begin{matrix}n + d \\ d \end{matrix} ) when p =

(\frac{n}{d})^{O(1)}.

4 Testing shift-equivalence of polynomials over a finite field: quantum computation

Let g = p^{m} and the polynomials f, g ∈ F_{q}[X_{1}, …, X_{n}], deg(f), deg(g) ≤ d. In this section we design a quantum machine which computes S_{f,f} ⊂ F_{q}^{n} and, furthermore, in the case of the fields characteristic p = 2 we design a quantum machine which computes S_{f,g}. Observe as above that S_{f,f} is an abelian group and S_{f,g} = v + S_{f,f} for an arbitrary v ∈ S_{f,g} (if S_{f,g} ≠ ∅).

The core of a quantum machine, a concept being an extension of a randomized algorithm (see e.g. [1, 16]), is a fast unitary transformation. In [13] it was shown that a quantum machine could compute in polynomial time the Fourier transform ϕ_{n} for the cyclic group Z_{n} of the order n for “smooth” n, namely n = p_{1} ⋯ p_{ℓ} being a product of pairwise distinct small primes. In [4] ϕ_{2^{k}} was computed by a quantum machine based on the fast Fourier transform. First we show (although we do not immediately use it below) that ϕ_{p^{k}} for any small p could be computed recursively on k by a quantum machine in a more succinct way using the product-formula for Fourier transform [2], which in its turn easily entails the fast Fourier transform algorithm.

The matrix ϕ_{p} = \frac{1}{\sqrt{p}} (exp (\frac{2πi}{p} sℓ))_{1≤s,ℓ≤p} the quantum machine computes directly. For the recursive step, let w be a primitive root of unity of the degree p^{k+1}. Denote by D a square p^{k} × p^{k} diagonal matrix with the diagonal elements being successive powers of w : 1, w, w^{2}, …, w^{p^{k}−1}. Denote by I_{ℓ} the unit ℓ × ℓ matrix. Then the following productformula

ϕ_{p^{k+1}} = (I_{p^{k}} ⊗ ϕ_{p}) ( \begin{matrix}I_{p^{k}} \\ & D & & & & & ◯ \\ & & D^{2} \\ & & & . & . & . \\ ◯ & & & & & & D^{p−1} \end{matrix} ) (ϕ_{p^{k}} ⊗ I_{p})

allows one to compute ϕ_{p^{k+1}} recursively by a quantum machine within time O((kp)^{2}). Also observe that this gives a representation of ϕ_{p^{k+1}} as a product of O(k) matrices, while

[4] provides for it the product of O(k^{2}) matrices.

Remark that as any finite abelian group G is a direct product Z_{p_{ℓ}^{k_{1}}} × ⋯ × Z_{p_{ℓ}^{k_{ℓ}}} of the cyclic groups its Fourier

transform ϕ_{G} = ϕ_{p_{1}^{k_{1}}} ⊗⋯⊗ϕ_{p_{ℓ}^{k_{ℓ}}} = (ϕ_{p_{1}^{k_{1}}} ⊗ I_{p_{2}^{k_{2}}} ⊗ ⋯ ⊗ I_{p_{ℓ}^{k_{ℓ}}} )

(I_{p_{1}^{k_{1}}} ⊗ ϕ_{p_{2}^{k_{2}}} ⊗ ⋯ ⊗ I_{p_{ℓ}^{k_{ℓ}}} ) ⋯ (I_{p_{1}^{k_{1}}} ⊗ I_{p_{2}^{k_{2}}} ⊗ ⋯ ⊗ ϕ_{p_{ℓ}^{k_{ℓ}}} ) could

be computed by a quantum machine within time O ( ∑_{1≤i≤ℓ}(p_{i}k_{i})^{2}).

First we design a quantum machine which computes the group S_{f,f} ⊂ F_{q}^{n}. This construction extends essentially the idea from [14]. We utilize the notations and terminology from the quantum computations which one could find in [1, 13, 14, 16]. Actually, the described algorithm and the above quantum computation of ϕ_{G} allows one to solve the following problem by means of a quantum machine. Let a finite abelian group G with all the primes dividing its order, being small, act on a set. The algorithm enables one to find for each element of the set the subgroup of G which preserves this element (the stabilizator subgroup, see also [17]). Furthermore, if G is a direct product of cyclic groups each of the order 2, one can design a quantum machine which for any pair of elements of the set tests, whether these two elements are on the same orbit of the action of G. In the case under consideration G = Z_{p} × ⋯ × Z_{p} is the direct product of mn copies of Z_{p}, herewith the action of (Z_{p})^{m} on each variable X_{i}, 1 ≤ i ≤ n is isomorphic to the action of the additive group of F_{q} by the shifts.

The quantum machine under description starts with the initial configuration (cf. [1, 13, 14, 16, 18])

C = \frac{1}{(\sqrt{q})^{n}} ∑_{(α_{1},...,α_{n})∈F_{q}^{n}}

|α_{1}, …, α_{n}, f(X_{1} + α_{1}, …, X_{n} + α_{n})⟩ ,

i.e. each basic state |α_{1}, …, α_{n}, f(X_{1} + α_{1}, …, X_{n} + α_{n})⟩ is taken with the amplitude \frac{1}{(\sqrt{q})^{n}}. Notice that each basic

state is a basic ort in (q^{n} · q^{( \begin{matrix}n + d \\ d \end{matrix} )})-dimensional C-

space with the Hermitean metric. Let w^{(1)}, …, w^{(m)} ∈ F_{q} be a basis over F_{p}. Then one can represent each basic state |α_{1}, …, α_{n}, f(X_{1} + α_{1}, …, X_{n} + α_{n})⟩ in the form |α_{1}^{(1)}, …, α_{1}^{(m)}, …, α_{n}^{(1)}, …, α_{n}^{(m)}, f(X_{1} + α_{1}, …, X_{n} + α_{n})⟩

where α_{ℓ} = ∑_{1≤j≤m}α_{ℓ}^{(j)}w^{(j)}, α_{ℓ}^{(j)} ∈ F_{p}, 1 ≤ ℓ ≤ n. The

additive group of F_{q}^{n} acts on the first nm components as a direct product (Z_{p})^{nm}.

Denote Q = q^{( \begin{matrix}n + d \\ d \end{matrix} )}. The quantum machine applies to C the matrix (see above) ϕ_{p} ⊗ ⋯ ⊗ ϕ_{p} ⊗ I_{Q} where the tensor product of ϕ_{p} is taken nm times (cf. [18]). Then in the resulting configuration any basic state |χ_{1}, …, χ_{nm}, \overline{f}⟩ where χ_{ℓ} : Z/pZ → C, 1 ≤ ℓ ≤ nm are the characters of the cyclic additive group of F_{p}, i.e. χ_{ℓ}(a) = exp (\frac{2πi a b}{p}) for a suitable b and \overline{f} = f(X_{1}+β_{1}, …, X_{n}+β_{n}) ∈ F_{q}[X_{1}, …, X_{n}]

for some (β_{1}, …, β_{n}) ∈ F_{q}^{n}, β_{ℓ} = ∑_{1≤j≤m}β_{ℓ}^{(j)}w^{(j)} 1 ≤ ℓ ≤ n,

occurs with the amplitude (cf. [13, 14, 18])

\frac{1}{q^{n}} ∑ ; (∑ α_{1}^{(j)}w^{(j)},...,∑ α_{n}^{(j)}w^{(j)})∈S_{f,f} χ_{1}(α_{1}^{(1)}

+ β_{1}^{(1)}) ⋯ χ_{m}(α_{1}^{(m)} + β_{1}^{(m)}) ⋯ χ_{nm−m+1}

(α_{n}^{(1)} + β_{n}^{(1)}) ⋯ χ_{nm}(α_{n}^{(m)} + β_{n}^{(m)})

= \frac{1}{q^{n}} χ_{1}(β_{1}^{(1)}) ⋯ χ_{nm}(β_{n}^{(m)}) ∑ ; (∑ α_{1}^{(j)}w^{(j)},...,∑ α_{n}^{(j)}w^{(j)})∈S_{f,f}

χ_{1}(α_{1}^{(1)}) ⋯ χ_{nm}(α_{n}^{(m)})

For every restriction of the character

χ = χ_{1} ⊗ ⋯ ⊗ χ_{nm}|_{S_{f,f}} the sum ∑_{α∈S_{f,f}} χ(α)

= \{ \begin{matrix}0 & if χ ≢ 1 \\ #S_{f,f} & if χ ≡ 1 \end{matrix}

where α = (∑ α_{1}^{(j)}w^{(j)}, …, ∑ α_{n}^{(j)}w^{(j)}). Thus, each of the basic states |χ_{1}, …, χ_{nm}, \overline{f}⟩ for which χ_{1} ⊗⋯⊗χ_{nm}|_{S_{f,f}} ≡

1 (and only these basic states) occurs in the resulting configuration with the same for each of them probability (which equals to the square of the absolute value of the amplitude, see [1, 13, 14, 16, 18]) \frac{(#S_{f,f})^{2}}{q^{2n}}. Hence, each vector (χ_{1}, …, χ_{nm}) such that χ_{1} ⊗ ⋯ ⊗ χ_{nm}|_{S_{f,f}} ≡ 1, occurs as the first nm coordinates of the basic states in the resulting configuration with the same for each of them probability \frac{#S_{f,f}}{q^{n}} , because for the rest of Q coordinates there are \frac{q^{n}}{#S_{f,f}}

possibilities for \overline{f}, each of them appearing with the same probability.

Since S_{f,f} is an abelian subgroup of the additive group of (F_{q})^{n}, the order #S_{f,f} = p^{k} for a certain 0 ≤ k ≤ nm. All the vectors of the characters (χ_{1}, …, χ_{nm}) such that the restriction χ_{1} ⊗ ⋯ ⊗ χ_{nm}|_{S_{f,f}} ≡ 1 constitute the (mul-

tiplicative) group S being isomorphic to the vector space (F_{p})^{nm−k} over F_{p}.

Applying nm times independently the described quantum machine and each time observing the projection onto the first nm coordinates of a basic state of the resulting configuration, we obtain a sequence of nm elements from S. The probability that the first nm − k vectors (one can assume that they are chosen independently as each of them appears with the same probability, see above) among them form a basis of S over F_{p} is greater or equal to (1−p^{−1})(1− p^{−2})(1 − p^{−3}) ⋯ > \frac{1}{4} .

Therefore, making 4 rounds each consisting of nm described applications of the quantum machine, with the probability greater than 1−(1− \frac{1}{4} )^{4} > \frac{2}{3} , the quantum algorithm yields at one of the rounds a basis for the space S over F_{p}. The algorithm returns as a basis the maximal set of linearly independent over F_{p} elements of S obtained at one of 4 rounds.

Having a basis of S, the algorithm can uniquely select the subgroup S_{f,f}. Indeed, for every element (χ_{1}, …, χ_{nm}) from the yielded basis let χ_{t}(α) = exp (\frac{2πi ℓ_{t}α}{p}), 1 ≤ t ≤ nm for appropriate 0 ≤ ℓ_{t} < p, then for any element

( ∑_{1≤j≤m}α_{1}^{(j)}w^{(j)}, …, ∑_{1≤j≤m}α_{n}^{(j)}w^{(j)}) ∈ S_{f,f} we have

χ_{1}(α_{1}^{(1)}) ⋯ χ_{nm}(α_{n}^{(m)}) = 1, i.e. p|ℓ_{1}α_{1}^{(1)} + ⋯ + ℓ_{nm}α_{n}^{(m)}. Conversely, if the latter divisibility holds for every element

from the basis then ( ∑_{1≤j≤m}α_{1}^{(j)}w^{(j)}, …, ∑_{1≤j≤m}α_{n}^{(j)}w^{(j)}) ∈

S_{f,f}. These divisibility conditions constitute a (homogeneous) linear system over F_{p}. Producing a basis of this linear system, the algorithm produces thereby a basis of S_{f,f}. This completes the description of the algorithm which computes S_{f,f}.

Now in the case of the fields characteristic p = 2 we design a quantum machine which tests, whether S_{f,g} ≠ ∅, and if it is the case the machine yields an element v ∈ S_{f,g}. Together with the described above construction of S_{f,f} this computes S_{f,g} = v+S_{f,f}. First the machine checks, whether f ≡ g, and if it is the case we are done by the above construction of S_{f,f}, so we can suppose w.l.o.g. that f ≢ g. Then applying the described above construction, the machine computes the groups S_{f,f} and S_{g,g}. If S_{f,f} ≠ S_{g,g} then S_{f,g} = ∅. So we can assume that S_{f,f} = S_{g,g}.

Observe that S = S_{f,f} ∪ S_{f,g} is a group since p = 2. Notice also that S coincides with the group of all the shifts (α_{1}, …, α_{n}) ∈ F_{q}^{n} which preserve the unordered pair of the polynomials {f(X_{1}, …, X_{n}), g(X_{1}, …, X_{n})} = {f(X_{1} + α_{1}, …, X_{n} + α_{n}), g(X_{1} + α_{1}, …, X_{n} + α_{n})}.

To compute S the quantum machine as the basic states takes

\begin{matrix}|α_{1}, …, α_{n}, \{f(X_{1} + α_{1}, …, X_{n} + α_{n}), g \\ (X_{1} + α_{1}, …, X_{n} + α_{n})\} & ⟩ \end{matrix}

where (α_{1}, …, α_{n}) ∈ F_{q}^{n}. Thus, a basic state could be treated as an ort from C-space of the dimension q^{n} ·a, where a = \frac{Q(Q+1)}{2} . As in the above construction, the quantum machine applies the Fourier transform ϕ = ϕ_{2} ⊗ ⋯ ⊗ ϕ_{2} (nm times) to the first n coordinates, formally the machine multiplies the initial configuration

\begin{matrix}\frac{1}{(\sqrt{q})^{n}} & ∑ & α_{1},...,α_{n}∈F_{q} & |α_{1}, …, α_{n}, \{f(X_{1} + α_{1}, …, X_{n} + α_{n}), \\ g(X_{1} + α_{1}, …, X_{n} + α_{n}\} & ⟩ \end{matrix}

by the matrix ϕ ⊗ Ia. Then as above the quantum machine computes the group S (by means of its basis over F_{2}).

Obviously, S_{f,g} ≠ ∅ ⟺ S_{f,f} ≠ S, and in this case we can take as v any element of the basis of S which does not belong to S_{f,f}. This completes the description of the quantum machine which computes S_{f,g}.

Finally, we estimate the complexity of the designed quantum machines. In the course of computing S_{f,f} the machine computes (deterministically) for any (α_{1}, …, α_{n}) ∈ F_{q}^{n} the coefficients of the polynomial f(X_{1}+α_{1}, …, X_{n}+α_{n})

which requires (m log p ( \begin{matrix}n + d \\ d \end{matrix} ))^{O(1)} time. Producing

Fourier transform ϕ_{p} takes p^{O(1)} time. So, the application of

the Fourier transform runs in (m p ( \begin{matrix}n + d \\ d \end{matrix} ))^{O(1)} time.

The machine makes O(nm) such rounds and at the end solves (deterministically) a linear over F_{p} system of the size O(nm). Thus, the running time of the designed quantum

machine does not exceed (m p ( \begin{matrix}n + d \\ d \end{matrix} ))^{O(1)}. The simi-

lar bound is valid for the quantum machine which computes S_{f,g}, this completes the proof of theorem 3.

Notice that this bound is always not worse that the complexity bound for the randomized algorithm designed in the

section 3 (for m = 1). When p grows like ( \begin{matrix}n + d \\ d \end{matrix} )^{O(1)}

the running time of the designed quantum machine is polynomial which is not the case for the randomized algorithm from the section 3.

Acknowledgements. The author is grateful to Aliosha Kitaev for valuable remarks.

References

[1] E. Bernstein, U. Vazirani, Quantum complexity theory, Proc. STOC, (ACM, 1993), 11–20

[2] T. Beth, Verfahren der schnellen Fourier-transfor-mation, (Teubner, Stuttgart, 1984)

[3] A. Chistov, D. Grigoriev, Solving algebraic systems in subexponential time. I, II., Preprints LOMI E-9-83, E-10-83, Leningrad, 1983

[4] D. Coppersmith An approximate Fourier transform useful in quantum factoring Research report 19642, IBM, 1994

[5] D. Grigoriev, M. Karpinski, An approximate algorithm for the number of zeroes of arbitrary polynomials over GF [q], Proc. FOCS (IEEE, 1991), 662–669

[6] D. Grigoriev, M. Karpinski, A zero-test and a interpolation algorithm for the shifted sparse polynomials, Proc. AEECC 1993, Lect. Notes in Comput. Sci., vol. 673, (Springer, Berlin, 1993) 162–169 [7] D. Grigoriev, Y. Lakshman, Algorithms for computing

sparse shifts for multivariate polynomials, Proc. Intern. Symp. on Symbol. Algebr. Comput. (ACM, Montreal, 1995) 96–103

[8] R. Karp, M. Luby, N. Madras, Monte-Carlo approximation algorithms for enumeration problems, J. of Algorithms, 10, N3 (1989), 429–448

[9] M. Karpinski, I. Shparlinski, Efficient approximation algorithms for sparse polynomials over finite fields, Technical Report 94–029, ICSI, Berkeley, 1994

[10] Y. Lakshman, D. Saunders, On computing sparse shifts for univariate polynomials, Proc. Intern. Symp. on Symbol. Algebr. Comput. (ACM, Oxford, 1994)

[11] R. Loos, Generalized polynomial remainder sequences, in B. Buchberger, J. Calmet, R. Loos, eds., Computer Algebra, (Springer, Berlin, 1982)

[12] T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities, J. ACM, 27 (1980), 701– 717

[13] P. W. Shor, Algorithms for quantum computation: discrete logarithms and factoring, Proc. FOCS, (IEEE, 1994), 124–134

[14] D. R. Simon, On the power of quantum computation, Proc. FOCS (IEEE, 1994), 116–123

[15] R. Smolensky, Private communication, 1995

[16] A. Yao, Quantum circuit complexity, Proc. FOCS (IEEE, 1993), 352–360

[17] A. Yu. Kitaev, Quantum measurements and the Abelian stabilizer problem, Preprint of the Institute for Theoretical Physics, Moscow, October 1995

[18] D. Boneh, R.Lipton, Quantum cryptanalysis of hidden linear functions, Lect. Notes Comput. Sci., 963 (1995), 424–437