Robust polynomials and quantum algorithms

DOI10.1007/s00224-006-1313-zzbMath1121.68049arXivquant-ph/0309220OpenAlexW1859250467MaRDI QIDQ2643136

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

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)

Related Items

Approximate Degree in Classical and Quantum Computing ⋮ Tangible reduction in learning sample complexity with large classical samples and small quantum system ⋮ Optimal direct sum results for deterministic and randomized decision tree complexity ⋮ Polynomial approximation on disjoint segments and amplification of approximation ⋮ Algorithmic Polynomials ⋮ The hardest halfspace ⋮ Improved direct product theorems for randomized query complexity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Algorithms and lower bounds for de morgan formulas of low-communication leaf gates ⋮ Bounded Indistinguishability and the Complexity of Recovering Secrets ⋮ Unnamed Item ⋮ Unnamed Item