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

2017年春天，Urmila Mahadev發(fā)現(xiàn)自己處于大多數(shù)研究生都會認(rèn)為相當(dāng)不錯的一個位置。她剛剛解決了量子計(jì)算領(lǐng)域的一個主要問題。量子計(jì)算是研究計(jì)算機(jī)的科學(xué)，它從量子物理學(xué)的奇怪定律中獲得強(qiáng)大的計(jì)算力。

德州大學(xué)奧斯汀分校的計(jì)算機(jī)科學(xué)家Scott Aaronson認(rèn)為，Mahadev關(guān)于“盲計(jì)算”的新成果與她之前的論文結(jié)合起來，顯然讓她成為“一顆冉冉升起的新星”

當(dāng)時(shí)28歲的Mahadev已經(jīng)在加州大學(xué)伯克利分校讀了七年研究生——遠(yuǎn)遠(yuǎn)超過了大多數(shù)學(xué)生迫切想要畢業(yè)的階段?，F(xiàn)在，正如她的博士導(dǎo)師Umesh Vazirani所說的，她終于有了一篇“非常漂亮的博士論文”。

但是那一年，Mahadev并沒有畢業(yè)，她甚至沒有考慮要畢業(yè)，因?yàn)槭虑檫€沒有完成呢。

量子計(jì)算+密碼學(xué)

在五年多的時(shí)間里，她還有另一個不同的研究目標(biāo)。她想解決的這個問題被Aaronson稱為“量子計(jì)算領(lǐng)域最基本的問題之一”，那就是：如果讓一臺量子計(jì)算機(jī)做計(jì)算，怎么知道它是否真的遵循了你的指令，或者它是否真的執(zhí)行了任何量子計(jì)算呢？

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

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

首先，量子計(jì)算機(jī)的內(nèi)部工作機(jī)制極其復(fù)雜：對于幾百個量子比特的計(jì)算機(jī)，要寫出關(guān)于其內(nèi)部狀態(tài)的描述將需要比整個可見宇宙還要大的一個硬盤。此外，即使有足夠的空間寫下這個描述，也沒有辦法得到它。通常，量子計(jì)算機(jī)的內(nèi)部狀態(tài)是許多不同的非量子的“經(jīng)典”態(tài)的疊加。（就像是薛定諤的貓，同時(shí)處于“死”和“活”的狀態(tài)）但是，一旦測量一個量子態(tài)，它就會坍縮為其中一個經(jīng)典態(tài)。凝視一臺300個量子比特的量子計(jì)算機(jī)，本質(zhì)上，你看到的只會是300個經(jīng)典比特，也就是0和1。

Vazirani說：“量子計(jì)算機(jī)非常強(qiáng)大，但是也非常神秘。”

考慮到這些限制，長久以來，計(jì)算機(jī)科學(xué)家一直好奇，是否有可能讓量子計(jì)算機(jī)提供任何嚴(yán)格的保證，證明它確實(shí)做了自己宣稱的事情。耶路撒冷希伯來大學(xué)的計(jì)算機(jī)科學(xué)家Dorit Aharonov問道：“量子和經(jīng)典世界之間的相互作用是否足夠強(qiáng)大，以至于能夠進(jìn)行對話呢？”

在研究生二年級的時(shí)候，Mahadev被這個問題迷住了，其中的原因連她自己都不完全明白。在隨后的幾年里，她嘗試了一種又一種方法。她說：“有很多次，我覺得自己做著正確的事情，但是接著就出錯了，有時(shí)很快，有時(shí)過了一年才出現(xiàn)?！?/p>

但是，Mahadev拒絕放棄。她表現(xiàn)出了Vazirani從未見過的持久的決心，Vazirani說：“從這個意義上說，Mahadev絕對是與眾不同的?！?/p>

現(xiàn)在，經(jīng)過八年的研究生學(xué)習(xí)，Mahadev終于成功了！她提出了一種交互式協(xié)議，通過這種協(xié)議，沒有量子計(jì)算能力的用戶也可以使用經(jīng)典的密碼學(xué)讓量子計(jì)算機(jī)做任何他們想做的事情，并確信量子計(jì)算機(jī)正在遵循他們的命令，就像是牽著馬具任意馳騁一樣。Vazirani說，Mahadev的方法給用戶提供了“讓計(jì)算機(jī)無法擺脫的手段“。

○Mahadev提出的協(xié)議。| 圖片來源：https://arxiv.org/pdf/1804.01082.pdf

Aaronson說，一個研究生能夠獨(dú)自完成這樣一個任務(wù)”非常令人震驚“。

