來自加州大學(xué)伯克利分校的研究生Urmila Mahadev解決了量子計算中的驗證問題。她將經(jīng)典密碼學(xué)與量子領(lǐng)域進行結(jié)合，解決了“量子計算中最根本的問題之一?！奔?，如果你讓一臺量子計算機為你執(zhí)行一個計算，那么你如何確定它確實執(zhí)行了你的指令，甚至如何得知它是否做了與量子相關(guān)的事情。

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

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

Mahadev當時28歲，已經(jīng)在加州大學(xué)伯克利分校讀了7年研究生，很多急于畢業(yè)的學(xué)生早就離開了學(xué)校。她在伯克利的博士導(dǎo)師Umesh Vazirani說：“她現(xiàn)在終于有了一個非常漂亮的博士論文?！?/p>

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

五年多來，在她眼中想要解決的問題與其他人不同，Aaronson將此稱之為“量子計算中最為基礎(chǔ)的問題之一?！奔矗绻阕屢慌_量子計算機為你執(zhí)行一個計算，那么你如何確定它確實執(zhí)行了你的指令，甚至如何得知它是否做了與量子相關(guān)的事情。

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

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

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

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

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

Vazirani說：“量子計算機功能非常強大，但同時它也非常隱秘?！?/p>

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

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

但她拒絕放棄。Mahadev表現(xiàn)出一種前所未有的決心。而今，經(jīng)過八年的研究生學(xué)習(xí)生涯，Mahadev終于成功了。

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

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

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

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

量子計算研究人員不僅對Mahadev的協(xié)議所取得的成就感到高興，更對她為解決這個問題所采取的全新方法感到興奮。Vidick寫道，在量子領(lǐng)域使用經(jīng)典密碼學(xué)是一個“真正新穎的想法”。“我預(yù)計，在這些想法的基礎(chǔ)上，還會有更多的成果?！?/p>

漫漫研究路

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

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

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

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

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

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

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

2012年，包括Vazirani在內(nèi)的一組研究人員表示，如果量子計算是由一對無法相互通信的量子計算機進行的，那么一個完全經(jīng)典的驗證者就可以檢查量子計算。Gottesman說，但那份論文的方法是針對這種特定情形而設(shè)計的，這個問題似乎陷入了死胡同?！拔蚁肟赡苡腥苏J為你不能再往下進行了。”

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

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

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

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

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

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

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

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

Mahadev本可以憑借這些結(jié)果畢業(yè)，但她決心繼續(xù)研究，直到解決驗證問題?！拔覐奈聪脒^畢業(yè)，因為我的目標從來就不是畢業(yè)，”她說。

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

解決驗證問題

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

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

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

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

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

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

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

Aaronson說，Mahadev的協(xié)議可能在未來五年之內(nèi)都不可行，但“在幻想世界里也不是完全不可行”?！叭绻磺许樌诹孔佑嬎銠C發(fā)展的下一個階段，就可以開始思考這個問題了?！?/p>

考慮到這個領(lǐng)域現(xiàn)在發(fā)展的速度有多快，這個階段可能會很快到來。Vidick說，畢竟，就在五年前，研究人員還認為量子計算機要想解決經(jīng)典計算機無法解決的任何問題都還需要很多年。“現(xiàn)在，”他說，“人們認為這將在一兩年內(nèi)發(fā)生?！?/p>

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

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

“我感覺會有很多后續(xù)研究，”Aharonov說，“我期待著Urmila取得更多結(jié)果?！?/p>