量子驗證問題被這位女博士生破解

2017年春季，Urmila Mahadev發現自己成為少數極為幸運的研究生之一。她剛剛解決了量子計算中的一個主要問題，即探索如何立足與直覺嚴重相悖的量子物理學定律構建起量子計算機。結合早期論文，Mahadev得出了所謂盲計算成果。德克薩斯大學奧斯汀分校的計算機科學家Scott Aaronson表示，這「無疑代表著她將成為一顆冉冉升起的新星。」

圖：Urmila Mahadev最近在加州大學伯克利分校舉辦了計算機科學研討會

當時剛剛28歲的Mahadev已經在加州大學伯克利分校進行第七年博士生學習——絕大多數學生顯然都忍受不了如此漫長的學習時間。她在伯克利的導師Umesh Varizani表示，如今，她擁有了這一「漂亮得令人羨慕的博士生」論文。

然而，Mahadev並沒有在那年畢業——她甚至沒有考慮過畢業，因為她認為自己的工作還沒有完成。

五年多以來，她在學習與研究當中遇到了另一個重要問題，也就是Aaronson所提到的「量子計算領域中的一大根本性問題」，即：如果要求量子計算機執行下達的指令，應如何判斷其是否真的按照指示進行，或者是否進行了任何量子性質的計算？

這個問題可能很快就會被學術界徹底解決。研究人員們希望能夠儘快讓量子計算機在各類問題當中提供指數級加速能力，包括模擬黑洞周邊活動到模擬蛋白質大分子的摺疊方式等等。

然而，如果說某些計算屬於只有量子計算機能夠執行、而經典計算機無法處理的類型，我們該如何判斷量子計算機是否做出了正確的計算處理？如果大家不信任傳統計算機，那麼在理論上我們完全可以對計算中的每個步驟進行複查。然而，量子系統從本質上無法被這種複查。首先，其內部工作原理非常複雜：對擁有數百個量子比特（或者稱「量子位」）的計算機進行內部狀態描述，就需要一塊能夠存儲下整個可見宇宙的巨大硬碟。

即使大家通過某種方式找到了記錄這一描述的充足存儲空間，問題仍然沒有得到解決。量子計算機的內部狀態通常由大量彼此不同的非量子「經典」態疊加而成（正如薛定諤的貓理論，其處於既死又生的狀態）。然而，在測量了其中某一量子態之後，其就會坍縮為經典狀態中的一種。同樣的，這意味著在300量子比特的量子計算機當中，我們觀察到的結果將僅僅只是300個經典比特——0或者1。

Vazirani解釋稱，「量子計算機非常強大，但同時也非常神秘。」

考慮到這些限制因素，計算機科學家們長期以來一直弄不清楚量子計算機是否能夠提供切實可信的運行保證，即證明其確實已經完成了聲稱的計算功能。耶路撒冷希伯來大學計算機科學家Dorit Aharonov提問道，「量子與經典世界之間的相互作用是否強大到足以進行對話？」

在研二階段，Mahadev被這個問題所深深迷住，因為她意識到自己無法完全理解問題本身。在接下來的幾年中，她嘗試了一種又一種實現方法。她表示，「我投入了很多時間，我認為自己找到了正確的方向，但很快在一年之後仍然宣告失敗。」

但她不願就此放棄。Mahadev表現出一種堅韌的決心，這是Vazirani此前從未見過的。他表示，「從這個角度來講，Mahadev絕對是一位了不起的學生。」

如今，經過八年的學習，Mahadev終於獲得成功。她提出一種互動式協議，通過該協議，不具備量子計算能力的用戶可以利用密碼方法將工具部署在量子計算機之上並隨時隨地加以驅動，從而確保量子計算機遵循其指令。Vazirani表示，Mahadev的方法幫助用戶們獲得了「計算機永遠無法擺脫的控制手段。」

Aaronson指出，對於一位在讀學生而言，這樣以一己之力完成的成果可謂「非常驚人」。

Mahadev如今已經成為伯克利大學的博士後研究員，並在日前召開的計算機科學基礎年度研討會上公布了自己的協議。該研討會是理論計算機科學領域規模最大的盛會之一，本屆會議於巴黎舉行。她的成果在會上被授予「最佳論文」與「最佳學生論文」獎，這一切即使是對理論計算機科學家們而言都堪稱巨大的榮譽。

在一篇博文中，曾與Mahadev進行過合作的加州理工學院計算機科學家Thomas Vidick指出，她的成果是「最近幾年以來，量子計算與理論計算機科學家領域出現的、最為傑出的思想之一。」

量子計算研究者們不僅對Mahadev協議所取得的成就感到興奮，同時亦讚歎她給這個問題帶來的全新處理方法。Vidick寫道，在量子領域使用經典密碼學手段是一種「真正新穎的思維。我希望以此為基礎，未來能夠出現更多振奮人心的成果。」

漫長的道路

