[[253413]]

馬哈德夫出席 10 月上旬在加州大學(xué)伯克利分校舉辦的計算機(jī)科學(xué)研討會；之后，她在巴黎舉行的計算機(jī)科學(xué)基礎(chǔ)學(xué)術(shù)報告會上發(fā)表了演講。

　　2017 年春天，烏爾米拉·馬哈德夫（Urmila Mahadev）讓大多數(shù)研究生都很羨慕。她剛剛解決了量子計算領(lǐng)域的一個重大問題。所謂量子計算，研究的是量子計算機(jī)，它的算力來自于量子物理學(xué)的奇異法則。德州大學(xué)奧斯汀分校的計算機(jī)科學(xué)家斯科特·阿倫森（Scott Aaronson）指出，馬哈德夫的新研究成果（稱為“盲計算”），加之她早先發(fā)表的論文，讓所有人看到，“她是一顆冉冉升起的新星”。

　　當(dāng)時，28 歲的馬哈德夫已經(jīng)在加州大學(xué)伯克利分校念了七年的研究生，早就過了大多數(shù)學(xué)生迫不及待想要畢業(yè)的階段?，F(xiàn)在，她終于具備了完成一篇“漂亮博士論文”的條件，馬哈德夫在伯克利的博士生導(dǎo)師優(yōu)曼許·瓦齊雷尼（Umesh Vazirani）如是說。

　　不過，馬哈德夫沒有在那一年畢業(yè)，她甚至沒有考慮過畢業(yè)的問題。她的研究還沒有完成。

　　量子計算領(lǐng)域的最基本問題之一

　　五年多來，馬哈德夫一直還在研究另一個問題，阿倫森稱之為“你能在量子計算領(lǐng)域提出的最基本問題之一”，即：如果我們讓量子計算機(jī)執(zhí)行一次計算任務(wù)，我們?nèi)绾沃浪娴淖裾樟酥噶?，它究竟有沒有做任何與量子計算有關(guān)的事情？

　　這個問題可能很快就會超越學(xué)術(shù)的范疇。研究人員希望，量子計算機(jī)能夠在相對較短的時間內(nèi)，在一系列問題上實現(xiàn)指數(shù)級的計算加速，包括對黑洞周圍的天體行為進(jìn)行建模、模擬大分子蛋白質(zhì)的折疊方式，等等。

　　不過，一旦量子計算機(jī)能夠執(zhí)行傳統(tǒng)計算機(jī)無法完成的任務(wù)，我們?nèi)绾尾拍苤浪挠嬎氵^程是對的呢？

　　如果我們不信任一臺傳統(tǒng)計算機(jī)，理論上說，我們可以親自對每一個計算步驟進(jìn)行檢驗。然而，量子系統(tǒng)從根本上是抵制這種檢驗的。首先，它們的內(nèi)部機(jī)制極其復(fù)雜：即便是一臺只有數(shù)百個量子比特（即量子位）的計算機(jī)，如果我們要把描述其內(nèi)部狀態(tài)的信息全部記錄下來，我們將需要一個比整個可觀測宇宙還要大的硬盤，才能把這些信息存儲下來。

[[253414]]

　　而且，即使有足夠的空間來存儲這些信息，我們也無法去理解它。量子計算機(jī)的內(nèi)部狀態(tài)，通常是許多非量子“經(jīng)典”狀態(tài)的疊加，這就像薛定諤的貓，同時處于既死又活的狀態(tài)。但是，一旦你對一個量子態(tài)進(jìn)行測量，它就會坍縮成其中一個經(jīng)典態(tài)。如果觀察一臺 300 量子比特計算機(jī)的內(nèi)部，其實你只會看到 300 個經(jīng)典比特（0 和1）對著我們笑。

　　“量子計算機(jī)非常強大，但它同樣非常神秘。”瓦齊雷尼說道。

