Urmila Mahadev在研究生院學習了八年，最終獨立解決了量子計算中最基本的問題之一：如何知道量子計算機是否已經(jīng)完成了任何量子計算？

2017年春天，加州大學伯克利分校的博士研究生Urmila Mahadev突然發(fā)現(xiàn)自己成了他人眼中的傾佩對象。她解決了量子計算中的一個主要問題，結(jié)合之前發(fā)表的論文，她儼然已經(jīng)成為學界一顆冉冉升起的新星。但28歲的她卻放棄了畢業(yè)，甚至壓根沒有考慮過畢業(yè)。

這是她在伯克利研究生院求學的第七年——很久之前，大多數(shù)學生都已經(jīng)不耐煩地畢業(yè)了。

Urmila Mahadev

早在五年前，她的目光就被一個與眾不同的研究問題所吸引，Aaronson稱之為“量子計算中你可以提出的最基本問題之一”，即：如果你要求量子計算機執(zhí)行計算，那你該怎么判斷它是否按指示執(zhí)行了任務，甚至只是做了任何和量子計算有關(guān)的事？

現(xiàn)在這個問題即將遠離學界。在過去的幾年里，研究人員一直希望能把量子計算機用于科研，從研究黑洞周圍的變化到大蛋白質(zhì)折疊，量子計算帶來的加速效果是指數(shù)級的。但是，一旦量子計算機真正執(zhí)行了經(jīng)典計算機無法做到的計算，那人類該怎么確保計算結(jié)果的可信度？

如果我們不相信經(jīng)典計算機的結(jié)果，我們可以從頭開始一步步驗證，但量子系統(tǒng)是從根本上就抵制這種檢查的。首先，它們的內(nèi)部工作非常復雜：即便只用幾百個量子比特（或“量子位”）寫下計算機內(nèi)部狀態(tài)的描述，那也需要一個比整個可見宇宙更大的硬盤。

其次，即便我們以某種方式記下這個描述，它也是難以理解的。量子計算機的內(nèi)部狀態(tài)通常是許多不同的非量子“經(jīng)典”狀態(tài)的疊加，如“薛定諤的貓”。但是，一旦你測量了一個量子態(tài)，它就會坍縮成這些經(jīng)典狀態(tài)中的一個。也就是說，當看著量子計算機里的300個量子比特時，我們基本上只能看到300個經(jīng)典比特——0和1。

“量子計算機非常強大，但它也非常隱秘?！?/p>

考慮到這些限制因素，計算機科學家們長期以來一直想知道量子計算機是否能提供一些“鐵證”，證明自己已經(jīng)完成某些計算。這也是量子計算和古典計算進行“對話”的橋梁。Mahadev被這個問題迷住是在她讀研究生的第二年，在之后的幾年里，她一直反復嘗試驗證方法，而在無數(shù)挫折中，她也展現(xiàn)了自己持久的耐心和決心。

經(jīng)過多年努力，現(xiàn)在她終于讓學界見證了她的成功。10月7日，計算機科學頂會FOCS 2018在法國巴黎正式召開，這是理論計算機科學最大的會議之一。在會上，Mahadev帶來了論文Classical Verification of Quantum Computations，她提出了一種交互式協(xié)議，用密碼學為量子計算這批野馬安上了“馬鞍”。她的作品被授予會議“最佳論文”和“最佳學生論文”獎，這是理論計算機科學家難得的榮譽。

一條漫長的道路

Mahadev在洛杉磯的一個醫(yī)生家庭長大，出于對成為醫(yī)生的抵觸心理，她在南加州大學求學期間聽了RSA加密算法的創(chuàng)造者之一、計算機科學家Leonard Adleman教授的課程，并把專業(yè)改成了理論計算機科學。直到在向伯克利研究生院遞交申請之前，量子計算于她都是最陌生、最不了解的事情。

但是，到了伯克利，一切就完全不同了。她的博士生導師Umesh Vazirani向她介紹了一個問題：找到一個驗證量子計算的協(xié)議。這個問題徹底激發(fā)了她的學術(shù)熱情。

