Aaronson–Ambainis conjecture proved: low-degree bounded polynomials must have an influential variable, so quantum query speedups need structure
The Aaronson–Ambainis conjecture had been proved only for special classes of polynomials, while general bounded low-degree polynomials had influence bounds decaying exponentially in the degree. This work gives an elementary proof that a function of degree at most d with values in [-1,1] has a variable of influence at least a negative constant power of d; in the original normalization, a polynomial with variance at least 1 also has a variable of influence at least the same order. Consequently, superpolynomial quantum speedups in the query model require structure or a promise on the inputs.