Efficient Quantum Algorithm for Hidden Quadratic and Cubic Polynomial Function Graphs

Details Efficient Quantum Algorithm for Hidden Quadratic and Cubic Polynomial Function Graphs Efficient Quantum Algorithm for Hidden Quadratic and Cubic Polynomial Function Graphs

2007-03-21

arxiv.org/abs/quant-ph/0703195v3

Physics

Quantum Physics

(v2) formulated the Hidden Polynomial Function Graph Problem for multivariate polynomials, added results on quantum query comp

Scientific paper

We introduce the Hidden Polynomial Function Graph Problem as a natural generalization of an abelian Hidden Subgroup Problem (HSP) where the subgroups and their cosets correspond to graphs of linear functions over the finite field F_p. For the Hidden Polynomial Function Graph Problem the functions are not restricted to be linear but can also be multivariate polynomial functions of higher degree. For a fixed number of indeterminates and bounded total degree the Hidden Polynomial Function Graph Problem is hard on a classical computer as its black box query complexity is polynomial in p. In contrast, this problem can be reduced to a quantum state identification problem so that the resulting quantum query complexity does not depend on p. For univariate polynomials we construct a von Neumann measurement for distinguishing the states. We relate the success probability and the implementation of this measurement to certain classical problems involving polynomial equations. We present an efficient algorithm for hidden quadratic and cubic function graphs by establishing that the success probability of the measurement is lower bounded by a constant and that it can be implemented efficiently.

Affiliated with

Also associated with

No associations

Rating

Efficient Quantum Algorithm for Hidden Quadratic and Cubic Polynomial Function Graphs 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 Hidden Quadratic and Cubic Polynomial Function Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Quantum Algorithm for Hidden Quadratic and Cubic Polynomial Function Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-382975