馬哈德夫出席10月上旬在加州大學伯克利分校舉辦的計算機科學研討會

之後，她在巴黎舉行的計算機科學基礎學術報告會上發表了演講

2017年春天，烏爾米拉·馬哈德夫（Urmila Mahadev）讓大多數研究生都很羨慕。她剛剛解決了量子計算領域的一個重大問題。

所謂量子計算，研究的是量子計算機，它的算力來自量子物理學的奇異法則。

德州大學奧斯汀分校的計算機科學家斯科特·阿倫森（Scott Aaronson）指出，馬哈德夫的新研究成果（稱為“盲計算”），加之她早先發表的論文，讓所有人看到，“她是一顆冉冉升起的新星”。

當時，28歲的馬哈德夫已經在加州大學伯克利分校唸了七年的研究生，早就過了大多數學生迫不及待想要畢業的階段。現在，她終於具備了完成一篇“漂亮博士論文”的條件，馬哈德夫在伯克利的博士生導師優曼許·瓦齊雷尼（Umesh Vazirani）如是說。

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

量子計算領域的最基本問題之一

五年多來，馬哈德夫一直還在研究另一個問題，阿倫森稱之為“你能在量子計算領域提出的最基本問題之一”，即：如果我們讓量子計算機執行一次計算任務，我們如何知道它真的遵照了指令，它究竟有沒有做任何與量子計算有關的事情？

這個問題可能很快就會超越學術的範疇。研究人員希望，量子計算機能夠在相對較短的時間內，在一系列問題上實現指數級的計算加速，包括對黑洞周圍的天體行為進行建模、模擬大分子蛋白質的摺疊方式，等等。

不過，一旦量子計算機能夠執行傳統計算機無法完成的任務，我們如何才能知道它的計算過程是對的呢？

如果我們不信任一臺傳統計算機，理論上說，我們可以親自對每一個計算步驟進行檢驗。然而，量子系統從根本上是抵制這種檢驗的。

首先，它們的內部機制極其複雜：即便是一臺只有數百個量子比特（即量子位）的計算機，如果我們要把描述其內部狀態的信息全部記錄下來，我們將需要一個比整個可觀測宇宙還要大的硬盤，才能把這些信息存儲下來。

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

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

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

八年，終於成功！

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

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

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

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

馬哈德夫現在是加州大學伯克利分校的博士後研究員，她最近在計算機科學基礎學術報告會上展示了自己的協議——該會議是理論計算機科學領域規模最大的會議之一，今年在巴黎舉行。馬哈德夫的研究成果被授予大會“最佳論文”和“最佳學生論文”。對一名理論計算機科學家來說，這是難得的殊榮。

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

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

“我的目標從來不是為了畢業”

馬哈德夫在洛杉磯的一個醫生家庭長大，她本科就讀於南加州大學，在那裡輾轉於多個研究領域。起初，她只是確信自己不想當一名醫生。後來，RSA加密算法的創造者之一、計算機科學家倫納德·阿德曼（Leonard Adleman）教授的一門課程，讓她對理論計算機科學產生了濃厚的興趣。

她向加州大學伯克利分校的研究生院提出了申請，並在申請書中表示，自己對理論計算機科學的各個方面都感興趣——量子計算除外。

“當時，它聽起來像是我最不熟悉、最不瞭解的東西。”馬哈德夫說。

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

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

如果量子計算機可以解決傳統計算機無法解決的問題，並不一定意味著我們難以檢驗量子計算機給出的解決方案。

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

然而，計算機科學家認為，量子計算機能夠解決的很多問題並不具備這個特性。換句話說，傳統計算機不但無法解決這些問題，而且也無法確認量子計算機給出的解決方案是否正確。

有鑑於此，2004年左右，加拿大圓周理論物理研究所的物理學家丹尼爾·戈特斯曼（Daniel Gottesman）提出了一個問題：

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

2012年，一支包括瓦齊雷尼在內的研究團隊證明，如果量子計算是由兩臺無法相互通信的量子計算機來執行，那麼一臺純粹的傳統計算機是能夠對量子計算結果進行檢驗的。

但是，那篇論文描述的方法是為特定情況量身定製的，而問題似乎在這裡走到了死衚衕，戈特斯曼說，“當時可能有人覺得，我們沒法再前進一步了。”

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

2016年，在與計算機科學家保羅·克里斯蒂亞諾（Paul Christiano）合作另一個課題的研究時，馬哈德夫和瓦齊雷尼取得了一項後來被證明至關重要的進展。他們開發出一種方法，

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

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

接下來，我們讓計算機測量輸出狀態，並得到結果。這種測量會讓輸出值疊加態坍縮為一個確定的潛在輸出值，然後，輸入值疊加態也會立刻坍縮來進行匹配——例如，當我們使用平方數函數時，如果輸出值是9，那麼輸入值將坍縮為3和-3的疊加態。

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

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

他們順著秘密狀態的思路，開發出了一種讓量子計算機生成“可證明隨機數”的簡單方法。

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

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

如何判定量子計算機在“作弊”？

馬哈德夫嘗試了多種途徑，想要通過秘密狀態方法，得出一種驗證協議，但有一段時間，她一無所獲。後來，她有了一個想法：研究人員已經證明，如果驗證者能夠對量子比特進行測量，那麼該驗證者便能檢驗量子計算機。顯然，傳統計算驗證者缺乏這種能力。但如果傳統驗證者能夠以某種方式迫使量子計算機自己進行測量，並如實地報告，結果會怎樣呢？

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

由於計算機不知道秘密狀態的構成而驗證者知道，馬哈德夫證明，如果量子計算機大肆“作弊”，一定會留下明顯的欺騙痕跡。維迪克認為，從本質上說，計算機要測量的量子比特已經被“釘在加密術的板子上”。因此，如果測量結果看起來像是一個正確的證明，那麼驗證者就可以確信，它們確實如此。

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

馬哈德夫的驗證協議——連同隨機數生成器和盲加密方法——取決於一個前提假設，即量子計算機無法破解LWE。目前，LWE被廣泛認為是後量子加密術的主要候選者，它可能很快會被美國國家標準與技術研究所選為新的加密標準，以取代那些可以被量子計算機破解的技術。

戈特斯曼提醒說，這並不能保證LWE就一定不會被量子計算機破解。“但到目前為止，它還是穩固的。”他說，“還沒有人發現它有可能被破解的證據。”

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

“現在，我需要找到一個新的問題來研究”

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

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

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

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

但在理論計算機科學家看來，馬哈德夫對量子計算和加密術的統一併不是故事的結束，而是對更豐富思想的初步探索。

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

閱讀更多 科什麼技 的文章

關鍵字: 洛杉磯 電腦 加利福尼亞