在一項(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ù)百萬個(gè)量子比特。
該團(tuán)隊(duì)的最新實(shí)驗(yàn)表明,依靠整數(shù)因子化的公鑰密碼技術(shù)可能很快就會(huì)受到當(dāng)今原始的NISQ(含噪聲中等規(guī)模)量子計(jì)算機(jī)的攻擊。
據(jù)研究人員稱,該算法是基于經(jīng)典的Schnorr算法——使用格約化來分解整數(shù),同時(shí)依靠量子近似優(yōu)化算法(QAOA)來優(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ù)分解問題,可能打破廣泛用于保護(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)
研究人員表示,“通過估算RSA-2048因式分解所需的量子資源來進(jìn)行。我們發(fā)現(xiàn),即使在最簡單的一維鏈系統(tǒng)中,也需要一個(gè)具有372個(gè)物理量子比特和數(shù)千深度的量子電路來挑戰(zhàn)RSA-2048。這樣規(guī)模的量子資源最有可能在不久的將來在NISQ設(shè)備上實(shí)現(xiàn)?!?
該團(tuán)隊(duì)在論文中指出,由于QAOA的收斂性不明確,該算法的量子加速還不清楚:“然而,通過QAOA優(yōu)化Babai算法中的‘size-reduce’程序的想法可以作為一大批廣泛使用的格約化算法中的子程序使用。進(jìn)一步說,它可以幫助分析基于格的抗量子密碼問題。”
該團(tuán)隊(duì)包括來自數(shù)學(xué)工程與先進(jìn)計(jì)算國家重點(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/