女博士7年不肯畢業，終一戰成名！

文匯網

 

　　

 

　　在今年於巴黎舉行的理論計算機科學領域的最頂級會議——計算機科學年度基礎論壇（FOCS）上，一位來自加州大學伯克利分校的博士後“一戰成名”：烏爾米拉·馬哈德（Urmila Mahadev）的成果被會議授予“最佳論文”和“最佳學生論文”獎。這是理論計算機科學家夢寐以求的殊榮。

 

　　曾經與馬哈德合作的加州理工計算機科學家托馬斯·溫迪克（Thomas Vidick）在博文中表示，“這是近年來理論計算機科學和量子計算交叉領域中最傑出的成果。”

 

　　如此成果的背後，是這位女科學家“頑固”的 7 年博士生涯：到了馬哈德 28 歲的時候，她已經在加州伯克利研究生院度過 7 個年頭——大多數研究生根本無法承受如此枯燥而“沒有盼頭的人生”。知道2017年春季，馬哈德發現自己成為少數極為幸運的研究生之一。她剛剛解決了量子計算中的一個主要問題，即探索如何立足與直覺嚴重相悖的量子物理學定律構建起量子計算機。結合早期論文，馬哈德得出了所謂盲計算成果。然而，馬哈德並沒有考慮畢業，因為她認為自己的工作還沒完成。

 

　　

 

　　量子計算領域最基礎的問題

 

　　馬哈德花了 5 年時間研究被阿倫森稱為“量子計算領域最基礎的問題”：如果要求量子計算機執行下達的指令，應如何判斷其是否真的按照指示進行，或者是否進行了任何量子性質的計算？

 

　　這個問題可絕不僅僅是一個象牙塔學術問題。如果不能證明量子計算機的輸出結果確實對應於用戶指令，那麽不管是仿真黑洞行為還是計算蛋白質構型，結果都不可信。量子計算機的速度確實令經典計算機望塵莫及，但是，經典計算機能忠實執行用戶指令，量子計算機可以麽？

 

　　馬哈德在伯克利的導師瓦斯拉米表示，量子計算機非常強大，但是其運算結果的可靠性難以核查。

 

　　計算機科學家一直以來都在尋找對量子計算結果進行檢驗的方法。

 

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

 

　　

 

　　但她不願就此放棄。馬哈德表現出一種堅韌的決心，這是瓦斯拉米此前從未見過的。他表示，“從這個角度來講，Mahadev絕對是一位了不起的學生。”

 

　　8 年之後，馬哈德成功了。她提出一種交互式協議，通過該協議，不具備量子計算能力的用戶可以利用密碼方法將工具部署在量子計算機之上並隨時隨地加以驅動，從而確保量子計算機遵循其指令。Vazirani表示，Mahadev的方法幫助用戶們獲得了“計算機永遠無法擺脫的控製手段。”

 

　　德克薩斯大學奧斯汀分校的計算機科學家阿倫森表示，對於一位在讀學生而言，這樣以一己之力完成的成果可謂“非常驚人”。

 

　　漫長的道路

 

　　馬哈德出生於洛杉磯的的一個醫生家庭，在南加州大學讀本科。除了確定自己不想成為醫生，馬哈德換個很多個專業。不過，在聽過計算機科學家，RAS 公鑰加密算法發明人勒納德·阿德曼（Leonard Adleman）的課之後，對於理論計算機科學產生了濃厚的興趣。她在提交給伯克利的研究生申請中表示，她對理論計算機科學的任何方向都感興趣，“除了量子計算”，因為這聽上去太過遙遠，她不怎麽了解。

 

　　然而，在伯克利，導師瓦斯拉米的教導很快使馬哈德改變了主意。瓦斯拉米說：“我引導馬哈德接觸了量子計算可靠性問題，這個問題激發了她無窮的想象。”

 

　　馬哈德說：“協議就像猜謎。我覺得它比其他的問題簡單一些，因為你可以立即在腦子裏思考和分析協議，並搞清協議的工作原理。”馬哈德將量子計算可靠性作為博士課題，瓦斯拉米導師稱“這是一條非常漫長的路。”

 

　　起初，她試圖直接做出一個終極結果，即“對量子計算機能做什麽和不能做什麽不加任何假定”。然而，碰壁之後，瓦斯拉尼建議，嚐試一下“後量子”密碼學方法。計算機科學家猜測（尚未嚴格證明），“後量子”密碼算法甚至能在量子計算機的破解下保持足夠的安全性。

 

