2017年春季，Urmila Mahadev發(fā)現(xiàn)自己成為少數(shù)極為幸運(yùn)的研究生之一。她剛剛解決了量子計(jì)算中的一個(gè)主要問(wèn)題，即探索如何立足與直覺(jué)嚴(yán)重相悖的量子物理學(xué)定律構(gòu)建起量子計(jì)算機(jī)。結(jié)合早期論文，Mahadev得出了所謂盲計(jì)算成果。德克薩斯大學(xué)奧斯汀分校的計(jì)算機(jī)科學(xué)家Scott Aaronson表示，這“無(wú)疑代表著她將成為一顆冉冉升起的新星。”

Urmila Mahadev最近在加州大學(xué)伯克利分校舉辦了計(jì)算機(jī)科學(xué)研討會(huì)

當(dāng)時(shí)剛剛28歲的Mahadev已經(jīng)在加州大學(xué)伯克利分校進(jìn)行第七年博士生學(xué)習(xí)——絕大多數(shù)學(xué)生顯然都忍受不了如此漫長(zhǎng)的學(xué)習(xí)時(shí)間。她在伯克利的導(dǎo)師Umesh Varizani表示，如今，她擁有了這一“漂亮得令人羨慕的博士生”論文。

然而，Mahadev并沒(méi)有在那年畢業(yè)——她甚至沒(méi)有考慮過(guò)畢業(yè)，因?yàn)樗J(rèn)為自己的工作還沒(méi)有完成。

五年多以來(lái)，她在學(xué)習(xí)與研究當(dāng)中遇到了另一個(gè)重要問(wèn)題，也就是Aaronson所提到的“量子計(jì)算領(lǐng)域中的一大根本性問(wèn)題”，即：如果要求量子計(jì)算機(jī)執(zhí)行下達(dá)的指令，應(yīng)如何判斷其是否真的按照指示進(jìn)行，或者是否進(jìn)行了任何量子性質(zhì)的計(jì)算？

這個(gè)問(wèn)題可能很快就會(huì)被學(xué)術(shù)界徹底解決。研究人員們希望能夠盡快讓量子計(jì)算機(jī)在各類(lèi)問(wèn)題當(dāng)中提供指數(shù)級(jí)加速能力，包括模擬黑洞周邊活動(dòng)到模擬蛋白質(zhì)大分子的折疊方式等等。

然而，如果說(shuō)某些計(jì)算屬于只有量子計(jì)算機(jī)能夠執(zhí)行、而經(jīng)典計(jì)算機(jī)無(wú)法處理的類(lèi)型，我們?cè)撊绾闻袛嗔孔佑?jì)算機(jī)是否做出了正確的計(jì)算處理？如果大家不信任傳統(tǒng)計(jì)算機(jī)，那么在理論上我們完全可以對(duì)計(jì)算中的每個(gè)步驟進(jìn)行復(fù)查。然而，量子系統(tǒng)從本質(zhì)上無(wú)法被這種復(fù)查。首先，其內(nèi)部工作原理非常復(fù)雜：對(duì)擁有數(shù)百個(gè)量子比特（或者稱「量子位」）的計(jì)算機(jī)進(jìn)行內(nèi)部狀態(tài)描述，就需要一塊能夠存儲(chǔ)下整個(gè)可見(jiàn)宇宙的巨大硬盤(pán)。

即使大家通過(guò)某種方式找到了記錄這一描述的充足存儲(chǔ)空間，問(wèn)題仍然沒(méi)有得到解決。量子計(jì)算機(jī)的內(nèi)部狀態(tài)通常由大量彼此不同的非量子“經(jīng)典”態(tài)疊加而成（正如薛定諤的貓理論，其處于既死又生的狀態(tài)）。然而，在測(cè)量了其中某一量子態(tài)之后，其就會(huì)坍縮為經(jīng)典狀態(tài)中的一種。同樣的，這意味著在300量子比特的量子計(jì)算機(jī)當(dāng)中，我們觀察到的結(jié)果將僅僅只是300個(gè)經(jīng)典比特——0或者1。

