PSI用AI 3天证明Aaronson-Ambainis猜想：60页论文

近日，一家Physical Superintelligence实验室拿AI把Aaronson-Ambainis猜想给证了。。这家实验室名为这家机构全称Physical Superintelligence（物理超级智能，PSI），成立时间很短，9月才亮相，主业是用AI做物理研究。今年

该实验室公开了一篇60页的学术预印本论文，题为《A PROOF OF THE AARONSON-AMBAINIS CONJECTURE》（Aaronson-Ambainis猜想的证明）。《-）。这一研究由PSI研究员David Turturean调用了Anthropic一款尚未公开的前沿大模型。在运行环境是PSI自建的算力集群。仅3天，就完成Aaronson-Ambainis猜想被证明，这道难题在理论计算机科学界悬了多年。长达18年之久。

同时，推导全程交给定理证明助手Lean 4做机器内核形式化审查，人工占位符一个没留，也没引入任何未经证明的外部假设。

虽然系统由人搭建，问题由人选定，但是证明本身完全交给了AI。甚至连猜想提出者之一Andris Ambainis也发帖感叹，“我最大的几个科学难题里，又有一个被AI解决了”。

18年难题

量子计算操纵量子比特干涉效应会让叠加态和纠缠态里错误路径的概率幅相互抵消，正确路径的概率幅则被抬高。但是，这种加速不过，这种加速并非没有前提条件。量子算法能跑出多少加速，很大程度上取决于问题本身具备什么样的“结构”

比如，拿大数分解来说，问题自身就带着是具有“周期性结构”。的，所以1994年正因如此，Shor算法才可以把RSA加密以指数级速度破开。。借助量子傅里叶变换（QFT），量子计算机得以跳过经典计算里那套低效的搜索流程。，从而把这种周期快速认出来。。

可要是问题压根没有这类结构呢？其实早在1996年，著名学者Lov Grove就回答过了。面对无序数据的搜索，量子算法相比经典算法能快多少？Grover搜索算法给出的答案是二次加速，也就是多项式级别的提速。

，打个比方，经典计算机要翻查一百万次，量子计算机只需翻查一千次。，则这一差距让一个问题困扰了计算科学近二十年。降低至几次。

的在完全没有代数结构、也没有预设约束的普通问题上，量子计算的加速极限到底在哪里？它能否在绝大多数普通输入上真正颠覆经典计算？

2008年，Scott Aaronson与Andris Ambainis把这个关乎量子物理终极极限的命题，压缩成一道布尔代数分析难题，也就是著名的Aaronson-Ambainis猜想。把猜想的核心命题是：对于任何具有低阶多项式界限的函数，其是否存在影响变量？

这一是，

这几位给出的结论是：对没有特殊结构承诺的判定问题来说，低查询开销的量子算法在绝大多数输入实例上的计算效果，一台普通经典计算机只要用规模相近的多项式查询开销，就能完全复现。

2019年11月，两位以色列学者Nathan Keller和Ohad Klein发布预印本，宣称攻克了Aaronson-Ambainis猜想。论文

不到一个月，佐治亚理工学院数学家Paata Ivanishvili在推演其引理时，发现了一个隐蔽且不可逆转的代数不等式错误。论文随即被作者主动撤回。

2023年，加州大学圣迭戈分校学者Shachar Lovett与Jiapeng Zhang引入布尔函数的分数证书复杂度理论，尝试借助几何凸包距离和再加上极值理论，传统解析路上的难点被绕了过去。

但是可他们最后停在自己搭起的一道坎上：一个关于高维几何分离的不等式猜想。这道猜想他们证不出来，后来的研究还发现，该几何假设放到某些极端边界条件下压根站不住。

沿着老理论往下走，路看上去已经堵死。

用多项式判断量子算力

2001年，Robert Beals等5位学者给出一个结论：任何执行T次黑盒查询的量子算法，对某一输入最终接受的概率，都能精确写成一个关于输入比特的实数多项式，该多项式的代数次数最多不超过2T。

换句话说，一个量子算法跑得快不快、查询次数省不省，跟这个概率多项式的代数次数高不高是一回事。算法如果跑得很快，那么，那对应的多项式次数一定低。

后来，Aaronson和Ambainis提了一个度量指标，叫“变量影响力”。在一个受大量输入比特控制的多项式里，只把某一个比特的取值翻过来，整个多项式的输出概率会出现明显只要翻转某个比特的取值、多项式输出的概率随之跳动，这个比特变量就算得上影响力很高。Ambainis为此提出了一个度量指标，名为“变量影响力”。