　　考慮到這些限制因素，計算機(jī)科學(xué)家一直以來就想知道，是否有可能讓量子計算機(jī)提供某種萬無一失的保證，即它確實做了自己宣稱做過的那些事情。“量子世界與經(jīng)典世界之間的相互作用是否強大到足以實現(xiàn)彼此之間的對話？”耶路撒冷希伯來大學(xué)的計算機(jī)科學(xué)家多瑞特·阿哈羅諾夫（Dorit Aharonov）這樣問道。

　　八年，終于成功！

　　在念研究生的第二年，馬哈德夫被這個問題迷住了，而且她自己也不完全明白其中的原因。隨后幾年，她嘗試了一個又一個方法。“很多時候，我都覺得自己做對了，然后它們卻崩潰了，有的耗時很短，有的則要花上一年。”她說。

　　但馬哈德夫沒有放棄，反而表現(xiàn)出一種持之以恒的決心，這是瓦齊雷尼在其他人身上不曾見過的，他說，“從這個方面講，烏爾米拉絕對與眾不同。”

　　如今，念了八年研究生后，馬哈德夫成功了。她構(gòu)想出一種交互協(xié)議，通過這種協(xié)議，那些自身不具備量子能力的用戶可以使用加密技術(shù)，給量子計算機(jī)套上“挽具”，駕馭它去往任何想去的地方，并且能夠確定量子計算機(jī)是在遵循指令行事。瓦齊雷尼表示，馬哈德夫的方法向用戶提供了“計算機(jī)無法掙脫的手段”。

　　阿倫森說，一名研究生能夠單槍匹馬取得這樣的成果，這“非常驚人”。

　　馬哈德夫現(xiàn)在是加州大學(xué)伯克利分校的博士后研究員，她最近在計算機(jī)科學(xué)基礎(chǔ)學(xué)術(shù)報告會上展示了自己的協(xié)議——該會議是理論計算機(jī)科學(xué)領(lǐng)域規(guī)模***的會議之一，今年在巴黎舉行。馬哈德夫的研究成果被授予大會“***論文”和“***學(xué)生論文”。對一名理論計算機(jī)科學(xué)家來說，這是難得的殊榮。

　　加州理工學(xué)院的計算機(jī)科學(xué)家托馬斯·維迪克（Thomas Vidick）曾與馬哈德夫共事，他在一篇博客文章中，把后者的研究成果稱為“近些年在量子計算和理論計算機(jī)科學(xué)交叉領(lǐng)域出現(xiàn)的最杰出成果之一”。

　　讓研究人員感到興奮的，不僅是馬哈德夫的協(xié)議所取得的效果，更在于她為解決這個問題而提出的全新方法。在量子領(lǐng)域使用經(jīng)典加密技術(shù)是一個“真正新穎的想法”，維迪克寫道，“我認(rèn)為這種想法將催生更多的研究成果。”

　　“我的目標(biāo)從來不是為了畢業(yè)”

　　馬哈德夫在洛杉磯的一個醫(yī)生家庭長大，她本科就讀于南加州大學(xué)，在那里輾轉(zhuǎn)于多個研究領(lǐng)域。起初，她只是確信自己不想當(dāng)一名醫(yī)生。后來，RSA 加密算法的創(chuàng)造者之一、計算機(jī)科學(xué)家倫納德·阿德曼（Leonard Adleman）教授的一門課程，讓她對理論計算機(jī)科學(xué)產(chǎn)生了濃厚的興趣。她向加州大學(xué)伯克利分校的研究生院提出了申請，并在申請書中表示，自己對理論計算機(jī)科學(xué)的各個方面都感興趣——量子計算除外。

　　“當(dāng)時，它聽起來像是我最不熟悉、最不了解的東西。”馬哈德夫說。

　　不過，她來到伯克利分校后，瓦齊雷尼通俗易懂的解釋很快改變了她的想法。瓦齊雷尼給她布置了一項任務(wù)，讓她找出一種能夠驗證量子計算的協(xié)議。瓦齊雷尼說，這個問題“真正激發(fā)了她的想象力”。

[[253415]]