Mahadev現(xiàn)在是伯克利大學(xué)的博士后研究員。近日，她在計(jì)算機(jī)科學(xué)基金會的年度研討會——理論計(jì)算機(jī)領(lǐng)域最大型的會議之一——上提交了自己的方案。她的作品獲得了這次會議的”最佳論文“和”最佳學(xué)生論文“獎，這對一位理論計(jì)算機(jī)科學(xué)家來說是罕見的榮譽(yù)。

加州理工學(xué)院的計(jì)算機(jī)科學(xué)家Thomas Vidick過去曾與Mahadev合作過，他在博客文章中寫道，Mahadev的研究成果是”近年來量子計(jì)算和理論計(jì)算機(jī)科學(xué)的交叉處出現(xiàn)的最杰出的思想之一“。

量子計(jì)算領(lǐng)域的研究人員之所以興奮，不僅是因?yàn)镸ahadev的協(xié)議能夠解決問題，還因?yàn)樗秊榻鉀Q這個問題所采取的全新方法。Vidick寫道，在量子計(jì)算領(lǐng)域使用經(jīng)典的密碼學(xué)真的是非常新穎的想法，”我希望，在這些想法的基礎(chǔ)上，會繼續(xù)產(chǎn)生更多成果。“

漫長的證明之路

Mahadev在洛杉磯的一個醫(yī)生家庭長大，她就讀于南加州大學(xué)，在那里，她從一個研究領(lǐng)域漂流到另一個。起初，她只確信一點(diǎn)，那就是自己不想成為一名醫(yī)生。后來，計(jì)算機(jī)科學(xué)家Leonard Adleman——RSA加密算法的三位創(chuàng)造者中的A——講授的一門課程讓她對理論計(jì)算機(jī)科學(xué)產(chǎn)生了興趣。之后，她申請成為加州大學(xué)伯克利分校的研究生，并在申請材料中解釋說，自己對理論計(jì)算機(jī)科學(xué)的所有方面都感興趣，除了量子計(jì)算。因?yàn)榱孔佑?jì)算“聽起來像是非常古怪的事情，是我知道得最少的事情”。

然而，一到伯克利，Vazirani深入淺出的解釋很快改變了她的想法。他向她介紹了一個問題——如何找到一個驗(yàn)證量子計(jì)算的協(xié)議？而這個問題“激發(fā)了她的想象力”，Vazirani說道。

Mahadev解釋說：“協(xié)議就像是謎題。對我來說，這種問題似乎比其他問題更容易，因?yàn)槟憧梢宰约毫⒓撮_始思考協(xié)議，然后破解它們，這樣你就會發(fā)現(xiàn)它們是如何運(yùn)作的?！?她選擇這個問題作為自己的博士研究課題，開始了Vazirani所說的“漫漫長路”。

○Urmila Mahadev。| 圖片來源：Quanta Magazine

如果一臺量子計(jì)算機(jī)可以解決經(jīng)典計(jì)算機(jī)無法解決的問題，那并不必然意味著解決方案將難以檢驗(yàn)。以大數(shù)的因數(shù)分解為例，一臺大型量子計(jì)算機(jī)可以高效解決這個問題，但經(jīng)典計(jì)算機(jī)被認(rèn)為無法完成這個任務(wù)。

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

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

鑒于這一點(diǎn)，大約在2004年，圓周理論物理研究所的物理學(xué)家Daniel Gottesman提出一個問題：是否有可能提出任何一種協(xié)議，通過這個協(xié)議，一臺量子計(jì)算機(jī)可以向非量子觀察者證明自己確實(shí)完成了聲稱的那些事情？

在四年內(nèi)，量子計(jì)算的研究人員已經(jīng)得到了部分答案。兩個不同的團(tuán)隊(duì)證明，一臺量子計(jì)算機(jī)有可能證明它的計(jì)算，但是不是向一臺純粹經(jīng)典的驗(yàn)證設(shè)備，而是向一個能夠進(jìn)入自己內(nèi)部非常小的量子計(jì)算機(jī)的驗(yàn)證設(shè)備。研究人員后來改進(jìn)了這種方法，并證明，驗(yàn)證設(shè)備所需要的只是每一次測量單個量子比特的能力。

2012年，包括Vazirani在內(nèi)的一組研究人員證明，如果量子計(jì)算是由一對無法相互通信的量子計(jì)算機(jī)進(jìn)行的，那么，一臺完全經(jīng)典的驗(yàn)證設(shè)備就能夠檢查量子計(jì)算。Gottesman表示，那篇論文的方法是針對這種特定情形設(shè)計(jì)的，這個問題似乎陷入了死胡同，一些人認(rèn)為不能再往前走了。