Mahadev出生於洛杉磯的一個醫生家庭，並在考入南加州大學之後進行過多次專業轉換，希望能夠在繼承醫生頭銜之外找到真正適合自己的發展道路。此後，由著名RSA加密演算法創造者之一、計算機科學家Leonard Adleman教授的課程讓她對理論計算機科學建立起濃厚興趣。她向伯克利研究生院提交了申請，解釋稱她對理論計算機科學中的各個方面都很感興趣——除了量子計算。

她回憶道，「當時，量子計算聽起來是種完全陌生的事物，我對此確實不太了解。」

她在進入伯克利之後，Vazirani輕鬆易懂的解釋很快改變了她的想法。Vazirani指出，他曾得這位優秀的學生介紹一個經典問題，即思考如何找到對量子計算進行驗證的協議。這個問題「徹底激發出了她的想像力。」

Mahadev解釋稱，「協議就像是謎題。對我來說，這類問題的切入門檻更低，因為我們可以立即開始構思自己的協議，而後進行嘗試以觀察其如何工作。」她選擇了這個方向作為自己的博士生課題，而Vazirani則將此稱為一條「漫長的道路。」

如果量子計算機能夠解決經典計算機無法解決的問題，這並不代表著相關解決方案必然難以檢查。舉例來說，在考慮大數因子分解問題時，量子計算機能夠有效解決這一經典計算機所無法處理的難題，而其驗證工作卻非常簡單。更具體地講，儘管經典計算機無法計算出具體數字，但其能夠將得出的因子相乘以觀察得出的大數是否與原始大數相等——只要相等，即代表得出了正確的答案。

然而，計算機科學家們認為（最近我們亦在證明層面邁出了重要一步），量子計算機能夠解決的眾多問題並不存在上述特徵。換言之，經典計算機不僅無法解決這類問題，甚至無法判斷給出的解決方案是否正確。有鑒於此，安大略省滑鐵盧周界理論物理研究所的物理學家Daniel Gottesman於2004年左右提出了一個問題，即是否有可能建立起一種協議，從而由量子計算機向某非量子觀察方證明其確實完成了宣稱的計算。

在四年之內，量子計算研究人員們已經得出了部分答案。已經有兩個團隊各自獨立給出證明，相較於利用純粹的經典驗證計算機，在量子計算機之內建立一個小型驗證系統有望對該量子計算機的計算過程進行證明。研究人員們之後對此種方法做出了改進，並證明對所有驗證方的需求，最終都可歸結於對單一量子比特的測量能力。

2012年，包括Vazirani在內的一組研究人員們證明，如果一套量子計算機是由兩台獨立且無法相互通信的量子計算機所構成，那麼經典的驗證計算機即可檢查其量子計算結果。然而，這篇論文的結果只適用於這一特定情況，而且似乎無法被擴展至其它更為廣泛的應用場景。Gottesman表示，「我認為有不少人認為這條道路恐怕走不通。」

大致就在同一時間，Mahadev接觸到了這一重要的驗證問題。起初，她希望提出一個「無條件」性結論，即不對量子計算機能做什麼或不能做什麼做出假設。但在這個方向探索一段時間並發現無果之後，Vazirani提出了使用「後量子」密碼學方法的可能性——換言之，研究人員們認為密碼學超出了量子計算機的處理能力。當然，他們對此也不太確定。（這裡需要強調，用於在線交易等事務的RSA加密演算法不屬於後量子密碼學，因為大型量子計算機完全可以解決這類將安全性建立在大數分解難度的加密方法。）

2016年，Mahadev與Vazirani在處理另一個不同問題方面取得了進展，而這一進展被證明極為關鍵。如今，舊金山OpenAI公司的計算機科學家Paul Christiano正與他們通力合作，開發出一種利用密碼學方法讓量子計算機構建起所謂「秘密狀態」的方法——無需量子計算機本身，經典驗證計算機已經能夠對秘密狀態做出描述。

他們提出的程序依賴於所謂「陷阱門」函數——這是一種易於執行的函數，但除非擁有加密密鑰，否則將難以逆向執行。（但目前研究人員們並不知道要如何實際構建起適合量子計算機的陷阱門函數，這將成為接下來的研究課題。）該函數亦需要「二合一」，即每項輸出都對應兩條不同的輸入。可以想像，假如要對數字進行平方計算，那麼除了數字0之外，每條輸出結果（例如9）都擁有兩個對應的輸入項（3與-3）。

利用這一函數，我們可以在量子計算機當中建立秘密狀態，具體方法如下所示：首先要求計算機建立一項函數，將其所有可能的輸入內容進行疊加（聽起來很複雜，但計算機執行起來其實非常容易）。在此之後，要求計算機將該函數應用於此大型疊加，從而建立起新狀態——該狀態為函數所有可能輸出的疊加集。輸入與輸出疊加集將彼此糾纏，意味著對其中一者的測量將立即對另一個產生影響。

接下來，要求計算機測量輸出狀態並報告結果。此測量將把輸出狀態摺疊為單一可能輸出，且輸入狀態也將立即摺疊從而與該輸出結果匹配——這是因為二者彼此糾纏。舉例來說，如果使用平方函數，那麼如果輸出狀態為9，則輸入將摺疊為3與-3的疊加。

