一個撼動了物理學和數學的簡單等式

在今年年初時，幾位計算機科學家在arXiv上提交了一篇題為“MIP* = RE”的論文，這份長165頁的論文旨在證明一個問題，即MIP*與RE是相同的。而這個精簡的結論所代表的是複雜性理論中的一項里程碑式的發現，它解決了計算機科學、物理學和數學中的一系列待決問題。

什麼是複雜性理論？什麼又是MIP*和RE？故事可以從停機問題説起。簡單地説，停機問題探討的是，是否能以算法的方法判斷一個計算機程序會終止運行還是無限循環運行下去。1936年，計算機之父阿蘭·圖靈（Alan Turing）提出了第一個關於計算機的一般理論，他證明了計算機不是全能的，有些問題本身是不可能用計算機得出結果的，停機問題就是其中一個例子。

這種思想革新了計算機研究領域。很快人們就意識到，就算有些問題的確能用計算機解決，但它所需的計算時間，可能直到地球被太陽吞沒那天都無法完成。因此，僅討論能否從算法上解決一個問題是不夠的，根據求解的效率對解決方案進行分類才至關重要。

而複雜性理論就是根據解決問題的難易程度而對問題進行分類的計算問題的集合，一個問題的難易程度是根據計算這個問題所需持續的時間來衡量的。基於這種衡量標準，它將問題分成不同的類型，MIP*和RE所代表的便是其中的兩類。

我們先來看RE類問題。

RE代表的是可以被計算機解決的那類問題，它還可以細分為一些子類。首先是P類問題，它代表的是可以用已知算法在多項式時間內解決的問題，或簡單地説就是可以由已知算法快速求解的問題。例如兩個數的相乘，再比如將數列從小到大排序，都屬於P類問題，因為存在已知算法可以有效地解決這些問題。

另一個要説的複雜類問題是NP類問題。NP中的N表示“非確定性”，NP對應的是對於一些“是否”問題，當答案為“是”時，存在一個有效證明來表明“答案為是”。換句話説，NP類所包含的是一些可能很難求解，但卻很容易檢查其答案的問題。我們可以以“是否有辦法走出一個迷宮”的是否問題為例：如果答案是肯定的，那麼只要給出一個明確的路線，而我們順着這個路線走找到了迷宮的出口，就能確信這個問題的答案的確為“是”；然而如果答案是否定的，那就是我們就得走遍整個迷宮，確定真的沒有出路，才能確信問題的答案為“否”。

一個與P類和NP類有關的重要問題便是，P類問題與NP類問題是否相同，即能夠被容易解決的問題集合是否也屬於能夠被容易驗證的問題集合中？沒有人知道這個問題答案，雖然大多數數學家認為P與NP是不同的，但至今無人能證明這一點。

到目前為止，我們只討論到了普通計算機所面臨的問題。但是，現代計算機正在發生根本性的轉變，比如世界各地的科學家正在努力研發創造出更加強大的量子計算機。那麼問題是，當新型計算機出現，並聲稱它們能解決普通計算機所無法解決的問題，我們要如何判斷它是否正確呢？

讓我們以警察審訊一名嫌疑人的審訊過程為例。在審訊過程中，嫌疑人需要撇清嫌疑以證明自己清白，警察必須判斷嫌疑人所説的是否是真的，還是在撒謊。這兩方之間存在一種”認知“層面上的不平衡，警察處於劣勢。對應於複雜性理論中，嫌疑人對應於一台計算功能強大，會提出問題的解決方案的計算機，即所謂的證明者；而警察則是一台計算能力有限但試圖解決問題的計算機，它需要向證明者提問，以確定答案是否正確，即所謂的驗證者。二者構成了一個交互式證明系統，驗證者用它來確定是否應該相信證明者。

繼續以警察和嫌疑人的類比來説，就是這些問題是警察無法求解的，但如果嫌疑人是無辜的，那他們至少可以説服警察自己是無辜的。這樣的問題屬於IP類問題。

如果可以審問多個證明者，且證明者不能互相交流彼此的“答案”（就像警察審訊多個嫌疑犯時會避免他們串供的情況一樣），那麼我們就進入了MIP類問題。這種問題通過對證明者的回答進行交叉檢查，為驗證者提供了更多的信息，因此MIP類問題包含了IP問題。

然而新的問題又來了。量子通信是一種新的通過量子位進行的通信形式。量子糾纏特性使得量子通信與普通通信之間存在根本上的差異。在量子通信的前提下，MIP類問題中的證明者可以共享一個糾纏的量子位，使得他們可以相互”交流“彼此的”答案“，由此導致MIP*類問題的產生。

如此看來，證明者之間的交流似乎顯然只能有助於證明者協調謊言，而對驗證者發現真相無益。因此，這種交流應該不能使計算問題變得更加可靠和更加可解。然而，新的證明卻表示MIP* = RE，這一等式的成立它意味着，對糾纏的證明者進行審訊，是可以驗證無法解決的問題的答案的。

這一證明的出現引發了一系列意想不到的結果。比如在20世紀70年代，數學家Alain Connes提出了所謂的科納嵌入猜想，這是純數學領域的一個重要問題，粗略地説，它探討的是無窮矩陣能否用有限矩陣近似。這個猜想已經存在了40多年之久，大多數人都希望希望這個猜想是正確的，即無窮矩陣可以用有限矩陣近似，因為如果是這樣的話，就可以證明其他的許多數學工具也是正確的。但是新論文的出現表明，這是不可能的，這種猜想是錯誤的。

再比如在1993年，數學家Boris Tsirelson指出了量子物理學中的一個問題，表明有兩種不同的用於描述量子力學中的某個情況的數學形式，實際上是等價的。一直以來，物理學家利用Tsirelson的這個理論成功地解釋了亞原子世界。然而MIP* = RE的結果表明，事實並非如此。這令物理學家們非常費解，他們困惑於如果是這樣的話，為何這兩種數學形式能產生相同的結果，也好奇於它們為何能描述相同的物理現實。

計算機科學中一個的證明，竟然對不同領域的重大問題的結果產生了如此深遠的影響，真着實令人震驚。現在，量子物理學家和數學家仍在消化這些結果。相信由這個證明帶來的驚喜與不解，時間會最終給我們答案。但毫無疑問的是，MIP* = RE是複雜性問題研究的一個巨大飛躍。

參考來源：

https://theconversation.com/major-quantum-computational-breakthrough-is-shaking-up-physics-and-maths-136634

https://www.quantamagazine.org/landmark-computer-science-proof-cascades-through-physics-and-math-20200304/

https://arxiv.org/abs/2001.04383

封面圖來源：qimono / Pixabay

【來源：原理】

聲明：轉載此文是出於傳遞更多信息之目的。若有來源標註錯誤或侵犯了您的合法權益，請作者持權屬證明與本網聯繫，我們將及時更正、刪除，謝謝。 郵箱地址：newmedia@xxcb.cn