大約就在這個時(shí)候，Mahadev遇到了這個驗(yàn)證問題。起初，她試圖得到一個“無條件”的結(jié)果，一個并不假定量子計(jì)算機(jī)能做什么或不能做什么的結(jié)果。

在她研究這個問題一段時(shí)間，且并沒有取得任何進(jìn)展后，Vazirani建議了一種不同的可能性——用“后量子”加密（post-quantum cryptography）。研究人員認(rèn)為，這是一種即使量子計(jì)算機(jī)也無法破解的加密方法，雖然他們還不確定。

像RSA加密算法之類用于加密在線交易等信息的方法不是后量子的，也就是說，一臺量子計(jì)算機(jī)能夠破解這種加密方法，因?yàn)樗鼈兊陌踩匀Q于對大數(shù)做因數(shù)分解的難度。

2016年，Mahadev和Vazirani在解決另一個問題的時(shí)候取得了進(jìn)展，這在后來被證明是至關(guān)重要的。

他們與如今在OpenAI公司工作的計(jì)算機(jī)科學(xué)家Paul Christiano合作，開發(fā)了一種方法，使用密碼學(xué)讓量子計(jì)算機(jī)構(gòu)建所謂的“加密態(tài)（secret state）”，這個加密態(tài)的描述對于經(jīng)典的驗(yàn)證設(shè)備是已知的，但是對于量子計(jì)算機(jī)本身卻是未知的。

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

有了這樣一個函數(shù)，就可以讓量子計(jì)算機(jī)按照下面的步驟構(gòu)建一個加密態(tài)：

首先，讓計(jì)算機(jī)構(gòu)建一個所有可能的函數(shù)輸入的疊加（這聽起來或許很復(fù)雜，但是事實(shí)上很容易）；

然后，讓計(jì)算機(jī)將函數(shù)應(yīng)用到這個巨大的疊加上，函數(shù)的所有可能輸出的疊加構(gòu)成一個新的態(tài)。

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

接下來，要求計(jì)算機(jī)測量輸出態(tài)，并告訴我們結(jié)果。這個測量會導(dǎo)致輸出態(tài)坍縮為所有可能輸出中的一個，而輸入態(tài)也會立即坍縮以與之匹配，因?yàn)樗鼈儽舜思m纏。例如，對于平方方程，如果測量得到的輸出態(tài)是9，那么輸入態(tài)會坍縮為3和?3的疊加態(tài)。

但是，如果使用的是暗門函數(shù)，那么我們就有暗門的秘鑰，因此可以很容易地找出構(gòu)成輸入態(tài)的兩種疊加態(tài)。然而，量子計(jì)算機(jī)不能。量子計(jì)算機(jī)不能簡單地測量輸入的疊加來求出它的構(gòu)成，因?yàn)闇y量會進(jìn)一步讓輸入的疊加坍縮，讓計(jì)算機(jī)只剩下其中一個輸入態(tài)，而無法求出另一個。

2017年，Mahadev使用一種名為“錯誤學(xué)習(xí)（Learning With Errors，LWE）”的加密技術(shù)，找到了在加密態(tài)方法的核心構(gòu)建暗門函數(shù)的方法。利用暗門函數(shù)，她就能夠創(chuàng)建一個量子版本的“盲”計(jì)算，使得云計(jì)算用戶可以屏蔽他們的數(shù)據(jù)，這樣云計(jì)算機(jī)即使在計(jì)算時(shí)也無法讀取數(shù)據(jù)。

不久之后，Mahadev、Vazirani 、Christiano與Vidick、Zvika Brakerski（以色列魏茨曼科學(xué)研究所的科學(xué)家）合作，進(jìn)一步改進(jìn)這些暗門函數(shù)，利用加密態(tài)方法發(fā)展出一種讓量子計(jì)算機(jī)產(chǎn)生可證實(shí)的真隨機(jī)數(shù)的安全方法。

Mahadev 本可以憑借這些結(jié)果畢業(yè)，但她決心繼續(xù)工作，直到解決驗(yàn)證問題。她說：“我從來沒有想畢業(yè)的事情，因?yàn)槲业哪繕?biāo)從來就不是畢業(yè)?！?/p>

不知道能否解決這個問題有時(shí)會讓人感到壓力，但是，她說：“我花時(shí)間學(xué)習(xí)自己感興趣的東西，因此，這也就不是真的在浪費(fèi)時(shí)間。”

