（圖片來(lái)源：網(wǎng)絡(luò)）

1994年，美國(guó)麻省理工學(xué)院 (MIT) 的應(yīng)用數(shù)學(xué)家Peter Shor實(shí)現(xiàn)了量子計(jì)算機(jī)的第一個(gè)實(shí)際應(yīng)用：破譯密碼。他展示了在查找大質(zhì)數(shù)的質(zhì)因子時(shí)，量子計(jì)算機(jī)比傳統(tǒng)計(jì)算機(jī)要快得多，查找速度呈指數(shù)級(jí)增加。這些大質(zhì)數(shù)通常用作密鑰，加密保護(hù)通過(guò)互聯(lián)網(wǎng)發(fā)送的大部分信息。

盡管今天量子計(jì)算機(jī)的量子比特?cái)?shù)量還不夠多或不夠可靠，無(wú)法實(shí)現(xiàn)大規(guī)模的Shor算法，但30年來(lái)，對(duì)Shor算法的研究一直經(jīng)久不衰。

現(xiàn)在，一位計(jì)算機(jī)科學(xué)家研發(fā)了一種比Shor算法更好的新量子算法。

8月12日首次發(fā)布到arXiv服務(wù)器的預(yù)印本中，紐約大學(xué)的Oded Regev提出了一種方案，可以大大減少分解非常大的質(zhì)數(shù)所需的邏輯門或邏輯步驟的數(shù)量。

原則上，該方案可以讓小規(guī)模的量子計(jì)算機(jī)找出密鑰，或者讓中等規(guī)模的量子計(jì)算機(jī)更快地解碼。

評(píng)估過(guò)這項(xiàng)工作的獨(dú)立密碼學(xué)家也很感興趣。例如下個(gè)月Regev將召開他的新算法座談會(huì)，麻省理工學(xué)院的計(jì)算機(jī)科學(xué)家Vinod Vaikuntanathan預(yù)計(jì)，屆時(shí)會(huì)座無(wú)虛席。Vaikuntanathan 表示：“在量子計(jì)算領(lǐng)域，自Shor算法提出的30年里，已經(jīng)出現(xiàn)了兩到三個(gè)新想法。雖然不能每天都會(huì)出現(xiàn)新想法，但這讓我們充滿希望。”杜克大學(xué)量子計(jì)算研究員Kenneth Brown對(duì)此表示贊同：“大家都花費(fèi)很長(zhǎng)時(shí)間研究Shor算法，而這個(gè)新結(jié)果是令人驚訝的，而且超級(jí)酷?！?/p>

與所有量子算法一樣，Shor算法依賴于量子比特的神秘屬性，它不僅可以設(shè)置為0和1的值，還可以同時(shí)設(shè)置為0和1的“疊加態(tài)”。量子比特可以拼接成量子門，執(zhí)行邏輯運(yùn)算。為了分解n位長(zhǎng)的數(shù)字，Shor 算法需要n^2個(gè)門的量子電路。

現(xiàn)在大多數(shù)互聯(lián)網(wǎng)加密都依賴于至少2048比特的二進(jìn)制質(zhì)數(shù)，相當(dāng)于617位長(zhǎng)的十進(jìn)制數(shù)字。因此，要用Shor算法找到它們的質(zhì)因數(shù)，需要至少有400萬(wàn)個(gè)量子門的量子計(jì)算機(jī)。

但迄今為止最大的量子計(jì)算機(jī)只有數(shù)百個(gè)量子比特。Brown說(shuō)：“它們的規(guī)模都遠(yuǎn)不及我們完成破解所需要的數(shù)字?！?/p>

更糟糕的是，環(huán)境噪聲常常破壞量子比特微妙的疊加態(tài)，從而破壞其運(yùn)行計(jì)算。Vaikuntanathan說(shuō)：“噪聲可以通過(guò)糾錯(cuò)來(lái)解決，但這需要更多的量子比特，數(shù)量達(dá)數(shù)百萬(wàn)甚至數(shù)十億。量子比特的數(shù)量因?yàn)榧m錯(cuò)需要爆炸式增長(zhǎng)了，這就是為什么我們離真正能夠分解2048位數(shù)字還很遠(yuǎn)。加強(qiáng)糾錯(cuò)會(huì)有所幫助，但改進(jìn)Shor算法也會(huì)有幫助?！?/p>

Regev找到了一種方法來(lái)實(shí)現(xiàn)這一點(diǎn)。由于Shor算法是一維的，它通過(guò)將單個(gè)數(shù)字進(jìn)行高次冪來(lái)搜索素因數(shù)。在得出結(jié)果之前，必須將許多大數(shù)相乘。Regev意識(shí)到他可以將多個(gè)不同維度的數(shù)字相乘。盡管這兩種算法需要的乘法總數(shù)大致相同，但Regev的多維特征意味著在得出結(jié)果之前，乘法數(shù)字不會(huì)變得那么大。最后，他發(fā)現(xiàn)只需要n^1.5個(gè)門即可分解一個(gè)n位整數(shù)。

Vaikuntanathan表示，這是30年來(lái)對(duì)Shor算法的首次重大改進(jìn)。

但瑞典政府的量子計(jì)算研究員Martin Eker?表示，Regev的算法也存在缺陷。Regev的算法需要量子存儲(chǔ)器在計(jì)算過(guò)程中存儲(chǔ)中間值，這意味著需要更多高質(zhì)量的量子比特，這增加了算法的成本。Regev承認(rèn)對(duì)量子內(nèi)存的需求，但表示當(dāng)量子內(nèi)存更便宜時(shí)，該算法最終仍然會(huì)有價(jià)值?！?/p>

當(dāng)量子計(jì)算機(jī)準(zhǔn)備好通過(guò)實(shí)施Regev或Shor算法來(lái)找到質(zhì)因數(shù)時(shí)，互聯(lián)網(wǎng)加密算法也在繼續(xù)發(fā)展。聯(lián)邦機(jī)構(gòu)和安全領(lǐng)導(dǎo)人已經(jīng)開始轉(zhuǎn)向替代方案，包括所謂的“晶格密學(xué)”，它可以免受使用量子計(jì)算機(jī)的黑客攻擊。即便如此，像Regev和Shor 這樣的算法可以用來(lái)解密當(dāng)前和已經(jīng)存下來(lái)的信息。

量子密碼學(xué)一直在努力尋求重大突破。無(wú)論如何，Brown相信Regev工作的新穎性可能會(huì)激發(fā)量子密碼學(xué)領(lǐng)域的其他新想法。他說(shuō)：“我正在思考如何進(jìn)一步推動(dòng)這一目標(biāo)。”

編譯：卉可

編輯：慕一

特此說(shuō)明：量子前哨翻譯此文僅作信息傳遞和參考，并不意味著同意此文中的觀點(diǎn)與數(shù)據(jù)。 —— end——