日韩黑丝制服一区视频播放|日韩欧美人妻丝袜视频在线观看|九九影院一级蜜桃|亚洲中文在线导航|青草草视频在线观看|婷婷五月色伊人网站|日本一区二区在线|国产AV一二三四区毛片|正在播放久草视频|亚洲色图精品一区

搜索
分享

這篇長達165頁的論文，用一個里程碑式的證明同時解決了量子物理學和理論數(shù)學的難題

 taotao_2016 2020-03-16
選自Quanta Magzine

作者：Kevin Hartnett

機器之心編譯

參與：Panda、蛋醬

計算機科學、數(shù)學、物理學，這三個學科各自的一些重大難題在近日發(fā)布的一篇標題簡潔的論文《MIP*=RE》中同時得到了解答。在該論文中，五位計算機科學家為可通過計算方式驗證的知識確立了一個新的邊界?；诖?，他們又為量子物理學和純數(shù)學領(lǐng)域仍未得到解決的重大難題帶去了答案。

這篇長達 165 頁的論文所揭示的研究成果，一經(jīng)發(fā)布，就在學界引發(fā)了廣泛的關(guān)注，《Nature》雜志也對此進行了介紹。原論文可訪問：https:///abs/2001.04383。


本文編譯自 Quanta Magazine，以下內(nèi)容是對該證明的詳細解讀：

故事要從 80 多年前說起。1935 年，阿爾伯特·愛因斯坦與鮑里斯·波多爾斯基（Boris Podolsky）和納森·羅森（Nathan Rosen）合作揭示了一種可能性：即使距離很遠，兩個粒子也可以發(fā)生糾纏或關(guān)聯(lián)。

就在接下來的一年里，阿蘭·圖靈（Alan Turing）提出了第一個通用計算理論，他證明了一件事：存在計算機永遠無法解決的問題。

這兩個想法都為各自的學科領(lǐng)域帶來了革命，而且它們看起來似乎并不相關(guān)。

但現(xiàn)在，一個具有里程碑意義的證明出現(xiàn)了，它將這兩種想法聯(lián)系在了一起，同時解決了計算機科學、物理學和數(shù)學領(lǐng)域許多尚未解決的問題。

這個新證明就是：理論上，使用糾纏態(tài)量子比特（qubit）而非經(jīng)典的 1 和 0 進行計算的量子計算機可用于驗證非常多的問題的答案。糾纏與計算之間的這種對應(yīng)關(guān)系震驚了許多研究者。

這個證明的作者們原本是想確定一種用于驗證計算問題的答案的方法局限性，這種方法涉及糾纏。找到那個局限性之后，順帶解決了另外兩個問題：物理學中的 Tsirelson 問題（關(guān)于如何用數(shù)學建模糾纏）以及純數(shù)學領(lǐng)域的一個相關(guān)問題（科納嵌入猜想）。

最終，這些結(jié)果像多米諾骨牌一樣級聯(lián)到了一起。

「這些思想都是同一時間出現(xiàn)的。它們能以如此戲劇性的方式再次聚首，真是很不錯?！乖撟C明的作者之一多倫多大學的 Henry Yuen 說。此外，該證明的作者還有悉尼科技大學的季錚鋒（Zhengfeng Ji）、加州理工學院的 Anand Natarajan 和 Thomas Vidick 以及德克薩斯州大學奧斯汀分校的 John Wright。這五位研究者都是計算機科學家。

不可定的問題

在計算機誕生之前，圖靈就已經(jīng)為計算方面的思考定義了一個基本框架。幾乎在同時，他也表明始終存在某些計算機無法解決的特定問題。這就是常說的「圖靈停機問題」。

經(jīng)典設(shè)計中，計算機程序可以接收輸入并產(chǎn)生輸出。但有時候，程序會進入無限的循環(huán)之中，不停地重復(fù)工作。如果你遇到了這種情況，那只能手動終止這個程序。

圖靈證明了，并不存在一個通用算法，可以確定一個計算機程序?qū)⑼Ｖ惯€是永遠運行。答案必須在運行這個程序后才能知道。

計算機科學家 Henry Yuen、Thomas Vidick、Zhengfeng Ji、Anand Natarajan 和 John Wright 合作證明了一個驗證計算問題的答案的問題，卻最終為數(shù)學和量子物理學領(lǐng)域的重大問題提供了解答。

「如果你已經(jīng)等待了 100 萬年而一個程序還未停止，你需要等待 200 萬年嗎？沒辦法知道答案。」滑鐵盧大學數(shù)學家 William Slofstra 說。