不過請注意，這裡我們使用的是陷阱門函數。我們擁有陷阱門的密鑰，因此能夠很容易地找出構成輸入疊加的兩個狀態。然而，量子計算機由於沒有這一密鑰，所以無法簡單地通過測量輸入疊加以找出其構成。這主要是因為測量會使結果進一步摺疊，從而導致量子計算機只能找到兩個輸入結果中的一個。

2017年，Mahadev通過使用一種名為Learning With Errors（簡稱LWE）的加密技術，發現了實現秘密狀態方法的核心——即構建陷阱門函數。利用這些陷阱門函數，她能夠創建盲計算的量化版本，雲計算用戶可以通過這種計算方式屏蔽自己的數據，從而確保雲計算機即使在處理的過程中也無法對內容進行讀取。不久之後，Mahadev、Vazirani以及與Christiano開始同Vidick與Zvika Brakerski（來自以色列Weizmann科學研究所）合作，大家共同進一步完善這些陷阱門函數，旨在利用秘密狀態方法為量子計算機開發出一種高度可靠的可證明隨機數生成方法。

Mahadev完全可以憑藉這一出色成果順利畢業，但她決定繼續工作直到徹底解決這個驗證問題。她表示，「我從未想過畢業，因為我的目標不存在畢業這一概念。」

雖然並不清楚她到底是否能夠解決這個問題，但她表示，「我願意花時間學習我感興趣的事情，所以這並不算是在浪費時間。」

一成不變

Mahadev嘗試了從秘密狀態方法到驗證協議的多種方法，但有一段時間，她也陷入了困境。在此之後，她考慮了一下：研究人員們已經證明，如果驗證計算機能夠測量量子比特，由驗證計算機即可檢查量子計算機。根據定義，經典驗證計算機缺乏這種能力。但如果經典驗證計算機能夠以某種方式迫使量子計算機自行執行測量並如實報告，結果又會如何？

Mahadev意識到，其中最棘手的部分是讓量子計算機在了解驗證計算機提出測量對象要求之前，就承諾了解對應的狀態——否則，計算機很容易欺騙驗證計算機。這正是秘密狀態方法發揮作用的地方：Mahadev的協議要求量子計算機首先創建一個秘密狀態，而後將其與應當測量的狀態糾纏起來。只有這樣，計算機才能找出要執行的測量類型。

由於計算機不知道秘密狀態的構成，但驗證計算機卻知道，因此Mahadev強調量子計算機無法在不留下明顯雙重性痕迹的前提下作弊。從本質上講，Vidick寫道，計算機測量的量子比特已經「設置為一成不變」的形式。如此一來，只要測量結果看起來是正確的，則驗證計算機即可確信其正確無誤。

Vidick寫道，「這是個非常好的主意！每當Mahadev做出解釋時，我都對此感到震驚！」

Mahadev的驗證協議——以及隨機數發生器與盲加密方法——立足於量子計算機無法破解LWE這一假設。目前，LWE被廣泛視為後量子密碼學領域的主要候選方案，亦可能很快被美國國家標準與技術研究所作為新的加密標準，用以取代量子計算機可能破解的現有標準。但Gottesman告誡稱，這並不能保證其真正應對量子計算機的強大處理能力。他表示，「不過到目前為止，這種解決方案還很穩固，沒有人發現其可能被破解的證據。」

Vidick寫道，無論如何，該協議對於LWE的高度依賴性使得Mahadev的成果具有雙贏潛力。量子計算機欺騙該協議的唯一方法，就是量子計算世界中有人想到如何破解LWE——而這本身也將成為一項了不起的成就。

Mahadev的協議不太可能在不久的未來在真正的量子計算機中實現。目前，該協議需要大量算力才能付諸實用。但隨著量子計算機規模的擴大以及研究人員對協議的簡化，這一情況未來幾年可能發生變化。

Aaronson表示，Mahadev的協議可能在未來五年內恐怕還不可行，但「其並非完全只是一種幻想。在量子計算機發展的下一階段，如果一切順利的話，大家就可以開始思考這個問題了。」

考慮到技術發展的速度極為可觀，相信下一階段應該會很快到來。畢竟就在五年之前，Vidick提到研究人員們還認為量子計算機尚需要多年才能真正解決傳統計算機所無法解決的問題。「現在，人們認為這種能力在未來一到兩年後即會實現。」

至於Mahadev，解決她最喜歡的問題讓她感覺有點像漂泊在大海之上。她提到，她希望自己能夠儘快找到那些最適合自己的研究方向。「現在我需要找個新的問題了，我對這一切充滿期待。」

不過理論計算機科學家們認為，Mahadev的量子計算與密碼學統一併不是結束，而將成為希望證明更多豐富思想的探索者們的新起點。

Aharonov表示，「我認為未來還將有很多後續發展，我期待著Mahadev能夠帶來更多激動人心的貢獻。」

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！