這篇長(zhǎng)達(dá)165頁(yè)的論文，用一個(gè)里程碑式的證明同時(shí)解決了量子物理學(xué)和理論數(shù)學(xué)的難題

taotao_2016 2020-03-16

展開(kāi)全文

選自Quanta Magzine

作者：Kevin Hartnett

機(jī)器之心編譯

參與：Panda、蛋醬

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

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

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

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

就在接下來(lái)的一年里，阿蘭·圖靈（Alan Turing）提出了第一個(gè)通用計(jì)算理論，他證明了一件事：存在計(jì)算機(jī)永遠(yuǎn)無(wú)法解決的問(wèn)題。

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

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

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

這個(gè)證明的作者們?cè)臼窍氪_定一種用于驗(yàn)證計(jì)算問(wèn)題的答案的方法局限性，這種方法涉及糾纏。找到那個(gè)局限性之后，順帶解決了另外兩個(gè)問(wèn)題：物理學(xué)中的 Tsirelson 問(wèn)題（關(guān)于如何用數(shù)學(xué)建模糾纏）以及純數(shù)學(xué)領(lǐng)域的一個(gè)相關(guān)問(wèn)題（科納嵌入猜想）。

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

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

不可定的問(wèn)題

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

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

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

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

「如果你已經(jīng)等待了 100 萬(wàn)年而一個(gè)程序還未停止，你需要等待 200 萬(wàn)年嗎？沒(méi)辦法知道答案?！够F盧大學(xué)數(shù)學(xué)家 William Slofstra 說(shuō)。

用技術(shù)術(shù)語(yǔ)來(lái)說(shuō)，圖靈證明這個(gè)停止問(wèn)題是不可定的（undecidable）——甚至可想象的最強(qiáng)大的計(jì)算機(jī)也無(wú)力解決。

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

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

審問(wèn)式驗(yàn)證

當(dāng)問(wèn)題相對(duì)簡(jiǎn)單時(shí)，判斷答案正確與否也很簡(jiǎn)單。但問(wèn)題變得更加復(fù)雜時(shí)，就很難直接判斷了。但就算無(wú)法確認(rèn)，你也能知道答案到底對(duì)不對(duì)。

此處就要提到「審問(wèn)式驗(yàn)證」了。這個(gè)方法跟警察審問(wèn)的邏輯差不多：

如果一個(gè)嫌犯講的故事是精心編造的，那你可能沒(méi)辦法去驗(yàn)證每一處細(xì)節(jié)。但只需要針對(duì)這個(gè)故事提出一些問(wèn)題，你就可以知道嫌犯是在說(shuō)謊，還是在如實(shí)陳述。

套用到計(jì)算機(jī)科學(xué)術(shù)語(yǔ)上說(shuō)，「審問(wèn)」的雙方分別是一臺(tái)強(qiáng)大的計(jì)算機(jī)和一臺(tái)更弱的計(jì)算機(jī)。其中強(qiáng)大的計(jì)算機(jī)（證明者）給出了一個(gè)解，較弱的計(jì)算機(jī)（驗(yàn)證者）則希望通過(guò)提問(wèn)來(lái)確定該解是否正確。

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

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

這種方法還可以驗(yàn)證大量不同類別問(wèn)題的解。以此推之，當(dāng)兩個(gè)證明者針對(duì)同一個(gè)問(wèn)題都給出解時(shí)，驗(yàn)證速度會(huì)變得更快。

就比如，你要審問(wèn)的嫌犯如果有兩個(gè)，解決一個(gè)犯罪案件就會(huì)更加輕松，因?yàn)槟憧梢越徊鏅z驗(yàn)他們的答案。如果這些嫌犯講的是實(shí)話，那么他們所說(shuō)的大多都對(duì)得上。如果他們?cè)谡f(shuō)謊，那么更多時(shí)候會(huì)出現(xiàn)互相矛盾的答案。

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

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

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

突破口：科納嵌入猜想

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

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

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

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

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

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

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

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

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

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

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

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

后來(lái)，計(jì)算機(jī)科學(xué)家又意識(shí)到，這種測(cè)試糾纏的方法也可用于驗(yàn)證非常復(fù)雜的問(wèn)題的答案。

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

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

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

圖片來(lái)自：Lucy Reading-Ikkanda/Quanta Magazine

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

物理學(xué)家在實(shí)驗(yàn)室中真正地執(zhí)行了這樣的實(shí)驗(yàn)。Yuen 說(shuō)：「多年來(lái)做實(shí)驗(yàn)的人已經(jīng)表明這樣這種鬼魅般的事情確實(shí)存在。」

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

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

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

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

但如果 Tsirelon 的預(yù)測(cè)不對(duì)，那么這兩個(gè)模型就不等價(jià)。Yuen 說(shuō)：「那么上限和下限就一直相隔很遠(yuǎn)。」那么也就沒(méi)有辦法計(jì)算非局部博弈的近似最大勝率了。

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

糾纏所提供的幫助

2000 年代早期，計(jì)算機(jī)科學(xué)家開(kāi)始思考：如果審問(wèn)兩個(gè)共享了糾纏粒子對(duì)的證明者，可驗(yàn)證問(wèn)題的范圍又將如何變化？

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

但最近幾年，計(jì)算機(jī)科學(xué)家已經(jīng)意識(shí)到事實(shí)恰恰相反。通過(guò)審問(wèn)共享了糾纏粒子的證明者，可驗(yàn)證問(wèn)題的范圍比沒(méi)有糾纏時(shí)更廣。

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