用技術(shù)術(shù)語來說，圖靈證明這個停止問題是不可定的（undecidable）——甚至可想象的最強大的計算機也無力解決。

圖靈之后，計算機科學家開始根據(jù)難度來對其它問題進行分類。要解決更難的問題，所需的計算資源也更多，也就是說需要更多運行時間、更多內(nèi)存。這些屬于計算復(fù)雜性問題。

最終而言，每個問題的求解都涉及到兩個重大問題：「這個問題的解決難度有多大？」和「驗證答案正確的難度有多大？」

審問式驗證

當問題相對簡單時，判斷答案正確與否也很簡單。但問題變得更加復(fù)雜時，就很難直接判斷了。但就算無法確認，你也能知道答案到底對不對。

此處就要提到「審問式驗證」了。這個方法跟警察審問的邏輯差不多：

如果一個嫌犯講的故事是精心編造的，那你可能沒辦法去驗證每一處細節(jié)。但只需要針對這個故事提出一些問題，你就可以知道嫌犯是在說謊，還是在如實陳述。

套用到計算機科學術(shù)語上說，「審問」的雙方分別是一臺強大的計算機和一臺更弱的計算機。其中強大的計算機（證明者）給出了一個解，較弱的計算機（驗證者）則希望通過提問來確定該解是否正確。

舉個簡單的例子，假設(shè)你是一個色盲，另一個人（證明者）稱兩顆彈珠顏色不同。你要怎么驗證他說的是不是真的呢？

你可以把這兩顆彈珠拿到身后混在一起，再拿出來讓證明者區(qū)分它們。如果它們顏色真的不同，那么證明者應(yīng)該每一次都能給出正確的答案。如果這兩顆彈珠實際上顏色一樣，那么證明者有一半的可能會猜錯（就算超過半數(shù)的時間能說對，那也能肯定顏色不一樣了）。

這種方法還可以驗證大量不同類別問題的解。以此推之，當兩個證明者針對同一個問題都給出解時，驗證速度會變得更快。

就比如，你要審問的嫌犯如果有兩個，解決一個犯罪案件就會更加輕松，因為你可以交叉檢驗他們的答案。如果這些嫌犯講的是實話，那么他們所說的大多都對得上。如果他們在說謊，那么更多時候會出現(xiàn)互相矛盾的答案。

計算復(fù)雜性可能看起來完全是理論方面的問題，但其實也與真實世界聯(lián)系很緊密。在求解和驗證問題的過程中，計算機需要時間和內(nèi)存資源，本質(zhì)上這是物理問題。

因此物理學領(lǐng)域的新發(fā)現(xiàn)會影響到計算復(fù)雜性。Natarajan 說：「如果你選擇了量子物理學而不是經(jīng)典物理學，那么你會得到不同的復(fù)雜性理論?！?/section>

這是 21 世紀的計算機科學家們，面對 20 世紀物理學中最古怪的糾纏思想，得到的最終結(jié)果。

突破口：科納嵌入猜想

當兩個粒子互相糾纏時，實際上并不會互相影響——它們之間不存在因果關(guān)系。愛因斯坦與其合作者在 1935 年的論文中闡述了這一思想。在那之后，物理學家和數(shù)學家都在努力想要通過數(shù)學的方式來描述糾纏的真正含義。

但是努力的結(jié)果卻有點混亂，科學家們?yōu)榧m纏構(gòu)想出了兩個不同的數(shù)學模型——而且之前并不清楚它們是否等效。

這種潛在的不和諧，最終給純數(shù)學領(lǐng)域帶來了一個重要問題，即科納嵌入猜想。最終，這成為了這五位計算機科學家新證明中的突破口。

第一種建模糾纏的方法將粒子視為在空間上是互相隔離的，比如一個在地球上，一個在火星上；妨礙兩者之間因果關(guān)系的是它們之間的距離。這被稱為張量積模型，但在某些情況下，兩個事物在因果關(guān)系上是否相互獨立卻并不非常明顯。

因此，數(shù)學家想出了另一種更通用的描述因果獨立性的方法。

當執(zhí)行兩個運算的順序不影響結(jié)果時，則這兩個運算滿足交換律：3×2 和 2×3 是一樣的。在第二種模型中，只要粒子的屬性互相關(guān)聯(lián)，則這些粒子便是互相糾纏的，但你執(zhí)行觀測的順序無關(guān)緊要：觀測粒子 A 來預(yù)測粒子 B 的動量或反過來，不管選用哪種順序，得到的答案都一樣。這被稱為交換算子式糾纏模型。

