你進入一個洞穴，在黑暗的走廊的盡頭，你會遇到一對密封的密室。每個密室內都有一個無所不知的神使。預言說，在這些神使的幫助下，你可以學習解決無法解決的問題的答案。但有一個問題：神使並不總是說實話。雖然他們無法相互溝通，但他們對你們問題看似隨機的回答，實際上是由宇宙的結構聯繫在一起的。要得到你所尋求的答案，你必須首先設計……問題。
計算機科學家正在忙著新的數學證明量子糾纏系統有點像上面的描述。它似乎反駁了一個44前的猜想，並詳細說明了一個理論機器能夠解決著名的停頓問題，即計算機無法確定它是否能解決它目前正在試圖解決的問題。
這份長達150頁的證明，標題為"MIP*=RE"，涉及計算複雜性的深奧主題。如果它通過審查，它證明了量子物理學、計算和數學之間的深刻聯繫。它表明，一個理論類的計算設備——一個驗證者——詢問量子糾纏的神使——可以檢查一些最複雜的計算機問題，這對量子物理學家有著重要的意義。
等號左側是理論計算類 MIP*。自20世紀80年代以來，研究人員分析了一類稱為IP（或稱交互式多息時間）的問題，這是一系列可以通過交互式證據解決的問題。這是一種證明，驗證器（一種常規計算機，基本上通過翻轉硬幣解決問題，即使用位）試圖檢查答案是否正確。為此，它可以向一個無所不知但不一定是誠實的觀察者提問，稱為證明者。
如果您熟悉複雜性類，您可能聽說過 P，這是一類可在多項式時間中解決的問題，這意味著時間量等於引發到常量指數（任意數字）的輸入大小。然後是 NP 問題，這些問題不清楚解決問題需要多長時間，但給定一個潛在的解決方案，只需多息時間來驗證該解決方案。
NP問題的一個著名例子是圖形著色問題：給定一系列由線連接的點（數學家稱之為圖形），如何使用三種顏色來繪製點，這樣兩種顏色不會接觸？20世紀80年代和90年代初的研究人員表明，這些交互式證據可以驗證所有的NP問題，以及一套至少複雜的問題，這些問題可以通過多式內存量來解決。
其他研究人員進一步擴展了可以通過交互式證據解決的 MIP 類問題：如果驗證者能夠向一對無所不知但不一定是誠實的證明者（如一對犯罪嫌疑人）提問，該怎麼辦？分成隔音房？這樣的證明系統可以有效地驗證更棘手的問題，例如驗證所需的時間會隨著輸入的大小呈指數級增長，就像三色圖形呈指數級增長一樣。
現在，研究人員正在探索一種更強大的類，稱為MIP*。在這種情況下，想象一下，同一對無所不知神靈坐在單獨的房間裡，但它們被量子力學的規則糾纏在一起。量子力學是描述亞原子粒子相互作用方式的數學系統，但其數學看起來像一個更復雜的概率版本。糾纏證明說，雖然他們分開，事情可能看起來隨機，當你只與一個證明人交談，實際上兩者之間是相關的。
量子糾纏
因此，回顧一下：MIP是一種假設的證明系統，一個普通的計算機向一對無所不知神使但不一定是誠實的、無法相互通信的"神使"提出問題。這種證明系統可以有效地檢查極其複雜的問題的答案。科學家們現在試圖理解，當MIP擴展到MIP*時，這種證明方法會有多強大——神使仍然無法通信，但它們現在被量子糾纏在一起，所以它們給出的答案比它們本來更相關。
現在加州理工學院的研究員阿南德·納塔拉詹（ Anand Natarajan），曾經聽過計算機科學家斯科特·亞倫森（Scott Aaronson）在MIP*上演講，並意識到人們對這個演講知之甚少。"研究報告的作者之一納塔拉詹（Natarajan）對我們說："在複雜性理論中，這是一種罕見的情況，在那裡，你擁有大量關於真相實際存在的可能性。”麻省理工學院研究員約翰·賴特（John Wright）向我們解釋說，IP和MIP已經有了定義，現在由他們來決定MIP*。
圖注：德國物理學家海森堡首次提出量子不確定原理
去年，賴特 和 納塔拉詹起草了一份證據，證明MIP*類中的幽靈式連接，使詢問糾纏的證明者能夠檢查更棘手的問題（其複雜性隨輸入的大小呈雙倍增長）。增加的糾纏為驗證者提供了更多的知識，以詢問證明者（神使）得更好問題。同時，量子力學的另一個原理，不確定性原理，每次驗證器詢問兩個互補特性之一時，都會擾亂驗證者的測量互補性，使得它們很難誤導驗證者。
這一作品來自賴特、納塔拉詹、悉尼科技大學的吉正峰、加州理工學院的托馬斯·維迪克和多倫多大學的亨利·袁，已經證明MIP*類的能力與去年的證明相形見絀。他們認為MIP*可以有效地驗證"遞歸枚舉類"或RE中的每一個問題，基本上，每個問題，如果答案為"是"，需要有限的時間來計算；如果回答"否"，那麼"否"答案可能需要無限時間才能計算。MIP*=RE。
賴特說，基本上，這個理論上的MIP*設備可以解決很多非常複雜的問題，包括著名的停頓問題，即計算機被問到當前運行的程序是否會終止。MIP*=RE證明在數學和物理中具有重要影響。
"簡而言之，我認為這是一個了不起的結果，"沒有參與這項研究的芝加哥大學計算機科學助理教授比爾·費弗曼在一封電子郵件中告訴我們。“這一結果是量子信息社會工具如何在廣泛的科學領域發揮作用，並在看似完全獨立的領域找到解決方案的一個很好的例子。這就是為什麼我對這個結果特別興奮的原因。”
代爾夫特科技大學量子信息學教授斯蒂芬妮·韋納告訴我們，只有證據才能證明了你對量子力學的瞭解程度。科學家們想知道糾纏的量子系統之間的相關性在最普遍意義上到底有多強。但是，作為證據機制的副作用，以及神使與驗證者之間的關係，事實證明，這個問題是無法估量的。
"這是一個基本聲明，事實上，我們真的不知道某些事情的答案，"韋納告訴我們。"我覺得這個證據很有趣。”
作為這種不可估量的副產品，眾多的證明駁斥了44年前的抽象代數猜想，叫做Connes嵌入猜想，這是一種深奧的數學陳述，在邏輯上等同於其他數學和物理主題中的陳述是等價的。麻省理工學院物理學家阿拉姆·哈羅告訴我們，許多人希望Connes猜想是真的，因為這將證明這個領域數學家的一些有用的事實和工具是真實的。
麻省理工學院
具體來說，對於物理學家來說，證明Connes嵌入猜想是錯誤的意味著，兩個獨立的數學對象曾經被認為，在如何解釋測量糾纏系統方面是等價的，事實上，它們並不是等價的。從無限到有限系統的某些近似不再起作用，正如物理學家曾經認為的那樣。
這不是一個永遠存在的真正設備——你不能把無所不知的神使的預言聯繫在一起，一個無所不知的神使的預言也根本不存在。但是研究人員使用這些抽象場景來理解，計算機能做什麼和不能做什麼的真正極限。也許，這些神使預言的縮減版本，就像依靠量子力學數學來進行計算的糾纏計算機一樣，其威力可能超出了物理學家先前的預期。
閱讀更多 科技領航人 的文章
