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 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.
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., Newman, I., Röhrig, H., & de Wolf, R. (2007). Robust Polynomials and Quantum Algorithms. Theory of Computing Systems, 40(4), 379–395. |