困扰量子计算领域十余年的“阿隆森-安巴伊尼斯猜想”（Aaronson-Ambainis Conjecture）已被正式证明为定理。这一突破厘清了量子计算机在处理随机数据时的能力边界。
物理超智能公司（Physical Superintelligence, PSI）宣布，其内部研发的研究系统在自有基础设施上运行非公开版本的Anthropic模型，成功找到了该猜想的完整证明。整个证明过程由计算机辅助证明助手Lean验证通过。在此基础上，系统进一步攻关相关开放问题，两次改进结果并均获Lean认可。
量子加速的边界：结构决定速度
自1994年彼得·肖尔（Peter Shor）提出肖尔算法以来，量子计算机在分解大数等特定任务上展现出远超传统计算机的速度。然而，这种指数级加速依赖于输入数据存在特定的“结构”或重复模式。对于缺乏此类结构的随机输入，量子计算机是否仍能实现指数级加速，一直是理论计算机科学的核心未解之谜。
2008年，斯科特·阿隆森（Scott Aaronson）和安德里斯·安巴伊尼斯（Andris Ambainis）提出猜想：如果该猜想成立，则量子计算机在处理随机输入时，最多只能实现多项式级的加速，而非指数级。这意味着，除非数据具有罕见模式，否则传统计算机可以通过少量查询模拟量子计算机的输出概率。
PSI的证明确认了这一猜想。结果表明，对于绝大多数随机字符串，传统计算机只需读取少量比特位，即可以较小误差预测量子计算机输出“是”的概率。查询次数仅随多项式增长，而非指数级爆炸。这从理论上划定了量子优势的范围：在没有结构化数据的情况下，量子计算机无法节省指数级的查询成本。
学界评价与技术路径
斯坦福大学学者Guy Blanc、Jordan Docter、Carmen Strassle和Li-Yang Tan曾在2026年8月针对固定并行轮次的特殊情况证明了该猜想的预测。在阅读了PSI的完整证明后，他们评价道：“这是一个巨大的成果。它解决了一个困扰学界数十年的猜想，对理解哪些类型的问题能够实现量子加速具有重要意义。”他们指出，该证明巧妙统一了布尔函数分析和概率组合学中的多个研究方向。
PSI的证明建立在Shachar Lovett、Jiapeng Zhang和David Reimer等人的前期工作之上。研究团队通过引入新的不等式替代原有猜想中的限制，并利用行列式配对及“蝴蝶引理”等数学工具，严格证明了低次有界多项式中必然存在显著影响的变量。这一数学突破确保了传统计算机在模拟过程中总能找到高影响度的比特位，从而有效逼近量子计算机的输出结果。
目前，量子计算领域仍有许多未解之谜，但随着阿隆森-安巴伊尼斯猜想的尘埃落定，学界对量子加速本质的理解迈出了关键一步。