大家好，我是大老李。今天的節(jié)目是有關(guān)近期幾則量子計(jì)算的新聞的，其實(shí)也不算太新，很多是去年的，但是幾乎沒有人用中文報(bào)道過，所以大老李給大家介紹下。

這幾則新聞共同點(diǎn)都是關(guān)于這個(gè)問題：量子計(jì)算機(jī)真的比經(jīng)典計(jì)算機(jī)優(yōu)越嗎？如何證明其優(yōu)越性？這幾年我們聽到過太多有關(guān)量子計(jì)算機(jī)的事情，它是如何得“快”等等。

通過前兩期有關(guān)復(fù)雜度的問題了解，你應(yīng)該了解到：量子計(jì)算機(jī)能快速處理的問題定義為“BQP”問題。對(duì)經(jīng)典計(jì)算機(jī)來說，能快速處理的問題是P問題，能快速驗(yàn)證的問題是NP問題。重復(fù)一次：P問題都是NP問題，但還沒有證明P！= NP，這就是克雷數(shù)學(xué)研究所懸賞的P vs NP 問題。但不管怎么樣 ，看起來經(jīng)典計(jì)算機(jī)能處理的最復(fù)雜的問題的上限，就是NP類問題。

量子計(jì)算機(jī)概念產(chǎn)生之后，科學(xué)家提出：是否有某個(gè)問題，屬于BQP問題，但不屬于NP問題？如果有，那么我們就證明量子計(jì)算機(jī)確實(shí)有其優(yōu)越性，因?yàn)樗芸焖偬幚硪恍┙?jīng)典計(jì)算機(jī)不能快速處理的問題。

2018年6月21日，在普斯頓和斯坦福大學(xué)任職的兩位計(jì)算機(jī)科學(xué)家(Ran Raz and Avishay Tal) 發(fā)表了一篇論文，第一次證實(shí)了，存在這樣一個(gè)問題，它屬于BQP問題，但不屬于NP問題。這個(gè)問題的描述是這樣的： 給你兩個(gè)隨機(jī)數(shù)生成器，并且你可以讓它們生成任意數(shù)量的隨機(jī)數(shù)。請(qǐng)問，你能否判斷這兩個(gè)隨機(jī)數(shù)生成器是“獨(dú)立”的？

我們?cè)趯W(xué)習(xí)概率的時(shí)候，有一個(gè)很重要的概念就是隨機(jī)變量的“獨(dú)立”性。在計(jì)算概率問題時(shí)，判斷清楚兩次概率事件是否獨(dú)立是一個(gè)很重要的前提。比如，連續(xù)丟兩次硬幣的結(jié)果我們認(rèn)為是獨(dú)立的。 而有些隨機(jī)事件就不是獨(dú)立的，比如你收聽“大老李聊數(shù)學(xué)”節(jié)目的概率和你的數(shù)學(xué)成績(jī)高于90分的概率是有相關(guān)性的。

現(xiàn)在有個(gè)特別的情況，有人說：我這里有兩串隨機(jī)數(shù)，它們是互相獨(dú)立的，絕無相關(guān)性。請(qǐng)問你有沒有辦法驗(yàn)證這一點(diǎn)？比如，如果其中一串隨機(jī)數(shù)其實(shí)是另一串隨機(jī)數(shù)經(jīng)過某種變換，比如傅里葉變換之后得到的，這樣這兩串隨機(jī)數(shù)就是完全相關(guān)的。但你僅憑目測(cè)是絕無可能發(fā)現(xiàn)這樣的相關(guān)的。

以上這個(gè)問題是2009年得克薩斯州大學(xué)的教授 Scott Aaronson, 首先提出的，他將其命名為“傅里葉相關(guān)”（forrelation=fourier+ relation）問題，并且證明了傅里葉相關(guān)問題是一個(gè)BQP問題，也就是量子計(jì)算機(jī)能快速處理這個(gè)問題。