有一個基礎(chǔ)事實是，也許量子計算機可以解決經(jīng)典計算機無法解決的問題，但它的解決方案不一定是難以驗證的。比如分解大數(shù)字，這是個經(jīng)典計算機無法計算而量子計算機可以高效解決的任務。雖然無法計算，可驗證量子計算機的因子分解是否正確對經(jīng)驗計算機來說很容易——它只需要將這些因子相乘，看看它們是否能產(chǎn)生正確的答案。

然而，計算機科學家認為量子計算機可以解決的許多問題不具備上述特征。換句話說，經(jīng)典計算機不僅無法解決它們，甚至也識別不了解決方案是否正確。鑒于此，2004年的時候，物理學家Daniel Gottesman把“量子驗證”這個問題拋給學界。

問題提出的四年內(nèi)，一些量子計算研究人員得到了部分答案。兩個不同的團隊證實確實存在一種能證明已經(jīng)完成量子計算的方法，他們的一個關(guān)鍵想法是利用交互性證明，即給定一定的計算，使得設(shè)備（以下稱為“證明者”）具有執(zhí)行計算的能力，但是另一個實體（以下稱為“驗證者”）不具有。假設(shè)證明者是不受信任的，也可能會欺騙驗證者，我們要找出一種方法，讓驗證者從證明者手中拿到高度可信的正確答案。

這個框架起源于20世紀90年代的復雜性理論。其中最簡單的方法是驗證者可以自己執(zhí)行驗證計算，直接檢查證明者的結(jié)果。第二種方法是驗證者無法執(zhí)行計算，但證明者可以提供一個簡短的“證據(jù)”，再由前者完全證明結(jié)果。交互式證明是一種協(xié)議，通過該協(xié)議，驗證者可以和更強大但不可信的證明者進行交互。

在Mahadev的成果出現(xiàn)之前，學界通過引入交互式模型，允許驗證者使用非常有限的量子計算機，在“量子驗證”這個問題上取得了一定進展。簡而言之，如果采用上述第一種方法，就是讓驗證者具備在它選擇的兩個可能的基礎(chǔ)中準備單個量子比特的能力，一次一個，由它把量子比特發(fā)送給證明者；如果采用第二種方法，就是讓驗證者可以一次一個地從證明者處接收單個量子比特，并在它選擇的兩個基礎(chǔ)之一中對它們進行驗證。

一般情況下，這兩種方法都能驗證任意多項式時間量子計算，而其中的重點是驗證者準備量子比特的能力，使證明者可以檢測到“證據(jù)”與預先確定的“誠實行為”是否存在偏差。

但問題依然存在：十年了，對于量子計算機這個“證明者”，我們能否找到一個完全經(jīng)典的“驗證者”？

2012年，包括Vazirani在內(nèi)的一組研究人員表明，如果一個量子計算機是由一對無法相互通信的量子計算機執(zhí)行的，那么一個完全經(jīng)典的驗證器可以檢查量子計算。雖然這篇論文只討論了某種特定狀態(tài)，但它給Mahadev帶來了啟發(fā)：是否能找到一個“無條件”的結(jié)果，一個不假設(shè)量子計算機能做什么或不做什么的結(jié)果。

進行了一段沒有進展的研究后，這對師生把目光轉(zhuǎn)向了密碼學（各自研究不同的問題）。由于大規(guī)模量子計算機在未來可能會出現(xiàn)，密碼學領(lǐng)域為了開發(fā)可抵抗量子攻擊的密碼架構(gòu)，提出了一種名為“后量子密碼學”的研究。2016年，他們和OpenAI的計算機科學家Paul Christiano達成合作，共同開發(fā)了一種利用密碼學方法讓量子計算機構(gòu)建“secret state”（秘密狀態(tài)，）的方法。

所謂秘密狀態(tài)，就是一種已為人知的經(jīng)典驗證者，但它不是量子計算機本身。