Vazirani解釋稱，“量子計(jì)算機(jī)非常強(qiáng)大，但同時(shí)也非常神秘。”

考慮到這些限制因素，計(jì)算機(jī)科學(xué)家們長(zhǎng)期以來(lái)一直弄不清楚量子計(jì)算機(jī)是否能夠提供切實(shí)可信的運(yùn)行保證，即證明其確實(shí)已經(jīng)完成了聲稱的計(jì)算功能。耶路撒冷希伯來(lái)大學(xué)計(jì)算機(jī)科學(xué)家Dorit Aharonov提問(wèn)道，“量子與經(jīng)典世界之間的相互作用是否強(qiáng)大到足以進(jìn)行對(duì)話？”

在研二階段，Mahadev被這個(gè)問(wèn)題所深深迷住，因?yàn)樗庾R(shí)到自己無(wú)法完全理解問(wèn)題本身。在接下來(lái)的幾年中，她嘗試了一種又一種實(shí)現(xiàn)方法。她表示，“我投入了很多時(shí)間，我認(rèn)為自己找到了正確的方向，但很快在一年之后仍然宣告失敗。”

但她不愿就此放棄。Mahadev表現(xiàn)出一種堅(jiān)韌的決心，這是Vazirani此前從未見(jiàn)過(guò)的。他表示，“從這個(gè)角度來(lái)講，Mahadev絕對(duì)是一位了不起的學(xué)生。”

如今，經(jīng)過(guò)八年的學(xué)習(xí)，Mahadev終于獲得成功。她提出一種交互式協(xié)議，通過(guò)該協(xié)議，不具備量子計(jì)算能力的用戶可以利用密碼方法將工具部署在量子計(jì)算機(jī)之上并隨時(shí)隨地加以驅(qū)動(dòng)，從而確保量子計(jì)算機(jī)遵循其指令。Vazirani表示，Mahadev的方法幫助用戶們獲得了“計(jì)算機(jī)永遠(yuǎn)無(wú)法擺脫的控制手段。”

Aaronson指出，對(duì)于一位在讀學(xué)生而言，這樣以一己之力完成的成果可謂“非常驚人”。

Mahadev如今已經(jīng)成為伯克利大學(xué)的博士后研究員，并在日前召開(kāi)的計(jì)算機(jī)科學(xué)基礎(chǔ)年度研討會(huì)上公布了自己的協(xié)議。該研討會(huì)是理論計(jì)算機(jī)科學(xué)領(lǐng)域規(guī)模最大的盛會(huì)之一，本屆會(huì)議于巴黎舉行。她的成果在會(huì)上被授予“最佳論文”與“最佳學(xué)生論文”獎(jiǎng)，這一切即使是對(duì)理論計(jì)算機(jī)科學(xué)家們而言都堪稱巨大的榮譽(yù)。

在一篇博文中，曾與Mahadev進(jìn)行過(guò)合作的加州理工學(xué)院計(jì)算機(jī)科學(xué)家Thomas Vidick指出，她的成果是“最近幾年以來(lái)，量子計(jì)算與理論計(jì)算機(jī)科學(xué)家領(lǐng)域出現(xiàn)的、最為杰出的思想之一。”

量子計(jì)算研究者們不僅對(duì)Mahadev協(xié)議所取得的成就感到興奮，同時(shí)亦贊嘆她給這個(gè)問(wèn)題帶來(lái)的全新處理方法。Vidick寫(xiě)道，在量子領(lǐng)域使用經(jīng)典密碼學(xué)手段是一種“真正新穎的思維。我希望以此為基礎(chǔ)，未來(lái)能夠出現(xiàn)更多振奮人心的成果。”

漫長(zhǎng)的道路