　　2016 年，馬哈德和瓦斯拉尼在另一個問題上取得了突破，這個成果在日後被證明是通向最終答案的關鍵。兩人與 OpenAI 公司的的計算機科學家保羅·克裏斯塔諾（Paul Christiano）合作，發明了一種利用密碼學來讓量子計算機創造“秘密狀態”的方法。“秘密狀態”對於經典計算機是不可知的，但是對於量子計算機本身是可知的的。

 

　　

 

　　他們的核心工具是“陷門函數”——該函數很容易正向計算，但是反向計算幾乎不可能，除非擁有密鑰。此外，陷門函數還必須是 2 對 1 的映射，即每 1 個輸出對應於 2 個不同的輸入。類似於 4 等於 2 的平方和-2 的平方。研究團隊成功構建了陷門函數。

 

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

 

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

 

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

 

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

 

　　2017 年，馬哈德提出，用一種被稱為“試錯方法”的加密方法構建陷門函數，是“秘密狀態”方法的核心。“試錯方法”作為一種加密方法被廣泛應用於雲計算領域，可以令雲端服務器無法讀取用戶未授權的數據，即使它正在處理用戶的數據。不久，馬哈德、瓦斯拉尼、克裏斯塔諾、溫迪克和以色列魏茨曼科學研究所的斯維卡·布拉克斯基（Zvika Brakerski）進一步推動了陷門函數的研究，成功利用“秘密狀態”方法構建了一種能證明量子計算機輸出的隨機數確實是隨機數的方法。

 

　　馬哈德此時完全可以畢業，但是她決心繼續工作，直到徹底解決量子計算可靠性問題。“我根本沒考慮過何時畢業，因為我的目標從來不是拿學位。”

 

　　她承認，探索未知領域有很大壓力。不過，“我想通了，花時間學習我感興趣的東西不算浪費時間。”

 

　　

 

　　一個有望通向更多豐碩研究成果的起點

 

　　馬哈德嚐試了各種辦法，希望基於“秘密狀態”方法設計出可靠性證明協議，但是很長時間沒有進展。

 

　　直到某天她想到：研究人員已經證明，如果檢查者可以測量量子比特，那麽就可以檢驗量子計算結果；經典計算機無法測量量子比特，因此無法利用這個方法檢驗計算結果。然而，如果檢查者能強迫量子計算機自己來測量量子比特，然後報告自查結果呢？

 

　　這個思路的核心前提在於：在檢驗者發出測量指令之前，量子計算機不能知道檢驗者要做什麽測量，否則計算機很容易愚弄檢驗者。“秘密狀態”方法簡直就是解決該問題的天賜工具：馬哈德令量子計算機首先創立一個“秘密狀態”，然後將該秘密狀態和待測狀態耦合。隻有在這個時候，量子計算機才會知道，要執行什麽測量。計算機不知道秘密狀態的內容，而檢驗者知道。馬哈德證明，量子計算機不可能欺騙檢驗者而不留下痕跡。溫迪克進一步解釋，待測量子比特是“整個方法的基石”。最終，如果檢驗結果看上去是正確的，那麽檢查者就大可放心。

 

　　溫迪克：“這個點子太驚人了，每次烏爾米拉解釋的時候，我都會被震驚。”

 

　　馬哈德的檢驗協議，以及隨機數生成器和盲加密算法，都依賴於這樣一個假定：量子計算機無法破解“試錯方法”。目前，“試錯方法”被認為是首屈一指的後量子加密方法，有望被美國國家標準和技術研究所認定為新的加密標準，來取代那些麵對量子計算機不堪一擊的加密方法。古斯曼表示，目前還不能說“試錯方法”可以萬無一失地克製量子計算機的解密，但是至少現在它足夠可靠，沒有誰發現這個算法有什麽弱點可利用。

 

　　

 

　　反過來，如果要愚弄馬哈德提出的檢驗協議，那麽就必須找出破解“試錯方法”的辦法，這同樣會是一個驚人的成就。

 

　　當然，馬哈德的協議不太可能馬上被應用，原因之一是執行該協議需要的計算量大得驚人。不過，當量子計算機更加強大，算法得以優化之後，該協議仍有很大的應用希望。

 

　　雖然馬哈德的協議不大可能在 5 年內得以應用。但是阿倫森表示，如果一切順利，這將是量子計算下一輪技術革命的起點。

 

　　溫迪克還補充，5 年前，計算機科學家普遍認為，量子計算機想要解決任何經典計算機解決不了的問題還要很多年。現在，科研界普遍認為：“隻要 1-2 年就夠了”。因此馬哈德協議的應用可能比想象的要快。

 

　　對於馬哈德，她承認自己的成就令自己有點迷茫，她個人希望找到一個新的問題來研究。

 

　　不過，在理論計算機科學圈看來，馬哈德一統量子計算和加密算法的工作遠遠不是終點，而是一個有望通向更多豐碩研究成果的起點。