這兩種對糾纏的描述都要用到按行列形式組織的數(shù)字陣列，即矩陣。第一種張量積模型使用了行數(shù)和列數(shù)有限的矩陣，第二種交換算子模型使用一個更通用的對象，其工作方式就像是一個行數(shù)和列數(shù)無限的矩陣。

隨著時間的推移，數(shù)學家開始以研究這些矩陣為目標，完全與物理學世界脫離了聯(lián)系。除了這項研究之外，數(shù)學家 Alain Connes 在 1976 年提出了一個猜想：有可能使用有限維矩陣來近似很多無限維矩陣。這是科納嵌入猜想暗含的結(jié)果之一。

下一個十年，物理學家 Boris Tsirelson 提出了該問題的一個版本，再次將這個問題納入了物理學研究中。Tsirelson 猜想張量積糾纏模型和交換算子式糾纏模型是大致等價的。這當然是合理的，因為是對同一物理現(xiàn)象的兩種不同的理論描述。后續(xù)的研究表明，由于矩陣以及使用這些矩陣的物理模型之間所存在的關(guān)聯(lián)性，科納嵌入猜想與 Tsirelson 問題實際上是互相暗含的。解決了其中一個，你也就解決了另一個。

然而，這兩個問題的解最終都源自另外一個完全不一樣的位置。

博弈所體現(xiàn)的物理學

1960 年代，物理學家約翰·貝爾（John Bell）提出了一種測試方法，可以確定糾纏究竟是真實的物理現(xiàn)象或只是一個理論概念。這種測試涉及到一種博弈，其結(jié)果可說明是否存在某種不同尋常的非量子物理學的東西。

后來，計算機科學家又意識到，這種測試糾纏的方法也可用于驗證非常復(fù)雜的問題的答案。

為了了解這種博弈的工作方式，我們先假設(shè)有兩個玩家 Alice 和 Bob 以及一個 3×3 的網(wǎng)格。裁判為 Alice 分配了一行，并告訴她在每個空格中輸入一個 0 和 1，并使得數(shù)字之和為一個奇數(shù)。Bob 則得到一列，他的填充方式要使得該列之和為一個偶數(shù)。如果他們在列與行的重疊區(qū)放的數(shù)字一樣，則他們就獲勝。同時不允許他們互相交流。

在經(jīng)典設(shè)置中，他們的最佳表現(xiàn)為 89% 的勝率。但在量子設(shè)置中，他們可以做得更好。

假設(shè)為 Alice 和 Bob 分配了一對互相糾纏的粒子。他們觀測各自的粒子，然后使用觀測結(jié)果來引導(dǎo)每個格子的數(shù)字填充。由于這些粒子互相糾纏，所以他們的觀測結(jié)果是互相關(guān)聯(lián)的，也就意味著他們填入的答案是互相關(guān)聯(lián)的——進一步意味著他們的勝率可達 100%。

圖片來自：Lucy Reading-Ikkanda/Quanta Magazine

所以如果兩個玩家獲勝的概率高出預(yù)期，可以得出結(jié)論：他們使用了某種超出經(jīng)典物理學之外的東西。這樣的貝爾式實驗現(xiàn)在被稱為「非局部博弈（nonlocal game）」，因為玩家之間是分開的。

物理學家在實驗室中真正地執(zhí)行了這樣的實驗。Yuen 說：「多年來做實驗的人已經(jīng)表明這樣這種鬼魅般的事情確實存在?！?/section>

在分析任何博弈時，你可能都想知道玩家如果竭盡全力地玩，在一場非局部博弈中的勝率是多少。但在 2016 年時，William Slofstra 證明不存在用于計算所有非局部博弈的確切最大勝率的通用算法。

所以研究者就想：能不能至少做到近似求取最大獲勝百分比？

使用兩個描述糾纏的模型，計算機科學家鎖定了答案。在近似所有非局部博弈的最大勝率時，使用張量積模型的算法可確立一個下限，即最小值。另一個使用交換算子模型的算法可確立一個上限。

運行這些算法的時間越長，得到的答案就會越精準。如果 Tsirelson 的預(yù)測是對的，這兩個模型確實等價，那么這個上限與下限之間應(yīng)當相距很近，最終收縮為單個值，這個值就是近似得到的最大勝率。

但如果 Tsirelon 的預(yù)測不對，那么這兩個模型就不等價。Yuen 說：「那么上限和下限就一直相隔很遠?！鼓敲匆簿蜎]有辦法計算非局部博弈的近似最大勝率了。

這五位研究者在他們的新研究中使用了這一問題：上限和下限能否收斂以及 Tsirelson 問題是否為真？目的是解決另一個問題：是否有可能驗證一個計算問題的答案。