Mahadev出生于洛杉磯的一個(gè)醫(yī)生家庭，并在考入南加州大學(xué)之后進(jìn)行過(guò)多次專(zhuān)業(yè)轉(zhuǎn)換，希望能夠在繼承醫(yī)生頭銜之外找到真正適合自己的發(fā)展道路。此后，由著名RSA加密算法創(chuàng)造者之一、計(jì)算機(jī)科學(xué)家Leonard Adleman教授的課程讓她對(duì)理論計(jì)算機(jī)科學(xué)建立起濃厚興趣。她向伯克利研究生院提交了申請(qǐng)，解釋稱她對(duì)理論計(jì)算機(jī)科學(xué)中的各個(gè)方面都很感興趣——除了量子計(jì)算。

她回憶道，“當(dāng)時(shí)，量子計(jì)算聽(tīng)起來(lái)是種完全陌生的事物，我對(duì)此確實(shí)不太了解。”

她在進(jìn)入伯克利之后，Vazirani輕松易懂的解釋很快改變了她的想法。Vazirani指出，他曾得這位優(yōu)秀的學(xué)生介紹一個(gè)經(jīng)典問(wèn)題，即思考如何找到對(duì)量子計(jì)算進(jìn)行驗(yàn)證的協(xié)議。這個(gè)問(wèn)題“徹底激發(fā)出了她的想象力。”

Mahadev解釋稱，“協(xié)議就像是謎題。對(duì)我來(lái)說(shuō)，這類(lèi)問(wèn)題的切入門(mén)檻更低，因?yàn)槲覀兛梢粤⒓撮_(kāi)始構(gòu)思自己的協(xié)議，而后進(jìn)行嘗試以觀察其如何工作。”她選擇了這個(gè)方向作為自己的博士生課題，而Vazirani則將此稱為一條“漫長(zhǎng)的道路。”

如果量子計(jì)算機(jī)能夠解決經(jīng)典計(jì)算機(jī)無(wú)法解決的問(wèn)題，這并不代表著相關(guān)解決方案必然難以檢查。舉例來(lái)說(shuō)，在考慮大數(shù)因子分解問(wèn)題時(shí)，量子計(jì)算機(jī)能夠有效解決這一經(jīng)典計(jì)算機(jī)所無(wú)法處理的難題，而其驗(yàn)證工作卻非常簡(jiǎn)單。更具體地講，盡管經(jīng)典計(jì)算機(jī)無(wú)法計(jì)算出具體數(shù)字，但其能夠?qū)⒌贸龅囊蜃酉喑艘杂^察得出的大數(shù)是否與原始大數(shù)相等——只要相等，即代表得出了正確的答案。

然而，計(jì)算機(jī)科學(xué)家們認(rèn)為（最近我們亦在證明層面邁出了重要一步），量子計(jì)算機(jī)能夠解決的眾多問(wèn)題并不存在上述特征。換言之，經(jīng)典計(jì)算機(jī)不僅無(wú)法解決這類(lèi)問(wèn)題，甚至無(wú)法判斷給出的解決方案是否正確。有鑒于此，安大略省滑鐵盧周界理論物理研究所的物理學(xué)家Daniel Gottesman于2004年左右提出了一個(gè)問(wèn)題，即是否有可能建立起一種協(xié)議，從而由量子計(jì)算機(jī)向某非量子觀察方證明其確實(shí)完成了宣稱的計(jì)算。

在四年之內(nèi)，量子計(jì)算研究人員們已經(jīng)得出了部分答案。已經(jīng)有兩個(gè)團(tuán)隊(duì)各自獨(dú)立給出證明，相較于利用純粹的經(jīng)典驗(yàn)證計(jì)算機(jī)，在量子計(jì)算機(jī)之內(nèi)建立一個(gè)小型驗(yàn)證系統(tǒng)有望對(duì)該量子計(jì)算機(jī)的計(jì)算過(guò)程進(jìn)行證明。研究人員們之后對(duì)此種方法做出了改進(jìn)，并證明對(duì)所有驗(yàn)證方的需求，最終都可歸結(jié)于對(duì)單一量子比特的測(cè)量能力。