怎么會(huì)這樣？要理解這一點(diǎn)，你首先需要了解你可以通過(guò)這個(gè)交互式流程驗(yàn)證的大量問(wèn)題。

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

如果你交給一對(duì)糾纏的證明者一張非常大的圖，而他們報(bào)告說(shuō)這張圖是三色可分的，那么你會(huì)疑問(wèn)：是否存在驗(yàn)證他們答案的方法？

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

但當(dāng)圖非常大時(shí)，這樣的審問(wèn)策略也會(huì)失效，比如當(dāng)邊和頂點(diǎn)的數(shù)量超過(guò)宇宙的原子數(shù)量時(shí)。甚至稱述一個(gè)具體問(wèn)題（「告訴我 XYZ 頂點(diǎn)的顏色」）的任務(wù)就超出你這個(gè)驗(yàn)證者的能力范圍，因?yàn)橛糜诿鱾€(gè)頂點(diǎn)所需的數(shù)據(jù)量超過(guò)了你工作內(nèi)存所能容納的極限。

但糾纏可以讓證明者自己想需要提出的問(wèn)題。Wright 說(shuō)：「驗(yàn)證者不必去計(jì)算問(wèn)題。驗(yàn)證者可以迫使證明者為其計(jì)算問(wèn)題。」

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

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

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

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

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

事實(shí)證明，這個(gè)驗(yàn)證流程不過(guò)是非局部博弈的又一案例而已。如果證明者能說(shuō)服你相信他們的解是正確的，那么該證明者便「獲勝」。

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

但那時(shí)計(jì)算機(jī)科學(xué)家尚不清楚可用這種方式驗(yàn)證的所有問(wèn)題類別。

而現(xiàn)在，情況發(fā)生了變化。

一連串的成果

這五位計(jì)算機(jī)科學(xué)家在他們的新論文中證明，通過(guò)審問(wèn)糾纏的證明者，可以驗(yàn)證無(wú)法求解的問(wèn)題的答案，包括停機(jī)問(wèn)題。

Yuen 說(shuō)：「這種模型的驗(yàn)證能力真的是超出了想象?！?/section>

但停機(jī)問(wèn)題是無(wú)法解決的。事實(shí)上，正是這種新提出的思想，有望為這一斷言帶來(lái)最終證明。

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

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

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

這又進(jìn)一步意味著 Tsirelson 問(wèn)題的答案是「否」——這兩個(gè)糾纏模型并不等價(jià)。因?yàn)槿绻鼈兪堑葍r(jià)的，那么你可以把上限和下限壓到一起，計(jì)算得到一個(gè)近似最大勝率。

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

這篇新論文證明：通過(guò)與糾纏的量子證明者交互所能驗(yàn)證的問(wèn)題類別（稱為 MIP* 類別）其實(shí)就等于不難于停機(jī)問(wèn)題的問(wèn)題類別（稱為 RE 類別）。該論文的標(biāo)題就簡(jiǎn)潔明了地說(shuō)明了這一點(diǎn)：「MIP* = RE」

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

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

「如果我看到一篇論文說(shuō) MIP* = RE，我認(rèn)為這和我的研究沒(méi)關(guān)系?！怪皣L試證明 Tsirelson 問(wèn)題和科納嵌入猜想的研究者之一 Navascués 說(shuō)，「對(duì)我來(lái)說(shuō)，這完全就是一個(gè)驚喜。」

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

Slofstra 說(shuō)：「他們的結(jié)果表明這是不可能的?！?/section>

這些計(jì)算機(jī)科學(xué)家并沒(méi)有以回答科納嵌入猜想為目標(biāo)，因此，他們并不是解釋他們最終解決的一個(gè)問(wèn)題的最佳人選。

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

他與其合作者預(yù)測(cè)數(shù)學(xué)家將會(huì)把這個(gè)新結(jié)果轉(zhuǎn)化成數(shù)學(xué)領(lǐng)域的語(yǔ)言。

在宣布這個(gè)證明的一篇博客文章中，Vidick 寫(xiě)道：「我懷疑最終不需要復(fù)雜性理論來(lái)獲得純數(shù)學(xué)的結(jié)果?！?/section>

然而，現(xiàn)在研究者可以使用這個(gè)證明了，探究之路就可以到此為止了。

在超過(guò) 30 年的時(shí)間里，計(jì)算機(jī)科學(xué)家一直想搞清楚交互式驗(yàn)證能讓他們前進(jìn)多遠(yuǎn)?，F(xiàn)在，以一篇標(biāo)題簡(jiǎn)單的長(zhǎng)論文，他們給出了答案，也映照了圖靈的思想。

「過(guò)去長(zhǎng)時(shí)間的研究都想要知道使用兩個(gè)糾纏的量子證明者的驗(yàn)證流程有多強(qiáng)大，」Natarajan 說(shuō)，「現(xiàn)在我們知道它有多強(qiáng)大了。故事也就到此為止?！?/section>

參考鏈接：

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

https://www./articles/d41586-020-00120-6

本文為機(jī)器之心編譯，轉(zhuǎn)載請(qǐng)聯(lián)系本公眾號(hào)獲得授權(quán)。

?------------------------------------------------

加入機(jī)器之心（全職記者 / 實(shí)習(xí)生）：hr@jiqizhixin.com

投稿或?qū)で髨?bào)道：content@jiqizhixin.com

廣告 & 商務(wù)合作：bd@jiqizhixin.com

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

轉(zhuǎn)藏 分享

QQ空間 QQ好友新浪微博微信

獻(xiàn)花（0） +1

來(lái)自： taotao_2016 > 《物理》

舉報(bào)/認(rèn)領(lǐng)