量子計(jì)算新突破：密碼學(xué)迎來(lái)大考

你最近發(fā)送的電子郵件很可能是使用一種經(jīng)典加密方法進(jìn)行加密的，這種方法基于這樣一個(gè)想法：即使是最快的計(jì)算機(jī)也無(wú)法高效地將一個(gè)巨大的數(shù)字分解成因數(shù)。

然而，量子計(jì)算機(jī)則有潛力能夠快速破解傳統(tǒng)計(jì)算機(jī)可能永遠(yuǎn)無(wú)法解決的復(fù)雜密碼系統(tǒng)。這可能會(huì)基于1994年由彼得·肖爾（現(xiàn)為美國(guó)麻省理工學(xué)院教授）提出的量子分解算法實(shí)現(xiàn)。

盡管過(guò)去30年來(lái)研究人員取得了巨大進(jìn)展，但科學(xué)家們?nèi)晕唇ㄔ斐鲎銐驈?qiáng)大的量子計(jì)算機(jī)來(lái)運(yùn)行肖爾的算法。

一些研究人員正在努力建造更大的量子計(jì)算機(jī)，而另一些研究人員則嘗試改進(jìn)肖爾的算法，使得它可以在較小的量子電路上運(yùn)行。大約一年前，紐約大學(xué)計(jì)算機(jī)科學(xué)家?jiàn)W德·雷格夫提出了一項(xiàng)重大理論改進(jìn)。他的算法運(yùn)行速度更快，但需要更多內(nèi)存。

基于這些研究結(jié)果，麻省理工學(xué)院的研究人員提出了一種結(jié)合了奧德·雷格夫算法速度和肖爾算法內(nèi)存效率的折中方法。這個(gè)新算法與奧德·雷格夫的算法一樣快，但需要更少的量子構(gòu)件（稱為量子比特），并且對(duì)量子噪聲的容忍度更高，這可能使其在實(shí)際中更容易實(shí)現(xiàn)。

從長(zhǎng)遠(yuǎn)來(lái)看，這種新算法可能為開(kāi)發(fā)能夠抵抗量子計(jì)算機(jī)破解能力的全新加密方法提供指導(dǎo)。 “如果大規(guī)模的量子計(jì)算機(jī)最終被建造出來(lái)，那么分解算法就失效了，我們必須找到其他的加密方法。但這真的會(huì)是個(gè)威脅嗎？ 我們能讓量子分解算法變得實(shí)用嗎？我們的研究可能讓我們離實(shí)用化更近了一步?！备Ｌ鼗饡?huì)工程學(xué)教授、計(jì)算機(jī)科學(xué)與人工智能實(shí)驗(yàn)室（CSAIL）成員兼該論文的資深作者維諾德說(shuō)。

該論文的主要作者是麻省理工學(xué)院電子工程與計(jì)算機(jī)科學(xué)系的研究生拉加萬(wàn)。這項(xiàng)研究將在2024年國(guó)際密碼學(xué)會(huì)議上發(fā)表。

破解密碼學(xué)

為了通過(guò)互聯(lián)網(wǎng)安全地傳輸信息，電子郵件客戶端和消息應(yīng)用等服務(wù)提供商通常依賴于一種名為RSA的加密方案。

然而，在1994年，肖爾在貝爾實(shí)驗(yàn)室工作時(shí)提出了一個(gè)算法，證明量子計(jì)算機(jī)可以快速分解，從而打破RSA加密。

“ 那是一個(gè)轉(zhuǎn)折點(diǎn)。但在1994年， 沒(méi)人知道如何建造足夠大的量子計(jì)算機(jī)。而我們現(xiàn)在還遠(yuǎn)遠(yuǎn)沒(méi)有實(shí)現(xiàn)這一目標(biāo)。有些人甚至懷疑它們是否真的會(huì)被建造出來(lái)。”維諾德說(shuō)。

據(jù)估計(jì)， 一臺(tái)量子計(jì)算機(jī)大約需要2000萬(wàn)個(gè)量子比特才能運(yùn)行肖爾的算法。而目前，最大的量子計(jì)算機(jī)大約只有1100個(gè)量子比特。

