Robust Polynomials and Quantum Algorithms |
| |
Authors: | Harry Buhrman Ilan Newman Hein Rohrig Ronald de Wolf |
| |
Affiliation: | (1) Centrum voor Wiskunde en Informatica, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands;(2) ILLC, University of Amsterdam, Plantage Muidergracht 24, 1018 TV Amsterdam, The Netherlands;(3) Department of Computer Science, Haifa University, Mount Carmel, Haifa 31905, Israel;(4) Department of Computer Science, University of Calgary, Calgary, Alberta T2N 1N4, Canada |
| |
Abstract: | 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 Θ(n log n) queries. We give several extensions and applications of these results. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|