讀博第八年，她破解了量子計算領域的大問題

厄米拉·馬哈德夫在研討會上。| 圖片來源：Jana A?enbrennerová/Quanta Magazine

來源 公眾號「原理」

原作Erica Klarreich

翻譯 烏鴉少年

厄米拉·馬哈德夫（Urmila Mahadev）花了八年時間在研究生院解決了量子計算領域最基本的問題之一：怎麼知道量子計算機是否做了量子計算呢？

2017 年春天，厄米拉發現自己處於大多數研究生都會認為相當不錯的一個位置。她剛剛解決了量子計算領域的一個主要問題。量子計算是研究計算機的科學，它從量子物理學的奇怪定律中獲得強大的計算力。

德州大學奧斯汀分校的計算機科學家斯科特·阿倫森（Scott Aaronson）認為，厄米拉·馬哈德夫關於「盲計算」的新成果與她之前的論文結合起來，顯然讓她成為「一顆冉冉升起的新星」。

當時 28 歲的厄米拉已經在加州大學伯克利分校讀了七年研究生——遠遠超過了大多數學生迫切想要畢業的階段。現在，正如她的博士導師烏曼什·瓦齊拉尼（Umesh Vazirani）所說的，她終於有了一篇「非常漂亮的博士論文」。

但是那一年，厄米拉並沒有畢業，她甚至沒有考慮要畢業，因為事情還沒有完成呢。

量子計算+密碼學

在五年多的時間裡，她還有另一個不同的研究目標。她想解決的這個問題被阿倫森稱為「量子計算領域最基本的問題之一」，那就是：如果讓一台量子計算機做計算，怎麼知道它是否真的遵循了你的指令，或者它是否真的執行了任何量子計算呢？

研究人員希望，過不了許多年，量子計算機就能指數級地加速為我們解答許多問題，比如模擬黑洞周圍的行為、蛋白質如何摺疊等等。但是，一旦量子計算機能夠完成經典計算機無法完成的計算，我們將如何知道它的計算是否正確呢？

如果你不信任一台普通的計算機，理論上，你可以親自檢查它的每一個計算步驟。但是，量子系統從根本上抵制這種檢查。

首先，量子計算機的內部工作機制極其複雜：對於幾百個量子比特的計算機，要寫出關於其內部狀態的描述將需要比整個可見宇宙還要大的一個硬碟。此外，即使有足夠的空間寫下這個描述，也沒有辦法得到它。通常，量子計算機的內部狀態是許多不同的非量子的「經典」態的疊加。（就像是薛定諤的貓，同時處於「死」和「活」的狀態）但是，一旦測量一個量子態，它就會坍縮為其中一個經典態。凝視一台 300 個量子比特的量子計算機，本質上，你看到的只會是 300 個經典比特，也就是 0 和 1 。

瓦齊拉尼說：「量子計算機非常強大，但是也非常神秘。」

考慮到這些限制，長久以來，計算機科學家一直好奇，是否有可能讓量子計算機提供任何嚴格的保證，證明它確實做了自己宣稱的事情。耶路撒冷希伯來大學的計算機科學家多瑞特·阿哈羅諾夫（Dorit Aharonov）問道：「量子和經典世界之間的相互作用是否足夠強大，以至於能夠進行對話呢？」

在研究生二年級的時候，厄米拉被這個問題迷住了，其中的原因連她自己都不完全明白。在隨後的幾年裡，她嘗試了一種又一種方法。她說：「有很多次，我覺得自己做著正確的事情，但是接著就出錯了，有時很快，有時過了一年才出現。」

但是，厄米拉拒絕放棄。她表現出了瓦齊拉尼從未見過的持久的決心，瓦齊拉尼說：「從這個意義上說，厄米拉絕對是與眾不同的。」