而去年兩位科學(xué)家的結(jié)論就是，“傅里葉相關(guān)”問題不屬于NP（或PH)問題，從而正式發(fā)現(xiàn)了一個(gè)量子計(jì)算機(jī)可以快速解決，而傳統(tǒng)計(jì)算機(jī)無法快速解決的問題。但另外，科學(xué)家也猜想，存在某些問題屬于NP，但不屬于BQP，也就是經(jīng)典計(jì)算機(jī)可以快速處理，而量子計(jì)算機(jī)無法快速處理的問題。如果這個(gè)猜想被證明，那意味著經(jīng)典計(jì)算機(jī)有其不可被取代的方面。目前這個(gè)猜想還有待證明。

第二則新聞是有關(guān)證明“量子計(jì)算的真實(shí)性”，換句話說就是：量子計(jì)算機(jī)真的在計(jì)算嗎？你可能問，這不是廢話嗎，量子計(jì)算能解決經(jīng)典計(jì)算機(jī)不能快速處理的問題，這不就是證明量子計(jì)算的真實(shí)性嗎？但可惜，這些都還是理論上的，因?yàn)槟壳皩?shí)驗(yàn)中的量子計(jì)算機(jī)還只能處理很簡(jiǎn)單的問題。

比如2016年，IBM公司曾經(jīng)演示過用量子計(jì)算機(jī)進(jìn)行15=3*5的因子分解，就有人質(zhì)疑：你怎么證明這是用量子計(jì)算方法算出來的，而不是里面藏了一個(gè)計(jì)算器？當(dāng)然，如果IBM能對(duì)一個(gè)非常的大的整數(shù)進(jìn)行這種分解，就不會(huì)有人質(zhì)疑了，但是目前還遠(yuǎn)做不到。即使有一天，有人能用量子計(jì)算機(jī)進(jìn)行大整數(shù)分解了 ，還是可以有人質(zhì)疑，是不是你只是偷偷改進(jìn)的經(jīng)典計(jì)算機(jī)上整數(shù)分解的算法，讓后騙大家說這是量子計(jì)算機(jī)完成的？

另一方面 ，量子計(jì)算是非常“隱秘”的。量子計(jì)算的一個(gè)基本原理是利用了量子的疊加態(tài)和糾纏，這些狀態(tài)是很“脆弱”的，你不能太早去“觀察”它。量子物理中，有個(gè)“觀察者效應(yīng)”就是說你不能“觀察”量子，一但“觀察”，量子的特殊性就消失了，與宏觀世界里的一個(gè)“小球”沒有區(qū)別了。在這里，什么樣的動(dòng)作是一個(gè)“觀察”，還是物理學(xué)家正在研究的領(lǐng)域。無論如何，你不能“看”量子計(jì)算機(jī)的計(jì)算過程，只能靜待結(jié)果。

因此，就有人問：如何證明量子計(jì)算是存在的？如何知道量子正在執(zhí)行我們賦予的那些“算法”。2018年10月，加州大學(xué)伯克利分校的一位女博士研究生(Urmila Mahadev )，在其博士論文里，給出了一種方法，可以讓量子計(jì)算機(jī)向一個(gè)只擁有經(jīng)典計(jì)算機(jī)的驗(yàn)證著，證明其計(jì)算的真實(shí)性。

她的思路是這樣的：之前已有人證明，如果一個(gè)觀察者有能力“測(cè)量”一個(gè)量子位，則這個(gè)觀察者可以驗(yàn)證這個(gè)量子計(jì)算機(jī)。這有點(diǎn)像讓一個(gè)量子計(jì)算機(jī)去檢查另一臺(tái)量子計(jì)算機(jī)的計(jì)算。但現(xiàn)在要求觀察者只有經(jīng)典計(jì)算機(jī)，那如何驗(yàn)證的？

那就讓量子計(jì)算機(jī)自己“檢查”的自己的計(jì)算。大致意思就是，讓量子計(jì)算機(jī)進(jìn)入一種糾纏態(tài)，但并不告訴計(jì)算機(jī)，未來會(huì)如何測(cè)量的。一直到測(cè)量時(shí)候，才真相大白，原來是為了完成這種計(jì)算，這樣量子計(jì)算機(jī)是無法產(chǎn)生欺騙行為的。

這就好比讓一個(gè)小學(xué)生做很多加減乘除四則運(yùn)算，這個(gè)小學(xué)生完全不知道干嘛要算這些，直到計(jì)算完成，你才跟他說這是一次矩陣乘法運(yùn)算。當(dāng)然，這也可能是一次求π的近似小數(shù)的運(yùn)算。因?yàn)檫\(yùn)算過程中，運(yùn)算求解的具體問題不知道，這個(gè)小學(xué)生就無法進(jìn)行欺騙。

