Algorithmic Polynomials
summary
Constructive approximating polynomials replace quantum-derived ones: using Chebyshev polynomials, an extension theorem (extending approximations costs a multiplicative factor ~sqrt(n/m) and an additive log(1/ε)) and a decoupling theorem, explicit low-degree polynomials match or improve known quantum query bounds. Key consequences: surjectivity has approximate degree O(n^{3/4}) despite linear quantum complexity, element distinctness admits the same degree as Belovs’ algorithm, and K-DNF / K-distinctness bounds depend only on K and the input Hamming-weight promise.
AI-written summary · about