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

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

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

然而，Mahadev并沒有在那年畢業(yè)——她甚至沒有考慮過畢業(yè)，因為她認(rèn)為自己的工作還沒有完成。

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

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

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

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

Vazirani解釋稱，“量子計算機非常強大，但同時也非常神秘。”

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

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

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

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

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

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

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

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

漫長的道路

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

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

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

Mahadev解釋稱，“協(xié)議就像是謎題。對我來說，這類問題的切入門檻更低，因為我們可以立即開始構(gòu)思自己的協(xié)議，而后進(jìn)行嘗試以觀察其如何工作。”她選擇了這個方向作為自己的博士生課題，而Vazirani則將此稱為一條“漫長的道路。”

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

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

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

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

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

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

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

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

接下來，要求計算機測量輸出狀態(tài)并報告結(jié)果。此測量將把輸出狀態(tài)折疊為單一可能輸出，且輸入狀態(tài)也將立即折疊從而與該輸出結(jié)果匹配——這是因為二者彼此糾纏。舉例來說，如果使用平方函數(shù)，那么如果輸出狀態(tài)為9，則輸入將折疊為3與-3的疊加。

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

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

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

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

一成不變

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

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

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

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

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

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

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

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

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

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

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

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