來自加州大學伯克利分校的研究生Urmila Mahadev解決了量子計算中的驗證問題。她將經典密碼學與量子領域進行結合，解決了“量子計算中最根本的問題之一。”即，如果你讓一臺量子計算機為你執行一個計算，那么你如何確定它確實執行了你的指令，甚至如何得知它是否做了與量子相關的事情。

2017年春天，Urmila Mahadev解決了量子計算中的一個重要問題，即從量子物理學的奇怪定律中獲得能量的計算機研究。Mahadev的新成果與她之前的論文結合在一起，被稱為“盲計算（blind computation）”。

德克薩斯大學奧斯汀分校的計算機科學家Scott Aaronson說：“她顯然是一顆冉冉升起的新星。”

Mahadev當時28歲，已經在加州大學伯克利分校讀了7年研究生，很多急于畢業的學生早就離開了學校。她在伯克利的博士導師Umesh Vazirani說：“她現在終于有了一個非常漂亮的博士論文。”

但是Mahadev并沒有在那年選擇畢業，她甚至沒有考慮過畢業。她覺得她的夢想并沒有完成。

五年多來，在她眼中想要解決的問題與其他人不同，Aaronson將此稱之為“量子計算中最為基礎的問題之一。”即，如果你讓一臺量子計算機為你執行一個計算，那么你如何確定它確實執行了你的指令，甚至如何得知它是否做了與量子相關的事情。

這個問題可能很快就會遠離學術界。研究人員希望，過不了太多年，量子計算機就能在許多問題上提供指數級的加速，例如模擬黑洞周圍的行為、模擬大蛋白質的折疊方式等。

但是，一旦量子計算機能夠完成經典計算機無法完成的計算，我們怎么知道它是否正確地完成了這些計算呢?

如果你不信任一臺普通的電腦，理論上，你可以自己仔細檢查它在計算過程中的每一個步驟。

但是量子系統從根本上來說是抵制這種檢查的。首先，它們的內部工作是極其復雜的：用幾百個量子比特（quantum bit）來描述一臺計算機的內部狀態需要一個比整個可見宇宙都大的硬盤。

即使你有足夠的空間寫下這個描述，也沒有辦法得到它。量子計算機的內部狀態通常是許多不同的非量子“經典”狀態的疊加（比如薛定諤的貓，它既死又活）。但是一旦你測量一個量子態，它就會崩潰成一個經典態。

Vazirani說：“量子計算機功能非常強大，但同時它也非常隱秘。”

考慮到這些限制因素，計算機科學家們長期以來一直想知道量子計算機是否有可能提供任何證據能夠證明它確實做到了聲明的那些功能。耶路撒冷希伯來大學的計算機科學家Dorit Aharonov問道：“量子和古典世界之間的相互作用是否足夠強大到可以進行對話?”

在研究生二年級的時候，馬哈德夫被這個問題迷住了，原因連她自己都不完全明白。在隨后的幾年里，她嘗試了一種接一種的方法。她說：“有很多次我覺得做得不錯的時候，要么很快就失敗了，要么做了一年才發現是失敗的。”

但她拒絕放棄。Mahadev表現出一種前所未有的決心。而今，經過八年的研究生學習生涯，Mahadev終于成功了。

她提出了一種交互式協議，通過這種協議，沒有量子能力的用戶可以使用密碼學在量子計算機上安裝一個套具，并在他們想要的任何地方驅動它，并保證量子計算機正在遵循他們的指令。

Aaronson說：“對于一個研究生來說，獨自完成這樣一個任務是非常令人震驚的！”

Mahadev現在是UC Berkeley的博士后研究員。昨天，她在計算機科學基金會（foundation of Computer Science）年度研討會上提交了自己的方案。她的作品獲得了該會議的“最佳論文”和“最佳學生論文”獎，這對一位理論計算機科學家來說是罕見的榮譽。

加州理工學院(California Institute of Technology)的計算機科學家Thomas Vidick過去曾與Mahadev有過合作，他在一篇博客文章中稱，Mahadev的研究成果“是近年來量子計算和理論計算機科學領域出現的最杰出的思想之一”。

量子計算研究人員不僅對Mahadev的協議所取得的成就感到高興，更對她為解決這個問題所采取的全新方法感到興奮。Vidick寫道，在量子領域使用經典密碼學是一個“真正新穎的想法”。“我預計，在這些想法的基礎上，還會有更多的成果。”

