PSI内部研究系统用Anthropic模型证明Aaronson-Ambainis猜想

Aaronson-Ambainis 猜想如今已成为定理。

这一由 Scott Aaronson 和 Andris Ambainis 于 2008 年提出的猜想，关乎量子计算机何时能比普通计算机快指数级，自提出以来一直悬而未决。如今，Physical Superintelligence（PSI）内部开发的一套研究系统运行了一个非公开的 Anthropic 模型，为该猜想找到了证明，从而解决了量子计算中最根本的问题之一。

1994 年，Peter Shor 发现了一种量子算法，其分解大数的速度远超任何已知的普通计算机方法 [1]。它能奏效，是因为该问题隐藏着一个重复模式，而量子计算机能找到它重复的频率。与大多数已知的显著量子加速一样，Shor 算法依赖于结构：即输入具有某种罕见模式的承诺。

量子计算机能否在几乎从不具备这种结构的随机输入上实现指数级加速，此前并不清楚。Aaronson 和 Ambainis 找到了一种用纯数学解决这一问题的方法。他们提出了一个关于多项式的猜想，并证明：如果该猜想成立，那么量子计算机在随机输入上至多只能实现多项式级的加速。研究人员一直将该猜想列为量子复杂性理论的核心未解问题之一 [3, 4]。

在 PSI，我们用内部开发的一套研究系统，在我们自己的基础设施上运行，找到了证明。运行中使用了非公开 Anthropic 模型的多个实例。该系统在运行的第三天就得到了该猜想的完整证明，并且 Lean——一个由计算机检查每一步的证明助手——接受了该证明。随后，我们让系统着手处理相关的未解问题。在此过程中，系统两次改进了结果，Lean 接受了最终版本。该证明建立在 Shachar Lovett 和 Jiapeng Zhang、David Reimer 以及其他人思想的基础之上 [5, 6]。

2026 年 8 月，斯坦福大学的 Guy Blanc、Jordan Docter、Carmen Strassle 和 Li-Yang Tan 在一个特殊情形下解决了该猜想的预测，证明了对于以固定数量的并行轮次查看输入的量子算法，在随机输入上不存在指数级加速 [7]。

此后，他们一直在阅读我们对完整猜想的证明，已向我们发来评论，并正在为专家撰写一份更简短的阐释。他们写信给我们说：

“这是一个巨大的结果。它解决了一个数十年前的猜想，对于哪些问题允许量子加速这一本质问题具有重要启示。该证明借鉴并扩展了布尔函数分析和概率组合学中的若干研究方向。一切都以一种相当神奇的方式汇集在一起。”

量子计算仍有许多未解之谜，但现在少了一个。

像 Shor 算法这样的加速可以用“查看次数”来衡量：计算机必须读取其输入的次数，输入是一长串 0 和 1。每次查看时，普通计算机读取字符串的一位，而量子计算机的一次查看可以通过叠加态分布在许多位置上。当字符串被承诺会重复时，如在 Shor 算法中，量子计算机所需的查看次数比任何普通计算机都少指数级。

Aaronson 和 Ambainis 问的是：量子计算机能否以比普通计算机少指数级的查看次数，回答关于一个随机字符串的是非问题。要证明不能，只需证明普通计算机可以在无需多出太多查看次数的情况下模仿量子计算机。量子计算机以依赖于该字符串的概率回答“是”，因此模仿它就意味着估计该概率。

Beals、Buhrman、Cleve、Mosca 和 de Wolf 已经证明，在 T 次查看之后，该概率是字符串各位的一个多项式，次数至多为 2T，取值在 0 和 1 之间 [8]。因此，普通计算机必须在只读取字符串少数几位的情况下，预测这种多项式的值。Aaronson 和 Ambainis 提出了一个关于这些多项式的猜想，这是一个纯数学陈述，并证明：如果它成立，普通计算机就能以少量查看次数做出预测。

既然该猜想已被证明，我们确知普通计算机可以对除一小部分字符串之外的所有字符串，在很小误差范围内预测量子计算机回答“是”的概率。普通计算机所需查看次数至多按 T 的某个固定幂增长（对于任意固定误差和比例），而非指数增长。因此，在是非问题上，除非字符串具有罕见模式，量子计算机无法节省指数级的查看次数。

该猜想涉及某一位的影响：当该位从 0 翻转为 1 或反之，多项式值的平均变化。要形象理解影响，可把多项式想象成一个刻度盘，连接到一组开关上，其中第 i 个开关是第 i 位的 0/1 值。每组至多 d 个开关，当组内所有开关都打开时，会贡献自己的量，可正可负（d 是多项式的次数）。刻度盘的读数（多项式的值）始终保持在 0 和 1 之间。量子计算机回答“是”的概率就是这样一个刻度盘：字符串设定开关，而 d 至多为 2T。

设 v 衡量刻度盘读数在不同设置下的变化程度（读数的方差）。Aaronson 和 Ambainis 猜想：无论有多少开关，翻转某个开关平均会使读数移动至少 v/d 的某个固定幂。

一个定义在四位上的二次多项式 f，f(x) = 0.1 + 0.5x4 + 0.2x1x2 + 0.1x3。开关设定输入，指针显示 f(x)。立方体的每个角是 2⁴=16 个输入之一，按其 f 值着色，翻转一个开关会沿着该位的边移动到相邻的角。某一位的影响是翻转它时 f 的变化量平方后对全部 16 个输入取平均。第 4 位的影响远大于其他位。

f(x) = 0.10 影响 第1位 第2位 第3位 第4位 每根柱是对全部 16 个输入的平均值。标记是当前输入处的变化量平方。

新多项式

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