Aaronson–Ambainis猜想获证：低次有界多项式必有高影响变量，量子查询加速须有结构
核心概要
Aaronson–Ambainis 猜想此前只对特殊多项式类成立，一般有界低次多项式的影响下界随次数指数衰减。这项工作给出初等证明：次数不超过 d、取值在 [-1,1] 的函数必有一个变量影响至少为 d 的负常数次幂；按原归一化，方差至少为 1 的多项式也有变量影响不低于同一量级。由此，查询模型中的超多项式量子加速必须依赖输入上的结构或承诺。
深度剖析
次数不超过 d、取值落在 [-1,1] 的离散立方体上的函数，必有一个坐标的影响至少是 d 的某个负常数次幂，常数与函数无关。 此前一般有界多项式只有随次数指数衰减的影响下界，猜想仅在若干特殊多项式类上得到证明。 证明同时给出原归一化下的推论：次数不超过 d、取值在 [-1,1] 且方差至少为 1 的多项式，存在影响不低于同一量级的变量。
证明把问题拆成布尔函数、有界低次函数和带行约束的实函数三段，核心是一条对所有点对成立的不等式。 此前的路线依赖 Lovett 与 Zhang 提出的一个关于分数证书的猜想不等式，该不等式按原文所述并不成立。 新路线改用布尔函数的全对不等式，在每一层水平集上应用并对所有层积分，不挑选单一层。
由此，每个做 T 次查询的量子算法，其接受概率都能被一个做多项式次查询的确定性经典算法在除很小比例之外的所有输入上以加法误差逼近。 这正是 Aaronson 与 Ambainis 所述民间猜想的内容，此前只能由他们证明其与多项式猜想等价。 证明在 Lean 证明助手中形式化了定理 1.1 与推论 1.2，并由其内核检查。
启示与展望
结论针对离散立方体上取值在 [-1,1]、次数不超过 d 的函数，以及查询模型中的量子算法；证明在 Lean 证明助手中形式化了定理 1.1 与推论 1.2，并由其内核检查。
原文说明，形如该界的指数尚非最优：方差指数至少为 1/2，且界必须依赖次数；是否存在形如该界而方差指数为 1 的版本仍未知。原文还指出，Lovett 与 Zhang 所猜的不等式按原表述并不成立，新证明绕开了它。