跳到正文
新浪科技·· 15 天前AI 評分71

Physical Superintelligence(PSI)研究系統藉助 Anthropic 未公開模型,三天給出 Aaronson–Ambainis 猜想完整證明

刚刚,Anthropic 神秘模型出手!3 天攻克 18 年量子计算难题

AI 導讀

PSI 研究系統藉助 Anthropic 未公開模型,第三天給出 Aaronson–Ambainis 猜想的完整證明。證明通過 Lean 檢查,研究系統以新不等式繞過 2023 年方案未能證明的不等式,並用兩套獨立實作的 Lean 內核重新檢查。不過,這份證明尚未經正式同行評審或外部團隊獨立驗證;Lean 檢查不能確認形式化命題是否準確表達原猜想,60 頁論文也未經機器檢查。

正文

在没有规律的问题上,量子计算机做不到指数级加速。

这就是 2008 年提出、困扰学术界整整 18 年的 Aaronson–Ambainis 猜想。

刚刚,一家 AI 物理实验室借助 Anthropic 未公开的模型,证明了这个猜想!

这家实验室名叫 Physical Superintelligence(物理超级智能,PSI),今年 9 月才亮相,专门用 AI 做物理研究。

证明出自 PSI 研究员 David Turturean 搭建的一套研究系统。系统调用的那个 Anthropic 模型,具体型号 PSI 没有透露。

这个系统运行到第三天,就给出了 Aaronson–Ambainis 猜想的完整证明,甚至证明还通过了 Lean 检查。

Lean 是一种证明助手,证明里的每一步推理,电脑都会逐一检查。

系统是人搭建的,问题是人选定的,证明本身交给了 AI。

连猜想的提出者之一 Andris Ambainis 都发帖感慨,「我最大的几个科学难题里,又有一个被 AI 解决了。」

用 AI 证明数学猜想,这个秋天快成 OpenAI 和 Anthropic 的传统保留节目了。

10 月底,这两个老对手还几乎同时宣称推翻了「指数时间假设」。

遇事不决,量子力学。

量子计算机也常被当成这种万能钥匙,就好像它能把所有可能的答案同时试一遍,什么难题都能秒杀。

可 Aaronson–Ambainis 猜想的另一位提出者、量子计算大牛 Scott Aaronson 的博客写着这样一句话,「量子计算机不会靠把所有答案并行试一遍,瞬间解开难题。」

量子计算机最出名的成果,是 1994 年的 Shor 算法,它分解大数的速度,比普通电脑上已知的任何方法都快得多。

Shor 算法这么快,是因为题目里藏着一个循环往复的规律,量子计算机只需要找出规律多久重复一次。

已知的大多数惊人的量子加速,靠的都是题目自带的这种规律,学术界称之为「结构」。

可要是题目根本没有规律呢?比如输入就是一串随机的 0 和 1。

Aaronson 1999 年刚入行时,最早研究的问题之一就是这个,但没能解决。

2008 年前后,他和拉脱维亚学者 Ambainis 把它转化成了一道纯数学题,也就是著名的 Aaronson–Ambainis 猜想。

要看懂这道题,你可以先想象一排藏在帘子后面的开关,每个开关有两种状态,对应输入里的 1 和 0。题目是一道关于这排开关的是非题,比如「开着的开关是不是超过一半」,电脑只需要回答「是」或「否」。

电脑想知道答案,就得掀开帘子查看开关,每看一次记一次数,比快慢就是比谁看的次数少。

普通电脑一次只能看一个开关,量子计算机借助叠加态,一次能同时看到多个开关,只是看到的信息混在一起,没法一下子全都看清。

要证明量子计算机在没规律的问题上做不到指数级加速,思路是证明普通电脑能模拟它,而且不用多看太多次。

量子计算机看完后,回答「是」的概率有多大,由这排开关的状态决定。这个概率就像一个表盘,背后连着所有开关,哪个开关状态变了,指针都可能跟着动。量子计算机看的次数越少,表盘背后的接线就越简单。

某个开关换个状态,指针平均挪动多少,就叫这个开关的「影响力」。

右上是 4 个开关和表盘指针,下方横条是每个开关的「影响力」,bit 1 那条最长,拨它指针挪得最多。左边立方体的 16 个顶点,对应 4 个开关的 16 种组合。

Aaronson–Ambainis 猜想说的是,「不管有多少个开关,只要指针不是纹丝不动,就一定有某个开关的影响力足够大。」

这句话一旦成立,普通电脑就有了模拟量子计算机的办法。

量子计算机的算法是已知的,表盘怎么接线,普通电脑计算得出来。它先查看一个影响力大的开关,看完再找下一个,直到剩下的开关不管怎么变,指针都基本不动,就停下来,把指针的平均读数当作量子计算机回答「是」的概率。

这个猜想保证了每一步都有值得看的开关,每看一个,指针还能晃动的余地就少一点,所以普通电脑看的次数,最多是量子计算机所看次数的某个固定次方,不会呈指数级增长。

也就是说,在没有规律的问题上,量子计算机最多只能实现多项式级的加速,想要指数级的加速,题目必须有规律。Shor 算法这类针对有规律难题的加速,照样成立。

PSI 的证明并非从零起步。

两位学者 Shachar Lovett 和 Jiapeng Zhang 曾于 2023 年提出过一套证明方案,方案卡在一个不等式上,这个不等式他们自己也没能证明出来。

PSI 的研究系统改用了一个新的不等式,并把它证明了出来,绕过了这道坎。

证明中的 Lean 检查已经完整,没有留下任何「先跳过、回头再证」的占位符,也没有引入额外公理。

PSI 还用两套独立实现的 Lean 内核,重新检查了一遍。

但有些地方,这些检查覆盖不到。

第一,Lean 里写下的那个命题,是不是准确表达了原猜想,相当于题目有没有理解对。

第二,60 页的论文是写给人看的,本身没经过机器检查。

Aaronson–Ambainis 猜想,其实「被证明」过一次。

2019 年 11 月,Nathan Keller 和 Ohad Klein 公布了一份证明的预印本。Aaronson 还专门写了一篇博文,给猜想标上了「2008-2019」。

不到一个月,数学家 Paata Ivanishvili 在论文的一个引理里发现了致命漏洞,随后两人撤回了论文。

截至目前,PSI 的这份证明还没有经过正式的同行评审,也没有外部团队完成独立验证。

Anthropic 的内部模型,在数学上不是第一次有突破了。

10 月底推翻指数时间假设的那篇论文,Anthropic 也声称,「找到核心算法的是一个内部研究用的 Claude 模型。」

这个模型何时对外开放,暂未可知。

來源:新浪科技 · finance.sina.com.cn