Aaronson--Ambainis conjecture: bounded low-degree polynomials have an influential variable
ProvedAaronsonAmbainis.aaronson_ambainis_conjectureLet be a real multivariate polynomial of degree at most , viewed as a function on the Boolean cube under the uniform distribution, with , and as in the imported definitions.
The conjecture asserts that boundedness together with low degree forces some single coordinate to carry a polynomially large share of the function's variance. Precisely, there is an absolute constant such that the following holds for every , every , every such and every : if
- for every ,
- , and
- ,
then there exists a coordinate with
The conjecture is the open problem at the centre of Aaronson and Ambainis's case that quantum speedups require structure: they prove that it would imply every bounded-error quantum algorithm making queries to a Boolean input can be simulated on most inputs, to small error, by a classical algorithm making queries. Note that the constant is quantified outermost, so it may not depend on , , or ; that uniformity is the whole content, since bounds degrading exponentially in are known.
Formalization Note Three choices are worth flagging. Boundedness is asserted only at cube points, not on all of , matching the source. The source's exact-degree hypothesis is rendered as p.totalDegree ≤ d universally quantified over ; this is equivalent, because the smallest admissible yields the strongest bound. The source's exponent is rendered as an existentially quantified C : ℕ with no leading multiplicative constant, since admitting one would weaken the claim. A fourth point concerns the degree hypothesis: MvPolynomial.totalDegree is the syntactic total degree of the representative polynomial, not the degree of the function it induces on the cube. Since and depend on only through its values at cube points, the polynomial induces the same cube function as while having total degree . This does not change the statement's content. Multilinear reduction never raises degree, because a monomial of total degree involves at most distinct variables, so the multilinear degree of the induced function is at most totalDegree; conversely every cube function has a multilinear representative whose totalDegree equals its multilinear degree, and that representative is itself an admissible instance. The formalization is therefore equivalent to the reading in which bounds the multilinear degree. Solvers should nonetheless expect to pass to the multilinear representative before using the degree hypothesis.
import Definitions.Def_AaronsonAmbainis
namespace AaronsonAmbainis
theorem aaronson_ambainis_conjecture :
∃ C : ℕ, ∀ (N d : ℕ) (p : MvPolynomial (Fin N) ℝ) (ε : ℝ),
p.totalDegree ≤ d →
(∀ x : Fin N → Bool, 0 ≤ cubeEval p x ∧ cubeEval p x ≤ 1) →
0 < ε → ε ≤ cubeVar p →
∃ i : Fin N, (ε / (d : ℝ)) ^ C ≤ cubeInfl p i := by sorry
end AaronsonAmbainis
Confirmed by the mission captain (proposal self-audit).