現在，經過八年的研究生學習，厄米拉終於成功了！她提出了一種互動式協議，通過這種協議，沒有量子計算能力的用戶也可以使用經典的密碼學讓量子計算機做任何他們想做的事情，並確信量子計算機正在遵循他們的命令，就像是牽著馬具任意馳騁一樣。瓦齊拉尼說，厄米拉·馬哈德夫的方法給用戶提供了「讓計算機無法擺脫的手段「。

阿倫森說，一個研究生能夠獨自完成這樣一個任務」非常令人震驚「。

厄米拉現在是伯克利大學的博士後研究員。近日，她在計算機科學基金會的年度研討會——理論計算機領域最大型的會議之一——上提交了自己的方案。她的作品獲得了這次會議的」最佳論文「和」最佳學生論文「獎，這對一位理論計算機科學家來說是罕見的榮譽。

加州理工學院的計算機科學家托馬斯·維迪克（Thomas Vidick）過去曾與厄米拉合作過，他在博客文章中寫道，厄米拉·馬哈德夫的研究成果是」近年來量子計算和理論計算機科學的交叉處出現的最傑出的思想之一「。

量子計算領域的研究人員之所以興奮，不僅是因為厄米拉的協議能夠解決問題，還因為她為解決這個問題所採取的全新方法。維迪克寫道，在量子計算領域使用經典的密碼學真的是非常新穎的想法，」我希望，在這些想法的基礎上，會繼續產生更多成果。「

漫長的證明之路

厄米拉·馬哈德夫在洛杉磯的一個醫生家庭長大，她就讀於南加州大學，在那裡，她從一個研究領域漂流到另一個。起初，她只確信一點，那就是自己不想成為一名醫生。後來，計算機科學家萊納德·艾德蒙（Leonard Adleman）——RSA 加密演算法的三位創造者中的 A——講授的一門課程讓她對理論計算機科學產生了興趣。之後，她申請成為加州大學伯克利分校的研究生，並在申請材料中解釋說，自己對理論計算機科學的所有方面都感興趣，除了量子計算。因為量子計算「聽起來像是非常古怪的事情，是我知道得最少的事情」。

然而，一到伯克利，瓦齊拉尼深入淺出的解釋很快改變了她的想法。他向她介紹了一個問題——如何找到一個驗證量子計算的協議？而這個問題「激發了她的想像力」，瓦齊拉尼說道。

厄米拉解釋說：「協議就像是謎題。對我來說，這種問題似乎比其他問題更容易，因為你可以自己立即開始思考協議，然後破解它們，這樣你就會發現它們是如何運作的。」 她選擇這個問題作為自己的博士研究課題，開始了瓦齊拉尼所說的「漫漫長路」。

厄米拉·馬哈德夫| 圖片來源：Quanta Magazine

如果一台量子計算機可以解決經典計算機無法解決的問題，那並不必然意味著解決方案將難以檢驗。以大數的因數分解為例，一台大型量子計算機可以高效解決這個問題，但經典計算機被認為無法完成這個任務。

雖然一個經典計算機不能對一個大的數字進行因數分解，但它卻能夠檢驗量子計算機的因數分解是否正確——只需要將這些因數相乘，看看它們是否得出正確答案。

然而，計算機科學家相信（並且最近已經向證明邁出了一步），量子計算機能夠解決的許多問題並沒有這個特性。也就是說，一台經典計算機不僅不能解決這些問題，甚至也不能判斷一個提出的解決方案是否正確。

鑒於這一點，大約在 2004 年，圓周理論物理研究所的物理學家丹尼爾·戈特斯曼（Daniel Gottesman）提出一個問題：是否有可能提出任何一種協議，通過這個協議，一台量子計算機可以向非量子觀察者證明自己確實完成了聲稱的那些事情？

在四年內，量子計算的研究人員已經得到了部分答案。兩個不同的團隊證明，一台量子計算機有可能證明它的計算，但是不是向一台純粹經典的驗證設備，而是向一個能夠進入自己內部非常小的量子計算機的驗證設備。研究人員後來改進了這種方法，並證明，驗證設備所需要的只是每一次測量單個量子比特的能力。

