劉安航,李浩昱,關(guān) 佳,張志華,方 愷,赫 麗,沈 軍

(同濟(jì)大學(xué) 物理科學(xué)與工程學(xué)院，上海 200092)

經(jīng)典計(jì)算機(jī)需要信息的載體、邏輯操作、狀態(tài)讀出等一系列基本元素. 量子計(jì)算機(jī)用量子比特作為量子信息的載體，對(duì)量子比特進(jìn)行初始化、操控和讀出等，再通過(guò)一系列的邏輯操作構(gòu)成量子算法，從而實(shí)現(xiàn)特定的計(jì)算目的. 比特是經(jīng)典計(jì)算和經(jīng)典信息中的基本概念，量子計(jì)算和量子信息則建立在類(lèi)似的概念——量子比特的基礎(chǔ)上. 經(jīng)典計(jì)算機(jī)中，比特有0和1兩種狀態(tài)，利用0和1構(gòu)成的比特串編碼分別表示不同的信息. 而在量子計(jì)算機(jī)中，信息單元被稱(chēng)為量子比特，除了可以處于0態(tài)或1態(tài)外，還可以處于疊加態(tài). 借助疊加態(tài)，可以實(shí)現(xiàn)利用較少的量子比特儲(chǔ)存更多的信息.

Shor算法由P. W. Shor在1994年提出，是針對(duì)整數(shù)分解問(wèn)題在量子計(jì)算機(jī)上運(yùn)作的算法[1],該算法可以解決如下問(wèn)題：給定整數(shù)N，找出其質(zhì)因數(shù). 現(xiàn)有的經(jīng)典算法還無(wú)法有效地解決該問(wèn)題[1-2]，因此Shor算法展示了量子計(jì)算的優(yōu)越性. 此外，Shor 算法的存在也直接威脅到經(jīng)典通訊的Rivest-Shamir-Adleman(RSA)加密算法. 所以關(guān)于Shor算法的相關(guān)研究一直備受矚目，2019年Aidan Dang等人詳細(xì)介紹了優(yōu)化Shor算法的高階經(jīng)典模擬技術(shù)，利用檢查電路的糾纏特性，有效地將其映射到矩陣乘積狀態(tài)的一維結(jié)構(gòu)中并對(duì)其進(jìn)行了優(yōu)化[3]；2020年在IEEE第5屆計(jì)算通信與自動(dòng)化國(guó)際會(huì)議上，Vaishali Bhatia等人提出了用Shor 算法破解RSA的高效量子計(jì)算技術(shù)[4].

目前我國(guó)在量子計(jì)算領(lǐng)域也頗有建樹(shù)，2017年中國(guó)科學(xué)技術(shù)大學(xué)杜江峰院士團(tuán)隊(duì)基于核磁共振系統(tǒng)和絕熱量子計(jì)算模型在Shor算法中實(shí)現(xiàn)了6位數(shù)291 311的因式分解[5]；2020年，段兆臣等人使用量子點(diǎn)單光子源成功編譯了Shor算法[6]；2021年，中國(guó)科學(xué)院量子信息與量子科技創(chuàng)新研究院潘建偉、朱曉波、彭承志等人組成的研究團(tuán)隊(duì)成功研制了62比特可編程超導(dǎo)量子計(jì)算原型機(jī)“祖沖之號(hào)”[7].

本文的設(shè)計(jì)思路來(lái)自于近代物理實(shí)驗(yàn)課程中的量子密鑰分發(fā)虛擬仿真實(shí)驗(yàn)[8]，并參考了一些與量子糾纏和量子保密通信相關(guān)的實(shí)驗(yàn)[9-13]. 設(shè)計(jì)出了基于Shor算法的實(shí)驗(yàn)，首先將質(zhì)因數(shù)分解問(wèn)題轉(zhuǎn)換為求函數(shù)的周期問(wèn)題，然后通過(guò)擬定已知函數(shù)和未知函數(shù)，從理論上對(duì)這2個(gè)函數(shù)進(jìn)行實(shí)驗(yàn)與分析，得出實(shí)驗(yàn)次數(shù)n(該實(shí)驗(yàn)次數(shù)是指為了獲得正確的周期結(jié)果所需要的運(yùn)算次數(shù)或者選取次數(shù)). 通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)量子方法需要的實(shí)驗(yàn)次數(shù)僅僅正比于要分解的大數(shù)N，而經(jīng)典計(jì)算方法需要的實(shí)驗(yàn)次數(shù)為nn.因此，由于量子算法的并行性，Shor算法在質(zhì)因子分解問(wèn)題中存在顯著的優(yōu)勢(shì).

