在没有规律的问题上，量子计算机做不到指数级加速。
这就是 2008 年提出、困扰学术界整整 18 年的 Aaronson–Ambainis 猜想。
AI物理实验室证实：量子计算在无结构问题上无指数加速
近日，一家名为 Physical Superintelligence（物理超级智能，简称 PSI）的 AI 物理实验室，借助 Anthropic 未公开的大模型，成功证明了这一长期悬而未决的猜想。
PSI 于今年 9 月正式亮相，专注于利用 AI 技术推进物理研究。此次证明由 PSI 研究员 David Turturean 搭建的研究系统完成，该系统调用的具体 Anthropic 模型型号未对外披露。
系统运行至第三天即给出了完整证明，并通过了形式化验证助手 Lean 的检查。Lean 能够对证明中的每一步推理进行逐一核查，确保逻辑严密性。
整个过程中，系统架构由人搭建，研究问题由人选定，而核心证明过程则交由 AI 完成。猜想的共同提出者之一 Andris Ambainis 对此感慨道：“我最大的几个科学难题里，又有一个被 AI 解决了。”
近期，利用 AI 解决高难度数学问题已成为业界热点。10 月底，OpenAI 和 Anthropic 几乎同时宣称在推翻“指数时间假设”方面取得突破，显示出 AI 在基础科学研究中的巨大潜力。
回溯猜想：量子计算的边界与“结构”依赖
公众常误以为量子计算机能并行尝试所有答案从而秒杀任何难题，但量子计算巨头 Scott Aaronson 指出，量子优势并非源于简单的暴力并行。
以 1994 年提出的 Shor 算法为例，其在大数分解上的卓越表现，依赖于题目中隐含的周期性“结构”。已知的大多数量子加速案例，均建立在利用此类内在规律的基础上。
然而，对于缺乏内在规律的随机输入（如随机序列），量子计算机是否仍具优势？2008 年，Scott Aaronson 与拉脱维亚学者 Andris Ambainis 将此问题转化为纯数学命题，即 Aaronson–Ambainis 猜想。
开关模型与影响力理论
该猜想可通过“开关模型”理解：假设有一排隐藏开关，每个开关对应输入的一位（0 或 1）。经典计算机每次只能查看一个开关，而量子计算机利用叠加态可同时观测多个开关，但获取的信息是混合的。
证明的核心思路在于论证经典计算机可以模拟量子计算机，且查询次数不会呈指数级增加。这引入了“影响力”概念：当某个开关状态改变时，导致输出概率指针平均移动的程度。
Aaronson–Ambainis 猜想断言：只要输出概率对输入敏感（指针非静止），必然存在至少一个具有显著“影响力”的开关。
若猜想成立，经典计算机可采取贪心策略：优先查询影响力大的开关。每查询一次，剩余的不确定性便大幅降低。因此，经典计算机所需的查询次数仅为量子计算机的多项式倍，而非指数倍。
结论表明：在无结构问题上，量子计算机仅能实现多项式级加速；若要获得指数级加速，问题必须具备特定的数学结构。
技术突破：绕过既往证明瓶颈
PSI 的证明并非从零开始。2023 年，学者 Shachar Lovett 和 Jiapeng Zhang 曾提出一套证明方案，但卡在其中一个关键不等式的证明上。
PSI 的研究系统通过引入并证明一个新的不等式，成功绕过了这一障碍。最终生成的 Lean 代码完整无误，未使用任何占位符或额外公理，并经过两套独立 Lean 内核的双重验证。
历史插曲与当前状态
该猜想曾在 2019 年被 Nathan Keller 和 Ohad Klein 声称证明，但不久后因发现引理漏洞而被撤回。
目前，PSI 的证明虽通过机器验证，但尚未经过正式的同行评审及外部团队的独立复核。此外，Lean 代码是否精准映射原猜想语义，以及 60 页论文的人类可读部分，仍需学界进一步审视。
值得注意的是，Anthropic 的内部模型已在多个数学前沿领域展现突破能力。随着 AI 辅助科研模式的成熟，更多基础科学难题有望迎来解答。