選自Quanta Magzine
機器之心編譯
參與：Panda、蛋醬
計算機科學、數學、物理學，這三個學科各自的一些重大難題在近日發佈的一篇標題簡潔的論文《MIP*=RE》中同時得到了解答。在該論文中，五位計算機科學家為可通過計算方式驗證的知識確立了一個新的邊界。基於此，他們又為量子物理學和純數學領域仍未得到解決的重大難題帶去了答案。
這篇長達 165 頁的論文所揭示的研究成果，一經發布，就在學界引發了廣泛的關注，《Nature》雜誌也對此進行了介紹。原論文可訪問：https://arxiv.org/abs/2001.04383。
本文編譯自 Quanta Magazine，以下內容是對該證明的詳細解讀：
故事要從 80 多年前說起。1935 年，阿爾伯特·愛因斯坦與鮑里斯·波多爾斯基（Boris Podolsky）和納森·羅森（Nathan Rosen）合作揭示了一種可能性：即使距離很遠，兩個粒子也可以發生糾纏或關聯。
就在接下來的一年裡，阿蘭·圖靈（Alan Turing）提出了第一個通用計算理論，他證明了一件事：存在計算機永遠無法解決的問題。
這兩個想法都為各自的學科領域帶來了革命，而且它們看起來似乎並不相關。
但現在，一個具有里程碑意義的證明出現了，它將這兩種想法聯繫在了一起，同時解決了計算機科學、物理學和數學領域許多尚未解決的問題。
這個新證明就是：理論上，使用糾纏態量子比特（qubit）而非經典的 1 和 0 進行計算的量子計算機可用於驗證非常多的問題的答案。糾纏與計算之間的這種對應關係震驚了許多研究者。
這個證明的作者們原本是想確定一種用於驗證計算問題的答案的方法侷限性，這種方法涉及糾纏。找到那個侷限性之後，順帶解決了另外兩個問題：物理學中的 Tsirelson 問題（關於如何用數學建模糾纏）以及純數學領域的一個相關問題（科納嵌入猜想）。
最終，這些結果像多米諾骨牌一樣級聯到了一起。
「這些思想都是同一時間出現的。它們能以如此戲劇性的方式再次聚首，真是很不錯。」該證明的作者之一多倫多大學的 Henry Yuen 說。此外，該證明的作者還有悉尼科技大學的季錚鋒（Zhengfeng Ji）、加州理工學院的 Anand Natarajan 和 Thomas Vidick 以及德克薩斯州大學奧斯汀分校的 John Wright。這五位研究者都是計算機科學家。
不可定的問題
在計算機誕生之前，圖靈就已經為計算方面的思考定義了一個基本框架。幾乎在同時，他也表明始終存在某些計算機無法解決的特定問題。這就是常說的「圖靈停機問題」。
經典設計中，計算機程序可以接收輸入併產生輸出。但有時候，程序會進入無限的循環之中，不停地重複工作。如果你遇到了這種情況，那隻能手動終止這個程序。
圖靈證明了，並不存在一個通用算法，可以確定一個計算機程序將停止還是永遠運行。答案必須在運行這個程序後才能知道。
計算機科學家 Henry Yuen、Thomas Vidick、Zhengfeng Ji、Anand Natarajan 和 John Wright 合作證明了一個驗證計算問題的答案的問題，卻最終為數學和量子物理學領域的重大問題提供瞭解答。
「如果你已經等待了 100 萬年而一個程序還未停止，你需要等待 200 萬年嗎？沒辦法知道答案。」滑鐵盧大學數學家 William Slofstra 說。
用技術術語來說，圖靈證明這個停止問題是不可定的（undecidable）——甚至可想象的最強大的計算機也無力解決。
圖靈之後，計算機科學家開始根據難度來對其它問題進行分類。要解決更難的問題，所需的計算資源也更多，也就是說需要更多運行時間、更多內存。這些屬於計算複雜性問題。
最終而言，每個問題的求解都涉及到兩個重大問題：「這個問題的解決難度有多大？」和「驗證答案正確的難度有多大？」
審問式驗證
當問題相對簡單時，判斷答案正確與否也很簡單。但問題變得更加複雜時，就很難直接判斷了。但就算無法確認，你也能知道答案到底對不對。
此處就要提到「審問式驗證」了。這個方法跟警察審問的邏輯差不多：
如果一個嫌犯講的故事是精心編造的，那你可能沒辦法去驗證每一處細節。但只需要針對這個故事提出一些問題，你就可以知道嫌犯是在說謊，還是在如實陳述。
套用到計算機科學術語上說，「審問」的雙方分別是一臺強大的計算機和一臺更弱的計算機。其中強大的計算機（證明者）給出了一個解，較弱的計算機（驗證者）則希望通過提問來確定該解是否正確。
舉個簡單的例子，假設你是一個色盲，另一個人（證明者）稱兩顆彈珠顏色不同。你要怎麼驗證他說的是不是真的呢？
你可以把這兩顆彈珠拿到身後混在一起，再拿出來讓證明者區分它們。如果它們顏色真的不同，那麼證明者應該每一次都能給出正確的答案。如果這兩顆彈珠實際上顏色一樣，那麼證明者有一半的可能會猜錯（就算超過半數的時間能說對，那也能肯定顏色不一樣了）。
這種方法還可以驗證大量不同類別問題的解。以此推之，當兩個證明者針對同一個問題都給出解時，驗證速度會變得更快。
就比如，你要審問的嫌犯如果有兩個，解決一個犯罪案件就會更加輕鬆，因為你可以交叉檢驗他們的答案。如果這些嫌犯講的是實話，那麼他們所說的大多都對得上。如果他們在說謊，那麼更多時候會出現互相矛盾的答案。
計算複雜性可能看起來完全是理論方面的問題，但其實也與真實世界聯繫很緊密。在求解和驗證問題的過程中，計算機需要時間和內存資源，本質上這是物理問題。
因此物理學領域的新發現會影響到計算複雜性。Natarajan 說：「如果你選擇了量子物理學而不是經典物理學，那麼你會得到不同的複雜性理論。」
這是 21 世紀的計算機科學家們，面對 20 世紀物理學中最古怪的糾纏思想，得到的最終結果。
突破口：科納嵌入猜想
當兩個粒子互相糾纏時，實際上並不會互相影響——它們之間不存在因果關係。愛因斯坦與其合作者在 1935 年的論文中闡述了這一思想。在那之後，物理學家和數學家都在努力想要通過數學的方式來描述糾纏的真正含義。
但是努力的結果卻有點混亂，科學家們為糾纏構想出了兩個不同的數學模型——而且之前並不清楚它們是否等效。
這種潛在的不和諧，最終給純數學領域帶來了一個重要問題，即科納嵌入猜想。最終，這成為了這五位計算機科學家新證明中的突破口。
第一種建模糾纏的方法將粒子視為在空間上是互相隔離的，比如一個在地球上，一個在火星上；妨礙兩者之間因果關係的是它們之間的距離。這被稱為張量積模型，但在某些情況下，兩個事物在因果關係上是否相互獨立卻並不非常明顯。
因此，數學家想出了另一種更通用的描述因果獨立性的方法。
當執行兩個運算的順序不影響結果時，則這兩個運算滿足交換律：3×2 和 2×3 是一樣的。在第二種模型中，只要粒子的屬性互相關聯，則這些粒子便是互相糾纏的，但你執行觀測的順序無關緊要：觀測粒子 A 來預測粒子 B 的動量或反過來，不管選用哪種順序，得到的答案都一樣。這被稱為交換算子式糾纏模型。
這兩種對糾纏的描述都要用到按行列形式組織的數字陣列，即矩陣。第一種張量積模型使用了行數和列數有限的矩陣，第二種交換算子模型使用一個更通用的對象，其工作方式就像是一個行數和列數無限的矩陣。
隨著時間的推移，數學家開始以研究這些矩陣為目標，完全與物理學世界脫離了聯繫。除了這項研究之外，數學家 Alain Connes 在 1976 年提出了一個猜想：有可能使用有限維矩陣來近似很多無限維矩陣。這是科納嵌入猜想暗含的結果之一。
下一個十年，物理學家 Boris Tsirelson 提出了該問題的一個版本，再次將這個問題納入了物理學研究中。Tsirelson 猜想張量積糾纏模型和交換算子式糾纏模型是大致等價的。這當然是合理的，因為是對同一物理現象的兩種不同的理論描述。後續的研究表明，由於矩陣以及使用這些矩陣的物理模型之間所存在的關聯性，科納嵌入猜想與 Tsirelson 問題實際上是互相暗含的。解決了其中一個，你也就解決了另一個。
然而，這兩個問題的解最終都源自另外一個完全不一樣的位置。
博弈所體現的物理學
1960 年代，物理學家約翰·貝爾（John Bell）提出了一種測試方法，可以確定糾纏究竟是真實的物理現象或只是一個理論概念。這種測試涉及到一種博弈，其結果可說明是否存在某種不同尋常的非量子物理學的東西。
後來，計算機科學家又意識到，這種測試糾纏的方法也可用於驗證非常複雜的問題的答案。
為了瞭解這種博弈的工作方式，我們先假設有兩個玩家 Alice 和 Bob 以及一個 3×3 的網格。裁判為 Alice 分配了一行，並告訴她在每個空格中輸入一個 0 和 1，並使得數字之和為一個奇數。Bob 則得到一列，他的填充方式要使得該列之和為一個偶數。如果他們在列與行的重疊區放的數字一樣，則他們就獲勝。同時不允許他們互相交流。
在經典設置中，他們的最佳表現為 89% 的勝率。但在量子設置中，他們可以做得更好。
假設為 Alice 和 Bob 分配了一對互相糾纏的粒子。他們觀測各自的粒子，然後使用觀測結果來引導每個格子的數字填充。由於這些粒子互相糾纏，所以他們的觀測結果是互相關聯的，也就意味著他們填入的答案是互相關聯的——進一步意味著他們的勝率可達 100%。
圖片來自：Lucy Reading-Ikkanda/Quanta Magazine
所以如果兩個玩家獲勝的概率高出預期，可以得出結論：他們使用了某種超出經典物理學之外的東西。這樣的貝爾式實驗現在被稱為「非局部博弈（nonlocal game）」，因為玩家之間是分開的。
物理學家在實驗室中真正地執行了這樣的實驗。Yuen 說：「多年來做實驗的人已經表明這樣這種鬼魅般的事情確實存在。」
在分析任何博弈時，你可能都想知道玩家如果竭盡全力地玩，在一場非局部博弈中的勝率是多少。但在 2016 年時，William Slofstra 證明不存在用於計算所有非局部博弈的確切最大勝率的通用算法。
所以研究者就想：能不能至少做到近似求取最大獲勝百分比？
使用兩個描述糾纏的模型，計算機科學家鎖定了答案。在近似所有非局部博弈的最大勝率時，使用張量積模型的算法可確立一個下限，即最小值。另一個使用交換算子模型的算法可確立一個上限。
運行這些算法的時間越長，得到的答案就會越精準。如果 Tsirelson 的預測是對的，這兩個模型確實等價，那麼這個上限與下限之間應當相距很近，最終收縮為單個值，這個值就是近似得到的最大勝率。
但如果 Tsirelon 的預測不對，那麼這兩個模型就不等價。Yuen 說：「那麼上限和下限就一直相隔很遠。」那麼也就沒有辦法計算非局部博弈的近似最大勝率了。
這五位研究者在他們的新研究中使用了這一問題：上限和下限能否收斂以及 Tsirelson 問題是否為真？目的是解決另一個問題：是否有可能驗證一個計算問題的答案。
糾纏所提供的幫助
2000 年代早期，計算機科學家開始思考：如果審問兩個共享了糾纏粒子對的證明者，可驗證問題的範圍又將如何變化？
大多數人都猜想糾纏不利於驗證。畢竟如果兩個嫌犯之間存在某種串通答案的方式，那麼他們就更容易編造出一致連貫的供詞。
但最近幾年，計算機科學家已經意識到事實恰恰相反。通過審問共享了糾纏粒子的證明者，可驗證問題的範圍比沒有糾纏時更廣。
Vidick 說：「糾纏可以產生關聯，你可能認為這能幫助他們說謊或欺騙，但事實上你能把它變成自己的優勢。」
怎麼會這樣？要理解這一點，你首先需要了解你可以通過這個交互式流程驗證的大量問題。
假設有一個圖，由一組點（頂點）和連接這些點的線（邊）構成，能否使用三種顏色給其中的頂點塗色，使得任何一條邊所連接的兩個頂點的顏色都不一樣？如果可以，那麼這個圖就是「三色可分的（three-colorable）」。
如果你交給一對糾纏的證明者一張非常大的圖，而他們報告說這張圖是三色可分的，那麼你會疑問：是否存在驗證他們答案的方法？
如果圖非常大，那麼直接檢查結果是不可行的。但是，你可以向每個證明者提問，讓他們告訴你兩個相連頂點中分別一個頂點的顏色。如果他們報告的顏色不一致，而且每次提問的結果都是如此，那麼你就能越來越相信這種三色塗色方案是可行的。
但當圖非常大時，這樣的審問策略也會失效，比如當邊和頂點的數量超過宇宙的原子數量時。甚至稱述一個具體問題（「告訴我 XYZ 頂點的顏色」）的任務就超出你這個驗證者的能力範圍，因為用於命名各個頂點所需的數據量超過了你工作內存所能容納的極限。
但糾纏可以讓證明者自己想需要提出的問題。Wright 說：「驗證者不必去計算問題。驗證者可以迫使證明者為其計算問題。」
驗證者想要證明者報告相連頂點的顏色。如果這些頂點不是相連的，那麼這些問題的答案與該圖是否三色可分無關。換句話說，驗證者想要證明者給出的問題是相關的。一個證明者問的是有關頂點 ABC 的情況，另一個證明者則問的是有關頂點 XYZ 的情況。希望是這兩個頂點是相連的，不過這兩個證明者都不知道彼此想的是哪個頂點。（就像 Alice 和 Bob 都希望在同一個方格中填入同樣的數字，即便他們都不知道對方被要求填哪一列或行。）
如果兩個證明者完全靠自己想出了這些問題，那麼就不可能迫使他們選擇相連或相關的頂點，也就沒法讓驗證者驗證他們的答案。
但糾纏能提供這樣的相關性。我們幾乎可以把所有任務都交給證明者，讓它們自行選擇問題。
到該流程結束時，每個證明者都報告一種顏色。驗證者檢查它們是否一樣。如果這個圖是真正三色可分的，那麼證明者永遠不應報告同一種顏色。
Yuen 說：「如果存在三種顏色，證明者可以說服你只有一種。」
事實證明，這個驗證流程不過是非局部博弈的又一案例而已。如果證明者能說服你相信他們的解是正確的，那麼該證明者便「獲勝」。
2012 年，Vidick 和 Tsuyoshi Ito 證明，有可能使用糾纏的證明者來執行種類廣泛的非局部博弈，以驗證問題的答案，而且這些問題的數量至少與可通過審問兩臺經典計算機驗證答案的問題數量一樣多。也就是說，使用糾纏的證明器與驗證不衝突。去年，Natarajan 和 Wright 證明：與糾纏的證明者交互實際上可以擴展可以驗證的問題的類別。
但那時計算機科學家尚不清楚可用這種方式驗證的所有問題類別。
而現在，情況發生了變化。
一連串的成果
這五位計算機科學家在他們的新論文中證明，通過審問糾纏的證明者，可以驗證無法求解的問題的答案，包括停機問題。
Yuen 說：「這種模型的驗證能力真的是超出了想象。」
但停機問題是無法解決的。事實上，正是這種新提出的思想，有望為這一斷言帶來最終證明。
設想你將一個程序提供給了一對糾纏的證明者，想要它們告訴你這個程序是否會停止。你已經準備好通過一種非局部博弈來驗證它們的答案：這些證明者會生成問題，然後會根據這些問題的答案的協調性來「獲勝」。
如果該程序事實上會停止，則證明器的勝率應為 100%——類似於一個圖確實三色可分的情況，糾纏的證明者不應該報告兩個相連的節點的顏色一樣。如果該程序不會停止，則證明者只能靠運氣獲勝——勝率為 50%。
這意味著如果某人要求你確定這個非局部博弈問題的一個具體實例的近似最大勝率，你首先需要解決這個停機問題。而解決這個停機問題是不可能的。這意味著為非局部博弈計算近似最大勝率的問題是不可定的，就像停機問題一樣。
這又進一步意味著 Tsirelson 問題的答案是「否」——這兩個糾纏模型並不等價。因為如果它們是等價的，那麼你可以把上限和下限壓到一起，計算得到一個近似最大勝率。
馬德里康普頓斯大學的 David Pérez-García 說：「不可能存在這樣一個算法，所以這兩個模型必定不同。」
這篇新論文證明：通過與糾纏的量子證明者交互所能驗證的問題類別（稱為 MIP* 類別）其實就等於不難於停機問題的問題類別（稱為 RE 類別）。該論文的標題就簡潔明瞭地說明了這一點：「MIP* = RE」
在證明這兩個複雜性類別相等的過程中，計算機科學家證明 Tsirelson 問題為假，而且由於之前的研究工作，也意味著科納嵌入猜想也為假。
對於這些領域的研究者而言，回答這些大問題的答案竟然來自於計算機科學領域一個看似不相關的證明，這著實讓人驚訝。
「如果我看到一篇論文說 MIP* = RE，我認為這和我的研究沒關係。」之前嘗試證明 Tsirelson 問題和科納嵌入猜想的研究者之一 Navascués 說，「對我來說，這完全就是一個驚喜。」
量子物理學家和數學家剛開始消化吸收這個證明。在這個新研究成果之前，數學家已經在思考能否用大型的有限維度矩陣來近似無限維度的矩陣。現在，由於科納嵌入猜想為假，他們知道這無法做到了。
Slofstra 說：「他們的結果表明這是不可能的。」
這些計算機科學家並沒有以回答科納嵌入猜想為目標，因此，他們並不是解釋他們最終解決的一個問題的最佳人選。
Natarajan 說：「我個人並不是一個數學家，我不是非常理解科納嵌入猜想的原始形式。」
他與其合作者預測數學家將會把這個新結果轉化成數學領域的語言。
在宣佈這個證明的一篇博客文章中，Vidick 寫道：「我懷疑最終不需要複雜性理論來獲得純數學的結果。」
然而，現在研究者可以使用這個證明了，探究之路就可以到此為止了。
在超過 30 年的時間裡，計算機科學家一直想搞清楚交互式驗證能讓他們前進多遠。現在，以一篇標題簡單的長論文，他們給出了答案，也映照了圖靈的思想。
「過去長時間的研究都想要知道使用兩個糾纏的量子證明者的驗證流程有多強大，」Natarajan 說，「現在我們知道它有多強大了。故事也就到此為止。」
參考鏈接：
https://www.quantamagazine.org/landmark-computer-science-proof-cascades-through-physics-and-math-20200304/
https://www.nature.com/articles/d41586-020-00120-6
閱讀更多 機器之心Pro 的文章