1 實(shí)驗(yàn)原理

1.1 量子比特

在量子計(jì)算機(jī)中，信息單元被稱(chēng)為量子比特，除了可以處于0態(tài)或1態(tài)外，還可處于疊加態(tài).用|0〉和|1〉表示量子比特可取的狀態(tài)基矢，單個(gè)量子比特可取的值為

|Ψ〉=α|0〉+β|1〉,

(1)

其中，α和β為復(fù)數(shù).因?yàn)榇嬖诩s束條件αα*+ββ*=1，量子比特可寫(xiě)成

(2)

其中，θ和φ為實(shí)數(shù)且-π≤θ≤π，0≤φ≤2π.

1.2 量子邏輯門(mén)

1.3 量子并行計(jì)算

量子并行性使得量子計(jì)算機(jī)可以在同一時(shí)間計(jì)算函數(shù)f(x)在多個(gè)不同x值處的函數(shù)值.對(duì)于b位的量子存儲(chǔ)器而言，可以同時(shí)存儲(chǔ)2b個(gè)數(shù)字(態(tài))，在量子力學(xué)中，對(duì)b個(gè)量子位的寄存器的一般態(tài)可表示為

(3)

其中，|cb|2表示取得對(duì)應(yīng)值的概率.由于儲(chǔ)存了2b個(gè)不同的態(tài)，使用1次量子邏輯門(mén)可以同時(shí)改變2b個(gè)態(tài)的cb值，改變了2b個(gè)信息，即為量子并行計(jì)算[14].

1.4 量子傅里葉變換

在函數(shù)的周期求解問(wèn)題中，量子傅里葉變換(Quantum Fourier transform，QFT)為

(4)

式(4)表示對(duì)任意量子態(tài)|x〉做傅里葉變換，得到以波矢k展開(kāi)的表達(dá)形式，其中，k=0，1，…,2b-1.

QFT同樣可以構(gòu)成邏輯門(mén),其QFT門(mén)矩陣表示為

(5)

1.5 素?cái)?shù)因子分解問(wèn)題轉(zhuǎn)換為求周期問(wèn)題

已知大數(shù)N，存在唯一的質(zhì)因子分解N=P1P2，求P1和P2.求解質(zhì)因子分解問(wèn)題的步驟包括：

1)隨機(jī)取大于1的正整數(shù)y，使得y

2)若r為奇數(shù)，則另取1個(gè)大于1的正整數(shù)y，繼續(xù)求r，直到r為偶數(shù).

3)若r為偶數(shù)，取x≡yr/2(modN)，則x2≡1(modN)，進(jìn)而有

x2-1≡0(modN),

(6)

即

(x+1)(x-1)≡0(modN).

(7)

于是可設(shè)

(x+1)(x-1)=tN=tP1P2=uvP1P2，

(8)

其中，t，u，v為正整數(shù)，進(jìn)而有

(x+1)(x-1)=(uP1)(vP2).

(9)

式(7)解為

x+1≡0(modP1),

(10)

x-1≡0(modP2),

(11)

即

P1=gcd(x+1,N)，

(12)

P2=gcd(x-1,N).

(13)

其中，gcd(x,N)可由輾轉(zhuǎn)相除法求得.因此，若求得大于1的正整數(shù)y關(guān)于N的階數(shù)r，則可求出P1和P2.

令yx≡z(modN)，因yr≡1(modN)，則對(duì)任意正整數(shù)h有

yx+hr≡z(modN)，

(14)

即以N為模的函數(shù)f(x)=yx的周期就是y關(guān)于N的階數(shù)r.素?cái)?shù)因子分解問(wèn)題，轉(zhuǎn)換為求函數(shù)f(x)≡ax(modN)的周期問(wèn)題，其中a為大于1的正整數(shù)[16].

2 實(shí)驗(yàn)內(nèi)容

Shor算法原理的裝置圖如圖1所示，圖中的2個(gè)寄存器負(fù)責(zé)儲(chǔ)存數(shù)字信息.

圖1 Shor算法實(shí)驗(yàn)裝置圖

算法流程為寄存器1作為|x〉，在經(jīng)過(guò)H門(mén)后儲(chǔ)存所有的數(shù)字信息，寄存器2經(jīng)過(guò)幺正變換與存儲(chǔ)器1中的x建立糾纏并儲(chǔ)存函數(shù)信息.完成上述流程后得到

(15)

