AI 系统证明 Aaronson-Ambainis 猜想，量子加速疑云尘埃落定

appenz · x · 2026-11-08

开放于 2008 年的 Aaronson-Ambainis 猜想已被证明为定理。该猜想由 Scott Aaronson 与 Andris Ambainis 提出，关乎量子计算机何时能比普通计算机快指数倍：已知的大幅量子加速（如 Shor 算法）都依赖输入的隐藏结构，而该猜想说若其成立，则量子计算机在（几乎无结构的）随机输入上至多多项式级加速。

证明由 Physical Superintelligence（PSI）内部开发的研究系统在自有基础设施上完成，运行中使用了非公开的 Anthropic 模型。系统在运行第三天得到完整证明，并被 Lean 证明助手指令逐步验证通过；随后系统又对相关开放问题展开工作，两次改进结果，最终版本同样通过 Lean 验证。证明建立在 Shachar Lovett、Jiapeng Zhang、David Reimer 等人的思想之上。