AI 证明 Aaronson-Ambainis 猜想,Scott Aaronson 本人发文确认

IgorCarron · x · 2026-11-09

Scott Aaronson 在博客确认,其与 Andris Ambainis 于 2009 年提出的 Aaronson-Ambainis 猜想已被 AI 证明。他惊讶于该猜想此前未出现在 OpenAI 几周前的「Mathocalypse」战果清单中。

猜想内容:每个方差为常数的有界次数 d 多项式 p:{0,1}^n→[0,1] 必存在某个变量,其影响度至少为 1/poly(d)。该猜想的意义在于:它证明了在大多数布尔输入上,量子查询复杂度相对经典查询复杂度不存在超多项式优势,意味着无法在随机预言机模型下分离 P 与 BQP,并回答了 Fortnow 与 Rogers 1998 年的问题。论证脉络基于 Beals 等人 1998 年的经典结果——量子算法的接受概率可写为次数不超过 2T 的实多项式。这是量子计算理论长期开放问题被 AI 攻克的又一标志性案例。