式(15)表明經(jīng)過(guò)變換后，若對(duì)初態(tài)|ψ0〉進(jìn)行觀測(cè)，將得到2b個(gè)出現(xiàn)概率相同的態(tài)，而當(dāng)每個(gè)態(tài)的|x〉確定后，相應(yīng)的|f(x)〉值也隨之確定.

觀測(cè)f(x)時(shí)將使其坍縮為f(x0)，由于存在周期性，這時(shí)x會(huì)坍縮成x0+jT0(T0為周期，j=0，1，2，…，m0-1)，需要指出的是此處總的周期數(shù)m0=N/T0，如不滿(mǎn)足則需做進(jìn)一步處理[1].這里只討論m0=N/T0的情況，可得

(16)

由于觀測(cè)到f(x0)會(huì)使得x坍縮成只與正整數(shù)j有關(guān)的值x0+jT0，此時(shí)x與f(x)之間不再存在函數(shù)關(guān)系(量子糾纏關(guān)系)，即式(16)可分離(兩寄存器之間退相干).

寄存器1在分離后可以表示為

(17)

對(duì)寄存器1進(jìn)行QFT，即經(jīng)過(guò)QFT門(mén)可得到

(18)

所以有

(19)

最終可以得到

(20)

此時(shí)進(jìn)行測(cè)量，將得到等概率的T0個(gè)|km0〉，將其與N進(jìn)行約分，得到的約分式分母將恰好為待求解的周期T0.可能存在k與T0有公約數(shù)的情況，分式可繼續(xù)約分，這一情況將在第3部分進(jìn)行討論.

(21)

經(jīng)典計(jì)算方法同樣可以按照?qǐng)D1裝置圖進(jìn)行實(shí)驗(yàn)，僅需要在QFT門(mén)前對(duì)x進(jìn)行觀測(cè).

3 實(shí)驗(yàn)結(jié)果與討論

3.1 周期測(cè)定

3.1.1 已知函數(shù)

假定已知函數(shù)為

(22)

即函數(shù)周期為2.

設(shè)寄存器1為3位量子比特，即b=3.寄存器2根據(jù)f(x)的值設(shè)置為1位量子比特.根據(jù)式(15)初始化賦予兩寄存器糾纏態(tài)，對(duì)式(15)中的f(x)進(jìn)行測(cè)量，假設(shè)得到f(x)=0，由于兩寄存器處于糾纏態(tài)，此時(shí)寄存器1坍縮為

(23)

對(duì)式(23)進(jìn)行QFT，可以得到的結(jié)果為

(24)

實(shí)際上在f(x)=1時(shí)進(jìn)行QFT能夠得到同樣的結(jié)果，±號(hào)對(duì)應(yīng)f(x)=1和f(x)=0的2種情況，即各有1/2 的概率得到|0〉或|4〉，當(dāng)?shù)玫絴0〉時(shí)，應(yīng)舍去，當(dāng)?shù)玫絴4〉時(shí)，根據(jù)

(25)

可得最終周期為2.

3.1.2 未知函數(shù)

在實(shí)際的質(zhì)因數(shù)分解中，已知條件僅為函數(shù)存在周期.假定函數(shù)周期為T(mén)=16，選擇b=6，即N=26=64.進(jìn)行QFT，可以得到結(jié)果為

(26)

在所有的f(x)值下進(jìn)行QFT都能得到相同結(jié)果，即等概率得到以上的T個(gè)解，注意T為未知量，需要多次測(cè)量來(lái)確定T的實(shí)際取值，該計(jì)算將在3.2節(jié)中展開(kāi).對(duì)所得數(shù)據(jù)進(jìn)行處理運(yùn)算，約分得到下列值

(27)

由式(27)可知有些值與周期并不相符，可推斷在測(cè)量次數(shù)較少時(shí)，并不能正確分辨待測(cè)定的周期值.所以需要多次測(cè)量，并選取最大的分母，作為最終的周期值，即16.由此可見(jiàn)該算法并不能在單次測(cè)量中得到100%正確的周期值.

3.2 測(cè)量次數(shù)的確定

3.2.1 經(jīng)典計(jì)算方法

經(jīng)典計(jì)算方法的運(yùn)算流程為：在通過(guò)Uf門(mén)后，直接觀測(cè)x和f(x)的值.假定函數(shù)周期為T(mén)，由于x與f(x)之間存在糾纏關(guān)系，多次重復(fù)觀測(cè)可發(fā)現(xiàn)，當(dāng)觀測(cè)到相同的f(x)時(shí)，對(duì)應(yīng)的觀測(cè)量x之間的差值必定是T的整數(shù)倍.這樣觀測(cè)相同的f(x)值下x之間的差值，取最小值作為周期T.

