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

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

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

Urmila Mahadev

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

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

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

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

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

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

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

一條漫長的道路

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

我從未想過畢業，因為我的目標從未畢業。

塵埃終落定

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

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

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

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

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

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

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