2012年，包括Vazirani在內(nèi)的一組研究人員們證明，如果一套量子計(jì)算機(jī)是由兩臺(tái)獨(dú)立且無(wú)法相互通信的量子計(jì)算機(jī)所構(gòu)成，那么經(jīng)典的驗(yàn)證計(jì)算機(jī)即可檢查其量子計(jì)算結(jié)果。然而，這篇論文的結(jié)果只適用于這一特定情況，而且似乎無(wú)法被擴(kuò)展至其它更為廣泛的應(yīng)用場(chǎng)景。Gottesman表示，“我認(rèn)為有不少人認(rèn)為這條道路恐怕走不通。”

大致就在同一時(shí)間，Mahadev接觸到了這一重要的驗(yàn)證問(wèn)題。起初，她希望提出一個(gè)“無(wú)條件”性結(jié)論，即不對(duì)量子計(jì)算機(jī)能做什么或不能做什么做出假設(shè)。但在這個(gè)方向探索一段時(shí)間并發(fā)現(xiàn)無(wú)果之后，Vazirani提出了使用“后量子”密碼學(xué)方法的可能性——換言之，研究人員們認(rèn)為密碼學(xué)超出了量子計(jì)算機(jī)的處理能力。當(dāng)然，他們對(duì)此也不太確定。（這里需要強(qiáng)調(diào)，用于在線交易等事務(wù)的RSA加密算法不屬于后量子密碼學(xué)，因?yàn)榇笮土孔佑?jì)算機(jī)完全可以解決這類(lèi)將安全性建立在大數(shù)分解難度的加密方法。）

2016年，Mahadev與Vazirani在處理另一個(gè)不同問(wèn)題方面取得了進(jìn)展，而這一進(jìn)展被證明極為關(guān)鍵。如今，舊金山OpenAI公司的計(jì)算機(jī)科學(xué)家Paul Christiano正與他們通力合作，開(kāi)發(fā)出一種利用密碼學(xué)方法讓量子計(jì)算機(jī)構(gòu)建起所謂“秘密狀態(tài)”的方法——無(wú)需量子計(jì)算機(jī)本身，經(jīng)典驗(yàn)證計(jì)算機(jī)已經(jīng)能夠?qū)γ孛軤顟B(tài)做出描述。

他們提出的程序依賴于所謂“陷阱門(mén)”函數(shù)——這是一種易于執(zhí)行的函數(shù)，但除非擁有加密密鑰，否則將難以逆向執(zhí)行。（但目前研究人員們并不知道要如何實(shí)際構(gòu)建起適合量子計(jì)算機(jī)的陷阱門(mén)函數(shù)，這將成為接下來(lái)的研究課題。）該函數(shù)亦需要“二合一”，即每項(xiàng)輸出都對(duì)應(yīng)兩條不同的輸入?？梢韵胂?，假如要對(duì)數(shù)字進(jìn)行平方計(jì)算，那么除了數(shù)字0之外，每條輸出結(jié)果（例如9）都擁有兩個(gè)對(duì)應(yīng)的輸入項(xiàng)（3與-3）。

利用這一函數(shù)，我們可以在量子計(jì)算機(jī)當(dāng)中建立秘密狀態(tài)，具體方法如下所示：首先要求計(jì)算機(jī)建立一項(xiàng)函數(shù)，將其所有可能的輸入內(nèi)容進(jìn)行疊加（聽(tīng)起來(lái)很復(fù)雜，但計(jì)算機(jī)執(zhí)行起來(lái)其實(shí)非常容易）。在此之后，要求計(jì)算機(jī)將該函數(shù)應(yīng)用于此大型疊加，從而建立起新?tīng)顟B(tài)——該狀態(tài)為函數(shù)所有可能輸出的疊加集。輸入與輸出疊加集將彼此糾纏，意味著對(duì)其中一者的測(cè)量將立即對(duì)另一個(gè)產(chǎn)生影響。

接下來(lái)，要求計(jì)算機(jī)測(cè)量輸出狀態(tài)并報(bào)告結(jié)果。此測(cè)量將把輸出狀態(tài)折疊為單一可能輸出，且輸入狀態(tài)也將立即折疊從而與該輸出結(jié)果匹配——這是因?yàn)槎弑舜思m纏。舉例來(lái)說(shuō)，如果使用平方函數(shù)，那么如果輸出狀態(tài)為9，則輸入將折疊為3與-3的疊加。