　　“協(xié)議就像謎題。”馬哈德夫解釋道，“對我來說，它們似乎比其他問題更容易切入，因為我可以立刻開始思考那些協(xié)議，然后打破它們，這可以讓我看到它們是如何發(fā)揮作用的。”馬哈德夫把這個問題作為了博士研究的課題，從而踏上了瓦齊雷尼所謂的“漫漫長路”。

　　如果量子計算機(jī)可以解決傳統(tǒng)計算機(jī)無法解決的問題，并不一定意味著我們難以檢驗量子計算機(jī)給出的解決方案。

　　以大數(shù)的因數(shù)分解為例，大型量子計算機(jī)能夠高效地加以解決，而傳統(tǒng)計算機(jī)在這方面則被認(rèn)為力有不逮。盡管傳統(tǒng)計算機(jī)無法分解出一個大數(shù)的因數(shù)，但它能夠輕易檢驗量子計算機(jī)得出的結(jié)果是否正確——它只需把所有因數(shù)相乘，看看結(jié)果是否與大數(shù)相等就行了。

　　然而，計算機(jī)科學(xué)家認(rèn)為，量子計算機(jī)能夠解決的很多問題并不具備這個特性。換句話說，傳統(tǒng)計算機(jī)不但無法解決這些問題，而且也無法確認(rèn)量子計算機(jī)給出的解決方案是否正確。

　　有鑒于此，2004 年左右，加拿大圓周理論物理研究所的物理學(xué)家丹尼爾·戈特斯曼（Daniel Gottesman）提出了一個問題：我們是否有可能構(gòu)想出一種協(xié)議，讓量子計算機(jī)可以借此向一個非量子觀察者證明，它確實做了自己宣稱做過的那些事情？

　　在四年的時間里，量子計算研究人員找到了部分答案。兩支不同的研究團(tuán)隊證明，量子計算機(jī)有可能證明自己的計算，但對象并非一個純粹的傳統(tǒng)計算驗證者，而是一個能夠訪問小型量子計算機(jī)的驗證者。研究人員后來改進(jìn)了這種方法，表明驗證者需要的只是一次對單個量子比特進(jìn)行測量的能力。

　　2012 年，一支包括瓦齊雷尼在內(nèi)的研究團(tuán)隊證明，如果量子計算是由兩臺無法相互通信的量子計算機(jī)來執(zhí)行，那么一臺純粹的傳統(tǒng)計算機(jī)是能夠?qū)α孔佑嬎憬Y(jié)果進(jìn)行檢驗的。

　　但是，那篇論文描述的方法是為特定情況量身定制的，而問題似乎在這里走到了死胡同，戈特斯曼說，“當(dāng)時可能有人覺得，我們沒法再前進(jìn)一步了。”

　　大約在此時，馬哈德夫也遇到了這個驗證問題。起初，她試圖得出一個“無條件限制”的結(jié)果，也就是不對關(guān)于量子計算機(jī)能做什么、不能做什么提出任何假設(shè)。而后，在馬哈德夫研究這個問題一段時間卻沒有絲毫進(jìn)展的情況下，瓦齊雷尼提出，也許可以試試“后量子”加密技術(shù)。所謂“后量子”加密技術(shù)，就是量子計算機(jī)也無力破解的加密術(shù)。（用于為在線交易加密的 RSA 算法并不屬于后量子加密術(shù)，大型量子計算機(jī)可以破解這些算法，因為它們的安全性取決于分解大數(shù)因數(shù)的難易程度。）

　　2016 年，在與計算機(jī)科學(xué)家保羅·克里斯蒂亞諾（Paul Christiano）合作另一個課題的研究時，馬哈德夫和瓦齊雷尼取得了一項后來被證明至關(guān)重要的進(jìn)展。他們開發(fā)出一種方法，可以利用加密術(shù)讓量子計算機(jī)生成所謂的“秘密狀態(tài)”——對于這種狀態(tài)的描述，傳統(tǒng)計算驗證者能夠知道，而量子計算機(jī)本身無法知道。