2012 年，包括瓦齊拉尼在內的一組研究人員證明，如果量子計算是由一對無法相互通信的量子計算機進行的，那麼，一台完全經典的驗證設備就能夠檢查量子計算。戈特斯曼表示，那篇論文的方法是針對這種特定情形設計的，這個問題似乎陷入了死胡同，一些人認為不能再往前走了。

大約就在這個時候，厄米拉遇到了這個驗證問題。起初，她試圖得到一個「無條件」的結果，一個並不假定量子計算機能做什麼或不能做什麼的結果。

在她研究這個問題一段時間，且並沒有取得任何進展後，瓦齊拉尼建議了一種不同的可能性——用「後量子」加密（post-quantum cryptography）。研究人員認為，這是一種即使量子計算機也無法破解的加密方法，雖然他們還不確定。

像 RSA 加密演算法之類用於加密在線交易等信息的方法不是後量子的，也就是說，一台量子計算機能夠破解這種加密方法，因為它們的安全性取決於對大數做因數分解的難度。

2016 年，厄米拉和瓦齊拉尼在解決另一個問題的時候取得了進展，這在後來被證明是至關重要的。

他們與如今在 OpenAI 公司工作的計算機科學家保羅·克里斯蒂亞諾（Paul Christiano）合作，開發了一種方法，使用密碼學讓量子計算機構建所謂的「加密態（secret state）」，這個加密態的描述對於經典的驗證設備是已知的，但是對於量子計算機本身卻是未知的。

他們的程序依賴於所謂的「暗門」函數（trapdoor function），這個函數很容易執行，但是要逆轉則非常困難，除非知道密鑰。（研究人員還不知道如何真正構建一個合適的暗門函數，之後將會提出。）另外，還要求這個函數是「二對應一」的，這意味著，每一個輸出對應著兩個不同的輸入。比如說，對於平方函數y=x2，除了數字 0 之外的每一個輸出（例如 9）都有兩個對應的輸入（3 和 ?3）。

有了這樣一個函數，就可以讓量子計算機按照下面的步驟構建一個加密態：

首先，讓計算機構建一個所有可能的函數輸入的疊加（這聽起來或許很複雜，但是事實上很容易）；

然後，讓計算機將函數應用到這個巨大的疊加上，函數的所有可能輸出的疊加構成一個新的態。

輸入的疊加和輸出的疊加會產生糾纏，這意味著，測量其中一個會立即影響另一個。

接下來，要求計算機測量輸出態，並告訴我們結果。這個測量會導致輸出態坍縮為所有可能輸出中的一個，而輸入態也會立即坍縮以與之匹配，因為它們彼此糾纏。例如，對於平方方程，如果測量得到的輸出態是 9，那麼輸入態會坍縮為 3 和 ?3 的疊加態。

但是，如果使用的是暗門函數，那麼我們就有暗門的秘鑰，因此可以很容易地找出構成輸入態的兩種疊加態。然而，量子計算機不能。量子計算機不能簡單地測量輸入的疊加來求出它的構成，因為測量會進一步讓輸入的疊加坍縮，讓計算機只剩下其中一個輸入態，而無法求出另一個。

2017 年，厄米拉使用一種名為「錯誤學習（Learning With Errors，LWE）」的加密技術，找到了在加密態方法的核心構建暗門函數的方法。利用暗門函數，她就能夠創建一個量子版本的「盲」計算，使得雲計算用戶可以屏蔽他們的數據，這樣雲計算機即使在計算時也無法讀取數據。

不久之後，厄米拉、瓦齊拉尼、克里斯蒂亞諾與維迪克、斯維卡·布雷克斯基（Zvika Brakerski，以色列魏茨曼科學研究所的科學家）合作，進一步改進這些暗門函數，利用加密態方法發展出一種讓量子計算機產生可證實的真隨機數的安全方法。