總之，有了以上成果，我們知道有辦法對(duì)量子計(jì)算的真實(shí)性進(jìn)行檢驗(yàn)，而無需等到量子計(jì)算機(jī)的計(jì)算能力超過經(jīng)典計(jì)算機(jī)，因?yàn)槿缯撊绾胃倪M(jìn)，經(jīng)典計(jì)算機(jī)無法通過這種檢驗(yàn)。

第三個(gè)新聞是有關(guān)量子計(jì)算機(jī)驗(yàn)證問題的能力的。我們已經(jīng)發(fā)現(xiàn)一些量子計(jì)算機(jī)算法，可以在多項(xiàng)式時(shí)間里求解NP問題，也就是那些在經(jīng)典計(jì)算機(jī)上只能在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證，而不能在多項(xiàng)式時(shí)間里求解的問題。這是我們研發(fā)量子計(jì)算機(jī)的主要?jiǎng)恿Α?/p>

另一方面：量子計(jì)算機(jī)有沒有可能使得之前不能在多項(xiàng)式時(shí)間里驗(yàn)證答案的問題，變得可以在多項(xiàng)式時(shí)間里驗(yàn)證呢？也就是原先比NP問題更復(fù)雜的問題，變?yōu)镹P問題呢？答案是可以的。

今年4月，加州理工大學(xué)和麻省理工大學(xué)的兩位計(jì)算機(jī)科學(xué)家發(fā)表了一篇論文，證明，利用量子計(jì)算機(jī)，可以大大提高我們對(duì)一些問題的驗(yàn)證能力。比如之前節(jié)目反復(fù)提到的過的三色著色問題：請(qǐng)你給一幅地圖用三種顏色著色，使任何相鄰的兩個(gè)區(qū)域具有不同的顏色。相應(yīng)的驗(yàn)證問題是：給你一副用三種顏色著色地圖，請(qǐng)你判斷，是否任意相鄰的兩個(gè)區(qū)域具有不同的顏色。很明顯這個(gè)問題是可以在多項(xiàng)式時(shí)間里驗(yàn)證的的，所以三色著色問題是一個(gè)NP問題。

但為了利用量子計(jì)算機(jī)進(jìn)行更快的驗(yàn)證，我們引入一個(gè)稱為“交互式驗(yàn)證”的概念，顧名思義，就是一問一答與機(jī)器交互驗(yàn)證的過程。比如還是這個(gè)三色著色問題，假設(shè)你自己是個(gè)色盲，完全辨別不了顏色，你只能讓另一個(gè)人幫你驗(yàn)證。但另一個(gè)人很不配合，他可能對(duì)你撒謊。

但是你可以對(duì)他進(jìn)行一種“拷問”，來確保得到你想要的結(jié)果。方法是這樣：你從已經(jīng)到手的著色完成的地圖里任選兩個(gè)區(qū)域里剪下相同形狀的一小塊。這樣，這兩小塊區(qū)域除了顏色不同，沒有任何不同。此時(shí)你不能直接問驗(yàn)證者，這兩塊區(qū)域是否同樣顏色，因?yàn)樗赡苋鲋e。但你可以左右手各放一個(gè)小塊，給他看，告訴他左手的那塊稱為“A塊”，右手的那叫作“B塊”。

然后，你把兩小塊區(qū)域放在身體后面任意交換，然后再給驗(yàn)證者看，哪塊是A，哪塊是B？此時(shí)，如果這兩塊區(qū)域顏色不同，且驗(yàn)證者沒有撒謊，那么這就太簡(jiǎn)單了。他應(yīng)該能夠穩(wěn)定的說出哪塊是A，哪塊是B。但如果兩塊顏色是一樣的，則他說對(duì)的概率應(yīng)該趨向于50%。只要經(jīng)過足夠多次的實(shí)驗(yàn)，你就能區(qū)分出以上兩種情況。以上過程就叫交互式證明。

