ARTICLE IN PRESS
Journal of Complexity 20 (2004) 404–422
http://www.elsevier.com/locate/jco
Classical and quantum function reconstruction via character evaluation Alexander Russella and Igor E. Shparlinskib, a
Department of Computer Science and Engineering, University of Connecticut, Storrs, CT 06269, USA b Department of Computing, Macquarie University, Sydney NSW 2109, Australia Received 3 December 2002; accepted 12 August 2003
Abstract We consider two natural instances of the problem of determining a function f : G-G defined on a group G by making repeated queries to the oracle OðxÞ ¼ wð f ðxÞÞ; where w is a known character of the group G: In particular, we consider the problem of recovering a hidden monic polynomial f ðX Þ of degree dX1 over a finite field Fp of p elements given a black box which, for any xAFp ; evaluates the quadratic character of f ðxÞ: We design a classical algorithm of complexity Oðd 2 pdþe Þ and also show that the quantum query complexity of this problem is OðdÞ: Some of our results extend those of Wim van Dam, Sean Hallgren and Lawrence Ip obtained in the case of a linear polynomial f ðX Þ ¼ X þ s (with unknown s); some are new even in this case. We then consider the related problem of determining an element s of a finite group G given the oracle OðxÞ ¼ wðsxÞ; where w is the character of a (known) faithful irreducible representation r of G: We show that if d is the dimension of r; then Oðd 2 logjGjÞ classical queries suffice to determine s: The proof involves development of a new ‘‘uncertainty principle’’ for the Fourier transform over finite non-Abelian groups. r 2003 Published by Elsevier Inc. Keywords: Character sums; Fourier transform; Polynomial reconstruction; Quantum algorithms
1. Introduction We consider two natural instances of the problem of determining a function f : G-G defined on a group G by making repeated queries to the oracle
Corresponding author. E-mail addresses:
[email protected] (A. Russell),
[email protected] (I.E. Shparlinski).
0885-064X/$ - see front matter r 2003 Published by Elsevier Inc. doi:10.1016/j.jco.2003.08.019
ARTICLE IN PRESS A. Russell, I.E. Shparlinski / Journal of Complexity 20 (2004) 404–422
405
Of ðxÞ ¼ wð f ðxÞÞ; where w is a known character of the group G: Specifically, we study the following problems: *
*
Reconstruction of a monic, square-free polynomial f AFp ½X based on repeated queries to the oracle Of : Fp -C given by Of ðxÞ ¼ wð f ðxÞÞ; where w is the quadratic character (Legendre symbol/) of Fp : Reconstruction of a ‘‘hidden shift’’ sAG over a finite group G based on repeated queries to the oracle Os : G-C given by Os ðxÞ ¼ wðsxÞ; where w is the character of a known faithful irreducible representation r of G:
We begin by discussing the problem of polynomial reconstruction. Let pX3 be a prime number and let Fp denote a finite field of p elements. We let w denote the quadratic character of Fp ; or the Legendre symbol modulo p; see [21]. Wim van Dam, Sean Hallgren and Lawrence Ip, in the series of papers [4–6,17] have considered the shifted Legendre symbol problem of finding an unknown shift sAFp given an oracle Os which for each xAFp computes wðx þ sÞ: They have designed efficient quantum algorithms for the above problem and its generalization to characters in residue rings. The problem is of intrinsic interest and also has strong cryptographic motivation; sequences of values of quadratic characters have been considered as sources of cryptographically strong pseudo-random bits in a number of papers, see [2,3,7,10,16,22,23,25,26] and references therein. Here, we consider a generalization of the above problem to polynomials. For an integer dX1 we let Md denote the set of square-free monic polynomials f ðX ÞAFp ½X of degree d; Md 9f f ðX Þ ¼ X d þ sd 1 X d 1 þ ? þ s0 AFp ½X j f is square-freeg: We study the problem of determining f AMd ; given an oracle Of which returns wð f ðxÞÞ for any xAFp : Of : x/wð f ðxÞÞ: It is obvious that the square-freeness condition is essential because polynomials of and f1 ðX Þ ¼ F ðX ÞG2 ðX Þ2 with the form f1 ðX Þ ¼ F ðX ÞG1 ðX Þ2 F ðX Þ; G1 ðX Þ; G2 ðX ÞAFp ½X -cannot be distinguished by this oracle. We remark that for the approach of [4–6,17] the orthogonality condition, X p 1 if a ¼ b; wððx þ aÞðx þ bÞÞ ¼ a; bAFp
1 if aab; xAFp appears to be crucial; however, this condition does not hold for nonlinear polynomials. On the other hand, the Weil bound, see [21], provides a certain approximate analogue of the above identity: X p þ OðdÞ if g ¼ h; wðgðxÞhðxÞÞ ¼ ð1Þ g; hAMd : Oðp1=2 Þ if gah; xAFp
ARTICLE IN PRESS 406
A. Russell, I.E. Shparlinski / Journal of Complexity 20 (2004) 404–422
Hereafter the implied constants in symbols ‘O’ may depend on d and also, where obvious, on the small positive parameter e: Using this property we demonstrate that the quantum query complexity of recovering f ; given the oracle Of ; is OðdÞ: In contrast, we observe that the classical query complexity is Oðd log pÞ: Furthermore, we give a classical algorithm for reconstructing f from Of ; which appears to be new even in the case of linear polynomials. In fact this algorithm is also based on the Weil bound. It is clear that the brute force approach leads to a (classical) algorithm of complexity Oðpdþ1þe Þ which is based on computation and comparison of the pdimensional vectors of the values of wð f ðxÞÞ and wðgðxÞÞ for all xAFp and all gAMd : A naive use of the Weil bound shows that it is enough to compute and compare wð f ðxÞÞ and wðgðxÞÞ only for 1pxpdp1=2 log2 p which, for d fixed, leads to an algorithm of complexity Oðpdþ1=2þe Þ: We show that using the Weil bound in a less obvious way one can obtain an Oðpdþe Þ algorithm. It could be relevant to recall the work of Dima Grigoriev [15] where a somewhat related question is considered for multivariate polynomials (although the field characteristic is assumed to be small). It is easy to see that our method applies to multiplicative characters of other orders and to multivariate polynomials as well. Finally, it is also easy to see that we can allow oracles which return the right value of wð f ðxÞÞ only with some fixed probability g412: We do not pursue this issue in this work, though. We also study a related problem, that of determining an element s of a finite group G; given oracle access to the function Os ðxÞ ¼ wðsxÞ; where w is the character of a (known) irreducible faithful representation r of G: Note that the condition that r be faithful is essential: otherwise two distinct group elements g1 ; g2 for which g1 g 1 2 lies in the kernel of r are indistinguishable. The proof involves a new ‘‘uncertainty principle’’ for the Fourier transform over an arbitrary finite group; this is perhaps of independent interest. Specifically, we show that if d is the dimension of the representation r; then Oðd 2 log jGjÞ classical queries to Os suffice to determine s: Note that the problem considered here is actually quite different from that studied by Hallgren, Ip, and van Dam in the series of papers [4–6,17]. Indeed, in their case, the ‘‘shift’’ is given by the additive structure of Fp ; whereas the character is given by the multiplicative structure. We remark that bounds on query complexity do not necessarily translate into bounds on quantum (or classical) computational complexity; in particular, the problem of efficiently reconstructing (with a quantum circuit) a low-degree polynomial from OðdÞ quantum queries remains an open question. We begin in Section 2 by recalling some variants of the Weil bound and briefly surveying the representation theory of finite groups; we also prove a generalization of the Heisenberg uncertainty principle for finite groups which may be of independent interest. In Sections 3 and 4, we develop classical algorithms and bound the quantum query complexity for the polynomial reconstruction problem. In Section 5, we establish bounds on the classical query complexity of shift reconstruction over groups.
ARTICLE IN PRESS A. Russell, I.E. Shparlinski / Journal of Complexity 20 (2004) 404–422
407
2. Preparation 2.1. Exponential sums First of all, we recall the Weil bound in its classical form given in Example 12 of Appendix 5 of [30]; see also Theorem 3 of Chapter 6 in [20] and Theorem 5.41 and comments to Chapter 5 of [21]. Lemma 1. For any F AMd which is not a perfect square of another polynomial, the bound X wðF ðxÞÞpdp1=2 xAFp holds. The following statement is also implied by the Weil bound and is essentially Theorem 2 of [23]. Lemma 2. For any integers Mop and any F AMd which is not a perfect square of another polynomial, the bound X M wðF ðxÞÞ ¼ Oðdp1=2 log pÞ x¼1 holds. We also need a similar statement for multivariate polynomials. Lemma 3. For any collection of c pairwise distinct linear forms Ln ðS0 ; y; Sd 1 Þ ¼ S0 þ S1 c1n þ ? þ Sd 1 cd 1;n þ cd;n ; over Fp the bound ! c Y X w Ln ðs0 ; y; sd 1 Þ p2cpd 1=2 s0 ;y;sd 1 AFp n¼1 holds.
n ¼ 1; y; c;
ARTICLE IN PRESS A. Russell, I.E. Shparlinski / Journal of Complexity 20 (2004) 404–422
408
Proof. We have ! c Y X w Ln ðs0 ; y; sd 1 Þ s0 ;y;sd 1 AFp n¼1 ! c X X Y p w Ln ðs0 ; y; sd 1 Þ : s1 ;y;sd 1 AFp s0 AFp n¼1 Clearly, there are at most ðc 1Þðc 2Þ d 2 p pc2 pd 2 ; 2 d 1-tuples ðs1 ; y; sd 1 ÞAFp for which the values of s1 c1n þ ? þ sd 1 cd 1;n þ cd;n ;
n ¼ 1; y; c
are not pairwise distinct. In this case we estimate the sum over s0 by p: Otherwise we see from Lemma 1 that the sum over s0 does not exceed cp1=2 : Therefore, ! c Y X w Ln ðs0 ; y; sd 1 Þ pcpd 1=2 þ c2 pd 1 : s0 ;y;sd 1 AFp n¼1 The claimed bound is trivial for cXp1=2 ; otherwise we have cpd 1=2 Xc2 pd 1 and the result follows. & We remark that one can also use stronger bounds based on the famous results of Pierre Deligne [8,9], however they do not improve our final results. Our next statement gives an upper bound ‘‘on average’’ for weighted character sums with polynomials. Lemma 4. For any integers Npp; rX1 and any sequence of real numbers ax with jax jp1; x ¼ 1; y; N; the bound 2r N X X ð2rÞ! r d Np ax wðgðxÞÞ p4rN 2r pd 1=2 þ r! gAM x¼1 d
holds.
ARTICLE IN PRESS A. Russell, I.E. Shparlinski / Journal of Complexity 20 (2004) 404–422
Proof. We have 2r N X X X ax wðgðxÞÞ ¼ x¼1 gAM gAM d
d
N X
2r Y
a xi
x1 ;y;x2r ¼1 i¼1 N X
p
axi wðgðxi ÞÞ
x1 ;y;x2r ¼1 i¼1
N X
¼
2r Y
x1 ;y;x2r
409
X gAMd
w
2r Y
! gðxi Þ
i¼1
! X 2r Y w gðxi Þ : ¼1 gAM i¼1 d
Assume that x1 ; y; x2r A½1; N contains m pairs of equal elements xin ¼ xjn ;
n ¼ 1; y; m
and c ¼ 2r 2m pairwise distinct elements yn ¼ xkn ; n ¼ 1; y; c: Then ! ! 2r l X Y X Y w gðxi Þ ¼ w gðyn Þ : gAMd
i¼1
gAMd
n¼1
If c ¼ 0; which happens for at most 2r ð2rÞ! r N; r! Nr ¼ r! r 2r-tuples ðx1 ; y; x2r ÞA½1; N2r ; then the sum over g is obviously equal to jMd j ¼ pd : For c40 we derive ! ! c c X Y X Y d 1 d w gðyn Þ ¼ w ðs0 þ s1 yn þ ? þ sd 1 yn þ yn Þ : gAMd
n¼1
s0 ;y;sd 1 AFp
n¼1
It is easy to verify that because y1 ; y; yc are pairwise distinct elements of Fp the linear forms S0 þ S1 yn þ ? þ Sd 1 yd 1 þ ydn ; n
n ¼ 1; y; c
satisfy the conditions of Lemma 3. Thus for at most N 2r remaining 2r-tuples ðx1 ; y; x2r ÞA½1; N2r the sum over g is at most 2lpd 1=2 p4rpd 1=2 : & We recall that, using the Horner scheme, for any gAMd the value of gðxÞ can be computed with OðdÞ arithmetic operations modulo p: We also recall that polynomial evaluation and computing the quadratic character can be done in polynomial time in the standard RAM model of computation. Explicit and efficient versions of these statements can be found in [1,14]. 2.2. A brief overview of the representation theory of finite groups The analysis of the query complexity of determining a hidden shift s from the oracle g/wðsgÞ will rely on some elements of the theory of group representations.
ARTICLE IN PRESS A. Russell, I.E. Shparlinski / Journal of Complexity 20 (2004) 404–422
410
We present here only enough material to set down notation, referring the reader to [13,27] for more complete expositions. Let G be a finite group. A representation r of G is a homomorphism r : G-GLðV Þ; where V is a finite-dimensional C-vector space and GLðV Þ is the group of invertible linear operators on V : The dimension of r; denoted dr ; is the dimension of the vector space V : By choosing a basis for V ; then, each rðgÞ is associated with a matrix ½rðgÞ so that for every g; hAG; ½rðghÞ ¼ ½rðgÞ½rðhÞ (this second product being matrix multiplication). If r : G-GLðV Þ is a representation of G; a subspace W CV is said to be invariant if rðgÞW CW for all gAG: In this case, restricting each rðgÞ to W results in another representation of G: When r has no invariant subspace other than the trivial space f0g and V ; r is said to be irreducible. For non-Abelian groups, the irreducible representations yield the basis functions used for the natural Fourier transform over G: Two representations r : G-GLðV Þ and s : G-GLðW Þ are said to be equivalent if they are identical upto isomorphism, which is to say that there is a linear isomorphism f : V -W so that for all g; rðgÞ ¼ f 1 sðgÞf: It is a fact that any finite group G has a finite number of distinct irreducible representations upto equivalence and for a group G; we let Gˆ denote a set of representations containing exactly one from each of these equivalence classes. The irreducible representations of a group G give rise to a Fourier transform over G as follows. Let LðGÞ ¼ f f : G-Cg denote the set of C-valued functions defined on G: For a function f ALðGÞ and an irreducible representation r; the Fourier transform of f at r, denoted fˆðrÞ; is the linear operator sffiffiffiffiffiffiffi dr X fˆðrÞ ¼ f ðgÞrðgÞ: ð2Þ jGj gAG ˆ comprise the Fourier transform of f : These linear operators fˆðrÞ; taken over all rAG; pffiffiffiffiffiffiffiffiffiffiffiffiffiffi The constants ð dr =jGjÞ appearing in (2) are chosen so that the transform is unitary in an appropriate sense to be discussed below. This gives rise to a natural Fourier inversion rule: For f ALðGÞ; sffiffiffiffiffiffiffi X dr trð fˆðrÞrðs 1 ÞÞ; f ðsÞ ¼ ð3Þ jGj ˆ rAG
where tr denotes the trace. One can deduce from the inversion formula an important relationship between the dimensions of the irreducible representations of G and the order jGj: X dr2 ¼ jGj: rAGˆ
If the group G is Abelian, all irreducible representations are one-dimensional and Eqs. (2) and (3) recover the familiar notion of Fourier transform and inversion.
ARTICLE IN PRESS A. Russell, I.E. Shparlinski / Journal of Complexity 20 (2004) 404–422
411
The space LðGÞ is a natural C-vector space, and can be made a Hilbert space by introducing the inner product X /f1 ; f2 S ¼ f1 ðgÞf2 ðgÞ: ð4Þ gAG
We mention that if r : G-GLðV Þ is a representation and V is an inner product space, then it is always possible to find an inner product on V for which the operators rðgÞ are simultaneously unitary; we will always work under this assumption. Choosing an orthonormal basis for V then determines dr2 coordinate functions rij ALðGÞ; where rij ðgÞ ¼ ½rðgÞij ; the i; jth entry of the matrix associated with rðgÞ: One consequence of the assumption that the rðgÞ are unitary is that the functions rij are then orthogonal under the inner product on LðGÞ given in Eq. (4). This shows, in particular, that the linear operators frðgÞjgAGg span the space of all linear operators from V to V ; a fact that we will apply in Section 5. This notion of Fourier transform preserves inner products in the following sense, giving rise to an analogue of the Plancherel equality: For f1 ; f2 ALðGÞ; X X f1 ðgÞf2 ðgÞ ¼ trðfb1 ðrÞfb2 ðrÞ Þ; gAG
rAGˆ
where z% denotes the conjugate of the complex number z and A denotes the adjoint of the linear operator A: If A is expressed as a matrix, the matrix of A is the conjugate transpose of that of A: In particular, the Fourier transform is norm-preserving: For f ALðGÞ; X X j f ðgÞj2 ¼ jj fˆðrÞjj2 ; jj f jj22 ¼ /f ; f S ¼ gAG
rAGˆ
pffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi where jjAjj ¼ trðAA Þ is the Frobenius norm. ˆ For Finally, we remark that there is a natural conjugation action on G: ˆ r : G-GLðV Þ; an element of G; let V ¼ HomðV ; CÞ denote the vector space of linear functionals on V and define the conjugate representation r% : G-GLðV Þ so that rðgÞ is the linear map ðrðgÞÞð f Þ ¼ f 3rðg 1 Þ: This notion of conjugation is % % chosen so that it preserves the natural pairing on V V given by /f ; xS ¼ f ðxÞ in the sense that /f ; xS ¼ /ðrðgÞÞð f Þ; ðrðgÞÞðxÞS: % Note that when a basis has been chosen for V and V ; rðgÞ ¼ rðg 1 Þt ; where t % denotes matrix transpose and the dual basis is used for V : We remark that r% is irreducible if and only if r is irreducible, and that these representations have the same dimension. A word on notation: We let id denote the identity element of a group G and ker f denote the kernel of a homomorphism f: For a linear operator T; we let rk T denote the rank of T: Finally, a representation is said to be faithful if ker r ¼ fidg:
ARTICLE IN PRESS 412
A. Russell, I.E. Shparlinski / Journal of Complexity 20 (2004) 404–422
2.3. An uncertainty principle for finite groups The familiar Heisenberg uncertainty principle asserts that for a square integrable function f on the real line, Z Z jj f jj42 x2 j f ðxÞj2 dx o2 j fˆðoÞj2 doX : 16p2 One consequence is that no square integrable function f with unit norm can have the property that both f and fˆ are supported on small neighbourhoods of 0: In fact, much more is true; see, for example, [12, Section 2.8-9] for general discussion and stronger conclusions. There is a natural interpretation of this principle in the realm of Fourier analysis over finite Abelian groups. Specifically, if G is Abelian and f ALðGÞ; so long as f is not everywhere zero one always has jsupp fˆj jsupp f jXjGj;
ð5Þ
ˆ fˆðwÞa0g). See [11,29] for where supp f ¼ fx j f ðxÞa0g (and supp fˆ ¼ fwAGj discussion and a number of extensions. We wish to develop an appropriate generalization of this inequality applicable to the Fourier transform over nonAbelian groups. Fix the group G: As before, let Gˆ ¼ fr1 ; y; rk g be a set of representatives for the irreducible representations of G and let dr denote the dimension of the ˆ One immediate difficulty in developing an analogue of (5) for representation rAG: this framework is that, in general, there is no canonical choice of basis for a group representation r; as a result, it is not a priori clear how to meaningfully define the support of the Fourier transform of a function f ALðGÞ: Below we show P ˆ that adopting the basis-independent quantity rAGˆ dr rk f ðrÞ as the support of f;ˆ we obtain a non-Abelian uncertainty principle which generalizes the Abelian version of (5). Lemma 5. Let f : G-C be a function on G with jsupp f j40: Then X jsupp f j dr rk fˆðrÞXjGj: rAGˆ
This tightens the non-Abelian uncertainty principle of Diaconis and Shahshahani, P which asserts that jsupp f j r; fˆ ðrÞa0 dr2 XjGj: See [11] for discussion. Proof. For a linear operator T : V -V on a C-vector space V we let LðTÞ denote the multiset of eigenvalues l of T: Each eigenvalue appears in LðTÞ with multiplicity equal to its algebraic multiplicity (that is, the highest power of ðx lÞ dividing the characteristic polynomial of T).
ARTICLE IN PRESS A. Russell, I.E. Shparlinski / Journal of Complexity 20 (2004) 404–422
413
Observe that by inversion, jj f jjN ¼ max j f ðsÞjp max sAG
sAG
sffiffiffiffiffiffiffi dr trð fˆðrÞrðs 1 ÞÞ; jGj ˆ
X
rAG
so that for some element s0 AG; 0
12 X p ffiffiffiffiffi 1 @ jj f jj22 p jsupp f j jj f jj2N pjsupp f j dr jtrð fˆðrÞrðs0 ÞÞjA jGj rAGˆ 0 12 X pffiffiffiffiffi 1 @X p jsupp f j dr jljA : jGj ˆ ˆ rAG lALð f ðrÞrðs0 ÞÞ
Observe that the total number of nonzero terms in the above double sum is P ˆ rAGˆ rk f ðrÞ; so that, by Cauchy–Schwarz, we may conclude that 1 0 1 0 X X X 1 @ jj f jj22 pjsupp f j dr rk fˆðrÞA @ jlj2 A: jGj ˆ ˆ ˆ rAG lALð f ðrÞrðs0 ÞÞ
rAG
P Now, for any linear operator T; one has lALðTÞ jlj2 ptrðTT Þ; so that 0 1 0 1 X X 1 @ dr rk fˆðrÞA @ trð fˆðrÞrðs0 Þrðs0 Þ fˆðrÞ ÞA jj f jj22 p jsupp f j jGj rAGˆ rAGˆ 0 1 X 1 @X ¼ jsupp f j dr rk fˆðrÞA trð fˆðrÞfˆðrÞ Þ; jGj ˆ ˆ rAG
rAG
because each rðsÞ is unitary. Recall that by the Plancherel equality X trð fˆðrÞfˆðrÞ Þ: jj f jj22 ¼ rAGˆ
Combining the last two equations, 0 1 X 1 @ dr rk fˆðrÞAjj f jj22 jj f jj22 pjsupp f j jGj ˆ rAG
so that 0 jGjpjsupp f j @
X rAGˆ
as desired.
&
1 dr rk fˆðrÞA;
ARTICLE IN PRESS A. Russell, I.E. Shparlinski / Journal of Complexity 20 (2004) 404–422
414
P 2 Recalling that rAGˆ dr ¼ jGj; we see that Lemma 5 is simply a weighted version of the principle of (5) above. (Indeed, for any Abelian group it recovers inequality (5).)
3. Classical polynomial reconstruction Here, we design an algorithm for the classical model of computation on a RAM computer. The complexity of our algorithm can be improved slightly if one uses fast algorithms for finite field arithmetic and polynomial evaluation, see [1,14]. In particular, one can replace pe by a reasonably small power of log p and also improve the term d 2 in our estimate. Simple counting arguments show that if 2p ppd then the oracle Of is not powerful enough to define the polynomial f uniquely. Our approach is based on the Weil bound thus it is reasonable to assume that dop1=2 (in fact to simplify some technical details we assume a slightly stronger inequality). Theorem 6. For any fixed e40 and p1=2 log 2 p4dX1; given an oracle Of one can find f AMd in Oðd 2 pdþe Þ binary operations. Proof. Obviously we can assume that p is sufficiently large. Put M ¼ Idp1=2 log2 pm and N ¼ Jd log2 pn: Using the square-freeness condition we conclude that for any gAMd with gaf the polynomial gf is not a prefect square. Thus from Lemma 2, we see that in this case M X
wðgðxÞf ðxÞÞ ¼ OðM=log pÞ
x¼1
while for g ¼ f this sum is at least M d: Using the Horner scheme, for any gAMd the value of gðxÞ can be computed with OðdÞ arithmetic operations modulo p: Thus for any polynomial gAMd the above sum can be evaluated and the identity g ¼ f can be verified in Oðd 2 p1=2þe Þ binary operations. We now show that in fact for all, except at most Oðpd 1=2 log pÞ polynomials gAMd one can verify the identity g ¼ f in OðdN log2 pÞ binary operations. It is enough to show that the inequality X N ð6Þ wðgðxÞf ðxÞÞXN d x¼1 is possible for at most Oðpd 1=2 log pÞ polynomials gAMd : Using Lemma 4 with ax ¼ wð f ðxÞÞ; we see that the number T of polynomials gAMd with (6), for any integer rX1; satisfies the inequality TðN dÞ2r p4rN 2r pd 1=2 þ
ð2rÞ! r d Np : r!
ARTICLE IN PRESS A. Russell, I.E. Shparlinski / Journal of Complexity 20 (2004) 404–422
415
Let r ¼ Jlog pn: We have ðN dÞ2r XN 2r ð1 d=NÞ2r XN 2r =2 for sufficiently large p: Therefore, Tp8rpd 1=2 þ 2
ð2rÞ! r d N p p8rpd 1=2 þ 2ð2rÞr N r pd : r!
Taking into account that ð2rÞr N r ¼ ð2r=NÞr pp 1=2 for our choice of N and r; and sufficiently large p; we obtain the desired statement. & 4. Quantum query complexity for polynomial reconstruction As above, we consider the problem of recovering a polynomial f from an oracle Of : x/wð f ðxÞÞ: An easy counting argument shows that the classical query complexity is Oðd log pÞ (it is in fact Yðd log pÞ): see [4], for example, for an analogous argument. We begin by showing that the quantum query complexity of this problem is at most OðdÞ: We refer the reader to accounts by Nielson and Chuang [24] and Kitaev [18] for a discussion of quantum computation and quantum algorithms. In particular, we use the notion of positive operator-valued measurement (POVM); see, for example, [28], for a discussion which matches our notation below. Recall that a POVM P on Hilbert space H is a set A and a family fWa jaAAg of positive semidefinite operators on H with the property that X Wa ¼ I; aAA
where I denotes the identity operator. The result of the measurement P on the state CAH is the probability distribution on A where aAA is observed with probability /Wa C; CS: Note that /Wa C; CSX0; as Wa is positive semidefinite, and that * + X X /Wa C; CS ¼ Wa C; C ¼ /IC; CS ¼ jjCjj2 ¼ 1: aAA
aAA
Note, also, that in the special case when Wa ¼ gp for a projection p and a scalar gA½0; 1; /Wa C; CS ¼ gjjpCjj2 : Theorem 7. Let f be a polynomial in Md : If dpp1=2 e for some fixed e40 then there exists a quantum algorithm which, after OðdÞ quantum queries to Of ; produces a state for which there is a POVM that determines f with probability at least 1 þ Oðp 1 Þ: Proof. Let us put k ¼ J2ðd þ 1Þe 1 n: For a prime p; let G denote a p-dimensional Hilbert space with an orthonormal basis fjzSjzAZp g: Initially, by applying the Fourier transform to a delta state, we arrive at the uniform superposition 1 X U 9pffiffiffi jxSAG p xAF p
ARTICLE IN PRESS 416
A. Russell, I.E. Shparlinski / Journal of Complexity 20 (2004) 404–422
which is used to query the oracle Of : Let w* : Fp -f71g be the function wðxÞ if xa0; w* ðxÞ ¼ 1 if x ¼ 0: ff ðxÞ ¼ w* ð f ðxÞÞ: ff with O We can certainly assume that in fact we are given an oracle O Then the result of the query may be computed into the phases by controlled phase shift yielding the state 1 X Cf 9pffiffiffi w* ð f ðxÞÞjxS; p xAF p
see, for example [18] for a discussion of quantum computation with oracles. Repeating the process independently kX1 times yields the tensor product state, ! k 1 X Y Cf ;k 9 k=2 w* ð f ðxi ÞÞ jxSAG#k ; p k i¼1 ~ x AFp
where x ¼ ðx1 ; y; xk Þ; G#k 9 G#?#G |fflfflfflfflfflfflfflffl{zfflfflfflfflfflfflfflffl} k
and jxS9jx1 S#?#jxk S: In general, we let Cg;k denote the state that would have arisen at this point had we started with the polynomial gAMd : Observe that for gAMd ; /Cg;k ; Cg;k S ¼ 1 and, furthermore, that for distinct g; hAMd ; k 1 X Y j/Cg;k ; Ch;k Sj ¼ k w* ðgðxi ÞÞ*wðhðxi ÞÞ p k i¼1 xAFp k X 1 Y : ¼ k w * ðgðzÞÞ* w ðhðzÞÞ p i¼1 zAF p
To bound this, we focus on the inner quantity X : s2d 9 max w * ðgðzÞÞ* w ðhðzÞÞ g; hAMd zAFp gah For a polynomial gAFp ½X ; let VðgÞ ¼ fxAFp jgðxÞ ¼ 0g: Recall that VðghÞ ¼ VðgÞ,VðhÞ and that for a nonzero univariate polynomial g; jVðgÞjpdegðgÞ:
ARTICLE IN PRESS A. Russell, I.E. Shparlinski / Journal of Complexity 20 (2004) 404–422
417
Considering that w* ð f ðxÞÞ ¼ wð f ðxÞÞ for xeVð f Þ; we bound s2d as follows: X X s2d ¼ max wðgðzÞÞwðhðzÞÞ þ w * ðgðzÞÞ* w ðhðzÞÞ g; hAMd zAFp \VðghÞ zAVðghÞ gah 0 1 X @ p max wðghðzÞÞ þ jVðghÞjA g; hAMd zAFp \VðghÞ gah
X þ 2d: p max wðghðzÞÞ g; hAMd zAFp gah Note now that for two distinct elements g; hAMd ; the product gh cannot be a perfect square and from Lemma 1 we conclude that X s2d p max wðgðzÞÞ þ 2dpdp1=2 þ 2dp2dp1=2 ð7Þ gAM2d zAFp provided that p43 (otherwise the result is trivial). Hence, for distinct g; hAMd we have j/Cg;k ; Ch;k Sjpsk2d p k : ð8Þ Now we show that there is a POVM that identifies the polynomial f with probability 1 þ Oðp 1 Þ: For each gAMd ; let pg;k be the projection operator onto the subspace spanned by Cg;k : As each pg;k is a projection operator, it is positive semidefinite, and we now show that for some 0oao1 with a ¼ 1 þ Oðp 1 Þ; there is a decomposition of the identity operator I of the form X apg;k ; I ¼rþ gAMd
where r and all pg;k are positive semidefinite operators on G#k : Note that if Cf ;k is measured according to this POVM, the ‘‘correct’’ index f ; k is observed with probability a: P So define r ¼ I gAMd apg;k ; we wish to select a ¼ 1 þ Oðp 1 Þ to insure that r is positive semidefinite. It suffices to see that for our choice of a X ð9Þ apg;k o1; gAM d
where jjMjj denotes the operator norm of M; given by jjMjj9 sup Fa0
jjMFjj ; jjFjj
ARTICLE IN PRESS A. Russell, I.E. Shparlinski / Journal of Complexity 20 (2004) 404–422
418
this supremum taken over all nonzero vectors F: Note that for a unit vector FAG#k ; X X pg;k F ¼ /F; Cg;k SCg;k : gAMd
gAMd
Let Fd be a Hilbert space of dimension jMd j with orthonormal basis fBg jgAMd g and let t : G#k -Fd be the linear operator X t9 Cg Bg ; gAMd
here
: Fd -C is the linear functional Bg : F//F; Bg S: Then X X X tt ðFÞ ¼ Cg Bg Bh Ch ðFÞ ¼ Cg Cg ðFÞ ¼ pg;k F;
Bg
g;hAMd
so that
P
g
gAMd
gAMd
pg;k ¼ tt ; recalling that jjt jj2 ¼ jjtt jj; it suffices to suitably upper
#k be an element in the span of fCg;k j gAMd g and let bound P jjt jj: So let FAG G ¼ g gg Bg AFd satisfy tðGÞ ¼ F; which is to say that X F¼ gg Cg;k : gAMd
Observe that
2 X X jjFjj ¼ gg Cg;k ¼ g g /Cg;k Ch;k S gAM g;hAM g h d d 0 !2 1 k X X s 2 ¼ jgg j þ O@ 2d jg j A pk gAM g gAMd d k s ¼ jjGjj2 þ O 2d pd jjGjj2 ¼ ð1 þ Oðpd k sk2d ÞÞjjGjj2 pk 2
ð10Þ
by the Cauchy–Schwarz inequality. With F expressed in this way, we expand jjt Fjj as follows: * + 2 X X X 2 2 jjt Fjj ¼ j/F; Cg;k Sj ¼ gh Ch;k ; Cg;k gAMd gAMd hAMd 2 X X ¼ gh /Ch;k ; Cg;k S : ð11Þ gg þ gAM hag d
Recalling the inner product bounds of (8), for any gAMd we must have X X pffiffiffiffiffi jgh jpsk2d p k pd jjGjj; gh /Ch;k ; Cg;k Spsk2d p k hAMd hAMd gah
ð12Þ
ARTICLE IN PRESS A. Russell, I.E. Shparlinski / Journal of Complexity 20 (2004) 404–422
419
again by the Cauchy–Schwarz inequality. Finally, considering that jja þ bjjpjjajj þ jjbjj; we conclude from (11) and (12) that jjt FjjpjjGjj þ pd k sk2d jjGjj ¼ 1 þ pd k sk2d jjGjj and, from (10), that jjt Fjjp 1 þ O pd k sk2d jjFjj: Hence, X pg;k p1 þ O pd k sk2d : gAM d
We can assume that p422=e and hence that 2ppe=2 ; because otherwise the result is trivial. Then by (7) we have pd k sk2d ppd k ð2dp1=2 Þk ppd k pð1 e=2Þk ¼ pd ke=2 pp 1 ; because of our choice of k ¼ J2ðd þ 1Þe 1 nX2ðd þ 1Þe 1 : Hence, we obtain X pg;k p1 þ Oðp 1 Þ gAM d
and are guaranteed that (9) holds (provided that p is large enough) for some a ¼ 1 þ Oðp 1 Þ (recall that ð1 þ dÞ 1 ¼ 1 þ OðdÞ). Thus the above POVM determines f with probability a ¼ 1 þ Oðp 1 Þ: &
5. Hidden shift problems over groups Here, we apply Lemma 5 to the problem of recovering a ‘‘hidden shift’’ sAG from an oracle Os ðxÞ ¼ wðsxÞ where w is the character of a known irreducible faithful representation r : G-GLðV Þ: Recall that a representation is called faithful if ker r ¼ fidg: Note that if r is not faithful, then the oracle Os does not determine s; as Os ¼ Or if s 1 rAker r: Theorem 8. Let r : G-GLðV Þ be an irreducible faithful representation of the finite group G and w : G-C be its character. Let Os : G-C be the function Os ðxÞ ¼ wðsxÞ: Then Oðd 2 log jGjÞ queries suffice to determine s from Os ; where d is the dimension of r: Proof. Let s and r be two distinct elements of G and let Os ; Or be as described above. We wish to show that PrgAG ½Os ðgÞ ¼ Or ðgÞ is small. To this end, consider the
ARTICLE IN PRESS 420
A. Russell, I.E. Shparlinski / Journal of Complexity 20 (2004) 404–422
function f ðgÞ ¼ Os ðgÞ Or ðgÞ: Note that f ðgÞ ¼ Os ðgÞ Or ðgÞ ¼ wðsgÞ wðrgÞ ¼ trðrðsgÞÞ trðrðrgÞÞ ¼ trððrðsÞ rðrÞÞrðgÞÞ and, since r is faithful, the operator rðsÞ rðrÞ is nonzero. Recall that the function ðA; BÞ/trðAB Þ is an inner product on EndðV Þ; the space of linear operators on V ; and hence that the function ðA; BÞ/trðABÞ is a bilinear form with no kernel on EndðV Þ; since the jGj linear operators frðgÞjgAGg span EndðV Þ we must have f ðgÞa0 for some gAG; see, for example [19, Section III.6] for discussion on this topic. In particular, jsupp f j40; and we may apply the uncertainty principle above. Let us now consider the Fourier transform f:ˆ By linearity, we have fˆðrÞ ¼ Obs ðrÞ Obr ðrÞ: Recall that if f1 and f2 are two C-valued functions on G for which for all xAG; f1 ðxÞ ¼ f2 ðsxÞ; then we have sffiffiffiffiffiffiffi sffiffiffiffiffiffiffi dr X dr X b f2 ðrÞ ¼ f2 ðgÞrðgÞ ¼ f1 ðgÞrðsgÞ jGj gAG jGj gAG sffiffiffiffiffiffiffi X dr rðsÞ ¼ f1 ðgÞrðgÞ ¼ rðsÞ fb1 ðrÞ; jGj gAG cid ðrÞ and we have fˆðrÞ ¼ ðrðs 1 Þ rðr 1 ÞÞO cid ðrÞ: Now hence Obs ðrÞ ¼ rðs 1 Þ O Oid ðgÞ ¼ wðgÞ and it is easy to see from the inversion formula (3) that in fact I if s ¼ r; % #wðsÞ ¼ 0 otherwise; where r% is the conjugate representation of r and I and 0 denote the identity and zero operators, respectively. In particular, we may conclude that the Fourier transforms of the two functions Os and Or and hence that of f ; are supported only on the representation r: % As f is nonzero, from Lemma 5 above we conclude that jsupp f jXP
jGj rAGˆ
dr rk fˆðrÞ
jGj X 2 d
and hence that Pr½Os ðgÞ ¼ Or ðgÞpð1 1=d 2 Þ: (Recall that the dimension of r% equals that of r:) If we consider now selection of group elements g1 ; y; gt ; each independently at random from the group, then jGj Pr½(s; (r; ras 8i; Os ðgi Þ ¼ Or ðgi Þp ð1 1=d 2 Þt : ð13Þ 2 Hence for t ¼ J2d 2 ln 2jGjn; this probability is no more than jGj 2 2 2 ð1 1=d 2 Þd ð2 ln jGjþkÞ pjGj2 ðe 1=d Þ2d ln 2jGjÞ pjGj2 e 2 ln 2jGj p1=4: 2 Therefore, there exists a sequence of samples g1 ; y; gt which determine s; this completes the proof. &
ARTICLE IN PRESS A. Russell, I.E. Shparlinski / Journal of Complexity 20 (2004) 404–422
421
Acknowledgments We thank Asma Harcharras, Lawrence Ip, and Wim van Dam for several useful discussions. A part of this work was done during a visit of the second author to the University of Connecticut whose generous support and hospitality are gratefully acknowledged. This research is supported, for A.R., by NSF CAREER award CCR0093065, NSF Grant CCR-0220264, and NSF Grant EIA-0218443 and, for I.S., by ARC Grant DP0211459.
References [1] A.V. Aho, J.E. Hopcroft, J.D. Ullman, The Design and the Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974. [2] M. Anshel, D. Goldfeld, Zeta functions, one-way functions, and pseudorandom number generators, Duke Math. J. 88 (1997) 371–390. [3] D. Boneh, R. Lipton, Algorithms for Black-box Fields and their Applications to Cryptography, Lecture Notes in Computer Science, Vol. 1109, Springer, Berlin, 1996, pp. 283–297. [4] W. van Dam, Quantum algorithms for weighing matrices and quadratic residues, Algorithmica 34 (2002) 413–428. [5] W. van Dam, S. Hallgren, Efficient quantum algorithms for shifted quadratic character problem, Preprint, 2001, pp. 1–15. [6] W. van Dam, S. Hallgren, L. Ip, Quantum algorithms for hidden coset problems, Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, 2003, pp. 489–498. [7] I.B. Damga˚rd, On the Randomness of Legendre and Jacobi sequences, Lecture Notes in Computer Science, Vol. 403, Springer, Berlin, 1990, pp. 163–172. [8] P. Deligne, La conjecture de Weil, I, Inst. Hautes Estudes Sci. Publ. Math. 43 (1974) 273–307. [9] P. Deligne, La conjecture de Weil, II, Inst. Hautes Estudes Sci. Publ. Math. 52 (1981) 313–428. [10] C. Ding, Pattern distributions of Legendre sequences, IEEE Trans. Inform. Theory 44 (1998) 1693–1699. [11] D.L. Donoho, P.B. Stark, Uncertainty principles and signal recovery, SIAM J. Appl. Math. 49 (1989) 906–931. [12] H. Dym, H.P. McKean, Fourier series and integrals, Probability and Mathematical Statistics, Vol. 14, Academic Press, New York, 1972. [13] W. Fulton, J. Harris, Representation Theory: A First Course, Springer, New York, 1991. [14] J. von zur Gathen, J. Gerhard, Modern Computer Algebra, Cambridge University Press, Cambridge, 1999. [15] D. Grigoriev, Testing shift-equivalence of polynomials by deterministic, probabilistic and quantum machines, Theor. Comput. Sci. 180 (1997) 217–228. [16] J. Hoffstein, D. Lieman, The distribution of the quadratic symbol in function fields and a faster mathematical stream cipher, Proceedings of the Workshop on Cryptography and Computational Number Theory, Singapore, 1999, Birkha¨user, Basel, 2001, pp. 59–68. [17] L. Ip, Solving shift problems and hidden coset problems using the Fourier transform, Preprint, 2002, pp. 1–15. [18] A. Yu. Kitaev, Classical and quantum computation, graduate studies in mathematics, Vol. 47, American Mathematical Society, Providence, RI, 2002. [19] S. Lang, Algebra, Springer, Berlin, New York, 2002. [20] W.-C.W. Li, Number Theory with Applications, World Scientific, Singapore, 1996. [21] R. Lidl, H. Niederreiter, Finite Fields, Cambridge University Press, Cambridge, 1997. [22] C. Mauduit, Finite and infinite pseudorandom binary words, Theor. Comput. Sci. 273 (2002) 249–261.
ARTICLE IN PRESS 422
A. Russell, I.E. Shparlinski / Journal of Complexity 20 (2004) 404–422
[23] C. Mauduit, A. Sa´rko¨zy, On finite pseudorandom binary sequences 1: measure of pseudorandomness, the Legendre symbol, Acta Arith. 82 (1997) 365–377. [24] M. Nielsen, I. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, Cambridge, 2002. [25] R. Peralta, On the distribution of quadratic residues and nonresidues modulo a prime number, Math. Comput. 58 (1992) 433–440. [26] J. Rivat, A. Sa´rko¨zy, On pseudorandom binary sequences and their applications, Preprint, 2001, pp. 1–18. [27] J.-P. Serre, Linear Representations of Finite Groups, Springer, Berlin, New York, 1977. [28] P. Shor, Quantum information theory: results and open problems, Geom. Functional Anal. 2 (2000) 816–838. [29] A. Terras, Fourier Analysis on Finite Groups and Applications, London Mathematical Society Student Texts, Vol. 43, Cambridge University Press, Cambridge, 1999. [30] A. Weil, Basic Number Theory, Springer, Berlin, New York, 1974.
