A note on quantum algorithms and the minimal degree of epsilon-error polynomials for symmetric functions

Details A note on quantum algorithms and the minimal degree of epsilon-error polynomials for symmetric functions A note on quantum algorithms and the minimal degree of epsilon-error polynomials for symmetric functions

2008-02-13

arxiv.org/abs/0802.1816v2

Physics

Quantum Physics

7 pages LaTeX. 2nd version: corrected a few small inaccuracies

Scientific paper

The degrees of polynomials representing or approximating Boolean functions are a prominent tool in various branches of complexity theory. Sherstov recently characterized the minimal degree deg_{\eps}(f) among all polynomials (over the reals) that approximate a symmetric function f:{0,1}^n-->{0,1} up to worst-case error \eps: deg_{\eps}(f) = ~\Theta(deg_{1/3}(f) + \sqrt{n\log(1/\eps)}). In this note we show how a tighter version (without the log-factors hidden in the ~\Theta-notation), can be derived quite easily using the close connection between polynomials and quantum algorithms.

Affiliated with

Also associated with

No associations

Rating

A note on quantum algorithms and the minimal degree of epsilon-error polynomials for symmetric functions 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 A note on quantum algorithms and the minimal degree of epsilon-error polynomials for symmetric functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A note on quantum algorithms and the minimal degree of epsilon-error polynomials for symmetric functions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-676722