Polynomial degree vs. quantum query complexity

Details Polynomial degree vs. quantum query complexity Polynomial degree vs. quantum query complexity

2003-05-06

arxiv.org/abs/quant-ph/0305028v4

Journal of Computer and System Sciences, 72(2): 220-238, 2006

Physics

Quantum Physics

23 pages, 1 figure, v4 "proof by old method" corrected, moderate changes to presentation elsewhere

Scientific paper

The degree of a polynomial representing (or approximating) a function f is a lower bound for the number of quantum queries needed to compute f. This observation has been a source of many lower bounds on quantum algorithms. It has been an open problem whether this lower bound is tight. We exhibit a function with polynomial degree M and quantum query complexity \Omega(M^{1.321...}). This is the first superlinear separation between polynomial degree and quantum query complexity. The lower bound is shown by a new, more general version of quantum adversary method.

Affiliated with

Also associated with

No associations

Rating

Polynomial degree vs. quantum query complexity 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 Polynomial degree vs. quantum query complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Polynomial degree vs. quantum query complexity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-263562