漫漫研究路

Mahadev在洛杉磯的一個醫生家庭長大，她就讀于南加州大學，她從一個學習領域徘徊到另一個領域，只是不想成為一名醫生。后來，計算機科學家Leonard Adleman教授的一門課讓她對理論計算機科學感到興奮。她申請了UC Berkeley的研究生院，在申請材料中解釋說她對理論計算機科學的所有方面都感興趣——除了量子計算。

她說：“量子計算聽起來特別遙遠，我對它一無所知。”

但是當她在伯克利的時候，Vazirani通俗易懂的解析很快改變了她的想法。他向她介紹了如何找到驗證量子計算的協議，這個問題“激發了她的想象力”，Vazirani說。

“協議就像謎題，”Mahadev解釋說。對我來說，這些問題似乎比其他問題更容易回答，因為你可以自己立即開始思考協議，然后打破它們，這樣你就能看到它們是如何工作的。她選擇了這個問題作為她的博士研究課題，開始了她的“漫漫長路”。

如果量子計算機可以解決一個經典計算機無法解決的問題，那并不意味著解決方案將難以檢驗。以大數因式分解為例，這是一個大型量子計算機可以有效解決的問題，但一般認為任何經典計算機都無法解決。即使經典計算機不能因式分解一個數字，它也可以很容易地檢查量子計算機的因式分解是否正確——它只需要把這些因子相乘，看看它們是否產生了正確的答案。

然而，計算機科學家認為（并且最近向證明邁出了一步）量子計算機可以解決的許多問題并沒有這個特征。換句話說，經典計算機不僅無法解決這些問題，甚至無法識別所提出的解決方案是否正確。鑒于此，于2004年左右，安大略省滑鐵盧周界理論物理研究所的物理學家Daniel Gottesman提出了一個問題，即，如果你讓一臺量子計算機為你執行一個計算，那么你如何確定它確實執行了你的指令，甚至如何得知它是否做了與量子相關的事情。

在四年時間里，量子計算研究人員已經得到了部分答案。兩個不同的團隊表明，量子計算機可以證明它的計算，不是一個純粹的經典驗證者（classical verifier），而是對一個能夠訪問它自己的非常小的量子計算機的驗證者。研究人員后來改進了這種方法，以表明驗證者所需要的是每次測量一個量子比特的能力。

2012年，包括Vazirani在內的一組研究人員表示，如果量子計算是由一對無法相互通信的量子計算機進行的，那么一個完全經典的驗證者就可以檢查量子計算。Gottesman說，但那份論文的方法是針對這種特定情形而設計的，這個問題似乎陷入了死胡同。“我想可能有人認為你不能再往下進行了。”

大約在這個時候Mahadev遇到了驗證問題。

起初，她試圖得出一個“無條件”的結果，一個對量子計算機能做什么或不能做什么的假設。但是，在她研究這個問題一段時間沒有取得任何進展后，Vazirani提出了使用“后量子”加密的可能性——也就是說，研究人員認為即使量子計算機也無法破解這種加密，盡管他們不確定。(用于加密在線交易等信息的RSA算法等方法并不是后量子算法——大型量子計算機可能會破壞它們，因為它們的安全性依賴于分解大數的難度。)

2016年，Mahadev和Vazirani在研究另一個問題時取得了進步，這在后來被證明是至關重要的。他們與OpenAI的研究科學家Paul Christiano合作，開發了一種利用密碼學的方法來讓量子計算機構建所謂的“secret state”——一種其描述為經典驗證者（classical verifier）所知，而不是為量子計算機本身所知的狀態。

他們的程序依賴于“陷門”（trapdoor）函數，這種函數很容易執行，但很難逆轉，除非你有一個私密的加密密鑰。（研究人員還不知道如何真正構建一個合適的陷門函數。）函數也要求是“2對1”，這意味著每個輸出對應兩個不同的輸入。例如，平方函數——除了0，每個輸出（例如9）有兩個對應輸入（3和?3）。

有了這樣一個函數，你就可以讓量子計算機創建一個secret state，如下所示：首先，要求計算機建立一個所有可能的函數輸入的疊加。然后，告訴計算機將函數應用到這個巨大的疊加上，創建一個新的狀態，這個狀態是函數的所有可能輸出的疊加。輸入和輸出的疊加會產生糾纏，這意味著其中對一個的測量結果會立即影響到另一個。

