來自加州大學(xué)伯克利分校的研究生Urmila Mahadev解決了量子計(jì)算中的驗(yàn)證問題。她將經(jīng)典密碼學(xué)與量子領(lǐng)域進(jìn)行結(jié)合,解決了“量子計(jì)算中最根本的問題之一?!奔矗绻阕屢慌_量子計(jì)算機(jī)為你執(zhí)行一個計(jì)算,那么你如何確定它確實(shí)執(zhí)行了你的指令,甚至如何得知它是否做了與量子相關(guān)的事情。
2017年春天,Urmila Mahadev解決了量子計(jì)算中的一個重要問題,即從量子物理學(xué)的奇怪定律中獲得能量的計(jì)算機(jī)研究。Mahadev的新成果與她之前的論文結(jié)合在一起,被稱為“盲計(jì)算(blind computation)”。
德克薩斯大學(xué)奧斯汀分校的計(jì)算機(jī)科學(xué)家Scott Aaronson說:“她顯然是一顆冉冉升起的新星。”
Mahadev當(dāng)時(shí)28歲,已經(jīng)在加州大學(xué)伯克利分校讀了7年研究生,很多急于畢業(yè)的學(xué)生早就離開了學(xué)校。她在伯克利的博士導(dǎo)師Umesh Vazirani說:“她現(xiàn)在終于有了一個非常漂亮的博士論文?!?/p>
但是Mahadev并沒有在那年選擇畢業(yè),她甚至沒有考慮過畢業(yè)。她覺得她的夢想并沒有完成。
五年多來,在她眼中想要解決的問題與其他人不同,Aaronson將此稱之為“量子計(jì)算中最為基礎(chǔ)的問題之一?!奔?,如果你讓一臺量子計(jì)算機(jī)為你執(zhí)行一個計(jì)算,那么你如何確定它確實(shí)執(zhí)行了你的指令,甚至如何得知它是否做了與量子相關(guān)的事情。
這個問題可能很快就會遠(yuǎn)離學(xué)術(shù)界。研究人員希望,過不了太多年,量子計(jì)算機(jī)就能在許多問題上提供指數(shù)級的加速,例如模擬黑洞周圍的行為、模擬大蛋白質(zhì)的折疊方式等。
但是,一旦量子計(jì)算機(jī)能夠完成經(jīng)典計(jì)算機(jī)無法完成的計(jì)算,我們怎么知道它是否正確地完成了這些計(jì)算呢?
如果你不信任一臺普通的電腦,理論上,你可以自己仔細(xì)檢查它在計(jì)算過程中的每一個步驟。
但是量子系統(tǒng)從根本上來說是抵制這種檢查的。首先,它們的內(nèi)部工作是極其復(fù)雜的:用幾百個量子比特(quantum bit)來描述一臺計(jì)算機(jī)的內(nèi)部狀態(tài)需要一個比整個可見宇宙都大的硬盤。
即使你有足夠的空間寫下這個描述,也沒有辦法得到它。量子計(jì)算機(jī)的內(nèi)部狀態(tài)通常是許多不同的非量子“經(jīng)典”狀態(tài)的疊加(比如薛定諤的貓,它既死又活)。但是一旦你測量一個量子態(tài),它就會崩潰成一個經(jīng)典態(tài)。
Vazirani說:“量子計(jì)算機(jī)功能非常強(qiáng)大,但同時(shí)它也非常隱秘。”
考慮到這些限制因素,計(jì)算機(jī)科學(xué)家們長期以來一直想知道量子計(jì)算機(jī)是否有可能提供任何證據(jù)能夠證明它確實(shí)做到了聲明的那些功能。耶路撒冷希伯來大學(xué)的計(jì)算機(jī)科學(xué)家Dorit Aharonov問道:“量子和古典世界之間的相互作用是否足夠強(qiáng)大到可以進(jìn)行對話?”
在研究生二年級的時(shí)候,馬哈德夫被這個問題迷住了,原因連她自己都不完全明白。在隨后的幾年里,她嘗試了一種接一種的方法。她說:“有很多次我覺得做得不錯的時(shí)候,要么很快就失敗了,要么做了一年才發(fā)現(xiàn)是失敗的。”
但她拒絕放棄。Mahadev表現(xiàn)出一種前所未有的決心。而今,經(jīng)過八年的研究生學(xué)習(xí)生涯,Mahadev終于成功了。
她提出了一種交互式協(xié)議,通過這種協(xié)議,沒有量子能力的用戶可以使用密碼學(xué)在量子計(jì)算機(jī)上安裝一個套具,并在他們想要的任何地方驅(qū)動它,并保證量子計(jì)算機(jī)正在遵循他們的指令。
Aaronson說:“對于一個研究生來說,獨(dú)自完成這樣一個任務(wù)是非常令人震驚的!”
Mahadev現(xiàn)在是UC Berkeley的博士后研究員。昨天,她在計(jì)算機(jī)科學(xué)基金會(foundation of Computer Science)年度研討會上提交了自己的方案。她的作品獲得了該會議的“最佳論文”和“最佳學(xué)生論文”獎,這對一位理論計(jì)算機(jī)科學(xué)家來說是罕見的榮譽(yù)。
加州理工學(xué)院(California Institute of Technology)的計(jì)算機(jī)科學(xué)家Thomas Vidick過去曾與Mahadev有過合作,他在一篇博客文章中稱,Mahadev的研究成果“是近年來量子計(jì)算和理論計(jì)算機(jī)科學(xué)領(lǐng)域出現(xiàn)的最杰出的思想之一”。
量子計(jì)算研究人員不僅對Mahadev的協(xié)議所取得的成就感到高興,更對她為解決這個問題所采取的全新方法感到興奮。Vidick寫道,在量子領(lǐng)域使用經(jīng)典密碼學(xué)是一個“真正新穎的想法”?!拔翌A(yù)計(jì),在這些想法的基礎(chǔ)上,還會有更多的成果?!?/p>
漫漫研究路
Mahadev在洛杉磯的一個醫(yī)生家庭長大,她就讀于南加州大學(xué),她從一個學(xué)習(xí)領(lǐng)域徘徊到另一個領(lǐng)域,只是不想成為一名醫(yī)生。后來,計(jì)算機(jī)科學(xué)家Leonard Adleman教授的一門課讓她對理論計(jì)算機(jī)科學(xué)感到興奮。她申請了UC Berkeley的研究生院,在申請材料中解釋說她對理論計(jì)算機(jī)科學(xué)的所有方面都感興趣——除了量子計(jì)算。
她說:“量子計(jì)算聽起來特別遙遠(yuǎn),我對它一無所知?!?/p>
但是當(dāng)她在伯克利的時(shí)候,Vazirani通俗易懂的解析很快改變了她的想法。他向她介紹了如何找到驗(yàn)證量子計(jì)算的協(xié)議,這個問題“激發(fā)了她的想象力”,Vazirani說。
“協(xié)議就像謎題,”Mahadev解釋說。對我來說,這些問題似乎比其他問題更容易回答,因?yàn)槟憧梢宰约毫⒓撮_始思考協(xié)議,然后打破它們,這樣你就能看到它們是如何工作的。她選擇了這個問題作為她的博士研究課題,開始了她的“漫漫長路”。
如果量子計(jì)算機(jī)可以解決一個經(jīng)典計(jì)算機(jī)無法解決的問題,那并不意味著解決方案將難以檢驗(yàn)。以大數(shù)因式分解為例,這是一個大型量子計(jì)算機(jī)可以有效解決的問題,但一般認(rèn)為任何經(jīng)典計(jì)算機(jī)都無法解決。即使經(jīng)典計(jì)算機(jī)不能因式分解一個數(shù)字,它也可以很容易地檢查量子計(jì)算機(jī)的因式分解是否正確——它只需要把這些因子相乘,看看它們是否產(chǎn)生了正確的答案。
然而,計(jì)算機(jī)科學(xué)家認(rèn)為(并且最近向證明邁出了一步)量子計(jì)算機(jī)可以解決的許多問題并沒有這個特征。換句話說,經(jīng)典計(jì)算機(jī)不僅無法解決這些問題,甚至無法識別所提出的解決方案是否正確。鑒于此,于2004年左右,安大略省滑鐵盧周界理論物理研究所的物理學(xué)家Daniel Gottesman提出了一個問題,即,如果你讓一臺量子計(jì)算機(jī)為你執(zhí)行一個計(jì)算,那么你如何確定它確實(shí)執(zhí)行了你的指令,甚至如何得知它是否做了與量子相關(guān)的事情。
在四年時(shí)間里,量子計(jì)算研究人員已經(jīng)得到了部分答案。兩個不同的團(tuán)隊(duì)表明,量子計(jì)算機(jī)可以證明它的計(jì)算,不是一個純粹的經(jīng)典驗(yàn)證者(classical verifier),而是對一個能夠訪問它自己的非常小的量子計(jì)算機(jī)的驗(yàn)證者。研究人員后來改進(jìn)了這種方法,以表明驗(yàn)證者所需要的是每次測量一個量子比特的能力。
2012年,包括Vazirani在內(nèi)的一組研究人員表示,如果量子計(jì)算是由一對無法相互通信的量子計(jì)算機(jī)進(jìn)行的,那么一個完全經(jīng)典的驗(yàn)證者就可以檢查量子計(jì)算。Gottesman說,但那份論文的方法是針對這種特定情形而設(shè)計(jì)的,這個問題似乎陷入了死胡同?!拔蚁肟赡苡腥苏J(rèn)為你不能再往下進(jìn)行了?!?/p>
大約在這個時(shí)候Mahadev遇到了驗(yàn)證問題。
起初,她試圖得出一個“無條件”的結(jié)果,一個對量子計(jì)算機(jī)能做什么或不能做什么的假設(shè)。但是,在她研究這個問題一段時(shí)間沒有取得任何進(jìn)展后,Vazirani提出了使用“后量子”加密的可能性——也就是說,研究人員認(rèn)為即使量子計(jì)算機(jī)也無法破解這種加密,盡管他們不確定。(用于加密在線交易等信息的RSA算法等方法并不是后量子算法——大型量子計(jì)算機(jī)可能會破壞它們,因?yàn)樗鼈兊陌踩砸蕾囉诜纸獯髷?shù)的難度。)
2016年,Mahadev和Vazirani在研究另一個問題時(shí)取得了進(jìn)步,這在后來被證明是至關(guān)重要的。他們與OpenAI的研究科學(xué)家Paul Christiano合作,開發(fā)了一種利用密碼學(xué)的方法來讓量子計(jì)算機(jī)構(gòu)建所謂的“secret state”——一種其描述為經(jīng)典驗(yàn)證者(classical verifier)所知,而不是為量子計(jì)算機(jī)本身所知的狀態(tài)。
他們的程序依賴于“陷門”(trapdoor)函數(shù),這種函數(shù)很容易執(zhí)行,但很難逆轉(zhuǎn),除非你有一個私密的加密密鑰。(研究人員還不知道如何真正構(gòu)建一個合適的陷門函數(shù)。)函數(shù)也要求是“2對1”,這意味著每個輸出對應(yīng)兩個不同的輸入。例如,平方函數(shù)——除了0,每個輸出(例如9)有兩個對應(yīng)輸入(3和?3)。
有了這樣一個函數(shù),你就可以讓量子計(jì)算機(jī)創(chuàng)建一個secret state,如下所示:首先,要求計(jì)算機(jī)建立一個所有可能的函數(shù)輸入的疊加。然后,告訴計(jì)算機(jī)將函數(shù)應(yīng)用到這個巨大的疊加上,創(chuàng)建一個新的狀態(tài),這個狀態(tài)是函數(shù)的所有可能輸出的疊加。輸入和輸出的疊加會產(chǎn)生糾纏,這意味著其中對一個的測量結(jié)果會立即影響到另一個。
接下來,要求計(jì)算機(jī)測量輸出狀態(tài)并告訴你結(jié)果。此測量將輸出狀態(tài)坍縮(collapse)為只有一個可能的輸出,并且輸入狀態(tài)立即坍縮來匹配它,因?yàn)樗鼈兪羌m纏的——例如,如果使用平方函數(shù),如果輸出是9的狀態(tài),輸入將會坍縮成3和?3的疊加態(tài)。
但要記住,你使用的是trapdoor函數(shù)。你有trapdoor的密鑰,所以你可以很容易地找出構(gòu)成輸入疊加的兩個態(tài)。但是量子計(jì)算機(jī)不能。它不能簡單地測量輸入疊加來求出它是由什么態(tài)構(gòu)成的,因?yàn)檫@個測量會使它進(jìn)一步坍縮,讓計(jì)算機(jī)只剩下兩個輸入中的一個,但無法找出另一個。
2017年,Mahadev通過一種名為“Learning With Errors”(LWE)的加密技術(shù),找到了如何在secret-state方法的核心構(gòu)建trapdoor函數(shù)的方法。利用這些trapdoor函數(shù),她能夠創(chuàng)建一個量子版本的“盲”計(jì)算(blind computation),通過這種計(jì)算,云計(jì)算用戶可以屏蔽他們的數(shù)據(jù),這樣云計(jì)算機(jī)即使在計(jì)算時(shí)也無法讀取數(shù)據(jù)。不久之后,Mahadev、Vazirani和Christiano與Vidick和Zvika Brakerski(以色列魏茨曼科學(xué)研究所的科學(xué)家)合作,進(jìn)一步完善了這些trapdoor函數(shù),利用secret-state方法開發(fā)了一種量子計(jì)算機(jī)生成可證實(shí)的隨機(jī)數(shù)的簡單方法。
Mahadev本可以憑借這些結(jié)果畢業(yè),但她決心繼續(xù)研究,直到解決驗(yàn)證問題?!拔覐奈聪脒^畢業(yè),因?yàn)槲业哪繕?biāo)從來就不是畢業(yè),”她說。
她不知道是否能解決這個問題,這有時(shí)會讓人感到壓力。但是,她說:“我花時(shí)間學(xué)習(xí)感興趣的東西,所以這真的不能說是浪費(fèi)時(shí)間?!?/p>
解決驗(yàn)證問題
Mahadev嘗試了從secret-state方法到驗(yàn)證協(xié)議的各種方法,但有一段時(shí)間她一無所獲。然后她產(chǎn)生了一個想法:研究人員已經(jīng)證明,如果一個驗(yàn)證者(verifier)能夠測量量子比特,它就可以檢驗(yàn)量子計(jì)算機(jī)。根據(jù)定義,classical verifier缺乏這種能力。但是,如果classical verifier能夠以某種方式強(qiáng)迫量子計(jì)算機(jī)執(zhí)行測量并誠實(shí)地報(bào)告它們,結(jié)果會怎樣呢?
Mahadev意識到,最棘手的部分是讓量子計(jì)算機(jī)在它知道verifier會要求哪種測量方法之前,先確定它要測量的state——否則,計(jì)算機(jī)很容易欺騙verifier。這就是secret-state方法發(fā)揮作用的地方:Mahadev的協(xié)議要求量子計(jì)算機(jī)首先創(chuàng)建一個secret state,然后將其與它應(yīng)該測量的state糾纏在一起。只有這樣,計(jì)算機(jī)才知道要執(zhí)行哪種測量。
由于計(jì)算機(jī)不知道secret state的構(gòu)成,但verifier知道,Mahadev表明,量子計(jì)算機(jī)不可能在不留下明顯的欺騙痕跡的情況下進(jìn)行大型作弊。Vidick寫道,從本質(zhì)上講,計(jì)算機(jī)要測量的量子比特被“加密且固定不變”。因此,如果測量結(jié)果看起來像一個正確的證明,verifier就能確信它們確實(shí)是。
“這是一個非常好的想法!””Vidick寫道,“每次Urmila解釋它的時(shí)候,都讓我感到震驚?!?/p>
Mahadev的驗(yàn)證協(xié)議——以及隨機(jī)數(shù)生成器和盲加密方法——取決于量子計(jì)算機(jī)不能破解LWE的假設(shè)。目前,LWE被廣泛認(rèn)為是后量子密碼學(xué)的主要候選,可能很快就會被國家標(biāo)準(zhǔn)和技術(shù)研究所采用作為其新的加密標(biāo)準(zhǔn),以取代量子計(jì)算機(jī)可能破解的標(biāo)準(zhǔn)。Gottesman警告說,這并不能保證它對量子計(jì)算機(jī)是安全的,“但到目前為止它還很穩(wěn)固,還沒有證據(jù)證明它可能被破解?!?/p>
Vidick寫道,無論如何,該協(xié)議對LWE的依賴使得Mahadev的工作帶來了雙贏。量子計(jì)算機(jī)欺騙協(xié)議的唯一方法是量子計(jì)算世界中有人找到了破解LWE的方法,這本身就是一項(xiàng)了不起的成就。
Mahadev的協(xié)議不太可能在不久的將來在真正的量子計(jì)算機(jī)上實(shí)現(xiàn)。目前,該協(xié)議需要很大的計(jì)算能力才能實(shí)現(xiàn)實(shí)用。但隨著量子計(jì)算機(jī)規(guī)模的越來越大,以及研究人員簡化協(xié)議,未來這種情況可能會改變。
Aaronson說,Mahadev的協(xié)議可能在未來五年之內(nèi)都不可行,但“在幻想世界里也不是完全不可行”。“如果一切順利,在量子計(jì)算機(jī)發(fā)展的下一個階段,就可以開始思考這個問題了?!?/p>
考慮到這個領(lǐng)域現(xiàn)在發(fā)展的速度有多快,這個階段可能會很快到來。Vidick說,畢竟,就在五年前,研究人員還認(rèn)為量子計(jì)算機(jī)要想解決經(jīng)典計(jì)算機(jī)無法解決的任何問題都還需要很多年?!艾F(xiàn)在,”他說,“人們認(rèn)為這將在一兩年內(nèi)發(fā)生。”
至于Mahadev,解決了她最喜歡的問題讓她有點(diǎn)茫然。她希望找到一個新問題。
但理論計(jì)算機(jī)科學(xué)家認(rèn)為,Mahadev將量子計(jì)算和密碼學(xué)統(tǒng)一起來與其說是故事的結(jié)束,不如說是有望證明許多觀點(diǎn)的初步探索。
“我感覺會有很多后續(xù)研究,”Aharonov說,“我期待著Urmila取得更多結(jié)果。”
-
計(jì)算機(jī)
+關(guān)注
關(guān)注
19文章
7663瀏覽量
90812 -
量子計(jì)算機(jī)
+關(guān)注
關(guān)注
4文章
535瀏覽量
26457
原文標(biāo)題:【八年苦讀】伯克利研究生解決量子計(jì)算驗(yàn)證問題
文章出處:【微信號:AI_era,微信公眾號:新智元】歡迎添加關(guān)注!文章轉(zhuǎn)載請注明出處。
發(fā)布評論請先 登錄
全球首顆電子光子量子一體化芯片問世:創(chuàng)新叩開量子實(shí)用化大門
NVIDIA助力全球最大量子研究超級計(jì)算機(jī)
“Quantum Origin”成首個獲NIST驗(yàn)證的軟件量子隨機(jī)數(shù)生成器
浙江大學(xué)與大華股份共建研究生聯(lián)合培育基地
NVIDIA助力解決量子計(jì)算領(lǐng)域重大挑戰(zhàn)
基于玻色量子相干光量子計(jì)算機(jī)的混合量子經(jīng)典計(jì)算架構(gòu)

Litestar 4D:McCree莫克利曲線
一種高靈敏的化學(xué)檢測系統(tǒng)

量子通信與量子計(jì)算的關(guān)系
廣立微助力2024中國研究生創(chuàng)“芯”大賽·EDA精英挑戰(zhàn)賽
玻色量子與北京理工大學(xué)達(dá)成量子云計(jì)算合作
“本源悟空”超導(dǎo)量子計(jì)算機(jī)助力大規(guī)模流體動力學(xué)量子計(jì)算

RISC-V AI技術(shù)正式納入北京大學(xué)研究生課程

評論