AI 系统给出 Aaronson-Ambainis 猜想证明,Lean 验证通过
fortnow · x · 2026-11-07
量子计算重大进展:悬置 18 年的 Aaronson-Ambainis 猜想被证明,证明出自 Physical Superintelligence(PSI)内部研发的研究系统,运行中使用的是非公开的 Anthropic 模型。
- 猜想意义:该猜想自 2008 年提出,关乎量子计算机何时能比经典计算机指数级加速。Shor 算法等已知的戏剧性量子加速都依赖输入的隐藏结构;猜想若成立,则量子计算机在无结构的随机输入上最多只能多项式级加速,是量子复杂性理论的核心开放问题之一
- 验证过程:系统在运行第三天得到完整证明,证明助手 Lean 逐步检查并接受;随后系统继续解决相关开放问题,过程中两次改进了结果
- 技术基础:证明建立在 Shachar Lovett 与 Jiapeng Zhang、David Reimer 等人此前工作之上
- 作者 fortnow(理论计算机科学家 Lance Fortnow)补充:他与 John Rogers 在 1998 年就曾讨论随机预言机下 P 与 BQP 的关系,该新结果隐含 (BQP in Average-P)^R
这是「AI 做数学研究」迄今最有分量的成果之一。
所属事件:PSI 系统 3 天证明悬置 18 年的 Aaronson-Ambainis 猜想(14 条相关)→
「漫话AGI」频道最新
- 经济学人作者：AI 腔正在渗入人们的日常口语 — paulnovosad · 2026-11-08
- 研究者提出「宇宙恐怖」假说：AI 编程智能繁荣或摧毁软件生态长期价值 — josephdviviano · 2026-11-08
- 瑞典日报邀 50 位专家绘制三大 AI 灾难场景 — anderssandberg · 2026-11-08
- AI 需求与成本同呈指数变化，评论称无需 FOMO — oran_ge · 2026-11-08
- 教授质疑读博价值：答辩当天 AI 花 1.5 欧元即给出更优答案 — FlorianGallwitz · 2026-11-08
- 「苦涩教训」作者 Sutton 重申：纯算力堆不动智能 — The Decoder · 2026-11-08