不過(guò)請(qǐng)注意，這里我們使用的是陷阱門(mén)函數(shù)。我們擁有陷阱門(mén)的密鑰，因此能夠很容易地找出構(gòu)成輸入疊加的兩個(gè)狀態(tài)。然而，量子計(jì)算機(jī)由于沒(méi)有這一密鑰，所以無(wú)法簡(jiǎn)單地通過(guò)測(cè)量輸入疊加以找出其構(gòu)成。這主要是因?yàn)闇y(cè)量會(huì)使結(jié)果進(jìn)一步折疊，從而導(dǎo)致量子計(jì)算機(jī)只能找到兩個(gè)輸入結(jié)果中的一個(gè)。

2017年，Mahadev通過(guò)使用一種名為L(zhǎng)earning With Errors（簡(jiǎn)稱LWE）的加密技術(shù)，發(fā)現(xiàn)了實(shí)現(xiàn)秘密狀態(tài)方法的核心——即構(gòu)建陷阱門(mén)函數(shù)。利用這些陷阱門(mén)函數(shù)，她能夠創(chuàng)建盲計(jì)算的量化版本，云計(jì)算用戶可以通過(guò)這種計(jì)算方式屏蔽自己的數(shù)據(jù)，從而確保云計(jì)算機(jī)即使在處理的過(guò)程中也無(wú)法對(duì)內(nèi)容進(jìn)行讀取。不久之后，Mahadev、Vazirani以及與Christiano開(kāi)始同Vidick與Zvika Brakerski（來(lái)自以色列Weizmann科學(xué)研究所）合作，大家共同進(jìn)一步完善這些陷阱門(mén)函數(shù)，旨在利用秘密狀態(tài)方法為量子計(jì)算機(jī)開(kāi)發(fā)出一種高度可靠的可證明隨機(jī)數(shù)生成方法。

Mahadev完全可以憑借這一出色成果順利畢業(yè)，但她決定繼續(xù)工作直到徹底解決這個(gè)驗(yàn)證問(wèn)題。她表示，“我從未想過(guò)畢業(yè)，因?yàn)槲业哪繕?biāo)不存在畢業(yè)這一概念。”

雖然并不清楚她到底是否能夠解決這個(gè)問(wèn)題，但她表示，“我愿意花時(shí)間學(xué)習(xí)我感興趣的事情，所以這并不算是在浪費(fèi)時(shí)間。”

一成不變

Mahadev嘗試了從秘密狀態(tài)方法到驗(yàn)證協(xié)議的多種方法，但有一段時(shí)間，她也陷入了困境。在此之后，她考慮了一下：研究人員們已經(jīng)證明，如果驗(yàn)證計(jì)算機(jī)能夠測(cè)量量子比特，由驗(yàn)證計(jì)算機(jī)即可檢查量子計(jì)算機(jī)。根據(jù)定義，經(jīng)典驗(yàn)證計(jì)算機(jī)缺乏這種能力。但如果經(jīng)典驗(yàn)證計(jì)算機(jī)能夠以某種方式迫使量子計(jì)算機(jī)自行執(zhí)行測(cè)量并如實(shí)報(bào)告，結(jié)果又會(huì)如何？

Mahadev意識(shí)到，其中最棘手的部分是讓量子計(jì)算機(jī)在了解驗(yàn)證計(jì)算機(jī)提出測(cè)量對(duì)象要求之前，就承諾了解對(duì)應(yīng)的狀態(tài)——否則，計(jì)算機(jī)很容易欺騙驗(yàn)證計(jì)算機(jī)。這正是秘密狀態(tài)方法發(fā)揮作用的地方：Mahadev的協(xié)議要求量子計(jì)算機(jī)首先創(chuàng)建一個(gè)秘密狀態(tài)，而后將其與應(yīng)當(dāng)測(cè)量的狀態(tài)糾纏起來(lái)。只有這樣，計(jì)算機(jī)才能找出要執(zhí)行的測(cè)量類(lèi)型。

