在一項(xiàng)最新研究中，清華大學(xué)龍桂魯、浙江大學(xué)王浩華等組成的團(tuán)隊(duì)創(chuàng)建了一種算法，僅用10個(gè)超導(dǎo)量子比特就實(shí)現(xiàn)了48位因式分解。

01 全新整數(shù)分解算法，刷新歷史記錄

大多數(shù)專家認(rèn)為這項(xiàng)任務(wù)將需要數(shù)百萬(wàn)個(gè)量子比特。

該團(tuán)隊(duì)的最新實(shí)驗(yàn)表明，依靠整數(shù)因子化的公鑰密碼技術(shù)可能很快就會(huì)受到當(dāng)今原始的NISQ（含噪聲中等規(guī)模）量子計(jì)算機(jī)的攻擊。

據(jù)研究人員稱，該算法是基于經(jīng)典的Schnorr算法——使用格約化來(lái)分解整數(shù)，同時(shí)依靠量子近似優(yōu)化算法（QAOA）來(lái)優(yōu)化Schnorr算法中最耗時(shí)的部分，以提高因式分解的速度。

研究人員表示，“使用這種算法，我們已經(jīng)成功地對(duì)整數(shù)1961（11位）、48567227（26位）和261980999226229（48位）進(jìn)行了因式分解，在超導(dǎo)量子處理器中分別使用了3、5和10個(gè)量子比特。對(duì)于48位的整數(shù)，261980999226229，我們也刷新了真正的量子設(shè)備中用一般方法算出的最大整數(shù)?！?

使用這種算法的近期量子計(jì)算機(jī)可能能夠處理更大的整數(shù)分解問(wèn)題，可能打破廣泛用于保護(hù)計(jì)算機(jī)數(shù)據(jù)和系統(tǒng)的RSA-2048加密方案。

次線性資源量子整數(shù)分解（SQIF）算法的工作流。

實(shí)驗(yàn)裝置和SQIF算法的QAOA電路

RSA數(shù)字的資源估計(jì)。提到的主要量子資源是量子比特的數(shù)量、QAOA的量子電路深度與三種典型拓?fù)浣Y(jié)構(gòu)的單次迭代。

02 即將在NISQ設(shè)備實(shí)現(xiàn)，算法加速有待確認(rèn)

研究人員表示，“通過(guò)估算RSA-2048因式分解所需的量子資源來(lái)進(jìn)行。我們發(fā)現(xiàn)，即使在最簡(jiǎn)單的一維鏈系統(tǒng)中，也需要一個(gè)具有372個(gè)物理量子比特和數(shù)千深度的量子電路來(lái)挑戰(zhàn)RSA-2048。這樣規(guī)模的量子資源最有可能在不久的將來(lái)在NISQ設(shè)備上實(shí)現(xiàn)。”

該團(tuán)隊(duì)在論文中指出，由于QAOA的收斂性不明確，該算法的量子加速還不清楚：“然而，通過(guò)QAOA優(yōu)化Babai算法中的‘size-reduce’程序的想法可以作為一大批廣泛使用的格約化算法中的子程序使用。進(jìn)一步說(shuō)，它可以幫助分析基于格的抗量子密碼問(wèn)題?！?

該團(tuán)隊(duì)包括來(lái)自數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室、清華大學(xué)、浙江大學(xué)、北京量子信息科學(xué)研究院、信息工程大學(xué)和量子信息前沿科學(xué)中心的科學(xué)家。

論文鏈接：

https://arxiv.org/pdf/2212.12372.pdf

參考鏈接：

https://thequantuminsider.com/2022/12/29/researchers-close-in-on-using-a-quantum-computer-to-crack-common-cryptographic-scheme/