在今年于巴黎舉行的理論計(jì)算機(jī)科學(xué)領(lǐng)域的最頂級會議——計(jì)算機(jī)科學(xué)年度基礎(chǔ)論壇(FOCS)上,一位來自加州大學(xué)伯克利分校的博士后“一戰(zhàn)成名”:烏爾米拉·馬哈德(Urmila Mahadev)的成果被會議授予“最佳論文”和“最佳學(xué)生論文”獎。這是理論計(jì)算機(jī)科學(xué)家夢寐以求的殊榮。
曾經(jīng)與馬哈德合作的加州理工計(jì)算機(jī)科學(xué)家托馬斯·溫迪克(Thomas Vidick)在博文中表示,“這是近年來理論計(jì)算機(jī)科學(xué)和量子計(jì)算交叉領(lǐng)域中最杰出的成果。”
美德州奧斯丁大學(xué)的計(jì)算機(jī)科學(xué)家斯科特·阿倫森(Scott Aaronson,)認(rèn)為,馬哈德這一被統(tǒng)稱為“盲計(jì)算”的工作,將使其成為量子計(jì)算理論領(lǐng)域的新星。馬哈德的博士生導(dǎo)師烏爾什·瓦斯拉米(Umesh Vazirani)也表示,她學(xué)生的論文非常出色。
圖 |馬哈德在計(jì)算機(jī)科學(xué)年度基礎(chǔ)論壇獲獎(來源:FOCS)
如此成果的背后,是這位女科學(xué)家“頑固”的 7 年博士生涯:到了馬哈德 28 歲的時(shí)候,她已經(jīng)在加州伯克利研究生院度過 7 個年頭——大多數(shù)研究生根本不會待這么久。然而,馬哈德并沒有考慮畢業(yè),因?yàn)樗J(rèn)為自己的工作還沒完成。
直到2017 年春季,她才終于確認(rèn),自己已經(jīng)解決了量子計(jì)算中的核心問題之一:如何證明量子計(jì)算機(jī)的輸出結(jié)果確實(shí)對應(yīng)于用戶指令,而不是對應(yīng)于與用戶指令無關(guān)的隨機(jī)的量子現(xiàn)象。
圖 | 烏爾米拉·馬哈德(來源:加州大學(xué)伯克利分校)
量子計(jì)算領(lǐng)域最基礎(chǔ)的問題
馬哈德花了 5 年時(shí)間研究被阿倫森稱為“量子計(jì)算領(lǐng)域最基礎(chǔ)的問題”:你如何知道一臺量子計(jì)算機(jī)的輸出結(jié)果確實(shí)來自于你輸入的指令,而不是某種跟指令無關(guān)的隨機(jī)量子現(xiàn)象的體現(xiàn)?
這個問題可絕不僅僅是一個象牙塔學(xué)術(shù)問題。如果不能證明量子計(jì)算機(jī)的輸出結(jié)果確實(shí)對應(yīng)于用戶指令,那么不管是仿真黑洞行為還是計(jì)算蛋白質(zhì)構(gòu)型,結(jié)果都不可信。量子計(jì)算機(jī)的速度確實(shí)令經(jīng)典計(jì)算機(jī)望塵莫及,但是,經(jīng)典計(jì)算機(jī)能忠實(shí)執(zhí)行用戶指令,量子計(jì)算機(jī)可以么?
(來源:Pixabay)
用來證明經(jīng)典計(jì)算機(jī)輸出結(jié)果符合用戶指令的方法,無法用來證明量子計(jì)算機(jī)的計(jì)算結(jié)果可靠性。至少在理論上,經(jīng)典計(jì)算機(jī)的每一步計(jì)算結(jié)果都可以被用戶復(fù)查。然而,物理原理決定,對量子系統(tǒng)不可能進(jìn)行這種核查。量子計(jì)算的過程復(fù)雜到連將其表述出來都在技術(shù)上不可行:對于只有數(shù)百個量子比特的量子計(jì)算機(jī),要想把其內(nèi)部狀態(tài)完整表達(dá)出來,需要一塊比整個可見宇宙還大的硬盤。
就算人類能制造出足夠大的硬盤,能完整描述量子計(jì)算機(jī)內(nèi)部狀態(tài),從理論上也不可能測量這個內(nèi)部狀態(tài)。量子計(jì)算機(jī)的內(nèi)部狀態(tài)是無數(shù)狀態(tài)的同時(shí)疊加,一經(jīng)測量,馬上坍縮到某個經(jīng)典狀態(tài)——經(jīng)典的“確定態(tài)”和量子的“疊加態(tài)”完全是兩回事。
瓦斯拉米表示,量子計(jì)算機(jī)非常強(qiáng)大,但是其運(yùn)算結(jié)果的可靠性難以核查。
計(jì)算機(jī)科學(xué)家一直以來都在尋找對量子計(jì)算結(jié)果進(jìn)行檢驗(yàn)的方法。耶路撒冷希伯倫大學(xué)計(jì)算機(jī)科學(xué)家多瑞特·阿倫諾夫(Dorit Aharonov)表示,問題的核心在于首先證明:量子世界和經(jīng)典世界的結(jié)果中間有足夠強(qiáng)的聯(lián)系,下一步才是基于這種聯(lián)系,來證明量子計(jì)算的可靠性。
馬哈德在讀研究生第 2 年的時(shí)候被這個問題深深吸引,盡管她甚至不能說清這個問題為何有這么大吸引力。多年來,她嘗試了一種又一種方法?!拔姨岢隽撕芏辔艺J(rèn)為可行的方法,但是一次又一次,它們被證明無效,要么很快,要么花上 1 年功夫。”
然而她沒有放棄。瓦斯拉米說:“馬哈德表現(xiàn)的決心無人能及——從這個意義上,她非常出色?!?/p>
8 年之后,馬哈德成功了。她提出了一套協(xié)議,基于這套簡單協(xié)議,用戶無需復(fù)雜的技術(shù),就可以對量子計(jì)算機(jī)施加一定的約束,然后輸入指令,即可拿到符合自己指令的輸出。至此,量子計(jì)算機(jī)終于成為不僅“高速”,而且“可靠”的計(jì)算工具。
阿倫森表示,一個研究生做出如此成果“極其驚人”。
量子計(jì)算專家不僅對于最終提出的準(zhǔn)則給予高度評價(jià),更對馬哈德采用的創(chuàng)新性方法興趣濃厚。將這種基于經(jīng)典密碼學(xué)的方法利用到量子領(lǐng)域是個“全新的點(diǎn)子”,未來可望產(chǎn)生更多的成果。
漫長的道路
馬哈德出生于洛杉磯的的一個醫(yī)生家庭,在南加州大學(xué)讀本科,嘗試過多個領(lǐng)域。最初,她只是知道,自己不想成為一名醫(yī)生。不過,在聽過計(jì)算機(jī)科學(xué)家,RAS 公鑰加密算法發(fā)明人勒納德·阿德曼(Leonard Adleman)的課之后,對于理論計(jì)算機(jī)科學(xué)產(chǎn)生了濃厚的興趣。她在提交給伯克利的研究生申請中表示,她對理論計(jì)算機(jī)科學(xué)的任何方向都感興趣,“除了量子計(jì)算”,因?yàn)檫@聽上去太過遙遠(yuǎn),她不怎么了解。
然而,在伯克利,導(dǎo)師瓦斯拉米的教導(dǎo)很快使馬哈德改變了主意。瓦斯拉米說:“我引導(dǎo)馬哈德接觸了量子計(jì)算可靠性問題,這個問題激發(fā)了她無窮的想象?!?/p>
馬哈德說:“協(xié)議就像猜謎。我覺得它比其他的問題簡單一些,因?yàn)槟憧梢粤⒓丛谀X子里思考和分析協(xié)議,并搞清協(xié)議的工作原理?!瘪R哈德將量子計(jì)算可靠性作為博士課題,瓦斯拉米導(dǎo)師稱“這是一條非常漫長的路。”
當(dāng)然,量子計(jì)算機(jī)“計(jì)算結(jié)果難以核查”的特性并不是絕對的。比如,對大數(shù)進(jìn)行因數(shù)分解的問題,量子計(jì)算機(jī)能以經(jīng)典計(jì)算機(jī)望塵莫及的速度解決。但是,量子計(jì)算機(jī)輸出結(jié)果,經(jīng)典計(jì)算機(jī)很容易核查這個結(jié)果是否正確:只需要做一次乘法。
然而,計(jì)算機(jī)科學(xué)家相信,大多數(shù)只有量子計(jì)算機(jī)可以解決的問題沒有這么好的特性。也就是說,對于這些問題的量子計(jì)算結(jié)果,經(jīng)典計(jì)算機(jī)無法檢驗(yàn)其正確與否。而這一特性直到最近才被部分證明。2004 年,滑鐵盧大學(xué)周界研究所的的理論物理學(xué)家丹尼爾·古斯曼(Daniel Gottesman)提出問題:是否能設(shè)計(jì)一款協(xié)議,根據(jù)該協(xié)議,量子計(jì)算機(jī)的輸出結(jié)果可以被非量子觀察者核查,以確定量子計(jì)算結(jié)果確實(shí)符合用戶的目的?
4 年后,量子計(jì)算研究者取得了一些進(jìn)展。2 個研究團(tuán)隊(duì)證明,如果借助一臺擁有少量量子比特的量子計(jì)算機(jī),那么核查量子計(jì)算輸出結(jié)果就是可能的——但是只依靠經(jīng)典計(jì)算機(jī)仍然不行。隨后,研究者又證明,只要檢查者可以 1 次測量 1 個量子比特,那么核查就可以做到。
2012 年,瓦斯拉尼所在的一個研究團(tuán)隊(duì)證明,如果使用 2 ***立的量子計(jì)算機(jī)對同一個問題進(jìn)行計(jì)算,那么經(jīng)典計(jì)算機(jī)可以通過比對 2 個量子結(jié)果來驗(yàn)證量子計(jì)算的可靠性。但是這個方法一直無法被拓展到更多的應(yīng)用中,研究人員普遍認(rèn)為,這條路繼續(xù)探索的價(jià)值不大。
(來源:Quanta Magazine)
此時(shí),馬哈德進(jìn)入了這個領(lǐng)域。起初,她試圖直接做出一個終極結(jié)果,即“對量子計(jì)算機(jī)能做什么和不能做什么不加任何假定”。然而,碰壁之后,瓦斯拉尼建議,嘗試一下“后量子”密碼學(xué)方法。計(jì)算機(jī)科學(xué)家猜測(尚未嚴(yán)格證明),“后量子”密碼算法甚至能在量子計(jì)算機(jī)的破解下保持足夠的安全性,而類似于 RAS 算法的基于大數(shù)分解的經(jīng)典加密算法,在量子計(jì)算機(jī)面前不堪一擊。
2016 年,馬哈德和瓦斯拉尼在另一個問題上取得了突破,這個成果在日后被證明是通向最終答案的關(guān)鍵。兩人與 OpenAI 公司的的計(jì)算機(jī)科學(xué)家保羅·克里斯塔諾(Paul Christiano)合作,發(fā)明了一種利用密碼學(xué)來讓量子計(jì)算機(jī)創(chuàng)造“秘密狀態(tài)”的方法?!懊孛軤顟B(tài)”對于經(jīng)典計(jì)算機(jī)是不可知的,但是對于量子計(jì)算機(jī)本身是可知的的。
他們的核心工具是“陷門函數(shù)”——該函數(shù)很容易正向計(jì)算,但是反向計(jì)算幾乎不可能,除非擁有密鑰。此外,陷門函數(shù)還必須是 2 對 1 的映射,即每 1 個輸出對應(yīng)于 2 個不同的輸入。類似于 4 等于 2 的平方和-2 的平方。研究團(tuán)隊(duì)成功構(gòu)建了陷門函數(shù)。
有了陷門函數(shù),就可以令量子計(jì)算機(jī)創(chuàng)建“秘密狀態(tài)”:首先,令計(jì)算機(jī)構(gòu)建一個陷門函數(shù)所有可能輸入的疊加態(tài)——這遠(yuǎn)遠(yuǎn)沒有聽起來那么難。接著,令計(jì)算機(jī)用陷門函數(shù)處理這個疊加態(tài),產(chǎn)生一個新狀態(tài),這個新狀態(tài)是函數(shù)所有可能輸出的疊加。輸入疊加態(tài)和輸出疊加態(tài)之間存在耦合,即對其中一個的測量會影響另外一個。
隨后,令計(jì)算機(jī)測量輸出疊加態(tài),然后輸出結(jié)果。這個測量過程會讓輸出疊加態(tài)坍縮到一個輸出結(jié)果上,同時(shí)(由于耦合)輸入疊加態(tài)也同時(shí)坍縮到對應(yīng)的輸入上。比如,如果陷門函數(shù)是“平方”,輸出態(tài)是“9”,那么觀察后結(jié)果會馬上坍縮到“3”和“-3”。
由于用戶手中有陷門函數(shù)的密鑰,因此可以輕易區(qū)分構(gòu)成輸入疊加態(tài)的 2 個輸入,但量子計(jì)算機(jī)做不到。更進(jìn)一步地,量子計(jì)算機(jī)甚至不能通過測量輸入疊加態(tài)來確定其構(gòu)成,因?yàn)檫@種測量會導(dǎo)致輸入疊加態(tài)進(jìn)一步坍縮,留下的只是 2 個可能輸入中的一個,但是永遠(yuǎn)不可能確定另外一個輸入是什么。
(來源:Pixabay)
2017 年,馬哈德提出,用一種被稱為“試錯方法”的加密方法構(gòu)建陷門函數(shù),是“秘密狀態(tài)”方法的核心?!霸囧e方法”作為一種加密方法被廣泛應(yīng)用于云計(jì)算領(lǐng)域,可以令云端服務(wù)器無法讀取用戶未授權(quán)的數(shù)據(jù),即使它正在處理用戶的數(shù)據(jù)。不久,馬哈德、瓦斯拉尼、克里斯塔諾、溫迪克和以色列魏茨曼科學(xué)研究所的斯維卡·布拉克斯基(Zvika Brakerski)進(jìn)一步推動了陷門函數(shù)的研究,成功利用“秘密狀態(tài)”方法構(gòu)建了一種能證明量子計(jì)算機(jī)輸出的隨機(jī)數(shù)確實(shí)是隨機(jī)數(shù)的方法。
馬哈德此時(shí)完全可以畢業(yè),但是他決心繼續(xù)工作,直到徹底解決量子計(jì)算可靠性問題?!拔腋緵]考慮過何時(shí)畢業(yè),因?yàn)槲业哪繕?biāo)從來不是拿學(xué)位?!?/p>
她承認(rèn),探索未知領(lǐng)域有很大壓力。不過,“我想通了,花時(shí)間學(xué)習(xí)我感興趣的東西不算浪費(fèi)時(shí)間?!?/p>
一成不變
馬哈德嘗試了各種辦法,希望基于“秘密狀態(tài)”方法設(shè)計(jì)出可靠性證明協(xié)議,但是很長時(shí)間沒有進(jìn)展。
直到某天她想到:研究人員已經(jīng)證明,如果檢查者可以測量量子比特,那么就可以檢驗(yàn)量子計(jì)算結(jié)果;經(jīng)典計(jì)算機(jī)無法測量量子比特,因此無法利用這個方法檢驗(yàn)計(jì)算結(jié)果。然而,如果檢查者能強(qiáng)迫量子計(jì)算機(jī)自己來測量量子比特,然后報(bào)告自查結(jié)果呢?
這個思路的核心前提在于:在檢驗(yàn)者發(fā)出測量指令之前,量子計(jì)算機(jī)不能知道檢驗(yàn)者要做什么測量,否則計(jì)算機(jī)很容易愚弄檢驗(yàn)者?!懊孛軤顟B(tài)”方法簡直就是解決該問題的天賜工具:馬哈德令量子計(jì)算機(jī)首先創(chuàng)立一個“秘密狀態(tài)”,然后將該秘密狀態(tài)和待測狀態(tài)耦合。只有在這個時(shí)候,量子計(jì)算機(jī)才會知道,要執(zhí)行什么測量。計(jì)算機(jī)不知道秘密狀態(tài)的內(nèi)容,而檢驗(yàn)者知道。馬哈德證明,量子計(jì)算機(jī)不可能欺騙檢驗(yàn)者而不留下痕跡。溫迪克進(jìn)一步解釋,待測量子比特是“整個方法的基石”。最終,如果檢驗(yàn)結(jié)果看上去是正確的,那么檢查者就大可放心。
溫迪克:“這個點(diǎn)子太驚人了,每次烏爾米拉解釋的時(shí)候,我都會被震驚?!?/p>
馬哈德的檢驗(yàn)協(xié)議,以及隨機(jī)數(shù)生成器和盲加密算法,都依賴于這樣一個假定:量子計(jì)算機(jī)無法破解“試錯方法”。目前,“試錯方法”被認(rèn)為是首屈一指的后量子加密方法,有望被美國國家標(biāo)準(zhǔn)和技術(shù)研究所認(rèn)定為新的加密標(biāo)準(zhǔn),來取代那些面對量子計(jì)算機(jī)不堪一擊的加密方法。古斯曼表示,目前還不能說“試錯方法”可以萬無一失地克制量子計(jì)算機(jī)的解密,但是至少現(xiàn)在它足夠可靠,沒有誰發(fā)現(xiàn)這個算法有什么弱點(diǎn)可利用。
反過來,如果要愚弄馬哈德提出的檢驗(yàn)協(xié)議,那么就必須找出破解“試錯方法”的辦法,這同樣會是一個驚人的成就。
當(dāng)然,馬哈德的協(xié)議不太可能馬上被應(yīng)用,原因之一是執(zhí)行該協(xié)議需要的計(jì)算量大得驚人。不過,當(dāng)量子計(jì)算機(jī)更加強(qiáng)大,算法得以優(yōu)化之后,該協(xié)議仍有很大的應(yīng)用希望。
雖然馬哈德的協(xié)議不大可能在 5 年內(nèi)得以應(yīng)用。但是阿倫森表示,如果一切順利,這將是量子計(jì)算下一輪技術(shù)革命的起點(diǎn)。
溫迪克還補(bǔ)充,5 年前,計(jì)算機(jī)科學(xué)家普遍認(rèn)為,量子計(jì)算機(jī)想要解決任何經(jīng)典計(jì)算機(jī)解決不了的問題還要很多年?,F(xiàn)在,科研界普遍認(rèn)為:“只要 1-2 年就夠了”。因此馬哈德協(xié)議的應(yīng)用可能比想象的要快。
對于馬哈德,她承認(rèn)自己的成就令自己有點(diǎn)迷茫,她個人希望找到一個新的問題來研究。
不過,在理論計(jì)算機(jī)科學(xué)圈看來,馬哈德一統(tǒng)量子計(jì)算和加密算法的工作遠(yuǎn)遠(yuǎn)不是終點(diǎn),而是一個有望通向更多豐碩研究成果的起點(diǎn)。
-
計(jì)算機(jī)科學(xué)
+關(guān)注
關(guān)注
1文章
142瀏覽量
11341 -
量子計(jì)算機(jī)
+關(guān)注
關(guān)注
4文章
516瀏覽量
25321
原文標(biāo)題:加州大學(xué)女博士7年不肯畢業(yè),終一戰(zhàn)成名!獲理論計(jì)算機(jī)界至高榮譽(yù),破解“量子計(jì)算問題”
文章出處:【微信號:gh_f97d2589983b,微信公眾號:高速射頻百花潭】歡迎添加關(guān)注!文章轉(zhuǎn)載請注明出處。
發(fā)布評論請先 登錄
相關(guān)推薦
評論