量子計(jì)算機(jī)通過(guò)量子電路執(zhí)行計(jì)算，就像經(jīng)典計(jì)算機(jī)使用經(jīng)典電路一樣。每個(gè)量子電路由一系列稱為量子門(mén)的操作組成，這些量子門(mén)利用量子比特（量子計(jì)算機(jī)最小的構(gòu)件）進(jìn)行計(jì)算。

但量子門(mén)會(huì)引入噪聲，因此減少量子門(mén)的數(shù)量可以提高機(jī)器的性能。研究人員一直在努力改進(jìn)肖爾的算法，以便它可以在較小的電路上運(yùn)行，使用更少的量子門(mén)。

這正是雷格夫在一年前提出的電路所做的。

“這是一個(gè)大新聞，因?yàn)檫@是自1994年肖爾提出的電路以來(lái)的首次真改進(jìn)。”維諾德說(shuō)。

肖爾提出的量子電路的大小與所分解數(shù)字的平方成正比。這意味著如果要分解一個(gè)2048位的整數(shù)，電路將需要數(shù)百萬(wàn)個(gè)量子門(mén)。

雷格夫的電路需要顯著更少的量子門(mén)，但它需要更多的量子比特來(lái)提供足夠的內(nèi)存，而這帶來(lái)了一個(gè)新的問(wèn)題。

“從某種意義上說(shuō)，有些類型的量子比特就像蘋(píng)果或橙子。如果你長(zhǎng)時(shí)間保留它們，它們會(huì)衰減。你希望盡量減少需要保留的量子比特的數(shù)量?！?/p>

他在2023年8月的一個(gè)研討會(huì)上聽(tīng)到了雷格夫的講座。在講座結(jié)束時(shí)，雷格夫提出了一個(gè)問(wèn)題：有人能改進(jìn)他的電路以減少所需的量子比特嗎？

量子乒乓

為了分解一個(gè)非常大的數(shù)字，量子電路需要多次運(yùn)行，執(zhí)行涉及計(jì)算冪次的操作，如2的100次方。

但是，計(jì)算如此大的冪次在量子計(jì)算機(jī)上成本高昂且難以執(zhí)行，因?yàn)榱孔佑?jì)算機(jī)只能執(zhí)行可逆操作。而平方一個(gè)數(shù)字不是一個(gè)可逆操作，所以每次進(jìn)行平方計(jì)算時(shí)，必須增加更多的量子內(nèi)存來(lái)計(jì)算下一個(gè)平方。

麻省理工學(xué)院的研究人員找到了一種巧妙的方法，通過(guò)使用一系列斐波那契數(shù)進(jìn)行冪次計(jì)算，這只需要簡(jiǎn)單的乘法操作，而乘法是可逆的。他們的方法只需要兩個(gè)量子內(nèi)存單元來(lái)計(jì)算任何冪次。

“這有點(diǎn)像乒乓球比賽，我們從一個(gè)數(shù)字開(kāi)始，然后在兩個(gè)量子內(nèi)存寄存器之間來(lái)回彈跳進(jìn)行乘法運(yùn)算?！本S諾德補(bǔ)充道。

他們還解決了糾錯(cuò)問(wèn)題。肖爾和雷格夫提出的電路要求每個(gè)量子操作都必須是正確的，算法才能正常工作。但在真實(shí)機(jī)器上實(shí)現(xiàn)無(wú)誤的量子門(mén)是不可行的。

他們通過(guò)使用一種技術(shù)過(guò)濾掉錯(cuò)誤的結(jié)果并僅處理正確的結(jié)果，克服了這個(gè)問(wèn)題。

最終結(jié)果是一個(gè)顯著更節(jié)省內(nèi)存的電路。此外，他們的糾錯(cuò)技術(shù)使該算法更具實(shí)用性。

“作者解決了之前量子分解算法中的兩個(gè)最重要瓶頸。盡管仍然不夠?qū)嵱?，但他們的工作讓量子分解算法更接近現(xiàn)實(shí)?！崩赘穹蜓a(bǔ)充道。

未來(lái)，研究人員希望使他們的算法更加高效，并有朝一日在真實(shí)的量子電路上測(cè)試分解。 （綜合整理報(bào)道）（策劃/克珂）