We define and study the complexity of \emph{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 \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.

Springer
Theory of Computing Systems
Quantum Information Processing , Quantum Computing: algorithms, proofs and tradeoffs , Qubit Applications
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.