在經(jīng)典計(jì)算方法中使正確率達(dá)到99%的運(yùn)算次數(shù)，可以分為2個(gè)步驟：

1)選擇相同的f(x)，由于N=mT，則單次實(shí)驗(yàn)的選取成功率為P(1)=1/m.

由于m不能確定，將m用N來(lái)表示，運(yùn)算結(jié)果如圖2所示，其中橫坐標(biāo)為要選取的大數(shù)N，縱坐標(biāo)表示在對(duì)數(shù)坐標(biāo)下的選取次數(shù)，紅色點(diǎn)是對(duì)應(yīng)大數(shù)N下計(jì)算得到的運(yùn)算次數(shù)在坐標(biāo)空間內(nèi)的點(diǎn)，對(duì)應(yīng)的選取次數(shù)在對(duì)數(shù)坐標(biāo)下與N基本呈正相關(guān)，當(dāng)N在104附近時(shí)，就需要101.2×105次選取，這樣計(jì)算量巨大，難以達(dá)到要求.如果分別計(jì)算兩步驟的選取次數(shù)，就可以得到2次的選取次數(shù)均與N呈正比例關(guān)系，即最終的表達(dá)式為c0Nd0N(c0和d0均為比例系數(shù)).因此，在經(jīng)典計(jì)算方法下，大數(shù)質(zhì)因子分解問(wèn)題的復(fù)雜度為指數(shù)級(jí)別O(nn).

圖2 對(duì)數(shù)坐標(biāo)系下選取次數(shù)與大數(shù)N的散點(diǎn)圖

3.2.2 量子方法

根據(jù)上面的計(jì)算，進(jìn)行QFT后共存在等概率的T個(gè)結(jié)果，一定能夠保持分母為T(mén)值的2個(gè)量分別為1/T和(T-1)/T.所以每次測(cè)量至少有P=2/T概率得到想要的值.在n次測(cè)量后得到該值的概率為

(28)

由于式(28)中的周期并不能事先確定，因此需要選取更大的大數(shù)N值.為了保證結(jié)果的準(zhǔn)確性，需要從理論上分析選取次數(shù)與正確率的關(guān)系,如圖3所示.

圖3 運(yùn)算次數(shù)與大數(shù)N的散點(diǎn)圖

圖3中橫坐標(biāo)為選擇的大數(shù)N，縱坐標(biāo)為在正確率為99%時(shí)需要的運(yùn)算次數(shù)，藍(lán)色圓圈是對(duì)應(yīng)周期下計(jì)算得到的運(yùn)算次數(shù)在坐標(biāo)空間內(nèi)的點(diǎn).由圖3可知對(duì)應(yīng)的運(yùn)算次數(shù)n與大數(shù)N呈正相關(guān).這說(shuō)明在量子計(jì)算方法下，僅需要多項(xiàng)式級(jí)別的復(fù)雜度O(n)就可以解決大數(shù)的質(zhì)因子分解問(wèn)題.

4 結(jié)束語(yǔ)

將量子計(jì)算方法與經(jīng)典計(jì)算方法進(jìn)行比較，得出在量子算法中分解質(zhì)因數(shù)的復(fù)雜度為多項(xiàng)式級(jí)別O(n)，而經(jīng)典計(jì)算方法中分解質(zhì)因數(shù)的復(fù)雜度為指數(shù)級(jí)別O(nn).因?yàn)榱孔佑?jì)算具有并行性，即在量子算法中，1個(gè)量子門(mén)可以對(duì)其儲(chǔ)存的2b個(gè)數(shù)據(jù)同時(shí)進(jìn)行運(yùn)算，省去了經(jīng)典計(jì)算方法中逐個(gè)進(jìn)行計(jì)算的過(guò)程.本實(shí)驗(yàn)中，量子傅里葉變換門(mén)同時(shí)對(duì)2b個(gè)數(shù)據(jù)展開(kāi)運(yùn)算，直接得到了包含T個(gè)數(shù)字的等概率的波函數(shù)，降低了計(jì)算的復(fù)雜程度.本文對(duì)設(shè)計(jì)的實(shí)驗(yàn)進(jìn)行了數(shù)值上的模擬和計(jì)算，驗(yàn)證和解釋了Shor算法的運(yùn)行機(jī)制以及量子計(jì)算的優(yōu)越性.