量子計算18年猜想證明公開，PSI稱研究使用Anthropic AI

人工智慧研究公司 Physical Superintelligence（PSI）公開了2008年提出的阿倫森—安拜尼斯猜想證明。這項猜想探討，在處理隨機輸入的特定計算中，量子電腦能否大幅減少查詢輸入的次數；證明指出，查詢次數無法因此呈指數級下降。

PSI於6日發布的研究公告表示，研究系統在自建基礎設施上運作，並使用Anthropic未公開名稱的模型。同一模型的多個執行實例參與研究；系統在執行的第三天完成完整證明，並通過Lean檢查。

PSI表示，之後又讓系統處理相關難題兩次，進一步改進結果，最終版本也通過Lean檢查。公司沒有公開所用模型的具體名稱。

史考特·阿倫森（Scott Aaronson）與安德里斯·安拜尼斯（Andris Ambainis）提出的猜想，關注量子電腦能否在沒有特殊規律的隨機輸入下，比一般電腦以指數級更少的查詢次數完成計算。研究中的輸入是由0和1組成的長字串，計算則要依據字串判斷答案為「是」或「否」。

一般電腦每次查詢輸入時會讀取字串中的一個位元。量子演算法則能利用多個位置的疊加態，在一次查詢中處理多個位置的資訊。

量子演算法回答「是」的機率，可以表示成輸入位元的多項式。PSI以既有研究為基礎建構證明；該研究指出，這個機率可用次數不超過查詢次數兩倍的多項式表示。

證明指出，對大多數隨機字串，一般電腦都能在小幅誤差範圍內近似量子演算法的回答機率。一般電腦所需的查詢次數，只會相對於量子演算法的查詢次數增加至固定的多項式級別，不會呈指數級增加。

猜想的數學核心，是單一輸入位元對多項式輸出的「影響力」。這項指標會計算翻轉一個位元後多項式輸出值的變化量平方，再對所有輸入取平均。

PSI提出一項下界：對輸出值介於0與1之間、非定值且次數較低的多項式，至少存在一個輸入位元具有一定影響力。若輸出變異數為v、多項式次數為d，影響力下界約為0.0025×v的2.5次方除以d的6次方。

這項結果不代表量子電腦的所有計算都無法加速，而是針對隨機輸入下特定「是或否」判斷所需查詢次數的理論結果。

能快速分解大數的Shor演算法，利用的是問題中隱藏的週期模式。PSI表示，已知多數顯著的量子加速案例都仰賴這類結構，而隨機輸入幾乎沒有相同模式。

史丹佛大學研究團隊於2026年8月證明了這項猜想的一個特例，研究對象是以固定次數的平行階段查詢輸入的量子演算法。PSI表示，目前有四名研究人員正在檢視完整證明。

研究人員在寄給PSI的信中稱，解決一項數十年的猜想是「一項重大成果」。他們也指出，這份證明串連了布林函數分析與機率組合學的多條研究脈絡。

PSI表示，證明沿用了夏哈爾·洛維特（Shachar Lovett）與張家鵬（Jiapeng Zhang）的方法。研究團隊以新的不等式取代兩人留下的不等式，並利用行列式得出配對輸入設定的結果。

PSI說明，帶領研究的負責人開發研究系統、設定問題並執行研究，也審閱AI撰寫的論文初稿並對其正確性負責。一名顧問委員審核證明，另一名顧問委員則檢視Lean形式化內容。

論文與Lean形式化程式碼已公開在GitHub儲存庫。儲存庫表示，程式碼沒有未完成的證明佔位內容或額外公理，並以兩種互相獨立的Lean核心實作重新檢查。

Lean會檢查程式碼中形式化命題及證明的邏輯步驟。儲存庫也提醒讀者，仍須將程式碼中的命題與問題定義對照，確認其與原始猜想一致。ABMedia報導稱，這篇論文尚未經學術期刊審查。AI形式化數學難題的其他案例，還包括OpenAI公開納維—斯托克斯方程式證明一事。