基于量子計算原理的Shor算法優(yōu)越性驗證

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

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

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

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

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

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

1 實驗原理

1.1 量子比特

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

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

(1)

其中，α和β為復數(shù).因為存在約束條件αα*+ββ*=1，量子比特可寫成

(2)

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

1.2 量子邏輯門

1.3 量子并行計算

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

(3)

其中，|cb|2表示取得對應值的概率.由于儲存了2b個不同的態(tài)，使用1次量子邏輯門可以同時改變2b個態(tài)的cb值，改變了2b個信息，即為量子并行計算[14].

1.4 量子傅里葉變換

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

(4)

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

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

(5)

1.5 素數(shù)因子分解問題轉(zhuǎn)換為求周期問題

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

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

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

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

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ù)，進而有

(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)，則對任意正整數(shù)h有

yx+hr≡z(modN)，

(14)

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

2 實驗內(nèi)容

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

圖1 Shor算法實驗裝置圖

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

(15)

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

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

(16)

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

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

(17)

對寄存器1進行QFT，即經(jīng)過QFT門可得到

(18)

所以有

(19)

最終可以得到

(20)

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

(21)

經(jīng)典計算方法同樣可以按照圖1裝置圖進行實驗，僅需要在QFT門前對x進行觀測.

3 實驗結(jié)果與討論

3.1 周期測定

3.1.1 已知函數(shù)

假定已知函數(shù)為

(22)

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

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

(23)

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

(24)

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

(25)

可得最終周期為2.

3.1.2 未知函數(shù)

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

(26)

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

(27)

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

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

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

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

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

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

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

圖2 對數(shù)坐標系下選取次數(shù)與大數(shù)N的散點圖

3.2.2 量子方法

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

(28)

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

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

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

4 結(jié)束語

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