本文參加百家號 #科學了不起# 系列徵文賽。
計算機科學中的一項新證明對量子力學和純數學的研究人員也有意義1935年，阿爾伯特·愛因斯坦與鮑裡斯·波多爾斯基和內森·羅森合作，試圖解決量子物理學新定律揭示的一種可能性：兩個粒子可以相互糾纏，或相互關聯，甚至跨越遙遠的距離。就在第二年，艾倫·圖靈提出了第一個計算通論，並證明了存在一個計算機永遠無法解決的問題。
這兩種思想革新了各自的學科。他們之間似乎也沒有任何關係。但現在，一個裡程碑式的證明將它們結合在一起，解決了計算機科學、物理和數學領域的一系列開放問題。
新的證明建立了量子計算機，通過糾纏量子比特或量子位來計算，而不是經典的1和0，理論上可以用來驗證大量問題的答案。糾纏和計算之間的對應關係讓許多研究人員感到震驚。
「這完全是一個驚喜，」維也納量子光學和量子信息研究所研究量子物理學的米格爾·納瓦斯克說。該證明的共同作者開始確定一種驗證計算問題答案的方法的極限。這種方法涉及到糾纏。通過發現這個極限，研究人員最終解決了另外兩個幾乎是「副產品」的問題：Tsirelson的物理問題，關於如何建立數學模型的糾纏，以及一個與之相關的純數學問題，叫做康乃狄克州嵌入猜想。
最後，結果就像多米諾骨牌一樣連鎖反應了。
不可判定的問題
在計算機真正出現之前，圖靈定義了一個計算的基本框架。與此同時，他還指出了一個計算機無法解決的問題。它與一個程序是否停止有關。
通常，電腦程式接收輸入並產生輸出。但有時他們會陷入無限的循環中。當這種情況發生在家裡時，就只剩下一件事要做了。手動關閉程序。把它剪了吧。」袁說
圖靈證明了沒有通用的算法可以決定一個電腦程式是停止還是永遠運行。必須運行程序才能找到答案。
計算機科學家最終解決了數學和量子物理中的主要問題。從技術上講，圖靈證明了這個停機問題是無法確定的——即使是最強大的計算機也無法解決它。圖靈之後，計算機科學家開始根據其他問題的難度來分類。更難的問題需要更多的計算資源來解決——更多的運行時間，更多的內存。這是計算複雜度的研究。最終，每個問題都會引出兩個大問題:「解決起來有多難?」以及「驗證答案是否正確有多難?」
當問題相對簡單時，你可以自己檢查答案。但當問題變得更複雜時，即使是檢查答案也可能是一項艱巨的任務。然而，在1985年，計算機科學家們意識到，即使你自己不能確認一個答案是否正確，也可以培養信心。
該方法遵循警方訊問的邏輯。
如果一個嫌疑犯講了一個精心設計的故事，也許你不能到外面去證實每一個細節。但是通過問正確的問題，你可以在謊言中抓住漏洞，或者建立起故事被證實的信心。
在計算機科學術語中，審訊中的雙方是一臺強大的計算機，它為一個問題提出一個解決方案和一臺不太強大的計算機，它想向驗證者提問，以確定答案是否正確。這第二臺計算機稱為驗證器。
舉個簡單的例子，假設你是色盲，而另一個人——證明者——聲稱兩顆彈珠是不同的顏色。你不能自己去核實這個說法，但通過巧妙的詢問，你仍然可以確定它是否正確。
然後讓驗證者告訴你哪個是哪個。如果它們真的是不同的顏色，驗證者每次都應該正確地回答這個問題。如果彈珠實際上是同一種顏色，也就是說它們看起來是一樣的，驗證者有一半的機率猜錯。通過提出驗證性問題，您可以驗證比您自己更廣泛的問題的解決方案。
1988年，計算機科學家們考慮了兩個驗證者對同一個問題提出解決方案時會發生什麼。畢竟，如果你有兩個嫌疑人要審問，那麼破案或驗證解決方案就更容易了，因為你可以讓他們互相競爭。
「這給了驗證者更多的籌碼。你相關的問題，反覆核對答案。」如果嫌疑人說的是真話，他們的反應大部分時間應該一致。如果他們在撒謊，答案會更經常地發生衝突。
類似地，研究人員表明，通過分別詢問兩個驗證者關於他們的答案，你可以很快地驗證一個更大的問題的解決方案，這比你只有一個驗證者要問的問題要大得多。
計算複雜性似乎完全是理論上的，但它也與現實世界緊密相連。計算機解決和驗證問題所需的資源——時間和內存——基本上是物理的。因此，物理學的新發現可以改變計算複雜度。
如果你選擇一套不同的物理，比如量子而不是經典，你就會得到一個不同的複雜性理論。新的證明是21世紀計算機科學家面對20世紀物理學中最奇怪的概念之一：糾纏的最終結果。
連接嵌入猜想
當兩個粒子糾纏在一起時，它們實際上並不相互影響——它們之間沒有因果關係。愛因斯坦和他的合著者在1935年的論文中詳細闡述了這一觀點。之後，物理學家和數學家試圖用數學方法來描述糾纏的真正含義。
然而，結果卻有點混亂。科學家們提出了兩種不同的糾纏數學模型，但並不清楚它們是否相等。
以一種迂迴的方式，這種潛在的不協調最終產生了一個重要的純數學問題，叫做「內嵌猜想」。最終，它也成為了五個計算機科學家在他們的新證據中利用的漏洞。
第一種建模纏結的方法是把粒子看作是在空間上彼此隔離的。一個在地球上，另一個在火星上，他們之間的距離阻礙了因果關係。這叫做張量積模型。
但在某些情況下，當兩種物質因果分離時，就不那麼明顯了。所以數學家們想出了第二種，更一般的方法來描述因果獨立。
當您執行兩個操作的順序不影響結果時，操作「交換」:3×2與2×3相同。在第二個模型中，當粒子的屬性相互關聯，但測量的順序並不重要時，粒子就會被糾纏：測量粒子A來預測粒子B的動量，反之亦然。不管怎樣，你得到的答案都是一樣的。這被稱為糾纏的交換算子模型。
這兩種對糾纏的描述都使用了被稱為矩陣的行和列組成的數字數組。張量積模型使用具有有限行數和列數的矩陣。交換運算符模型使用一個更一般的對象，它的功能類似於具有無限行和列的矩陣。
隨著時間的推移，數學家們開始把這些矩陣作為他們自己感興趣的對象來研究，完全與物理世界無關。作為這項工作的一部分，一位名叫阿蘭·康尼斯的數學家在1976年推測，用有限維矩陣來近似許多無限維矩陣是可能的。這是嵌入推測的一個推論。
在接下來的十年裡，一位名叫鮑裡斯·齊瑞森的物理學家提出了這個問題的另一個版本，再次將其建立在物理學的基礎上。Tsirelson推測，張量積和交換算符的糾纏態模型大致相等。這是有道理的，因為從理論上講，它們是描述同一物理現象的兩種不同方式。
然而，這兩個問題的解決方案最終完全來自第三位。
20世紀60年代，一位名叫約翰·貝爾的物理學家提出了一項測試，以確定糾纏態是否是一種真實的物理現象，而不僅僅是一種理論概念。測試涉及一種遊戲，其結果揭示了是否有比普通的非量子物理更重要的東西在起作用。
計算機科學家後來意識到，這種關於糾纏的測試也可以用來驗證非常複雜問題的答案。
但是首先，為了了解遊戲是如何工作的，讓我們想像兩個玩家，愛麗絲和鮑勃，和一個3×3的網格。裁判給愛麗絲分配一行，並告訴她在每個方框中輸入0或1，以便數字和為奇數。鮑勃得到一列，必須把它填滿，這樣它的和就是偶數。如果他們把相同的數字放在她的行和他的列重疊的地方，他們就贏了。他們不允許交流。
在正常情況下，他們最多能贏得89%的機會。但在量子環境下，它們可以做得更好。
想像一下，愛麗絲和鮑勃分開了一對糾纏的粒子。他們對各自的粒子進行測量，並使用結果來決定在每個方框中寫1還是0。因為這些粒子被纏結在一起，它們的測量結果將會相互關聯，這意味著它們的答案也會相互關聯——這意味著它們可以100%地贏得比賽。
因此，如果你看到兩個玩家以出乎意料的高概率贏得遊戲，你就可以得出結論，他們利用的不是經典物理學的優勢。這種鍾型實驗現在被稱為「非局部」遊戲，指的是玩家之間的分離。物理學家實際上是在實驗室裡進行的。
在分析任何遊戲時，你可能想要知道玩家在非本地遊戲中獲勝的頻率，前提是他們盡其所能。例如，使用單人紙牌遊戲，你可以計算出一個玩得很好的人獲勝的機率。
但在2016年，威廉·斯洛夫斯特拉證明，沒有通用的算法來計算所有非本地遊戲的準確最大獲勝概率。因此，研究人員想知道，你能接近最大勝率嗎？
計算機科學家利用描述糾纏態的兩個模型找到了答案。一個使用張量積模型的算法在所有非局部博弈的近似最大獲勝概率上建立一個下限或最小值。另一種算法使用交換運算符模型，建立一個上限。
這些算法運行時間越長，得到的答案就越精確。如果Tsirelson的預測是正確的，而且這兩個模型確實是等價的，那麼下限和上限就應該不斷地擠壓在一起，縮小到一個單一的數值上，以獲得近似的最大勝率。
但如果Tsirelson的預測是錯誤的，而且這兩個模型並不等價，「天花板和地板將永遠是分開的。在他們的新工作中，五名研究人員使用這個問題——關於天花板和地板是否收斂，Tsirelson的問題是對的還是錯的——來解決一個單獨的問題，即什麼時候可以驗證一個計算問題的答案。
糾纏的援助
在21世紀初，計算機科學家們開始思考：如果你詢問兩個共享糾纏粒子的驗證者，它如何改變你可以驗證的問題範圍？大多數人認為，糾纏是不利於驗證的。畢竟，如果兩名嫌疑人有某種方法來協調他們的答案，他們就更容易說出一個連貫的謊言。
但在過去的幾年裡，計算機科學家們意識到事實正好相反:通過詢問共享糾纏粒子的驗證者，你可以驗證比沒有糾纏時更大範圍的問題。「糾纏是一種產生關聯的方式，你認為這種關聯可能有助於他們撒謊或欺騙，」維迪克說。「但事實上，你可以利用這一點。」
要了解如何解決這些問題，您首先需要掌握這些問題的幾乎超凡脫俗的規模，您可以通過這個交互過程驗證這些問題的解決方案。想像一個圖形——一個由線(邊)連接的點(頂點)的集合。你可能想知道是否可以用三種顏色來給頂點上色，這樣通過邊連接的頂點就不會有相同的顏色。如果可以，這個圖是「三色的」。
如果你給一對糾纏的驗證者一個非常大的圖形，他們報告說它可以是三色的，你會想:有辦法驗證他們的答案嗎?
對於非常大的圖形，不可能直接檢查工作。相反，你可以讓每個驗證者告訴你兩個相連頂點中的一個的顏色。如果他們每個人報告的顏色都不一樣，而且每次你問他們的時候他們都是這麼做的，你就會相信三種顏色真的有用。
但是，當圖形變得非常大時，即使是這種詢問策略也會失敗——圖上的邊和頂點比宇宙中原子的數量還多。即使是陳述一個特定問題的任務(「告訴我XYZ頂點的顏色」)也超出了你這個驗證者的能力:命名一個特定頂點所需的數據量超出了你的工作記憶。
但是糾纏使證明者自己提出問題成為可能驗證者不需要計算問題。驗證者迫使驗證者為他們計算問題。驗證者希望驗證者報告連接頂點的顏色。如果頂點沒有連接，那麼問題的答案將不會說明圖是否有三種顏色。
換句話說，驗證者希望驗證者問相關的問題:一個驗證者問關於頂點ABC，另一個驗證者問關於頂點XYZ。希望這兩個頂點是相互連接的，即使驗證者不知道另一個在考慮哪個頂點。(就像愛麗絲和鮑勃希望在同一個正方形中填入相同的數字一樣，儘管他們都不知道對方被問到的是哪一行或哪一列。)
這些想法都來自同一時間。他們以這種戲劇性的方式重新走到一起，這很奇妙。如果兩個驗證者完全獨立地提出這些問題，那麼就沒有辦法強迫他們選擇連接的或相關的頂點，從而允許驗證者驗證他們的答案。但這種相關性正是纏結所能實現的。
「我們將使用『糾纏』來把幾乎所有的東西都轉移到『證明者』身上。我們讓他們自己選擇問題。」在這個過程的最後，驗證者報告一個顏色。驗證者檢查它們是否相同。如果圖表真的是三色的，驗證者不應該報告相同的顏色。
事實證明，這個驗證過程是另一個非本地遊戲的例子。如果他們讓你相信他們的解決方案是正確的，他們就「贏了」。
在2012年，Vidick和Tsuyoshi Ito證明了使用糾纏驗證器來驗證至少相同數量問題的答案是可能的，你可以通過詢問兩臺經典計算機來驗證。也就是說，使用糾纏的驗證器並不會妨礙驗證。去年，Natarajan和Wright證明了與糾纏的驗證者交互實際上擴展了可以驗證的問題的類別。但是計算機科學家並不知道可以用這種方法驗證的所有問題。直到現在。
一連串的後果
在他們的新論文中，五名計算機科學家證明，通過詢問糾纏驗證器，可以驗證無法解決的問題的答案，包括停機問題。但停機問題是無法解決的。而這一事實正是最終證明的火花。
想像你把一個程序交給一對糾纏不清的驗證者。你讓他們告訴你它是否會停止。您準備通過一種非本地的遊戲來驗證他們的答案:驗證者生成問題並基於他們的答案之間的協調來「贏」。
如果程序實際上停止了，驗證者應該能夠在100%的時間內贏得這個遊戲——類似於如果一個圖形實際上是三色的，糾纏的驗證者不應該報告兩個連接的頂點的相同顏色。如果它不停止，驗證者應該只在50%的情況下偶然獲勝。
這意味著，如果有人要求您為這個非本地遊戲的特定實例確定近似的最大獲勝概率，您首先需要解決停機問題。而解決停機問題是不可能的。這意味著計算非本地遊戲的近似最大獲勝概率是不可決定的，就像暫停問題一樣。
這就意味著Tsirelson的問題的答案是否定的——這兩種糾纏模型是不相等的。因為如果它們是，你可以同時捏住地板和天花板來計算一個近似的最大獲勝概率。
馬德裡孔普盧騰斯大學的戴維佩雷斯-加西亞表示:「不可能有這樣一個算法，因此這兩個(模型)必須不同。」
新論文證明了類的問題可以通過與糾纏的量子相互作用來驗證驗證,一個類稱為MIP *,正好等於類的問題沒有比停止的問題,一個類稱為再保險。論文的標題簡潔地陳述它:「MIP * =再保險」。
在證明這兩個複雜度等級相等的過程中，計算機科學家證明了Tsirelson的問題是錯誤的，由於之前的工作，這意味著Connes嵌入猜想也是錯誤的。
對於這些領域的研究人員來說，這些大問題的答案竟然來自於計算機科學中一個看似毫不相關的證明，這令人震驚。
量子物理學家和數學家才剛剛開始消化這個證明。在這項新工作之前，數學家們想知道他們是否可以用大的有限維矩陣來代替無限維矩陣的近似。現在，因為嵌入推測是假的，他們知道他們不能。
計算機科學家本身並沒有打算回答Connes embedded猜想，因此，他們並不能很好地解釋他們最終解決的一個問題的含義。
他和他的合著者預計數學家們將把這個新結果翻譯成他們自己領域的語言。在一篇宣布證明的博文中，維迪克寫道:我不懷疑最終將不需要複雜性理論來獲得純粹的數學結果。
然而，就在其他研究人員拿著證據進行研究的時候，導致這一研究停滯不前。三十多年來，計算機科學家們一直在試圖弄清楚交互驗證能讓他們走多遠。他們現在面對的是答案，是一篇很長的論文，標題很簡單，圖靈的回音。