|
來(lái)源： 公眾號“原理” 厄米拉·馬哈德夫（Urmila Mahadev）花了八年時(shí)間在研究生院解決了量子計算領(lǐng)域最基本的問(wèn)題之一：怎么知道量子計算機是否做了量子計算呢？ 2017 年春天，厄米拉發(fā)現自己處于大多數研究生都會(huì )認為相當不錯的一個(gè)位置。她剛剛解決了量子計算領(lǐng)域的一個(gè)主要問(wèn)題。量子計算是研究計算機的科學(xué)，它從量子物理學(xué)的奇怪定律中獲得強大的計算力。 德州大學(xué)奧斯汀分校的計算機科學(xué)家斯科特·阿倫森（Scott Aaronson）認為，厄米拉·馬哈德夫關(guān)于“盲計算”的新成果與她之前的論文結合起來(lái)，顯然讓她成為“一顆冉冉升起的新星”。 當時(shí) 28 歲的厄米拉已經(jīng)在加州大學(xué)伯克利分校讀了七年研究生——遠遠超過(guò)了大多數學(xué)生迫切想要畢業(yè)的階段�，F在，正如她的博士導師烏曼什·瓦齊拉尼（Umesh Vazirani）所說(shuō)的，她終于有了一篇“非常漂亮的博士論文”。 但是那一年，厄米拉并沒(méi)有畢業(yè)，她甚至沒(méi)有考慮要畢業(yè)，因為事情還沒(méi)有完成呢。 量子計算+密碼學(xué) 在五年多的時(shí)間里，她還有另一個(gè)不同的研究目標。她想解決的這個(gè)問(wèn)題被阿倫森稱(chēng)為“量子計算領(lǐng)域最基本的問(wèn)題之一”，那就是：如果讓一臺量子計算機做計算，怎么知道它是否真的遵循了你的指令，或者它是否真的執行了任何量子計算呢？ 研究人員希望，過(guò)不了許多年，量子計算機就能指數級地加速為我們解答許多問(wèn)題，比如模擬黑洞周?chē)男袨�、蛋白質(zhì)如何折疊等等。但是，一旦量子計算機能夠完成經(jīng)典計算機無(wú)法完成的計算，我們將如何知道它的計算是否正確呢？ 如果你不信任一臺普通的計算機，理論上，你可以親自檢查它的每一個(gè)計算步驟。但是，量子系統從根本上抵制這種檢查。 首先，量子計算機的內部工作機制極其復雜：對于幾百個(gè)量子比特的計算機，要寫(xiě)出關(guān)于其內部狀態(tài)的描述將需要比整個(gè)可見(jiàn)宇宙還要大的一個(gè)硬盤(pán)。此外，即使有足夠的空間寫(xiě)下這個(gè)描述，也沒(méi)有辦法得到它。通常，量子計算機的內部狀態(tài)是許多不同的非量子的“經(jīng)典”態(tài)的疊加。（就像是薛定諤的貓，同時(shí)處于“死”和“活”的狀態(tài)）但是，一旦測量一個(gè)量子態(tài)，它就會(huì )坍縮為其中一個(gè)經(jīng)典態(tài)。凝視一臺 300 個(gè)量子比特的量子計算機，本質(zhì)上，你看到的只會(huì )是 300 個(gè)經(jīng)典比特，也就是 0 和 1 。 瓦齊拉尼說(shuō)：“量子計算機非常強大，但是也非常神秘�！� 考慮到這些限制，長(cháng)久以來(lái)，計算機科學(xué)家一直好奇，是否有可能讓量子計算機提供任何嚴格的保證，證明它確實(shí)做了自己宣稱(chēng)的事情。耶路撒冷希伯來(lái)大學(xué)的計算機科學(xué)家多瑞特·阿哈羅諾夫（Dorit Aharonov）問(wèn)道：“量子和經(jīng)典世界之間的相互作用是否足夠強大，以至于能夠進(jìn)行對話(huà)呢？” 在研究生二年級的時(shí)候，厄米拉被這個(gè)問(wèn)題迷住了，其中的原因連她自己都不完全明白。在隨后的幾年里，她嘗試了一種又一種方法。她說(shuō)：“有很多次，我覺(jué)得自己做著(zhù)正確的事情，但是接著(zhù)就出錯了，有時(shí)很快，有時(shí)過(guò)了一年才出現�！� 但是，厄米拉拒絕放棄。她表現出了瓦齊拉尼從未見(jiàn)過(guò)的持久的決心，瓦齊拉尼說(shuō)：“從這個(gè)意義上說(shuō)，厄米拉絕對是與眾不同的�！� 現在，經(jīng)過(guò)八年的研究生學(xué)習，厄米拉終于成功了！她提出了一種交互式協(xié)議，通過(guò)這種協(xié)議，沒(méi)有量子計算能力的用戶(hù)也可以使用經(jīng)典的密碼學(xué)讓量子計算機做任何他們想做的事情，并確信量子計算機正在遵循他們的命令，就像是牽著(zhù)馬具任意馳騁一樣。瓦齊拉尼說(shuō)，厄米拉·馬哈德夫的方法給用戶(hù)提供了“讓計算機無(wú)法擺脫的手段“。 
厄米拉·馬哈德夫提出的協(xié)議。 阿倫森說(shuō)，一個(gè)研究生能夠獨自完成這樣一個(gè)任務(wù)”非常令人震驚“。 厄米拉現在是伯克利大學(xué)的博士后研究員。近日，她在計算機科學(xué)基金會(huì )的年度研討會(huì )——理論計算機領(lǐng)域最大型的會(huì )議之一——上提交了自己的方案。她的作品獲得了這次會(huì )議的”最佳論文“和”最佳學(xué)生論文“獎，這對一位理論計算機科學(xué)家來(lái)說(shuō)是罕見(jiàn)的榮譽(yù)。 加州理工學(xué)院的計算機科學(xué)家托馬斯·維迪克（Thomas Vidick）過(guò)去曾與厄米拉合作過(guò)，他在博客文章中寫(xiě)道，厄米拉·馬哈德夫的研究成果是”近年來(lái)量子計算和理論計算機科學(xué)的交叉處出現的最杰出的思想之一“。 量子計算領(lǐng)域的研究人員之所以興奮，不僅是因為厄米拉的協(xié)議能夠解決問(wèn)題，還因為她為解決這個(gè)問(wèn)題所采取的全新方法。維迪克寫(xiě)道，在量子計算領(lǐng)域使用經(jīng)典的密碼學(xué)真的是非常新穎的想法，”我希望，在這些想法的基礎上，會(huì )繼續產(chǎn)生更多成果�！� 漫長(cháng)的證明之路 厄米拉·馬哈德夫在洛杉磯的一個(gè)醫生家庭長(cháng)大，她就讀于南加州大學(xué)，在那里，她從一個(gè)研究領(lǐng)域漂流到另一個(gè)。起初，她只確信一點(diǎn)，那就是自己不想成為一名醫生。后來(lái)，計算機科學(xué)家萊納德·艾德蒙（Leonard Adleman）——RSA 加密算法的三位創(chuàng )造者中的 A——講授的一門(mén)課程讓她對理論計算機科學(xué)產(chǎn)生了興趣。之后，她申請成為加州大學(xué)伯克利分校的研究生，并在申請材料中解釋說(shuō)，自己對理論計算機科學(xué)的所有方面都感興趣，除了量子計算。因為量子計算“聽(tīng)起來(lái)像是非常古怪的事情，是我知道得最少的事情”。 然而，一到伯克利，瓦齊拉尼深入淺出的解釋很快改變了她的想法。他向她介紹了一個(gè)問(wèn)題——如何找到一個(gè)驗證量子計算的協(xié)議？而這個(gè)問(wèn)題“激發(fā)了她的想象力”，瓦齊拉尼說(shuō)道。 厄米拉解釋說(shuō)：“協(xié)議就像是謎題。對我來(lái)說(shuō)，這種問(wèn)題似乎比其他問(wèn)題更容易，因為你可以自己立即開(kāi)始思考協(xié)議，然后破解它們，這樣你就會(huì )發(fā)現它們是如何運作的�！� 她選擇這個(gè)問(wèn)題作為自己的博士研究課題，開(kāi)始了瓦齊拉尼所說(shuō)的“漫漫長(cháng)路”。
厄米拉·馬哈德夫 | 圖片來(lái)源：Quanta Magazine 如果一臺量子計算機可以解決經(jīng)典計算機無(wú)法解決的問(wèn)題，那并不必然意味著(zhù)解決方案將難以檢驗。以大數的因數分解為例，一臺大型量子計算機可以高效解決這個(gè)問(wèn)題，但經(jīng)典計算機被認為無(wú)法完成這個(gè)任務(wù)。 雖然一個(gè)經(jīng)典計算機不能對一個(gè)大的數字進(jìn)行因數分解，但它卻能夠檢驗量子計算機的因數分解是否正確——只需要將這些因數相乘，看看它們是否得出正確答案。 然而，計算機科學(xué)家相信（并且最近已經(jīng)向證明邁出了一步），量子計算機能夠解決的許多問(wèn)題并沒(méi)有這個(gè)特性。也就是說(shuō)，一臺經(jīng)典計算機不僅不能解決這些問(wèn)題，甚至也不能判斷一個(gè)提出的解決方案是否正確。 鑒于這一點(diǎn)，大約在 2004 年，圓周理論物理研究所的物理學(xué)家丹尼爾·戈特斯曼（Daniel Gottesman）提出一個(gè)問(wèn)題：是否有可能提出任何一種協(xié)議，通過(guò)這個(gè)協(xié)議，一臺量子計算機可以向非量子觀(guān)察者證明自己確實(shí)完成了聲稱(chēng)的那些事情？ 在四年內，量子計算的研究人員已經(jīng)得到了部分答案。兩個(gè)不同的團隊證明，一臺量子計算機有可能證明它的計算，但是不是向一臺純粹經(jīng)典的驗證設備，而是向一個(gè)能夠進(jìn)入自己內部非常小的量子計算機的驗證設備。研究人員后來(lái)改進(jìn)了這種方法，并證明，驗證設備所需要的只是每一次測量單個(gè)量子比特的能力。 2012 年，包括瓦齊拉尼在內的一組研究人員證明，如果量子計算是由一對無(wú)法相互通信的量子計算機進(jìn)行的，那么，一臺完全經(jīng)典的驗證設備就能夠檢查量子計算。戈特斯曼表示，那篇論文的方法是針對這種特定情形設計的，這個(gè)問(wèn)題似乎陷入了死胡同，一些人認為不能再往前走了。 大約就在這個(gè)時(shí)候，厄米拉遇到了這個(gè)驗證問(wèn)題。起初，她試圖得到一個(gè)“無(wú)條件”的結果，一個(gè)并不假定量子計算機能做什么或不能做什么的結果。 在她研究這個(gè)問(wèn)題一段時(shí)間，且并沒(méi)有取得任何進(jìn)展后，瓦齊拉尼建議了一種不同的可能性——用“后量子”加密（post-quantum cryptography）。研究人員認為，這是一種即使量子計算機也無(wú)法破解的加密方法，雖然他們還不確定。 像 RSA 加密算法之類(lèi)用于加密在線(xiàn)交易等信息的方法不是后量子的，也就是說(shuō)，一臺量子計算機能夠破解這種加密方法，因為它們的安全性取決于對大數做因數分解的難度。 2016 年，厄米拉和瓦齊拉尼在解決另一個(gè)問(wèn)題的時(shí)候取得了進(jìn)展，這在后來(lái)被證明是至關(guān)重要的。 他們與如今在 OpenAI 公司工作的計算機科學(xué)家保羅·克里斯蒂亞諾（Paul Christiano）合作，開(kāi)發(fā)了一種方法，使用密碼學(xué)讓量子計算機構建所謂的“加密態(tài)（secret state）”，這個(gè)加密態(tài)的描述對于經(jīng)典的驗證設備是已知的，但是對于量子計算機本身卻是未知的。 他們的程序依賴(lài)于所謂的“暗門(mén)”函數（trapdoor function），這個(gè)函數很容易執行，但是要逆轉則非常困難，除非知道密鑰。（研究人員還不知道如何真正構建一個(gè)合適的暗門(mén)函數，之后將會(huì )提出。）另外，還要求這個(gè)函數是“二對應一”的，這意味著(zhù)，每一個(gè)輸出對應著(zhù)兩個(gè)不同的輸入。比如說(shuō)，對于平方函數y=x²，除了數字 0 之外的每一個(gè)輸出（例如 9）都有兩個(gè)對應的輸入（3 和 −3）。 有了這樣一個(gè)函數，就可以讓量子計算機按照下面的步驟構建一個(gè)加密態(tài)： 首先，讓計算機構建一個(gè)所有可能的函數輸入的疊加（這聽(tīng)起來(lái)或許很復雜，但是事實(shí)上很容易）； 然后，讓計算機將函數應用到這個(gè)巨大的疊加上，函數的所有可能輸出的疊加構成一個(gè)新的態(tài)。 輸入的疊加和輸出的疊加會(huì )產(chǎn)生糾纏，這意味著(zhù)，測量其中一個(gè)會(huì )立即影響另一個(gè)。 接下來(lái)，要求計算機測量輸出態(tài)，并告訴我們結果。這個(gè)測量會(huì )導致輸出態(tài)坍縮為所有可能輸出中的一個(gè)，而輸入態(tài)也會(huì )立即坍縮以與之匹配，因為它們彼此糾纏。例如，對于平方方程，如果測量得到的輸出態(tài)是 9，那么輸入態(tài)會(huì )坍縮為 3 和 −3 的疊加態(tài)。 但是，如果使用的是暗門(mén)函數，那么我們就有暗門(mén)的秘鑰，因此可以很容易地找出構成輸入態(tài)的兩種疊加態(tài)。然而，量子計算機不能。量子計算機不能簡(jiǎn)單地測量輸入的疊加來(lái)求出它的構成，因為測量會(huì )進(jìn)一步讓輸入的疊加坍縮，讓計算機只剩下其中一個(gè)輸入態(tài)，而無(wú)法求出另一個(gè)。 2017 年，厄米拉使用一種名為“錯誤學(xué)習（Learning With Errors，LWE）”的加密技術(shù)，找到了在加密態(tài)方法的核心構建暗門(mén)函數的方法。利用暗門(mén)函數，她就能夠創(chuàng )建一個(gè)量子版本的“盲”計算，使得云計算用戶(hù)可以屏蔽他們的數據，這樣云計算機即使在計算時(shí)也無(wú)法讀取數據。 不久之后，厄米拉、瓦齊拉尼、克里斯蒂亞諾與維迪克、斯維卡·布雷克斯基（Zvika Brakerski，以色列魏茨曼科學(xué)研究所的科學(xué)家）合作，進(jìn)一步改進(jìn)這些暗門(mén)函數，利用加密態(tài)方法發(fā)展出一種讓量子計算機產(chǎn)生可證實(shí)的真隨機數的安全方法。 厄米拉本可以憑借這些結果畢業(yè)，但她決心繼續工作，直到解決驗證問(wèn)題。她說(shuō)：“我從來(lái)沒(méi)有想畢業(yè)的事情，因為我的目標從來(lái)就不是畢業(yè)�！� 不知道能否解決這個(gè)問(wèn)題有時(shí)會(huì )讓人感到壓力，但是，她說(shuō)：“我花時(shí)間學(xué)習自己感興趣的東西，因此，這不是真的在浪費時(shí)間�！� 如何加密？ 厄米拉嘗試了各種方法，試圖從加密態(tài)方法抵達一種驗證協(xié)議，但是有一段時(shí)間，她一無(wú)所獲。然后，她有了一個(gè)想法：研究人員已經(jīng)證明，如果驗證設備能夠測量量子比特，它就能夠檢驗量子計算機。根據定義，一個(gè)經(jīng)典的驗證設備缺乏這種能力。但是，如果這個(gè)經(jīng)典的驗證設備能夠以某種方式強迫量子計算機自己進(jìn)行測量，然后誠實(shí)地報告測量結果呢？ 厄米拉意識到，最棘手的部分是，在量子計算機知道驗證設備會(huì )要求哪種測量之前，就讓量子計算機確定它將要測量的狀態(tài)。否則，量子計算機很容易欺騙驗證設備。這正是加密態(tài)方法發(fā)揮作用的地方：厄米拉的協(xié)議要求量子計算機首先創(chuàng )建一個(gè)加密態(tài)，然后將它與應該測量的狀態(tài)糾纏在一起。只有到那時(shí)，計算機才會(huì )知道要進(jìn)行何種測量。 由于量子計算機不知道加密態(tài)的構成，但驗證設備知道，厄米拉證明，量子計算機不可能在不留下明顯的欺騙痕跡的情況下做出嚴重的欺騙。 維迪克寫(xiě)道，本質(zhì)上，計算機要測量的量子比特被“設置為密碼石”。正因為如此，如果測量結果看起來(lái)像是一個(gè)正確的證明，驗證設備就能確信它們真的是�！罢媸莻�(gè)好主意！每一次厄米拉解釋它的時(shí)候，我都驚呆了�！� 量子計算機不能破解的密碼？ 厄米拉·馬哈德夫的驗證協(xié)議，連同隨機數生成器和盲加密方法，都取決于量子計算機不能破解 LWE 的假設。目前，LWE 被廣泛認為是后量子密碼學(xué)的優(yōu)先候選對象，而且，它或許很快會(huì )被美國國家標準與技術(shù)研究所（NIST）采用作為其新的加密標準，取代那些量子計算機可能破解的方法。 戈特斯曼警告說(shuō)，這并不能確保這種加密方法真的能抵御量子計算機，“但是到目前為止，這種方法是可靠的，還沒(méi)有人找到證據，證明這種方法有可能被破解�！� 維迪克寫(xiě)道，無(wú)論如何，協(xié)議對 LWE 的依賴(lài)給厄米拉的作品帶來(lái)了雙贏(yíng)的意味。量子計算機可能欺騙協(xié)議的唯一方法是，量子計算領(lǐng)域的某個(gè)人找到了破解 LWE 的方法，而這本身將會(huì )是一項了不起的成就。 厄米拉·馬哈德夫的協(xié)議不太可能在不久的將來(lái)就在真正的量子計算機上實(shí)現。目前，這個(gè)協(xié)議需要太多的計算能力，因而不太有實(shí)用性。但在未來(lái)幾年，隨著(zhù)量子計算機越來(lái)越大，以及研究人員對協(xié)議進(jìn)行簡(jiǎn)化，情況可能會(huì )改變。 阿倫森說(shuō)，厄米拉的協(xié)議可能在未來(lái)五年內都沒(méi)有可行性，但是，“在假想世界里也不是完全不可行。如果一切順利，在量子計算機演化的下一個(gè)階段，就可以開(kāi)始思考這個(gè)問(wèn)題�！� 考慮到這個(gè)領(lǐng)域現在的發(fā)展速度有多快，這個(gè)階段可能會(huì )更早到來(lái)。維迪克說(shuō)，畢竟，就在五年前，研究人員還認為量子計算機要想解決經(jīng)典計算機無(wú)法解決的任意問(wèn)題還需要很多年�，F在，人們認為這將在一兩年內發(fā)生。 至于厄米拉，解決了自己最喜歡的問(wèn)題讓她有點(diǎn)茫然。她希望自己能明白，是什么讓這個(gè)問(wèn)題適合自己去研究�！拔椰F在必須找到一個(gè)新問(wèn)題，所以很希望能知道這個(gè)答案�！� 然而，理論計算機科學(xué)家更多地是將厄米拉·馬哈德夫統一量子計算與密碼學(xué)一事視為對那些豐富多彩的思想脈絡(luò )的初步探索，而不是故事的結束。 |