他們的程序依賴于所謂的“trapdoor”函數(shù)——一個易于執(zhí)行但難以反轉(zhuǎn)的函數(shù)，除非你有加密密鑰。這個函數(shù)需要“二對一”，也就是每個輸出對應兩個不同的輸入。有了它，我們就能用“trapdoor”函數(shù)創(chuàng)建秘密狀態(tài)——首先，要求計算機建立一個函數(shù)所有可能輸入的疊加；其次，讓計算機將該函數(shù)應用于此巨型疊加，創(chuàng)建一個新狀態(tài)，該狀態(tài)是函數(shù)的所有可能輸出的疊加。這時輸入和輸出疊加將被糾纏，這意味著對其中一個進行驗證會立即影響另一個。

這之后，我們就能要求計算機檢查輸出狀態(tài)并匯報結(jié)果，它在檢查時可以把輸出狀態(tài)折疊成一個可能的輸出，由于輸入輸出是糾纏的，這時輸入也會被折疊。

2017年，Mahadev解決的那個量子計算主要問題就是提出構(gòu)建“trapdoor”函數(shù)的加密方法：Learning With Errors（LWE）。她本可以憑借這個成果畢業(yè)，但面對還沒有解決的“量子驗證”難題，她表示：

我從未想過畢業(yè)，因為我的目標從未畢業(yè)。

塵埃終落定

還是那個問題：是否存在一個完全經(jīng)典的驗證者。

從交互性證明到秘密狀態(tài)，Mahadev已經(jīng)試遍了所有方法，有一段時間，她甚至感到走投無路。但上天還是眷顧她的，一次，她突然萌生了一個新想法：研究人員已經(jīng)證實，如果驗證者能夠檢查量子比特，那么它也可以檢查量子計算機。根據(jù)定義，經(jīng)典驗證者不具備這種能力，但是如果經(jīng)典驗證者能以某種方式迫使量子計算機自己執(zhí)行檢查并誠實地報告呢？

這個問題的難點是讓量子計算機承諾在驗證者檢查之前，自己知道對方要測量的狀態(tài)，Mahadev將其稱為量子比特承諾問題。假設(shè)證明者聲稱準備了一個選擇的單量子比特狀態(tài)|φ>（驗證者不知道），驗證者向證明者詢問執(zhí)行|φ>測量的結(jié)果。無論是在計算基礎(chǔ)上（Pauli Z的本征基礎(chǔ)），還是在Hadamard基礎(chǔ)上（Pauli X的本征基礎(chǔ)），是否存在一種協(xié)議，保證在協(xié)議結(jié)束時，驗證者能夠產(chǎn)生與所選基礎(chǔ)中的測量結(jié)果相匹配的結(jié)果？

這個新協(xié)議具有以下屬性。首先，正如預期的那樣，對于任何量子計算，都有一個量子證明者可以使經(jīng)典驗證者相信計算結(jié)果的正確性，此屬性稱為協(xié)議的完整性。其次，沒有證據(jù)可以說服經(jīng)典驗證者接受錯誤的結(jié)果，此屬性稱為協(xié)議的健全性。在Mahadev的結(jié)果中，后者的屬性有一個轉(zhuǎn)折點：如果證明者不能破壞后量子加密（LWE），那么穩(wěn)健性就會保持不變。

該協(xié)議對LWE的依賴使得Mahadev的成果具有雙贏的風格。量子計算機愚弄協(xié)議的唯一方法是量子計算世界中能有人想出如何破解LWE。但目前，LWE被廣泛認為是后量子密碼學的主要候選者，它可能很快就會取代其他可能會被量子計算機破解的標準，被國家標準與技術(shù)研究所采用作為其新的加密標準。破解難度可想而知。

在未來幾年內(nèi)，Mahadev的協(xié)議暫時還不太可能被部署進真正的量子計算機中，因為協(xié)議所需算力太高了。根據(jù)專家推測，具體數(shù)字應該至少會是5年。但現(xiàn)如今的科學發(fā)展是日新月異的，曾經(jīng)我們認為有些難題可能需要幾十年才能解決，但它們紛紛只用一兩年就搞定了。

隨著量子計算機規(guī)模的擴大和協(xié)議的不斷簡化，相信我們會盡快看到這個理論成果落地的那一天。