Classical and quantum function reconstruction via character evaluation
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) = chi(f (x)), where chi is a known character of the group G. In particular, we consider the problem of recovering a hidden monic polynomial f (X) of degree d greater than or equal to 1 over a finite field F(p) of p elements given a black box which, for any x is an element of F(p), evaluates the quadratic character of f(x). We design a classical algorithm of complexity O(d(2)p(d+epsilon)) 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) = chi(sx), where chi is the character of a (known) faithful irreducible representation rho of G. We show that if d is the dimension of rho, then O(d(2) log\G\) classical queries suffice to determine s. The proof involves development of a new "uncertainty principle" for the Fourier transform over finite non-Abelian groups. (C) 2003 Published by Elsevier Inc.
fourier transform character sums polynomial reconstruction quantum algorithms