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

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

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

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

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

五年多來(lái)，在她眼中想要解決的問(wèn)題與其他人不同，Aaronson將此稱之為“量子計(jì)算中最為基礎(chǔ)的問(wèn)題之一。”即，如果你讓一臺(tái)量子計(jì)算機(jī)為你執(zhí)行一個(gè)計(jì)算，那么你如何確定它確實(shí)執(zhí)行了你的指令，甚至如何得知它是否做了與量子相關(guān)的事情。

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

但是，一旦量子計(jì)算機(jī)能夠完成經(jīng)典計(jì)算機(jī)無(wú)法完成的計(jì)算，我們?cè)趺粗浪欠裾_地完成了這些計(jì)算呢?

如果你不信任一臺(tái)普通的電腦，理論上，你可以自己仔細(xì)檢查它在計(jì)算過(guò)程中的每一個(gè)步驟。

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

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

Vazirani說(shuō)：“量子計(jì)算機(jī)功能非常強(qiáng)大，但同時(shí)它也非常隱秘。”

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

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

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

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

Aaronson說(shuō)：“對(duì)于一個(gè)研究生來(lái)說(shuō)，獨(dú)自完成這樣一個(gè)任務(wù)是非常令人震驚的！”

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

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

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

漫漫研究路

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

她說(shuō)：“量子計(jì)算聽(tīng)起來(lái)特別遙遠(yuǎn)，我對(duì)它一無(wú)所知。”

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

“協(xié)議就像謎題，”Mahadev解釋說(shuō)。對(duì)我來(lái)說(shuō)，這些問(wèn)題似乎比其他問(wèn)題更容易回答，因?yàn)槟憧梢宰约毫⒓撮_(kāi)始思考協(xié)議，然后打破它們，這樣你就能看到它們是如何工作的。她選擇了這個(gè)問(wèn)題作為她的博士研究課題，開(kāi)始了她的“漫漫長(zhǎng)路”。

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

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

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

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

大約在這個(gè)時(shí)候Mahadev遇到了驗(yàn)證問(wèn)題。

起初，她試圖得出一個(gè)“無(wú)條件”的結(jié)果，一個(gè)對(duì)量子計(jì)算機(jī)能做什么或不能做什么的假設(shè)。但是，在她研究這個(gè)問(wèn)題一段時(shí)間沒(méi)有取得任何進(jìn)展后，Vazirani提出了使用“后量子”加密的可能性——也就是說(shuō)，研究人員認(rèn)為即使量子計(jì)算機(jī)也無(wú)法破解這種加密，盡管他們不確定。(用于加密在線交易等信息的RSA算法等方法并不是后量子算法——大型量子計(jì)算機(jī)可能會(huì)破壞它們，因?yàn)樗鼈兊陌踩砸蕾囉诜纸獯髷?shù)的難度。)

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

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

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

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

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

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

Mahadev本可以憑借這些結(jié)果畢業(yè)，但她決心繼續(xù)研究，直到解決驗(yàn)證問(wèn)題。“我從未想過(guò)畢業(yè)，因?yàn)槲业哪繕?biāo)從來(lái)就不是畢業(yè)，”她說(shuō)。

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

解決驗(yàn)證問(wèn)題

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

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

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

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

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

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

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

Aaronson說(shuō)，Mahadev的協(xié)議可能在未來(lái)五年之內(nèi)都不可行，但“在幻想世界里也不是完全不可行”。“如果一切順利，在量子計(jì)算機(jī)發(fā)展的下一個(gè)階段，就可以開(kāi)始思考這個(gè)問(wèn)題了。”

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

至于Mahadev，解決了她最喜歡的問(wèn)題讓她有點(diǎn)茫然。她希望找到一個(gè)新問(wèn)題。

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

“我感覺(jué)會(huì)有很多后續(xù)研究，”Aharonov說(shuō)，“我期待著Urmila取得更多結(jié)果。”