　　他們的程序依賴于所謂的“陷門”函數(shù)，該函數(shù)易于執(zhí)行，但難于逆轉(zhuǎn)，除非你擁有私密的加密密鑰。（當(dāng)時，研究人員還不知道如何創(chuàng)建一個合適的陷門函數(shù)，后來才知道。）此外，陷門函數(shù)還需要是“二對一”，這意味著，每個輸出值都對應(yīng)著兩個不同的輸入值。比如說平方數(shù)函數(shù)，除了數(shù)字 0 之外，每個輸出值（例如9）都有兩個相應(yīng)的輸入值（3 和-3）。

　　有了這樣的函數(shù)之后，我們便能讓量子計算機(jī)按照如下步驟生成一個秘密狀態(tài)：首先，我們讓計算機(jī)建立一個包含函數(shù)所有潛在輸入值的疊加態(tài)。然后，我們讓計算機(jī)把函數(shù)應(yīng)用在這個巨型疊加態(tài)上，從而生成一個新狀態(tài)，它是函數(shù)所有潛在輸出值的疊加態(tài)。輸入值和輸出值的疊加態(tài)將被糾纏在一起，這意味著，對其中一個進(jìn)行測量會立刻影響到另一個。

　　接下來，我們讓計算機(jī)測量輸出狀態(tài)，并得到結(jié)果。這種測量會讓輸出值疊加態(tài)坍縮為一個確定的潛在輸出值，然后，輸入值疊加態(tài)也會立刻坍縮來進(jìn)行匹配——例如，當(dāng)我們使用平方數(shù)函數(shù)時，如果輸出值是9，那么輸入值將坍縮為 3 和-3 的疊加態(tài)。

　　但不要忘了，我們使用的是陷門函數(shù)。我們有陷門的密鑰，所以，我們可以很容易找出構(gòu)成輸入值疊加態(tài)的兩個狀態(tài)。但量子計算機(jī)不行，而且量子計算機(jī)也不能通過簡單地測量輸入值疊加態(tài)，來弄清它由什么構(gòu)成，因為這種測量會讓它進(jìn)一步坍縮，使計算機(jī)只能得到兩個輸入值中的一個，而無法得到另一個。

　　2017 年，馬哈德夫利用一種名為“容錯學(xué)習(xí)”（LWE）的加密技術(shù)，想出了如何在秘密狀態(tài)的核心方法中構(gòu)建陷門函數(shù)。利用這些陷門函數(shù)，她得以創(chuàng)建量子版本的“盲”計算——在盲計算中，云計算用戶可以屏蔽數(shù)據(jù)，使云計算機(jī)無法讀取，即便云計算機(jī)在使用數(shù)據(jù)進(jìn)行計算。不久之后，馬哈德夫、瓦齊雷尼、克里斯蒂亞諾聯(lián)手維迪克和以色列魏茨曼科學(xué)研究所的茲維卡·布拉克斯基（Zvika Brakerski），希望進(jìn)一步完善這些陷門函數(shù)。

　　他們順著秘密狀態(tài)的思路，開發(fā)出了一種讓量子計算機(jī)生成“可證明隨機(jī)數(shù)”的簡單方法。

　　馬哈德夫本可以憑借這些成果順利畢業(yè)，但她決心繼續(xù)研究，直至解決驗證問題為止。“我從未想過畢業(yè)的問題，因為我的目標(biāo)從來不是為了畢業(yè)。”她說道。

　　有時，由于不知道自己能否解決這個問題，馬哈德夫會感受到壓力。但她說，“我是在花時間學(xué)習(xí)自己感興趣的事情，所以這真的不算是浪費時間。”

　　如何判定量子計算機(jī)在“作弊”？

　　馬哈德夫嘗試了多種途徑，想要通過秘密狀態(tài)方法，得出一種驗證協(xié)議，但有一段時間，她一無所獲。后來，她有了一個想法：研究人員已經(jīng)證明，如果驗證者能夠?qū)α孔颖忍剡M(jìn)行測量，那么該驗證者便能檢驗量子計算機(jī)。顯然，傳統(tǒng)計算驗證者缺乏這種能力。但如果傳統(tǒng)驗證者能夠以某種方式迫使量子計算機(jī)自己進(jìn)行測量，并如實地報告，結(jié)果會怎樣呢？

