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

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

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

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

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

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

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

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

實驗裝置和SQIF算法的QAOA電路

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

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

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

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

該團(tuán)隊包括來自數(shù)學(xué)工程與先進(jì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/