如何加密？

Mahadev嘗試了各種方法，試圖從加密態(tài)方法抵達(dá)一種驗(yàn)證協(xié)議，但是有一段時(shí)間，她一無所獲。然后，她有了一個想法：研究人員已經(jīng)證明，如果驗(yàn)證設(shè)備能夠測量量子比特，它就能夠檢驗(yàn)量子計(jì)算機(jī)。根據(jù)定義，一個經(jīng)典的驗(yàn)證設(shè)備缺乏這種能力。但是，如果這個經(jīng)典的驗(yàn)證設(shè)備能夠以某種方式強(qiáng)迫量子計(jì)算機(jī)自己進(jìn)行測量，然后誠實(shí)地報(bào)告測量結(jié)果呢？

Mahadev意識到，最棘手的部分是，在量子計(jì)算機(jī)知道驗(yàn)證設(shè)備會要求哪種測量之前，就讓量子計(jì)算機(jī)確定它將要測量的狀態(tài)。否則，量子計(jì)算機(jī)很容易欺騙驗(yàn)證設(shè)備。這正是加密態(tài)方法發(fā)揮作用的地方：Mahadev的協(xié)議要求量子計(jì)算機(jī)首先創(chuàng)建一個加密態(tài)，然后將它與應(yīng)該測量的狀態(tài)糾纏在一起。只有到那時(shí)，計(jì)算機(jī)才會知道要進(jìn)行何種測量。

由于量子計(jì)算機(jī)不知道加密態(tài)的構(gòu)成，但驗(yàn)證設(shè)備知道，Mahadev證明，量子計(jì)算機(jī)不可能在不留下明顯的欺騙痕跡的情況下做出嚴(yán)重的欺騙。

Vidick寫道，本質(zhì)上，計(jì)算機(jī)要測量的量子比特被“設(shè)置為密碼石”。正因?yàn)槿绱?，如果測量結(jié)果看起來像是一個正確的證明，驗(yàn)證設(shè)備就能確信它們真的是。“真是個好主意！每一次Urmila解釋它的時(shí)候，我都驚呆了。”

量子計(jì)算機(jī)不能破解的密碼？

Mahadev的驗(yàn)證協(xié)議，連同隨機(jī)數(shù)生成器和盲加密方法，都取決于量子計(jì)算機(jī)不能破解LWE的假設(shè)。目前，LWE被廣泛認(rèn)為是后量子密碼學(xué)的優(yōu)先候選對象，而且，它或許很快會被美國國家標(biāo)準(zhǔn)與技術(shù)研究所（NIST）采用作為其新的加密標(biāo)準(zhǔn)，取代那些量子計(jì)算機(jī)可能破解的方法。

Gottesman警告說，這并不能確保這種加密方法真的能抵御量子計(jì)算機(jī)，“但是到目前為止，這種方法是可靠的，還沒有人找到證據(jù)，證明這種方法有可能被破解?！?/p>

Vidick寫道，無論如何，協(xié)議對LWE的依賴給Mahadev的作品帶來了雙贏的意味。量子計(jì)算機(jī)可能欺騙協(xié)議的唯一方法是，量子計(jì)算領(lǐng)域的某個人找到了破解LWE的方法，而這本身將會是一項(xiàng)了不起的成就。

Mahadev的協(xié)議不太可能在不久的將來就在真正的量子計(jì)算機(jī)上實(shí)現(xiàn)。目前，這個協(xié)議需要太多的計(jì)算能力，因而不太有實(shí)用性。但在未來幾年，隨著量子計(jì)算機(jī)越來越大，以及研究人員對協(xié)議進(jìn)行簡化，情況可能會改變。

Aaronson說，Mahadev的協(xié)議可能在未來五年內(nèi)都沒有可行性，但是，“在假想世界里也不是完全不可行。如果一切順利，在量子計(jì)算機(jī)演化的下一個階段，就可以開始思考這個問題?！?/p>

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

至于Mahadev，解決了自己最喜歡的問題讓她有點(diǎn)茫然。她希望自己能明白，是什么讓這個問題適合自己去研究。“我現(xiàn)在必須找到一個新問題，所以很希望能知道這個答案?！?/p>

然而，理論計(jì)算機(jī)科學(xué)家更多地是將Mahadev統(tǒng)一量子計(jì)算與密碼學(xué)一事視為對那些豐富多彩的思想脈絡(luò)的初步探索，而不是故事的結(jié)束。