再一次，科學(xué)家定義了“IP”(interactive polynomial)問題概念，意思是“交互式多項(xiàng)式時(shí)間”問題的意思。經(jīng)過前兩集音頻節(jié)目，相信你也能猜出這個(gè)定義的意思就是：可以用交互的方式，在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證的問題。

科學(xué)家證明了所有NP問題都是IP問題（再一次請(qǐng)讀者自己思考為啥）。另外，以上問題中只有一個(gè)驗(yàn)證者，如果你可以詢問多個(gè)人進(jìn)行交互式證明，則這類問題稱為MIP問題，這里M就是英語mulitple=“多個(gè)”的意思。當(dāng)然IP問題，都屬于MIP問題。

所以，P問題，NP問題，IP問題和MIP問題再一次構(gòu)成了一組復(fù)雜度的“俄羅斯套娃”。而科學(xué)家也證明了，量子計(jì)算機(jī)能在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證所有MIP問題，所以量子計(jì)算機(jī)能快速驗(yàn)證的問題復(fù)雜度上界似乎就是MIP。

之前，科學(xué)家還定義過一個(gè)復(fù)雜度：稱為“NEEXP”，意思是“非確定性雙重指數(shù)時(shí)間”。它的意思有點(diǎn)類似NP問題。NP問題的字面意思是“非確定性多項(xiàng)式時(shí)間”， 同理我們從中可以推廣出“非確定性指數(shù)時(shí)間”和“非確定性雙重指數(shù)時(shí)間的概念”。

如果一個(gè)問題，用傳統(tǒng)計(jì)算機(jī)檢查答案的話，需要雙重指數(shù)的時(shí)間，那么它就是NEEXP問題。雙重指數(shù)就是說指數(shù)有兩層，比如2^2^n次方。可以想象這種問題要比NP問題復(fù)雜非常多，因?yàn)镹P問題檢查只需要多項(xiàng)式時(shí)間。

這次，兩位科學(xué)家證明了，所有NEEXP問題都是MIP問題，意思就是所有用傳統(tǒng)計(jì)算機(jī)需要雙重指數(shù)時(shí)間來驗(yàn)證的問題，都可以用量子計(jì)算機(jī)在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證。這意味量子計(jì)算機(jī)不但計(jì)算能力優(yōu)越，連驗(yàn)證問題結(jié)果的能力也遠(yuǎn)優(yōu)于經(jīng)典計(jì)算機(jī)。當(dāng)然，以上都是理論，如何實(shí)現(xiàn)還需要等待。

最后要聊的一則新聞與以上新聞都不同的是：以上新聞都是關(guān)于量子計(jì)算機(jī)對(duì)比傳統(tǒng)計(jì)算機(jī)的優(yōu)越性，而這則新聞則是關(guān)于傳統(tǒng)計(jì)算機(jī)借鑒了量子計(jì)算機(jī)算法，從而提高了算法效率的。這個(gè)算法是關(guān)于購(gòu)物網(wǎng)站的“推薦算法”。

現(xiàn)在有很多網(wǎng)站都有一個(gè)“猜你喜歡”的功能，就是通過你之前看過的內(nèi)容，買過的東西來推測(cè)你喜歡什么。其原理就是根據(jù)歷史上很多人的購(gòu)物記錄，從中分析那兩樣的組合最常出現(xiàn)，這個(gè)問題學(xué)術(shù)上稱為“推薦問題”（recommendation problem）。

你腦子里稍微思考一下，你能想到的推薦問題通常都是一個(gè)指數(shù)時(shí)間算法，甚至找出一個(gè)多項(xiàng)式時(shí)間里的檢查算法都很難。而在2016年，有兩位計(jì)算機(jī)科學(xué)家（Iordanis Kerenidis, Anupam Prakash）發(fā)表了一個(gè)關(guān)于”推薦問題”的量子計(jì)算機(jī)算法，其復(fù)雜度是多項(xiàng)式時(shí)間。(O(poly(k)polylog(mn))。

2018年7月，在德克薩斯大學(xué)奧斯丁分校的就讀的研究生，時(shí)年18歲的華裔少女，Ewin Tang發(fā)表了一篇論文，她證明了，對(duì)“推薦問題”，經(jīng)典計(jì)算機(jī)也可以達(dá)到與量子計(jì)算同樣的復(fù)雜度效率，而她的思路正是借鑒了量子計(jì)算機(jī)的算法。

這就回到了一個(gè)老問題：量子計(jì)算機(jī)對(duì)比經(jīng)典計(jì)算機(jī)，到底有沒有意義？從理論上看，我們確實(shí)證明量子計(jì)算機(jī)優(yōu)越性，但是從實(shí)踐上講，量子計(jì)算機(jī)除了少數(shù)為其“量身定做”的問題，在其他大多數(shù)可以比較的問題上，其計(jì)算效率還遠(yuǎn)不如經(jīng)典計(jì)算機(jī)。甚至談不上計(jì)算效率，因?yàn)槎歼€沒有量子計(jì)算機(jī)可以使用的算法。