糾纏所提供的幫助

2000 年代早期，計算機科學家開始思考：如果審問兩個共享了糾纏粒子對的證明者，可驗證問題的范圍又將如何變化？

大多數(shù)人都猜想糾纏不利于驗證。畢竟如果兩個嫌犯之間存在某種串通答案的方式，那么他們就更容易編造出一致連貫的供詞。

但最近幾年，計算機科學家已經(jīng)意識到事實恰恰相反。通過審問共享了糾纏粒子的證明者，可驗證問題的范圍比沒有糾纏時更廣。

Vidick 說：「糾纏可以產(chǎn)生關(guān)聯(lián)，你可能認為這能幫助他們說謊或欺騙，但事實上你能把它變成自己的優(yōu)勢?！?/section>

怎么會這樣？要理解這一點，你首先需要了解你可以通過這個交互式流程驗證的大量問題。

假設(shè)有一個圖，由一組點（頂點）和連接這些點的線（邊）構(gòu)成，能否使用三種顏色給其中的頂點涂色，使得任何一條邊所連接的兩個頂點的顏色都不一樣？如果可以，那么這個圖就是「三色可分的（three-colorable）」。

如果你交給一對糾纏的證明者一張非常大的圖，而他們報告說這張圖是三色可分的，那么你會疑問：是否存在驗證他們答案的方法？

如果圖非常大，那么直接檢查結(jié)果是不可行的。但是，你可以向每個證明者提問，讓他們告訴你兩個相連頂點中分別一個頂點的顏色。如果他們報告的顏色不一致，而且每次提問的結(jié)果都是如此，那么你就能越來越相信這種三色涂色方案是可行的。

但當圖非常大時，這樣的審問策略也會失效，比如當邊和頂點的數(shù)量超過宇宙的原子數(shù)量時。甚至稱述一個具體問題（「告訴我 XYZ 頂點的顏色」）的任務(wù)就超出你這個驗證者的能力范圍，因為用于命名各個頂點所需的數(shù)據(jù)量超過了你工作內(nèi)存所能容納的極限。

但糾纏可以讓證明者自己想需要提出的問題。Wright 說：「驗證者不必去計算問題。驗證者可以迫使證明者為其計算問題?！?/section>

驗證者想要證明者報告相連頂點的顏色。如果這些頂點不是相連的，那么這些問題的答案與該圖是否三色可分無關(guān)。換句話說，驗證者想要證明者給出的問題是相關(guān)的。一個證明者問的是有關(guān)頂點 ABC 的情況，另一個證明者則問的是有關(guān)頂點 XYZ 的情況。希望是這兩個頂點是相連的，不過這兩個證明者都不知道彼此想的是哪個頂點。（就像 Alice 和 Bob 都希望在同一個方格中填入同樣的數(shù)字，即便他們都不知道對方被要求填哪一列或行。）

如果兩個證明者完全靠自己想出了這些問題，那么就不可能迫使他們選擇相連或相關(guān)的頂點，也就沒法讓驗證者驗證他們的答案。

但糾纏能提供這樣的相關(guān)性。我們幾乎可以把所有任務(wù)都交給證明者，讓它們自行選擇問題。

到該流程結(jié)束時，每個證明者都報告一種顏色。驗證者檢查它們是否一樣。如果這個圖是真正三色可分的，那么證明者永遠不應(yīng)報告同一種顏色。

Yuen 說：「如果存在三種顏色，證明者可以說服你只有一種?！?/section>

事實證明，這個驗證流程不過是非局部博弈的又一案例而已。如果證明者能說服你相信他們的解是正確的，那么該證明者便「獲勝」。

2012 年，Vidick 和 Tsuyoshi Ito 證明，有可能使用糾纏的證明者來執(zhí)行種類廣泛的非局部博弈，以驗證問題的答案，而且這些問題的數(shù)量至少與可通過審問兩臺經(jīng)典計算機驗證答案的問題數(shù)量一樣多。也就是說，使用糾纏的證明器與驗證不沖突。去年，Natarajan 和 Wright 證明：與糾纏的證明者交互實際上可以擴展可以驗證的問題的類別。

但那時計算機科學家尚不清楚可用這種方式驗證的所有問題類別。
而現(xiàn)在，情況發(fā)生了變化。

一連串的成果

這五位計算機科學家在他們的新論文中證明，通過審問糾纏的證明者，可以驗證無法求解的問題的答案，包括停機問題。

Yuen 說：「這種模型的驗證能力真的是超出了想象?！?/section>

