AI 證明了 Aaronson-Ambainis 猜想:量子電腦在無結構任務中受到限制

编辑者: Svitlana Velhush

在解決輸入資料近乎隨機、缺乏特殊數學結構的任務時,量子電腦無法以指數級速度超越普通電腦。這不僅僅是又一項限制——這是一項由人工智慧得出的證明。

2026年十一月,美國新創公司 Physical Superintelligence(PSI)宣布證明了一項猜想,該猜想由德州大學奧斯汀分校的 Scott Aaronson 與拉脫維亞大學的 Andris Ambainis 於2011年提出。該猜想主張:對於在布林立方體上取值介於0到1之間的低次多項式,總能找到一個具有顯著影響的變數。證明由 PSI 基於 Anthropic 未公開模型的內部研究系統找到。全文通過了 Lean 系統的驗證,而闡述則由史丹佛大學的研究人員——Guy Blank、Jordan Docter、Carmen Strassl 與 Li-Yang Tan——撰寫。

該系統運行了四天:首先得出完整證明,隨後兩次對其進行改進,而每一個版本 Lean 都無誤地接受了。這不是量子處理器上的實驗,而是查詢複雜度理論領域中純粹的數學證明。它表明,對於一個對輸入進行 T 次查詢的量子演算法,在多數隨機輸入上,只需使用多項式數量的查詢,就能以高精度在經典電腦上對其進行模擬。

想像一座巨大的倉庫,裡面有數十億個箱子,而所需物品隨機放在某處,沒有任何提示。經典搜尋會逐一翻找箱子。量子搜尋乍看之下似乎能同時窺視所有箱子——但該證明表明,若沒有像 Shor 因式分解演算法那樣的特定結構,這種「窺視」只能帶來多項式級加速,而非指數級加速。多項式中單一變數的影響保證了隨機輸入幾乎總能透過少量位元來預測。

這一結果改變了人們對量子霸權邊界的認知。如今已清楚:對於沒有內建結構的任務——隨機圖、隨機函數——不應期待指數級的優勢。量子電腦在存在結構的地方仍保有優勢,例如在密碼學或具有特殊性質的最佳化問題中。這並未否定實際建造裝置的意義,而是將努力引導向尋找這類結構化任務。

《New Scientist》12年十一月2026日的文章以及 arXiv 上8年十一月的預印本,詳細描述了證明的過程及其對隨機預言機世界中 BPP 與 BQP 類別關係的影響。

量子霸權如今有了更清晰的輪廓:它是真實存在的,但需要的不是隨機性,而是隱藏的規律。

3 浏览量

來源

  • AI confirms a long-suspected limit on quantum computers’ advantages

  • psi.inc

  • arxiv.org

留言

发现错误或不准确的地方吗?我们会尽快处理您的评论。