Robust polynomials and quantum algorithms

DOI10.1007/S00224-006-1313-ZMaRDI QIDQ2643136zbMATH OpenOpenAlexFDO

Authors Harry Buhrman, Ilan Newman, Hein Rohrig, Ronald de Wolf

Publication date 23 August 2007

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/0309220

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68)

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 Theta(n*log n) queries. We give several extensions and applications of these results.

Recommendations

• STACS 2005
• Making polynomials robust to noise
• Making polynomials robust to noise
• Quantum lower bounds by polynomials
• SOFSEM 2005: Theory and Practice of Computer Science

Cited in

(22)

• The hardest halfspace
• Tangible reduction in learning sample complexity with large classical samples and small quantum system
• Bounded indistinguishability and the complexity of recovering secrets
• Making polynomials robust to noise
• scientific article; zbMATH DE number 5320307 (Why is no real title available?)
• scientific article; zbMATH DE number 5320378 (Why is no real title available?)
• Robust Quantum Algorithms with ε-Biased Oracles
• Optimal direct sum results for deterministic and randomized decision tree complexity
• scientific article; zbMATH DE number 6820205 (Why is no real title available?)
• On multiparty communication with large versus unbounded error
• Approximate Degree in Classical and Quantum Computing
• Optimal separation and strong direct sum for randomized query complexity
• Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
• scientific article; zbMATH DE number 7561760 (Why is no real title available?)
• Algorithmic Polynomials
• The polynomial method strikes back: tight quantum query bounds via dual polynomials
• Making polynomials robust to noise
• STACS 2005
• Polynomial approximation on disjoint segments and amplification of approximation
• Approximate degree composition for recursive functions
• Improved direct product theorems for randomized query complexity
• A new minimax theorem for randomized algorithms

This page was built for publication: Robust polynomials and quantum algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2643136)