但停機問題是無法解決的。事實上，正是這種新提出的思想，有望為這一斷言帶來最終證明。

設(shè)想你將一個程序提供給了一對糾纏的證明者，想要它們告訴你這個程序是否會停止。你已經(jīng)準備好通過一種非局部博弈來驗證它們的答案：這些證明者會生成問題，然后會根據(jù)這些問題的答案的協(xié)調(diào)性來「獲勝」。

如果該程序事實上會停止，則證明器的勝率應(yīng)為 100%——類似于一個圖確實三色可分的情況，糾纏的證明者不應(yīng)該報告兩個相連的節(jié)點的顏色一樣。如果該程序不會停止，則證明者只能靠運氣獲勝——勝率為 50%。

這意味著如果某人要求你確定這個非局部博弈問題的一個具體實例的近似最大勝率，你首先需要解決這個停機問題。而解決這個停機問題是不可能的。這意味著為非局部博弈計算近似最大勝率的問題是不可定的，就像停機問題一樣。

這又進一步意味著 Tsirelson 問題的答案是「否」——這兩個糾纏模型并不等價。因為如果它們是等價的，那么你可以把上限和下限壓到一起，計算得到一個近似最大勝率。

馬德里康普頓斯大學的 David Pérez-García 說：「不可能存在這樣一個算法，所以這兩個模型必定不同。」

這篇新論文證明：通過與糾纏的量子證明者交互所能驗證的問題類別（稱為 MIP* 類別）其實就等于不難于停機問題的問題類別（稱為 RE 類別）。該論文的標題就簡潔明了地說明了這一點：「MIP* = RE」

在證明這兩個復(fù)雜性類別相等的過程中，計算機科學家證明 Tsirelson 問題為假，而且由于之前的研究工作，也意味著科納嵌入猜想也為假。

對于這些領(lǐng)域的研究者而言，回答這些大問題的答案竟然來自于計算機科學領(lǐng)域一個看似不相關(guān)的證明，這著實讓人驚訝。

「如果我看到一篇論文說 MIP* = RE，我認為這和我的研究沒關(guān)系?！怪皣L試證明 Tsirelson 問題和科納嵌入猜想的研究者之一 Navascués 說，「對我來說，這完全就是一個驚喜?！?/section>

量子物理學家和數(shù)學家剛開始消化吸收這個證明。在這個新研究成果之前，數(shù)學家已經(jīng)在思考能否用大型的有限維度矩陣來近似無限維度的矩陣?，F(xiàn)在，由于科納嵌入猜想為假，他們知道這無法做到了。

Slofstra 說：「他們的結(jié)果表明這是不可能的。」

這些計算機科學家并沒有以回答科納嵌入猜想為目標，因此，他們并不是解釋他們最終解決的一個問題的最佳人選。

Natarajan 說：「我個人并不是一個數(shù)學家，我不是非常理解科納嵌入猜想的原始形式。」

他與其合作者預(yù)測數(shù)學家將會把這個新結(jié)果轉(zhuǎn)化成數(shù)學領(lǐng)域的語言。
在宣布這個證明的一篇博客文章中，Vidick 寫道：「我懷疑最終不需要復(fù)雜性理論來獲得純數(shù)學的結(jié)果?！?/section>

然而，現(xiàn)在研究者可以使用這個證明了，探究之路就可以到此為止了。
在超過 30 年的時間里，計算機科學家一直想搞清楚交互式驗證能讓他們前進多遠?，F(xiàn)在，以一篇標題簡單的長論文，他們給出了答案，也映照了圖靈的思想。

「過去長時間的研究都想要知道使用兩個糾纏的量子證明者的驗證流程有多強大，」Natarajan 說，「現(xiàn)在我們知道它有多強大了。故事也就到此為止。」

參考鏈接：
https://www./landmark-computer-science-proof-cascades-through-physics-and-math-20200304/
https://www./articles/d41586-020-00120-6

本文為機器之心編譯，轉(zhuǎn)載請聯(lián)系本公眾號獲得授權(quán)。
?------------------------------------------------
加入機器之心（全職記者 / 實習生）：hr@jiqizhixin.com
投稿或?qū)で髨蟮溃篶ontent@jiqizhixin.com
廣告 & 商務(wù)合作：bd@jiqizhixin.com

    本站是提供個人知識管理的網(wǎng)絡(luò)存儲空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點。請注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購買等信息，謹防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請點擊一鍵舉報。
    轉(zhuǎn)藏 分享 獻花（0）

    0條評論

    發(fā)表

    請遵守用戶 評論公約

    類似文章 更多