Classical and quantum function reconstruction via character evaluation

Alexander Russell, Igor E. Shparlinski*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

18 Citations (Scopus)


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) = χ(f(x)), where χ 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≥1 over a finite field Fp of p elements given a black box which, for any x∈Fp, evaluates the quadratic character of f (x). We design a classical algorithm of complexity O(d2pd+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) = χ(sx), where χ is the character of a (known) faithful irreducible representation p of G. We show that if d is the dimension of p, then O(d2 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.

Original languageEnglish
Pages (from-to)404-422
Number of pages19
JournalJournal of Complexity
Issue number2-3
Publication statusPublished - Apr 2004


  • Character sums
  • Fourier transform
  • Polynomial reconstruction
  • Quantum algorithms


Dive into the research topics of 'Classical and quantum function reconstruction via character evaluation'. Together they form a unique fingerprint.

Cite this