GPT-5解決量子版NP難題？半小時(shí)內(nèi)給出有效方案

量子計(jì)算聽起來(lái)就很燒腦了，但在理論世界里還有一群人，他們專門研究「量子證明」能做到什么程度。這個(gè)領(lǐng)域叫量子復(fù)雜性理論，其中很出名的一個(gè)類是QMA——它是「量子版的NP問題」，可以理解成：有一個(gè)「量子證明」，由驗(yàn)證者用量子計(jì)算機(jī)來(lái)檢查真假。

過去二十年，研究者不斷嘗試把驗(yàn)證錯(cuò)誤率壓得越來(lái)越低，就像玩游戲要刷「滿暴擊率」。而這次，理論物理學(xué)家Scott Aaronson和合作者Freek Witteveen給出了一個(gè)明確答案：用黑箱方法，你刷到頭了。

他們的思路已經(jīng)走到了盡頭，因此轉(zhuǎn)而尋求 GPT-5 的幫助。通過不斷改進(jìn)，該模型最終提出了一種巧妙的數(shù)學(xué)函數(shù)，使得可以精確分析特征值的行為。

相關(guān)的研究?jī)?nèi)容以「Limits to black-box amplification in QMA」為題發(fā)表在 arxiv。

論文鏈接：https://arxiv.org/abs/2509.21131

放大是什么？極限又在哪里？

我們先來(lái)見到了解一下什么是 NP 問題。在這里，它是所有決策問題的集合，對(duì)于這些問題的答案如果是「是」，則有 2/3 的概率被接收，反之則最多是 1/3。正如復(fù)雜性理論中通常所做的那樣，2/3 和 1/3 只是慣例，可以用放大（例如）替換為 1-2 ? ? 和 2 ? ? 。

好吧，量子領(lǐng)域的相關(guān)知識(shí)著實(shí)令人頭疼。就好比說(shuō)在經(jīng)典復(fù)雜性理論里，有一個(gè)常識(shí)：只要多跑幾次驗(yàn)證，就能把出錯(cuò)概率降到很小很小。本來(lái)有 90% 把握，現(xiàn)在重復(fù)一百次取多數(shù)票，就能讓把握接近 100%，這就叫放大（amplification）。

在量子世界里也類似，QMA 協(xié)議也能通過放大來(lái)提高「完整性」（正確證明被接受的概率）和降低「健壯性」（錯(cuò)誤證明蒙混過關(guān)的概率）。 今年六月，F(xiàn)reek Witteveen 和博客的老朋友 Stacey Jeffery 就已經(jīng)證明過：完整性可以被放大到雙指數(shù)級(jí)接近 1。聽起來(lái)很瘋狂——比指數(shù)級(jí)還狠。

圖示：對(duì)或然黑盒進(jìn)行訪問以決定θ ≤ π/3（是實(shí)例）或θ ≥ 2π/3（否實(shí)例）。

Scott 表示，在四分之一個(gè)世紀(jì)后仍能以一種從未想過的方法做到了這一點(diǎn)（其中接受的概率是通過量子態(tài)的幅度在幾何級(jí)數(shù)中減小來(lái)編碼），著實(shí)令他驚喜。不過，在此基礎(chǔ)上是否可以更進(jìn)一步？比如真的做到「100% 接受正確證明」？

但回答卻是：不能，至少黑箱方法到此為止了。

使用黑匣子技術(shù)，雙倍指數(shù)小完整性誤差是能做的最好的事情。換句話說(shuō)：Scott 表明，當(dāng)人們將他的 2008 年 QMA ≠(QMA 1) 量子預(yù)言機(jī)分離定量化時(shí)，人們會(huì)得到一個(gè)與 Freek 和 Stacey 的協(xié)議完全匹配的下限。

就在這里，AI 出手了

寫到這里，其實(shí)作者完全可以憑借自己與同伴完成這份工作（當(dāng)然他也是這么認(rèn)為的），但他還是嘗試把其中的關(guān)鍵技術(shù)步驟交給人工智能——GPT-5。

五分鐘之后，AI 給出了一堆看上去是對(duì)的但實(shí)際上邏輯根本不通的東西。不過好在作者知道哪里需要改進(jìn)哪里需要糾錯(cuò)，就在這么半小時(shí)之后，AI 給出了一條建議：

關(guān)于這些，Scott 調(diào)侃道：目前，它可能還無(wú)法撰寫整篇研究論文（至少如果你希望它正確且出色的話），但它可以幫助你擺脫困境。誰(shuí)知道這種狀態(tài)會(huì)持續(xù)多久呢？他想他應(yīng)該感激自己擁有終身教職。

一些愉快的小討論

技術(shù)上，作者們給出了定量版本的分離結(jié)果，把自己 2008 年的工作延伸到了今天。雖然這還不是解決「QMA 是否等于 QMA 1」的最終答案，但至少說(shuō)明了某條路已經(jīng)走到盡頭。

他們留下的核心未解問題是，在部分或者所有有限門控集的影響下，QMA 是否可以等于 QMA 1。

另一個(gè)較小的問題開放性問題是，在算子分離中，是否可以取角度 θ 為一個(gè)固定的值，比如 θ = π，在無(wú)案例中，而不是屬于一個(gè)值域。

猜測(cè)答案是肯定的，但似乎需要一個(gè)新的論據(jù)。

作者博客：https://scottaaronson.blog/?p=9183

相關(guān)鏈接：https://x.com/kimmonismus/status/1972399015825203463