Efficient Quantum Algorithm for Identifying Hidden Polynomials

Details Efficient Quantum Algorithm for Identifying Hidden Polynomials Efficient Quantum Algorithm for Identifying Hidden Polynomials

2007-06-08

arxiv.org/abs/0706.1219v3

Physics

Quantum Physics

17 pages

Scientific paper

We consider a natural generalization of an abelian Hidden Subgroup Problem where the subgroups and their cosets correspond to graphs of linear functions over a finite field F with d elements. The hidden functions of the generalized problem are not restricted to be linear but can also be m-variate polynomial functions of total degree n>=2. The problem of identifying hidden m-variate polynomials of degree less or equal to n for fixed n and m is hard on a classical computer since Omega(sqrt{d}) black-box queries are required to guarantee a constant success probability. In contrast, we present a quantum algorithm that correctly identifies such hidden polynomials for all but a finite number of values of d with constant probability and that has a running time that is only polylogarithmic in d.

Affiliated with

Also associated with

No associations

Rating

Efficient Quantum Algorithm for Identifying Hidden Polynomials does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Efficient Quantum Algorithm for Identifying Hidden Polynomials, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Quantum Algorithm for Identifying Hidden Polynomials will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-653351