Robust Quantum Algorithms and Polynomials
Harry Buhrman, Ilan Newman, Hein Röhrig, de Ronald Wolf · 2005
We study the complexity of robust quantum algorithms. These still work with high probability if the n input bits are noisy. We exhibit a robust quantum algorithm that recovers the complete input with high probability using O(n) queries. This implies that every n-bit function can be quantum computed robustly with O(n) queries, which contrasts with Feige et al.’s Ω(n log n) classical bound for PARITY. We also give similar bounds on the degrees of multilinear polynomials that robustly approximate Boolean functions. 1