厄米拉本可以憑藉這些結果畢業，但她決心繼續工作，直到解決驗證問題。她說：「我從來沒有想畢業的事情，因為我的目標從來就不是畢業。」

不知道能否解決這個問題有時會讓人感到壓力，但是，她說：「我花時間學習自己感興趣的東西，因此，這不是真的在浪費時間。」

如何加密？

厄米拉嘗試了各種方法，試圖從加密態方法抵達一種驗證協議，但是有一段時間，她一無所獲。然後，她有了一個想法：研究人員已經證明，如果驗證設備能夠測量量子比特，它就能夠檢驗量子計算機。根據定義，一個經典的驗證設備缺乏這種能力。但是，如果這個經典的驗證設備能夠以某種方式強迫量子計算機自己進行測量，然後誠實地報告測量結果呢？

厄米拉意識到，最棘手的部分是，在量子計算機知道驗證設備會要求哪種測量之前，就讓量子計算機確定它將要測量的狀態。否則，量子計算機很容易欺騙驗證設備。這正是加密態方法發揮作用的地方：厄米拉的協議要求量子計算機首先創建一個加密態，然後將它與應該測量的狀態糾纏在一起。只有到那時，計算機才會知道要進行何種測量。

由於量子計算機不知道加密態的構成，但驗證設備知道，厄米拉證明，量子計算機不可能在不留下明顯的欺騙痕迹的情況下做出嚴重的欺騙。

維迪克寫道，本質上，計算機要測量的量子比特被「設置為密碼石」。正因為如此，如果測量結果看起來像是一個正確的證明，驗證設備就能確信它們真的是。「真是個好主意！每一次厄米拉解釋它的時候，我都驚呆了。」

量子計算機不能破解的密碼？

厄米拉·馬哈德夫的驗證協議，連同隨機數生成器和盲加密方法，都取決於量子計算機不能破解 LWE 的假設。目前，LWE 被廣泛認為是後量子密碼學的優先候選對象，而且，它或許很快會被美國國家標準與技術研究所（NIST）採用作為其新的加密標準，取代那些量子計算機可能破解的方法。

戈特斯曼警告說，這並不能確保這種加密方法真的能抵禦量子計算機，「但是到目前為止，這種方法是可靠的，還沒有人找到證據，證明這種方法有可能被破解。」

維迪克寫道，無論如何，協議對 LWE 的依賴給厄米拉的作品帶來了雙贏的意味。量子計算機可能欺騙協議的唯一方法是，量子計算領域的某個人找到了破解 LWE 的方法，而這本身將會是一項了不起的成就。

厄米拉·馬哈德夫的協議不太可能在不久的將來就在真正的量子計算機上實現。目前，這個協議需要太多的計算能力，因而不太有實用性。但在未來幾年，隨著量子計算機越來越大，以及研究人員對協議進行簡化，情況可能會改變。

阿倫森說，厄米拉的協議可能在未來五年內都沒有可行性，但是，「在假想世界裡也不是完全不可行。如果一切順利，在量子計算機演化的下一個階段，就可以開始思考這個問題。「

考慮到這個領域現在的發展速度有多快，這個階段可能會更早到來。維迪克說，畢竟，就在五年前，研究人員還認為量子計算機要想解決經典計算機無法解決的任意問題還需要很多年。現在，人們認為這將在一兩年內發生。

至於厄米拉，解決了自己最喜歡的問題讓她有點茫然。她希望自己能明白，是什麼讓這個問題適合自己去研究。「我現在必須找到一個新問題，所以很希望能知道這個答案。」

然而，理論計算機科學家更多地是將厄米拉·馬哈德夫統一量子計算與密碼學一事視為對那些豐富多彩的思想脈絡的初步探索，而不是故事的結束。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！