Aaronson–Ambainis conjecture proved: low-degree bounded polynomials must have an influential variable, so quantum query speedups need structure
Synopsis
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.
Interpretation
A function on the discrete cube of degree at most d with values in [-1,1] must have a coordinate whose influence is at least a negative constant power of d, with a constant independent of the function. Previously, general bounded polynomials had only influence bounds decaying exponentially with the degree, and the conjecture was proved only for several special classes of polynomials. The proof also yields the corollary in the original normalization: a polynomial of degree at most d with values in [-1,1] and variance at least 1 has a variable of influence at least the same order.
The proof splits the problem into Boolean functions, bounded low-degree functions, and real functions with a bounded-cost row at every point, with an inequality over all pairs of points at its core. The earlier route relied on a conjectured inequality of Lovett and Zhang about fractional certificates, which the source states is not true as formulated. The new route instead uses an all-pairs inequality for Boolean functions, applies it at every level set, and integrates over all levels without choosing a single level.
As a result, the acceptance probability of every quantum algorithm making T queries can be approximated to within an additive error on all but a small fraction of inputs by a deterministic classical algorithm making polynomially many queries. This is exactly the folklore conjecture stated by Aaronson and Ambainis, which they had previously shown to be equivalent to the polynomial conjecture. The proof of Theorem 1.1 and Corollary 1.2 has been formalized in the Lean proof assistant and checked by its kernel.
Perspective
The conclusion concerns functions on the discrete cube with values in [-1,1] and degree at most d, and quantum algorithms in the query model; the proof of Theorem 1.1 and Corollary 1.2 has been formalized in the Lean proof assistant and checked by its kernel.
The source states that the exponents in such a bound are not known to be optimal: the exponent of the variance is at least 1/2, and the bound must depend on the degree; whether a bound of this form with variance exponent 1 exists remains unknown. The source also notes that the inequality conjectured by Lovett and Zhang is not true as stated, and the new proof avoids it.