接下來，要求計算機測量輸出狀態并告訴你結果。此測量將輸出狀態坍縮（collapse）為只有一個可能的輸出，并且輸入狀態立即坍縮來匹配它，因為它們是糾纏的——例如，如果使用平方函數，如果輸出是9的狀態，輸入將會坍縮成3和?3的疊加態。

但要記住，你使用的是trapdoor函數。你有trapdoor的密鑰，所以你可以很容易地找出構成輸入疊加的兩個態。但是量子計算機不能。它不能簡單地測量輸入疊加來求出它是由什么態構成的，因為這個測量會使它進一步坍縮，讓計算機只剩下兩個輸入中的一個，但無法找出另一個。

2017年，Mahadev通過一種名為“Learning With Errors”（LWE）的加密技術，找到了如何在secret-state方法的核心構建trapdoor函數的方法。利用這些trapdoor函數，她能夠創建一個量子版本的“盲”計算（blind computation），通過這種計算，云計算用戶可以屏蔽他們的數據，這樣云計算機即使在計算時也無法讀取數據。不久之后，Mahadev、Vazirani和Christiano與Vidick和Zvika Brakerski（以色列魏茨曼科學研究所的科學家）合作，進一步完善了這些trapdoor函數，利用secret-state方法開發了一種量子計算機生成可證實的隨機數的簡單方法。

Mahadev本可以憑借這些結果畢業，但她決心繼續研究，直到解決驗證問題。“我從未想過畢業，因為我的目標從來就不是畢業，”她說。

她不知道是否能解決這個問題，這有時會讓人感到壓力。但是，她說：“我花時間學習感興趣的東西，所以這真的不能說是浪費時間。”

解決驗證問題

Mahadev嘗試了從secret-state方法到驗證協議的各種方法，但有一段時間她一無所獲。然后她產生了一個想法：研究人員已經證明，如果一個驗證者（verifier）能夠測量量子比特，它就可以檢驗量子計算機。根據定義，classical verifier缺乏這種能力。但是，如果classical verifier能夠以某種方式強迫量子計算機執行測量并誠實地報告它們，結果會怎樣呢？

Mahadev意識到，最棘手的部分是讓量子計算機在它知道verifier會要求哪種測量方法之前，先確定它要測量的state——否則，計算機很容易欺騙verifier。這就是secret-state方法發揮作用的地方：Mahadev的協議要求量子計算機首先創建一個secret state，然后將其與它應該測量的state糾纏在一起。只有這樣，計算機才知道要執行哪種測量。

由于計算機不知道secret state的構成，但verifier知道，Mahadev表明，量子計算機不可能在不留下明顯的欺騙痕跡的情況下進行大型作弊。Vidick寫道，從本質上講，計算機要測量的量子比特被“加密且固定不變”。因此，如果測量結果看起來像一個正確的證明，verifier就能確信它們確實是。

“這是一個非常好的想法！””Vidick寫道，“每次Urmila解釋它的時候，都讓我感到震驚。”

Mahadev的驗證協議——以及隨機數生成器和盲加密方法——取決于量子計算機不能破解LWE的假設。目前，LWE被廣泛認為是后量子密碼學的主要候選，可能很快就會被國家標準和技術研究所采用作為其新的加密標準，以取代量子計算機可能破解的標準。Gottesman警告說，這并不能保證它對量子計算機是安全的，“但到目前為止它還很穩固，還沒有證據證明它可能被破解。”

Vidick寫道，無論如何，該協議對LWE的依賴使得Mahadev的工作帶來了雙贏。量子計算機欺騙協議的唯一方法是量子計算世界中有人找到了破解LWE的方法，這本身就是一項了不起的成就。

Mahadev的協議不太可能在不久的將來在真正的量子計算機上實現。目前，該協議需要很大的計算能力才能實現實用。但隨著量子計算機規模的越來越大，以及研究人員簡化協議，未來這種情況可能會改變。

Aaronson說，Mahadev的協議可能在未來五年之內都不可行，但“在幻想世界里也不是完全不可行”。“如果一切順利，在量子計算機發展的下一個階段，就可以開始思考這個問題了。”

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

至于Mahadev，解決了她最喜歡的問題讓她有點茫然。她希望找到一個新問題。

但理論計算機科學家認為，Mahadev將量子計算和密碼學統一起來與其說是故事的結束，不如說是有望證明許多觀點的初步探索。

“我感覺會有很多后續研究，”Aharonov說，“我期待著Urmila取得更多結果。”