2007
Robust Polynomials and Quantum Algorithms
Publication
Publication
Theory of Computing Systems , Volume 40  Issue 4 p. 379 395
We define and study the complexity of \emph{robust} polynomials for Boolean functions and the related faulttolerant quantum decision trees, where input bits are perturbed by noise. We compare several different possible definitions. Our main results are \begin{itemize} \item For every $n$bit Boolean function $f$ there is an $n$variate polynomial $p$ of degree $\bigO(n)$ that \emph{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. \item There is an $\bigO(n)$query quantum algorithm that \emph{robustly} recovers $n$ noisy input bits. Hence every $n$bit function can be quantum computed with $\bigO(n)$ queries in the presence of noise. This contrasts with the classical model of Feige~\etal, where functions such as parity need $\Theta(n\log n)$ queries. \end{itemize} We give several extensions and applications of these results.
Additional Metadata  

Springer  
Theory of Computing Systems  
Quantum Information Processing , Quantum Computing: algorithms, proofs and tradeoffs , Qubit Applications  
Organisation  Quantum Computing and Advanced System Research 
Buhrman, H.M, Newman, I, Röhrig, H, & de Wolf, R.M. (2007). Robust Polynomials and Quantum Algorithms. Theory of Computing Systems, 40(4), 379–395.