基于此，Aaronson-Ambainis猜想给出的判断是：对任何取值落在有限区间内、代数次数不高的非平庸多项式来说，不管它带多少个输入变量，所有变量里必定至少有一个的影响力存在一个不可逾越的非零下界。这个下界跟输入比特的总规模毫无关系。，，只它由什么决定？多项式自身的方差和代数次数。。

经典计算机若要评估一个高效量子算法的输出，做法是把算法拆解成对应的低度多项式。要可以直接把猜想断言必定存在一个影响力大的关键输入比特。经典算法于是先查询这个关键比特。很大待其确定之后，整个函数剩余的不确定性就会随之收窄。关键比特大幅降低接下来，经典算法再去找下一个影响力最大的比特。……

事实上，每一次查询都会削减函数的方差，经典计算机因此只需多项式级别的查询次数，就能以很高精度逼近量子计算机最终的测定结果。

到这一步，证明量子计算机在无结构世界中无法实现指数加速这件事，已经被彻底等价转化为另一个命题：即“低度有界多项式必然存在高影响力变量”。

整个证明在3天内完成。

据PSI论文披露了技术细节：研究员David Turturean搭起一套“研究框架”，先圈定命题边界，再输入历史文献成果，然后搭建调度框架，且把并接入算力环境到与内部科研系统。具体推导、引理假设和以及跨学科工具的组合，全部交给交给模型在后端并发迭代。

系统内部还分配了不同角色的智能体实例，。比如，有的专管检索历史极值组合数学里的冷门定理，有的负责构建反例做检验，有的承担具体不等式的代数变形推导，还有的充当同行评审员。，证明逻辑跳跃。

就在系统启动后的第3天，大模型重新找到了一条纯代数分析的路线被摆上了台面。，完全跳出Lovett和Zhang当初设下的，是高维几何里的凸包陷阱。。

系统的第一步，是把人为设定丢到一边。把它把函数按大于均值、小于均值切成高阶硬性截断，转而引入连续全能级积分，并对所有可能的临界能级铺开一族阶跃水平集函数，由此拿到连续的实数测度。和离散空间分析与连续分析之间，就这样完成了无损过渡。

接下来，系统搬出极值组合论里的工具。Reimer不等式和蝴蝶引理被调用，还配上反极点矩阵变换，搭出一个对称消除恒等式。这一恒等式纯矩阵代数消元法派上用场，证明任意两组点集之间，必定存在满足紧致放缩的代数匹配，这就避开了过去那些让分析失真的测度长尾障碍，就此被绕开。

最后，系统推出一个确定性的代数定量关系。。对任意代数次数不高、取值有界的多项式，其最大单变量影响力的下界，正比于函数方差的二分之五次方，反比于多项式代数次数的六次方，并且与总变量规模无关。

未来多项式次数上的衰减指数，后续可能还有学者继续做数学上的收紧，但是，放到计算复杂性理论里看，来说只要这个下界成立，和从变量规模看，这一结果给出的是多项式级的依赖关系，与规模无关。牢牢绑定在定性层面，只要这个下界成立，Aaronson-Ambainis猜想也随之已经被彻底攻克。

机器内核的验算

众所周知，一篇60页的科研论文按常规流程，需要较长时间的要经过同行评审，其间也可能冒出类似2019年那种隐蔽漏洞的风险。不过这一次，PSI团队把整个流程都交给了Lean 4的形式化机器审查完成，几乎让面对这些质疑，反对者找不到可以指摘的地方。。

目前最先进的交互式定理证明工具当属Lean 4，它Lean的底层逻辑建立在依赖类型论之上。在Lean这套体系里，自然语言中那些跳跃、含糊的表述，以及“显而易见”这类人类惯用的说法，都会被清理掉。想让一个命题站得住，就得把它拆成机器内核可以直接跑的基础逻辑步骤。

PSI团队公开的Lean代码仓库非常清晰：从核心定理一路到所有支撑引理，整个链条完整无缺口，没有留下任何供人工标注跳步的占位符，也没有引入任何额外的公理假设。团队还拿两套架构不同的独立Lean内核做了交叉复核。

截至目前，PSI的这个成果这项成果尚未经过正式同行评审，也没有外部团队完成独立验证。

但这项研究证明当下指向的是AI探索前沿科学的新纵深：它不再只是生成可疑的代码片段，或者帮着润色论文的工具，完成自主打通一条严格的推导链路。

技术一直在往前走，这件事也提醒我们：弄清楚算力到底能干什么、不能干什么，总比一味迷信技术更有意义。

[1]https://github.com/physical-superintelligence/aaronson-ambainis/blob/main/paper/aaronson_ambainis_paper.pdf

[2]https://psi.inc/research/aaronson-ambainis/

[3]https://blog.csdn.net/weixin_40774379/article/details/170236712

[4]https://abmedia.io/psi-anthropic-aaronson-ambainis-proof