而這次，Ewin Tang僅根據(jù)理論上的量子計(jì)算機(jī)算法，就能把經(jīng)典計(jì)算機(jī)上的算法效率改進(jìn)得跟量子計(jì)算機(jī)上一樣好，這使得經(jīng)典計(jì)算機(jī)在實(shí)踐領(lǐng)域里又前進(jìn)一步。

喜馬拉雅上“古哥古點(diǎn)”節(jié)目中，曾提到過“量子霸權(quán)”和”量子優(yōu)越”這兩個(gè)概念。簡(jiǎn)單說，“霸權(quán)”就是絕對(duì)的優(yōu)勢(shì)，“優(yōu)越”是暫時(shí)局部的優(yōu)勢(shì)。那么Ewin Tang的成果至少是延遲了“量子優(yōu)越”的時(shí)間，因?yàn)樵谶@個(gè)“猜你喜歡”的問題計(jì)算上，經(jīng)典計(jì)算機(jī)可以做的與量子計(jì)算機(jī)一樣好。

順便說下，Ewing Tang在本科時(shí)期的導(dǎo)師就是之前提到過的，提出“傅里葉相關(guān)”問題的Scott Aaronson，可謂名師出高徒。現(xiàn)在，今年19歲的Ewing Tang已經(jīng)進(jìn)入華盛頓大學(xué)攻讀博士學(xué)位。

以上就是給大家播報(bào)的四則量子計(jì)算相關(guān)新聞，總結(jié)一下：

1. 科學(xué)家發(fā)現(xiàn)了一個(gè)量子計(jì)算可以快速處理，而經(jīng)典計(jì)算機(jī)不能快速處理的問題，即考察兩個(gè)隨機(jī)數(shù)序列是否具有相關(guān)性的問題。
   

2. 科學(xué)家發(fā)現(xiàn)了一個(gè)交互式證明方法，可以證實(shí)量子計(jì)算機(jī)確實(shí)是以量子理論的方法進(jìn)行了“計(jì)算”，而不被其他計(jì)算形式欺騙或是因?yàn)椤斑\(yùn)氣”好得到了計(jì)算結(jié)果。
   

3. 科學(xué)家證實(shí)了量子計(jì)算機(jī)對(duì)那些在傳統(tǒng)計(jì)算機(jī)上需要雙重指數(shù)時(shí)間進(jìn)行驗(yàn)證的問題，在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證。所以，量子計(jì)算機(jī)在驗(yàn)證問題的能力上比經(jīng)典計(jì)算機(jī)非常優(yōu)越。
   

4. 科學(xué)家成功移植量子計(jì)算機(jī)上的“推薦問題”，也就是“猜你喜歡”問題的算法到經(jīng)典計(jì)算機(jī)上，使得在這一問題上，經(jīng)典計(jì)算機(jī)有與量子計(jì)算機(jī)有相同的計(jì)算效率。
   

好了，祝各位學(xué)生朋友暑期愉快，多做數(shù)學(xué)題，下期再見！

參考鏈接：

https://www.quantamagazine.org/graduate-student-solves-quantum-verification-problem-20181008/

https://www.quantamagazine.org/teenager-finds-classical-alternative-to-quantum-recommendation-algorithm-20180731/

https://www.quantamagazine.org/finally-a-problem-that-only-quantum-computers-will-ever-be-able-to-solve-20180621/

https://www.quantamagazine.org/computer-scientists-expand-the-frontier-of-verifiable-knowledge-20190523/