Scott Aaronson 官宣：悬置 16 年的 Aaronson-Ambainis 猜想被 AI 证明
fortnow · x · 2026-11-10
Scott Aaronson 在博客宣布，他与 Andris Ambainis 于 2009 年提出的 Aaronson-Ambainis 猜想已被证明，证明由 AI 完成，新阐述论文来自 Guy Blanc、Jordan Docter、Carmen Strassle 和 Li-Yang Tan。他在「外行版」说明中给出关键定性：
- AI 确实解决了一个量子计算的重大公开问题；
- 但这并不推翻量子优越性，也不改变量子计算机的构建方式；
- 它排除的是一类大多数人本就不相信存在的量子加速——即对指数多随机比特的是/否性质做超多项式加速的量子查询算法；
- 猜想内容：每个方差为常数、定义在 n 个布尔变量上的 d 次多项式，必有某个变量影响度至少为 1/poly(d)，由此可推出决策问题上量子查询复杂度没有超多项式优势。
Aaronson 感叹理论计算机科学与数学中「长期悬而未决的问题正在成批倒下」，并幽默表示「我的预测是对的，所以以后该多听我的」——他 2019 年还曾博客讨论过一次最终被证伪的证明尝试。
所属事件:AI 证明悬置16年的 Aaronson-Ambainis 猜想(5 条相关)→
「漫话AGI」频道最新
- 美国 30 岁以下人群最常用聊天机器人，却只有 14% 相信 AI 有益社会 — PeterDiamandis · 2026-11-10
- 不可验证的领域没有安全区，智能体让努力变得免费 — generativist · 2026-11-10
- Rasmus：软件像酒店，AI 时代该像家——引发产品观争论 — round · 2026-11-10
- 研究者：不可验证领域并非人类避风港，agent 免费供给努力 — burny_tech · 2026-11-10
- CMU 教授谈 Agent 信任难题：模型对你数据的判断其实很差 — niloofar_mire · 2026-11-10
- Anthropic 与 OpenAI 算力结构剧变:预训练占比两年从 67% 跌至 7% — akbirthko · 2026-11-10