AI 证明了 Aaronson-Ambainis 猜想

“傻瓜版”说明（抱歉没早点加这一段）：

当然，我们如今身处这样一个时代：量子计算理论（以及整个理论计算机科学、整个数学领域）中悬而未决多年的开放问题正接连被攻克，多到我根本不可能为每一个重磅突破都单独写一篇文章。但Aaronson-Ambainis猜想我实在绕不过去——毕竟我的名字就挂在上面，而且这个问题的答案对我很重要（2019年我甚至写过博客，讨论一个最终被证明是错误的尝试性解法）。

给在家关注的读者补一下背景：AA猜想是我和Andris在2009年提出的，说的是对于n个布尔变量上的任意有界d次多项式p:{0,1}n→[0,1]，若其方差为常数，则必存在某个变量的影响至少为1/poly(d)。我和Andris关心这个猜想，是因为我们证明了它蕴含：对于大多数布尔输入都成立的判定问题，量子查询复杂度相对于经典查询复杂度不存在超多项式优势。或者用复杂度类的语言说：在不证明P≠BQP（或类似的非相对化结论）的前提下，不可能相对于随机预言机分离P和BQP。这将最终回答Fortnow和Rogers在1998年提出的一个问题。

量子算法与多项式之间的联系来自Beals等人1998年的著名论文：若Q是一个对预言机X做T次查询的量子算法，则Pr[Q(X)接受]可以写成X各比特上的一个多变量实多项式p(X)，次数至多2T。我和Andris结果的证明则很简单：取多项式p，找到其中影响至少为1/poly(T)的变量，查询该变量，如此反复，直到不再存在这样有影响力的变量——此时按假设p已接近常数多项式，也就意味着你已以高概率（对X）得知Q是否接受。这就给出了量子算法Q的经典模拟，对预言机X做poly(T)次查询，且对大多数X都有效。

AA猜想受欢迎的程度远超我和Andris的预料。有些研究它的人几乎不关心它对量子计算的含义，只想解决这个关于多项式的问题！既自豪又抱歉地报告：有些傅里叶分析专家和研究生把整个研究方向都围绕证明AA来组织，产生了大量特殊情形的证明，有些还非常新。完整AA的证明是量子查询复杂度中最后几个剩下的开放问题之一，大家都一致认为它至关重要。说实话，几周前OpenAI的“数学末日”式成果发布里没有它，我很惊讶。他们肯定试过，难道它真的比所有已解决的问题都难那么多？

现在，一家名为Physical Superintelligence的初创公司宣布证明了AA猜想，具体证明了存在影响至少约1/d6的变量，他们说这是用其专有研究框架在内部Claude模型上得到的。（框架相对于内部模型起了多大作用，我不清楚。）这项工作由PSI的David Turturean和Jim Halverson领导。他们几周前就告诉了我，但我一直保密到上周晚些时候的公告发布。

我还没理解这个证明，但我希望能理解。不过与此同时，我相信证明是对的，有两个原因。第一，有Lean证书；第二，人类专家（我自己已经不再是“我自己猜想”的专家了！）已经审阅并理解了它。事实上，MIT的Guy Blanc和斯坦福的Jordan Docter、Carmen Strassle、Li-Yang Tan已经写了一篇看起来很漂亮的阐述，对于想深入得多的人来说是完美的起点。或者，对于只想稍微深入一点的人，PSI关于这一进展的博客文章写得足够好，省得我在这里写太多。

唉，正如Ashley Montanaro所报道的，关于这个结果对量子计算意味着什么，照例出现了那些令人拍额的误解。比如华盛顿大学的Pedro Domingos向他13.7万X粉丝宣称，这个证明意味着“量子霸权的梦想已死”。真相是——Pedro完全清楚（或很容易知道）——它排除的是某一特定类型的量子霸权（即相对于随机预言机的判定问题），而我们本来就已猜想这种霸权不存在。它丝毫没有动摇我们确实猜想存在的任何形式的量子霸权！例如，它对Shor因数分解算法零影响，该算法在关键内部步骤使用高度非随机（周期性）的预言机。它对量子物理和化学的模拟零影响，后者通常根本不依赖预言机算法。即便仅相对于随机预言机，2022年Yamakawa-Zhandry的突破也极大地表明：如果我们把注意力从判定问题转向其他类型的问题（在Yamakawa和Zhandry的案例中是NP搜索问题），指数级量子加速确实成为可能。总之，Pedro这种做法在智识上极不诚实，让我以后不愿再认真对待他的任何说法。

如果你想知道我对AA证明的感受——嗯，就像我妻子Dana对Unique Games猜想那样，是许多种情绪同时涌上心头。

总之，热烈祝贺David Turturean和Jim Halverson，祝贺Physical Superintelligence，当然也祝贺Claude取得这一成就！

本文于2026年11月8日星期日下午3:44发布，归类于AI、公告、复杂性、量子、怒斥愚蠢。

（原文较长，此处译出前 6000 字，完整内容请点「打开原文」。）