AI 证明 Aaronson-Ambainis 猜想，量子计算界开放难题再被攻克
ns123abc · x · 2026-11-09
理论计算机科学家 Scott Aaronson 在博客宣布：由 AI 证明了他在 2009 年与 Andris Ambainis 共同提出的 Aaronson-Ambainis 猜想——即每个常数方差的 n 元布尔变量度数 d 多项式中，必存在影响力至少 1/poly(d) 的变量。
这条结果意味着什么：
- 它排除了大多数研究者本就不相信存在的一类量子加速，即对多数布尔输入不存在量子查询复杂度对经典查询复杂度的超多项式优势
- 用复杂度类语言说，相对随机 oracle 分离 P 与 BQP 的希望基本被封死（回答了 Fortnow 与 Rogers 1998 年的问题）
Aaronson 特别强调“给傻瓜的版本”：这不推翻量子霸权、也不改变量子计算机的构建方式，只是排除了一个理论上的潜在加速类别。他还感慨如今数学与理论计算机领域的长期开放问题正被 AI 接连攻克，多到他无法一一撰文。
所属事件:AI 证明 Aaronson-Ambainis 猜想，量子加速难题获解(3 条相关)→
「漫话AGI」频道最新
- 冯内古特「买一个信封」语录在AI圈刷屏：我们是会跳舞的动物 — msfeldstein · 2026-11-10
- AACL 2026 综述：元推理框架破解大推理模型过思考与欠思考 — kalyan_kpl · 2026-11-10
- Justine Bateman 回怼科技大佬:他们预测不了人类的未来 — GaryMarcus · 2026-11-10
- 环保组织用 AI 监测野火与气候数据，反驳反 AI 叙事 — castrotech · 2026-11-09
- 开源模型只落后闭源 2 个月，Kimi K3.1 Pro 成最强开放权重模型 — 0xsachi · 2026-11-09
- 反AI浪潮即反智能？小V四论AI是经济与医疗唯一解 — JHochderffer · 2026-11-09