　　馬哈德夫意識到，棘手的地方在于，要讓量子計算機(jī)在知道驗證者要求進(jìn)行哪種測量之前，就確定它要測量的狀態(tài)——否則，計算機(jī)很容易欺騙驗證者。這就是秘密狀態(tài)方法的用武之地了：按照馬哈德夫的協(xié)議，量子計算機(jī)會先創(chuàng)建一個秘密狀態(tài)，然后將其與它應(yīng)該測量的狀態(tài)糾纏在一起。只有這樣，計算機(jī)才能知道要執(zhí)行哪種測量。

　　由于計算機(jī)不知道秘密狀態(tài)的構(gòu)成而驗證者知道，馬哈德夫證明，如果量子計算機(jī)大肆“作弊”，一定會留下明顯的欺騙痕跡。維迪克認(rèn)為，從本質(zhì)上說，計算機(jī)要測量的量子比特已經(jīng)被“釘在加密術(shù)的板子上”。因此，如果測量結(jié)果看起來像是一個正確的證明，那么驗證者就可以確信，它們確實如此。

　　“這個想法真是太棒了！”維迪克寫道，“每次烏爾米拉進(jìn)行解釋，我都會感到驚艷。”

　　馬哈德夫的驗證協(xié)議——連同隨機(jī)數(shù)生成器和盲加密方法——取決于一個前提假設(shè)，即量子計算機(jī)無法破解 LWE。目前，LWE 被廣泛認(rèn)為是后量子加密術(shù)的主要候選者，它可能很快會被美國國家標(biāo)準(zhǔn)與技術(shù)研究所選為新的加密標(biāo)準(zhǔn)，以取代那些可以被量子計算機(jī)破解的技術(shù)。

　　戈特斯曼提醒說，這并不能保證 LWE 就一定不會被量子計算機(jī)破解。“但到目前為止，它還是穩(wěn)固的。”他說，“還沒有人發(fā)現(xiàn)它有可能被破解的證據(jù)。”

　　維迪克表示，無論如何，協(xié)議對 LWE 的依賴讓馬哈德夫的研究成果具有了雙贏屬性。量子計算機(jī)能夠“欺騙”該協(xié)議的唯一方法，是量子計算領(lǐng)域中，有人想到了如何破解 LWE，而這本身就將是一項了不起的成就。

　　“現(xiàn)在，我需要找到一個新的問題來研究”

　　馬哈德夫的協(xié)議不太可能很快就在真正的量子計算機(jī)中實現(xiàn)。目前來說，該協(xié)議要成為現(xiàn)實，還需要太多的算力才行。但未來幾年，隨著量子計算機(jī)的規(guī)模不斷擴(kuò)大以及研究人員繼續(xù)對協(xié)議進(jìn)行簡化，情況是有可能發(fā)生改變的。

　　也許，這份協(xié)議在未來五年內(nèi)都不具有可行性，但“它也并不完全是幻想中的事物”，阿倫森說道，“如果一切順利，在量子計算機(jī)發(fā)展的下一個階段，我們就可以開始思考這個問題了。”

　　而考慮到該領(lǐng)域的發(fā)展之快，這個階段或許很快就會到來。維迪克說，畢竟，就在五年前，研究人員還認(rèn)為，量子計算機(jī)還需要很多年才能解決傳統(tǒng)計算機(jī)無法解決的問題，“而現(xiàn)在，人們覺得只需要一兩年就可以了。”

　　至于馬哈德夫，解決了自己最喜歡的問題后，她覺得有點茫然。她說，她想知道這個問題究竟有何魔力，讓自己如此著迷。“現(xiàn)在，我需要找到一個新的問題來研究，如果能知道，就太好了。”

　　但在理論計算機(jī)科學(xué)家看來，馬哈德夫?qū)α孔佑嬎愫图用苄g(shù)的統(tǒng)一并不是故事的結(jié)束，而是對更豐富思想的初步探索。

　　“我感覺接下來，會有很多后續(xù)研究。”阿倫森說，“我期待看到烏爾米拉帶來更多的成果。”