Robust Polynomials and Quantum Algorithms

Details Robust Polynomials and Quantum Algorithms Robust Polynomials and Quantum Algorithms

2003-09-30

arxiv.org/abs/quant-ph/0309220v2

Physics

Quantum Physics

Scientific paper

We define and study the complexity of robust polynomials for Boolean functions and the related fault-tolerant quantum decision trees, where input bits are perturbed by noise. We compare several different possible definitions. Our main results are * For every n-bit Boolean function f there is an n-variate polynomial p of degree O(n) that robustly approximates it, in the sense that p(x) remains close to f(x) if we slightly vary each of the n inputs of the polynomial. * There is an O(n)-query quantum algorithm that robustly recovers n noisy input bits. Hence every n-bit function can be quantum computed with O(n) queries in the presence of noise. This contrasts with the classical model of Feige et al., where functions such as parity need Theta(n*log n) queries. We give several extensions and applications of these results.

Affiliated with

Also associated with

No associations

Rating

Robust Polynomials and Quantum Algorithms 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 Robust Polynomials and Quantum Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Robust Polynomials and Quantum Algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-280419