由于計(jì)算機(jī)不知道秘密狀態(tài)的構(gòu)成，但驗(yàn)證計(jì)算機(jī)卻知道，因此Mahadev強(qiáng)調(diào)量子計(jì)算機(jī)無(wú)法在不留下明顯雙重性痕跡的前提下作弊。從本質(zhì)上講，Vidick寫(xiě)道，計(jì)算機(jī)測(cè)量的量子比特已經(jīng)“設(shè)置為一成不變”的形式。如此一來(lái)，只要測(cè)量結(jié)果看起來(lái)是正確的，則驗(yàn)證計(jì)算機(jī)即可確信其正確無(wú)誤。

Vidick寫(xiě)道，“這是個(gè)非常好的主意！每當(dāng)Mahadev做出解釋時(shí)，我都對(duì)此感到震驚！”

Mahadev的驗(yàn)證協(xié)議——以及隨機(jī)數(shù)發(fā)生器與盲加密方法——立足于量子計(jì)算機(jī)無(wú)法破解LWE這一假設(shè)。目前，LWE被廣泛視為后量子密碼學(xué)領(lǐng)域的主要候選方案，亦可能很快被美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)研究所作為新的加密標(biāo)準(zhǔn)，用以取代量子計(jì)算機(jī)可能破解的現(xiàn)有標(biāo)準(zhǔn)。但Gottesman告誡稱，這并不能保證其真正應(yīng)對(duì)量子計(jì)算機(jī)的強(qiáng)大處理能力。他表示，“不過(guò)到目前為止，這種解決方案還很穩(wěn)固，沒(méi)有人發(fā)現(xiàn)其可能被破解的證據(jù)。”

Vidick寫(xiě)道，無(wú)論如何，該協(xié)議對(duì)于LWE的高度依賴性使得Mahadev的成果具有雙贏潛力。量子計(jì)算機(jī)欺騙該協(xié)議的唯一方法，就是量子計(jì)算世界中有人想到如何破解LWE——而這本身也將成為一項(xiàng)了不起的成就。

Mahadev的協(xié)議不太可能在不久的未來(lái)在真正的量子計(jì)算機(jī)中實(shí)現(xiàn)。目前，該協(xié)議需要大量算力才能付諸實(shí)用。但隨著量子計(jì)算機(jī)規(guī)模的擴(kuò)大以及研究人員對(duì)協(xié)議的簡(jiǎn)化，這一情況未來(lái)幾年可能發(fā)生變化。

Aaronson表示，Mahadev的協(xié)議可能在未來(lái)五年內(nèi)恐怕還不可行，但“其并非完全只是一種幻想。在量子計(jì)算機(jī)發(fā)展的下一階段，如果一切順利的話，大家就可以開(kāi)始思考這個(gè)問(wèn)題了。”

考慮到技術(shù)發(fā)展的速度極為可觀，相信下一階段應(yīng)該會(huì)很快到來(lái)。畢竟就在五年之前，Vidick提到研究人員們還認(rèn)為量子計(jì)算機(jī)尚需要多年才能真正解決傳統(tǒng)計(jì)算機(jī)所無(wú)法解決的問(wèn)題。“現(xiàn)在，人們認(rèn)為這種能力在未來(lái)一到兩年后即會(huì)實(shí)現(xiàn)。”

至于Mahadev，解決她最喜歡的問(wèn)題讓她感覺(jué)有點(diǎn)像漂泊在大海之上。她提到，她希望自己能夠盡快找到那些最適合自己的研究方向。“現(xiàn)在我需要找個(gè)新的問(wèn)題了，我對(duì)這一切充滿期待。”

不過(guò)理論計(jì)算機(jī)科學(xué)家們認(rèn)為，Mahadev的量子計(jì)算與密碼學(xué)統(tǒng)一并不是結(jié)束，而將成為希望證明更多豐富思想的探索者們的新起點(diǎn)。

Aharonov表示，“我認(rèn)為未來(lái)還將有很多后續(xù)發(fā)展，我期待著Mahadev能夠帶來(lái)更多激動(dòng)人心的貢獻(xiàn)。”