量子噪聲對Shor 算法的影響

黃天龍 吳永政 倪明 汪士 葉永金

(中國電子科技集團公司第三十二研究所,上海 201808)

Shor 算法能夠借助量子計算機以多項式級別復雜度解決大整數因式分解問題,從而破解一系列安全性基于大整數因式分解的加密算法,例如Rivest-Shamir-Adleman 加密算法、Diffie-Hellman 密鑰交換協議等.由于量子測量結果是概率性的,在運行量子線路時很容易受到噪聲的干擾,這將導致無法測量得到預期結果.本文分別研究了不同通道的噪聲對Shor 算法的影響,分別是去極化通道、狀態制備與測量通道以及熱退相干通道.本文模擬在噪聲環境中運行Shor 算法并且給出了數值結果.數值結果表明Shor 算法成功分解整數的概率易受到噪聲影響,其中去極化通道中的噪聲能夠以指數形式影響Shor 算法成功分解整數的概率,其次是熱退相干通道噪聲,最后是狀態制備與測量通道噪聲,能夠線性影響到Shor 算法成功分解的概率.本文能夠為后續糾錯、改進Shor 算法以及確定工程實現Shor 算法所需要的保真度等提供建設性意見.

1 引言

Shor[1]于1994 年提出用于解決大整數因式分解的量子算法,該算法能夠以多項式級的復雜度解決大整數因式分解及離散對數問題[1,2].相較于經典因式分解算法,Shor 算法有指數級提升.目前復雜度最低的傳統大整數分解算法是數域篩法[3-5],它的復雜度為Kleinjung等[6]借助上百臺計算機花費兩年時間使用數域篩法分解了一個768 比特的RSA (Rivest-Shamir-Adleman)整數,并且指出分解2048 比特的RSA 整數的開銷是前者的百萬倍.而文獻[7]指出理論上在一臺擁有兩千萬個物理比特的量子計算機上運行Shor 算法可以在8 h 內完成2048 比特的RSA 整數的分解.然而目前的量子計算機系統仍然處于萌芽狀態,我們處于帶噪聲的中等規模的量子計算機時代(noise intermediate-scale quantum,NISQ)[8].中等規模指的是量子計算機所含有的量子比特個數范圍為50—100,并且量子計算機運行量子算法時會受到噪聲的影響.噪聲是搭建NISQ 時代量子計算機的主要障礙[9,10].噪聲出現的主要原因在于硬件(酉門)的失真以及量子計算機與環境之間會產生交互(例如弛豫與退相位、電磁退相干、引力退相干等)[11-13],這些噪聲會對算法結果產生影響,導致與預期結果產生偏差.因此研究噪聲對Shor 算法的影響是十分重要的.本文分別針對不同通道的噪聲對Shor 算法的影響進行深入研究,通過數值分析任一通道中不同噪聲大小與Shor 算法分解整數成功率的關系(Shor 算法成功率定義見2.2 節).

Shor 算法中的量子線路十分復雜,因此大量關于優化線路的文獻被提出.Vedral等[14]首先搭建了算術運算的量子線路,其中包括加法門、乘法門以及模指數門等.模指數門是構成Shor 算法量子線路的重要組成部分.使用Vedral 等的方法搭建Shor 算法所需的量子線路需要7n+2 個邏輯比特,其中n是待分解整數N的二進制比特數.在此基礎上Draper[15]改進了加法門.改進后的加法器需要兩個輸入a,b.與一般加法器不同的是,Draper加法門首先計算a的量子傅里葉(quatnum fourier transform,QFT)結果,記作F(a),緊接著再計算F(a+b),能夠將Shor 算法中需要的邏輯比特數量級降低至2n.Beauregard[16]使用量子QFT 加法器以及半經典QFT (semi-classical QFT)構建Shor 算法線路.如果只使用一個量子比特循環控制受控模指數門,分解大整數N只需要2n+3 個邏輯比特.

由于真實量子計算機中噪聲的存在,在不糾錯的情況下運行復雜量子線路很難得到正確結果.關于在真實量子計算機上運行Shor 算法(使用糾錯算法后)的開銷也被分析.Fowler等[17]指出,以表面碼為基礎,當量子門噪聲大小為10-3時,需要在一臺擁有 2.2×108個物理比特的量子計算機上運行26.7 h,才能夠分解一個2000 比特的整數.在O’Gorman 和Campbell[18]的工作中,使用了改進后的表面碼,每個邏輯比特需要的物理比特數目更少,在量子門噪聲大小為10-4的情況下,整個線路只需要 6.3×106個物理比特.Hwang等[19]在使用Steane 碼以及表面碼的基礎上,對Shor 算法進行了分析,相比于文獻[17,18]的工作,他們對Shor算法的分析更加詳細,從而取得了更合理的結果,他們指出在量子門噪聲大小為10-3的情況下使用Shor 算法分解一個512 比特的整數需要9.5×1010個物理比特并且花費 8.78×105h.Ha等[20]在使用旋轉平面表面碼[21]的基礎上給出了待分解整數的比特數與分解時間以及分解所需要的量子比特數目的具體關系,他們指出,在量子門噪聲大小為10-3的情況下分解2048 比特的RSA 整數需要1.37×107個物理比特,并且要花費 1.89×107h 完成.在Gidney[7]的工作中,他指出為了分解一個2048 比特的整數,在量子門噪聲大小為10-3的情況下需要在一臺擁有 2×107個物理比特的量子計算機上運行大約8 h.此外,Gidney[22]將窗口法與量子線路融合,進行量子運算的加窗操作,能夠降低模乘法門中的線路深度.Xiao等[23]提出以量子隱形傳態為基礎使用兩臺量子計算機實現分布式的Shor 算法,能夠降低每臺量子計算機運行所需要的量子比特數目以及線路深度.Rossi等[24]提出了Shor 算法的簡化版本,并且在IBM 的真實量子計算機上進行了驗證,結果表明在損失部分準確率的情況下仍能夠得到正確的分解結果.

然而鮮有強調關于給噪聲建?；蛘吣M噪聲對算法影響的文獻[9,25,26].文獻[10,25]提及了噪聲建模的重要意義并且建立了對應的噪聲模型.文獻[27]研究了特定噪聲對量子近似優化算法[28]的影響并且進行了數值分析.大部分實驗室并沒有可以運行的量子計算機,而一些公用量子計算機的比特數量以及相應參數不同,因此很難準確地進行量子噪聲建模[29].根據文獻[10],本文將噪聲分成3 個通道分別進行研究,分別是去極化通道(depolarizing channel,DC)[30-32];狀態制備與測量通道(state preparation and measurement channel,SPAM)[33];熱退相干通道(thermal relaxation channel,TRC)[13,30].

目前Shor 算法中的量子線路的復雜度仍然很高.本文搭建的量子線路的深度達到了O(n3),線路寬度達到了4n+2.因此線路可能很容易受到噪聲影響.一方面,明確量子計算機中噪聲來源能夠更有效地進行糾錯[34,35];另一方面,了解不同噪聲對Shor 算法的影響程度對于糾錯也是十分重要的.本文針對噪聲對Shor 算法的影響進行研究,根據文獻[10]將噪聲分成3 個通道,通過一系列模擬得到了每個通道中不同大小的噪聲與Shor 算法成功率的數值關系,對于后續對Shor 算法進行糾錯、改進等能夠提供建設性的意見.

本文第1 節介紹Shor 算法以及量子噪聲對Shor 算法的影響,分析本項研究的創新性以及意義;第2 節對Shor 算法進行系統梳理,定義了Shor 算法整數分解的成功率和均方誤差并且分析了量子線路的復雜度;第3 節討論3 個通道中噪聲的模型以及作用過程;第4 節詳述模擬噪聲的實驗過程并且對數值結果進行分析;第5 節總結數值模擬結果并且提出未來研究方向.

2 Shor 算法

Shor 算法將因數分解問題轉換至一個求a在乘法群中的階的問題[1].a的階r=ord(a,N)的定義是能夠使ar≡1(modN) 成立的最小的正整數r.算法流程如表1 所列.

表1 Shor 算法流程Table 1.Pseudo of Shor’s algorithm.

Shor 分解算法包括經典部分與量子部分.量子噪聲會直接影響到其中的量子線路運行的結果.本節對Shor 算法量子部分進行系統梳理.

2.1 Shor 算法量子線路

Shor 算法的量子線路(量子求階程序)如圖1所示.

圖1 Shor 算法中的量子線路Fig.1.Quantum circuit of Shor’s algorithm.

線路需要兩個量子寄存器,分別含有t=個量子比特.對第一個寄存器中的每個比特施加一個H門得到均勻疊加態.并且第二個寄存器的初態為 |1〉.那么|ψ1〉=其中j=2t.Va量子門是通過量子線路實現的模指數運算,本質上是一個受控酉門[30],其定義為根據相位反沖原理,如果對第二個寄存器進行測量,將測量結果記作ab,其中 0 ≤b＜r.|ψ2〉將坍縮 至所有 |l〉的疊加,l滿足al≡abmodN,即al與ab同余,并且l=kr+b,其中 0 ≤k＜r.那么|ψ3〉=其中c=.此時使用量子傅里葉逆變換[36-38]提取隱藏在第一個寄存器中的周期信息.根據量子傅里葉變換的定義可以得到:

其中ω=exp(2πi/j) .該態的含義是包含兩種情況,分別是j|lr以及j?lr的不同情況的疊加態.測量0 ≤l＜j的概率大小是:

當j能夠被(lr)整除時,概率大小是c/j,此時對應的測量結果l滿足l=kj,其中k是正整數.當j不能被(lr)整除時,P(l)會在l滿足sin2(πlr/j)≈0的條件下產生極大值,對應的測量結果l應該滿足l≈kj/r.因此對 |ψ4〉進行測量時,會有更高的概率使測量結果l滿足l≈kj/r(約等于符號是因為測量得到的l是整數,是離散的)[39].

假設待分解的整數N=21,隨機數選擇a=2,那么r=ord21(2)=6,t==10,j=2t=1024,c==171,l的范圍是0 ≤l＜1024,l∈Z.l的理論概率分布如圖2 所示.

圖2 Shor 算法分解(N=21,a=2)實驗中 |ψ4〉 的預期概率分布Fig.2.Expected probability distribution of |ψ4〉 in factoring (N=21,a=2).

當l=0 或者l=512 時滿足l|(qr),對應于圖2 中最高的兩個峰,其大小等于 1/r≈0.167 .其他情況(l≠0,l≠512 )下,當l≈k(j/r),即l=171,341,683,853 時,在圖像中對應第二高的峰,大小約為0.114.|ψ4〉分布是有規律的.選擇不同的隨機數分解同一個整數時,分布會因隨機數階的不同發生差異.并且隨著待分解整數增大,峰值概率也會降低.對于不同大小噪聲下的情況,可以比較分布的差異從而判斷出噪聲對于線路影響程度的不同.

2.2 成功率的定義

在經典計算機上模擬時,能夠計算 |ψ4〉的狀態向量,因此能夠得到l的分布.如果測量結果滿足l=k(j/r),1≤k＜r,則可以進一步求其連分數[1](具體實現在附錄A 中)最終完成對N的分解.例如在分解N=21(a=2)的實驗中,|ψ4〉的概率分布如圖2 所示,除去l=0,l=512,該分布有4 個峰值,將該4 個峰值的測量概率求和作為Shor 算法整數分解的成功率,即Ps=P(171)+P(341)+P(683)+P(853).對于一般情況,成功率的定義則是:

此外,本文還將均方誤差(mean squared error,MSE)這一指標用于實驗結果的比較,該指標定義式為

其中,P(l)theory代表l的理論概率分布,P(l)j代表某一噪聲環境下第j次實驗中l的概率分布,一共重復實驗k次.而(P(l)theory-P(l)j)2的定義是所有可能測量得到的結果的理論概率與實際概率作差并求其平方和.這一指標能夠很好地反映 |ψ4〉在不同噪聲環境下的分布與理論分布的差異,從而能夠幫助我們判斷分解是否成功.

2.3 量子線路復雜度分析

本文以Draper[15]提出的QFT 加法器作為量子線路的算術基礎,并且按照Beauregard[16]的方法依次搭建了模N加法門、受控模N乘法門、受控模指數門.與Beauregard 的方法不同的是,本文并沒有使用半經典QFT,而是一般QFT (normal QFT),因此共需要4n+2 個量子比特.

QFT 加法門的深度為1,需要n+1 個量子比特,其中n是待分解整數N的二進制比特數.額外的一個量子比特用于防止溢出.模N加法門的復雜度取決于QFT 的精度.如果使用精確QFT,那么量子門數量為O(n2),線路深度達到了O(n),一共使用n+4 個量子比特,其中n+1 個比特用于實現QFT 加法門;2 個用于控制比特;1 個作為輔助比特.受控模N乘法門需要2 次QFT 以及n個模N加法門,線路深度達到了O(n2),共需要2n+3 個量子比特,其中n+2 個量子比特用于模N加法,另外n個比特用于存放 |x〉,剩下一個量子比特用于控制比特.受控模N指數門由一個受控模N加法門、受控交換門以及一個受控模N乘法門的逆門構成,因此深度仍然是O(n2),并且所需要的量子比特數目和受控模N乘法門相同,均為2n+3 個量子比特.搭建圖1 中的Va門需要2n個Ua門,每個Ua門由不同的量子比特控制.最終的線路寬度為4n+2,線路的總深度達到了O(n3).

Shor 算法中的量子線路首先對第一個寄存器的所有的比特施加1個H門,并且在對第一個寄存器進行測量前進行1 次QFT 逆運算,分別需要O(n)個單比特門以及O(n2) 個雙比特門.在QFT加法器中,需要1 次QFT 以及n(n+1)/2 個雙比特門,那么單比特門的數量為O(n),雙比特門的數量為O(n2) .在模N加法門中,需要3 個受控加法門、2 個加法門以及4 次QFT (其中2 次是逆變換)和2個X門以及2個CX門.那么雙比特門的數量仍是O(n2),單比特門的數量為O(n).受控模N乘法門需要n個模N加法門以及2 次QFT (其中1 次是逆運算),因此該門共需要O(n3) 個雙比特門以及O(n2) 個單比特門.Ua門包含 一個受 控模N乘法門、一個CSWAP 門以及一個受控模N乘法門的逆,不會改變所需量子門數目的量級.整個Shor 算法中共需要2n個Ua門來完成模指數運算.因此整個Shor 量子線路中共使用了O(n4)個雙比特門以及O(n3) 個單比特門.

3 量子噪聲

在量子計算機上運行量子算法的過程中噪聲是不可避免的.噪聲是構建大型量子計算機的主要障礙[9,10].隨著構成量子線路的門數量增多以及使用的量子比特數增多,線路更容易受到噪聲的影響,從而導致最終結果與預期產生偏差.根據2.3 節中的分析,Shor 算法中量子線路的寬度達到了4n+2,量子門數量達到了O(n4),在量子計算機上運行時很容易受到噪聲影響,從而影響Shor 算法的成功率.因此模擬噪聲環境中運行Shor 算法能夠研究得到哪種噪聲對算法的影響最大,能夠使得糾錯環節更加高效[34].本文根據文獻[10]將噪聲分為3 個通道進行研究,分別是去極化通道;狀態制備與測量通道;熱退相干通道.這3 個通道的噪聲能夠涵蓋真實量子計算機環境中常見的噪聲類別.

3.1 去極化通道

由于量子門的保真度無法達到100%,因此量子比特在經過量子門時會有一定的概率產生相位翻轉或者比特翻轉或者同時發生[30,40].比特翻轉相當于在原有量子門基礎上添加了一個X門.而相位翻轉相當于在原有量子門基礎上添加了一個Z門.當相位翻轉和比特翻轉同時發生時,相當于在原有量子門基礎上添加了一個Y門.3 種泡利噪聲出現的可能性相等.去極化通道作用于量子線路如下:

3.2 狀態制備與測量通道

SPAM 通道的噪聲僅導致狀態制備后以及測量前的比特翻轉.將SPAM 通道與DC 區別的原因在于,狀態制備會向量子寄存器中注入預期的初態,會需要進行額外的操作,后者主要是發生在量子線路的運行過程中[33].將此通道中發生比特翻轉的大小記作Pspam.使用算符和表達則是:

3.3 熱退相干通道

退相干指的是量子比特與環境耦合過程中逐漸失去相干性的過程,來源于噪聲與量子比特的微弱耦合[30,41].實際的量子比特系統很難做到完全孤立,除此之外,還要對量子比特進行測量,這就會使得量子比特總會與外部環境耦合.按照對量子比特的影響不同可以分為退相位(dephasing)[30]、弛豫(relaxation)[42].

3.3.1 退相位

3.3.2 弛豫

當T1越大時,該量子比特能夠保持 |1〉狀態的時間也越久.將純退相位的過程一起考慮進來.根據(8)式,當能量弛豫與純退相位兩種噪聲同時作用時,有

這里引入了參數T2來描述弛豫與純退相位共同作用的結果,T2也被稱為退相位時間.在實驗中使用T1與T2來描述熱退相干[25]噪聲.T2與T1的關系為在模擬時,T2最大能夠取到 2T1.在量子線路運行時(不包括測量與狀態制備)每個量子比特經過量子門(單比特門、雙比特門)都會按照(9)式同時發生弛豫與純退相位.并且本文假定所有比特的熱退相干模型相同,即共享一組T1,T2參數.

4 數值模擬

本文以Python 作為開發語言,借助用于量子計算的Qiskit庫[44]進行模擬實驗,在此基礎上搭建了Shor 算法的量子線路、設置了不同的噪聲環境以及計算 |ψ4〉的狀態向量,從而計算 |ψ4〉的概率分布,并且按照2.2 節中的定義能夠計算出成功率.這樣做的優點在于僅進行一次模擬就可以得到準確的概率分布以及成功率,避免了通過重復測量得到分布的繁瑣.按照第3 節將噪聲分成3 類進行單獨模擬.對于每一種噪聲分別設置了不同參數區間,在不同噪聲大小的基礎上模擬運行Shor 算法量子線路,并且記錄 |ψ4〉的分布.對于每次模擬,都至少重復1000 次,從而減弱隨機誤差的影響,將每次計算得到的成功率進行平均,作為最后的成功率,并進行進一步的分析.

4.1 去極化通道

本文針對去極化通道分別研究了單比特門去極化噪聲與雙比特門去極化噪聲對Shor 算法的影響,并且認為所有的單比特門(X門,H門等)所經歷的噪聲大小相同.在運行量子線路過程中(不包括狀態制備以及測量)當量子比特經過任意單比特門后,可能會發生X門翻轉或者Y門翻轉或者Z門翻轉,概率均為P1/3 .本實驗模擬了N=15,N=21,N=35 的分解,對于每個整數使用不同的隨機數進行分解,具體組合如表2 所列.一次模擬整數分解實驗所消耗的資源隨著待分解整數比特增加而指數上升,代碼運行時間只與待分解大整數的比特數目與硬件配置有關.平均1 s 左右即可完成一次對N=15 的分解.一次N=21 的分解實驗需要消耗約12 s.而在對N=35 進行分解時,每進行一次分解實驗需要花費大約2 min 的時間.對于每一次模擬都重復1000 次從而減弱隨機誤差,因此共需要花費約1.4 d 的時間完成,這導致無法對更大的整數進行模擬分解.

表2 實驗選擇的待分解整數與隨機數組合(N,a)Table 2.Combination of integer about to be factored and random number (N,a).

對于每一個(N,a)組合,本文模擬了不同大小的單比特門去極化噪聲作用于量子線路的實驗.單比特去極化噪聲大小取值為[0,0.0005,0.001,0.0015,···,0.01].對于雙比特門去極化噪聲,只有當目標比特經過任意雙比特門(如CY門,CZ門,CX門等)后會發生X翻轉或Y翻轉或Z翻轉,3 種噪聲發生的概率均為P2/3,而控制比特不會受到影響.本文選擇表2 的大整數、隨機數組合進行模擬,對于每一個組合都模擬了其在不同噪聲大小下的實驗.P2取值為[0,0.00015,0.0003,0.00045,···,0.003].在去極化通道的模擬實驗中,首先對比不同大小的單比特門去極化噪聲對|ψ4〉的影響,如圖3 所示.

圖3 去極化通道中單比特門噪聲對(N=15,a=2),(N=21,a=2),(N=35,a=2)中 |ψ4〉 概率分布的影響Fig.3.Effect of one-qubit gate noise in DC on probability distribution of |ψ4〉 in (N=15,a=2),(N=21,a=2),(N=35,a=2).

每一列子圖都代表一組(N,a)組合,從左至右依次是N=15,N=21,N=35,每一組都選擇a=2 作為隨機數.每條曲線的數據都是1000 次模擬的平均并且歸一化處理后的結果.|ψ4〉的分布隨著噪聲大小增大而變得更混亂.隨著噪聲逐漸增大,峰值大小相比無噪聲時下降了很多.在3 組整數分解中,分解N=35 的實驗受噪聲影響最大.不同大小的雙比特門去極化噪聲對 |ψ4〉的影響如圖4 所示.

圖4 去極化通道中雙比特門噪聲對(N=15,a=2),(N=21,a=2),(N=35,a=2)中 |ψ4〉 概率分布的影響Fig.4.Effect of two-qubit gate noise in DC on probability distribution of |ψ4〉 in (N=15,a=2),(N=21,a=2),(N=35,a=2).

類似于圖3,隨著雙比特門去極化噪聲增大,每一組的分布更加混亂,峰值大小逐漸降低,分解N=35 受到噪聲影響最大.按照2.2 節中定義的Shor 分解算法的成功率,給出了Ps和MSE 分別與兩種去極化噪聲的關系,如圖5(a)和圖5(b)所示(這里只給出部分結果,所有結果見附錄B).

圖5 (a) Ps 與去極化通道中單比特門噪聲的關系;(b) Ps 與去極化通道中雙比特門噪聲的關系;(c) Ps 與狀態 制備與測量 通道中噪聲的關系Fig.5.(a) Effect of one-qubit gate noise in DC on Ps ;(b) effect of two-qubit gate noise in DC on Ps ;(c) effect of noise in SPAM channel on Ps .

圖5(a)和圖5(b)中的每個點對應相應噪聲大小下成功率的具體值,曲線是對成功率與噪聲大小關系的擬合,每組實驗都選擇隨機數a=2.去極化噪聲大小對成功率的影響呈指數形式,2.3 節中分析了量子門數量與待分解整數的二進制比特數的關系.隨著待分解整數比特數目增多,線路中的門數量更多,導致成功率隨著噪聲增大而下降更快.成功率隨著雙比特去極化噪聲增大而降低的趨勢快于單比特門,原因在于線路中雙比特門的數量多于單比特門數目.圖6(a)和圖6(b)是MSE 與兩種去極化噪聲的關系.

圖6 (a) MSE 與去極化通道中單比特門噪聲的關系;(b) MSE 與去極化通道中雙比特門噪聲的關系;(c) MSE 與狀態制備與測量通道中噪聲的關系Fig.6.(a) Effect of one-qubit gate noise in DC on MSE;(b) effect of two-qubit gate noise in DC on MSE;(c) effect of noise in SPAM channel on MSE.

4.2 狀態制備與測量通道

在狀態制備與測量過程中,本文假定所有制備狀態或者測量的量子比特都會按照Pspam的概率發生比特翻轉,選擇表2 中的大整數、隨機數的組合進行模擬.Pspam的范圍是 [0.01,0.02,0.03,···,0.2] .類似于去極化通道,對于每一次模擬都重復1000次.首先對比不同大小的SPAM噪聲對 |ψ4〉的影響,如圖7 所示.

圖7 狀態制備與測量通道中噪聲對(N=15,a=2),(N=21,a=2),(N=35,a=2)中 |ψ4〉 概率分布的影響Fig.7.Effect of noise in SPAM channel on probability distribution of |ψ4〉 in (N=15 a=2),(N=21,a=2) and (N=35,a=2).

在分解N=15 中,隨著噪聲增大,概率分布的峰值降低.|ψ4〉的分布相較無噪聲情況更混亂.本文使用Ps與MSE 來量化SPAM 噪聲對Shor算法的影響程度,分別如圖5(c)和圖6(c)所示.曲線中的每個點是實際計算的成功率大小,曲線則是對結果的擬合.通過曲線可以看出SPAM 噪聲的影響是線性的.因為在線路中一共只會受到2t+n次SPAM 噪聲的影響.理論上隨著待分解整數比特數目增加,線路會更容易受到噪聲影響,反映在圖5(c)中是斜率的絕對值更大.然而模擬結果這種特征并不明顯,主要原因在于分解的整數相差不大,相鄰兩個整數只相差了一位.并且由于測量次數與帶分解整數二進制位數呈線性關系,導致圖中擬合曲線斜率變化不明顯.

4.3 熱退相干通道

本文假定所有量子比特共享一組T1,T2,并且選擇表2 中的大整數、隨機數的組合進行模擬,對于每一個組合都模擬了在不同T1,T2組合下的算法運行.T1,T2參數選擇如表3 所列,共100 組.在模擬中量子門的時間均設置為 50 ns .并且分別針對退相干通道中N=15,N=21,N=35 的分解實驗重復了2000 次、4000 次以及8000 次.

表3 退相干通道中 T1,T2 的取值Table 3.Choice of T1,T2 in TRC.

對比不同T1,T2對于分解N=15,N=21,N=35的|ψ4〉分布的影響,如圖8 所示.

圖8 熱退相干通道中不同 T1,T2 對(N=15,a=2),(N=21,a=2),(N=35,a=2) 中的 |ψ4〉 概率分布的影響Fig.8.Different T1,T2 of TRC on probability distribution of |ψ4〉 in (N=15,a=2),(N=21,a=2) and (N=35,a=2).

隨著退相干時間降低,每一組 |ψ4〉的峰值大小降低,分布也更混亂.待分解的整數越大,對應的|ψ4〉分布的峰值下降得越明顯.與去極化通道的噪聲類似,在模擬中每當量子比特經過一個量子門時都會按照(9)式發生熱退相干.通過Ps以及MSE與退相干時間的關系可以更好地分析該類噪聲對Shor 算法的影響,如圖9 和圖10 所示.

圖9 Ps與熱退相干通道的噪聲的關系Fig.9.Effect of noise in TRC on Ps.

圖10 MSE 與熱退相干通道的噪聲的關系Fig.10.Effect of noise in TRC on MSE.

圖9 中白色區域是沒有數據的點.其他區域里顏色越深代表該T1,T2條件下的成功率越高.隨著T1,T2增大,成功率逐漸增大,并且隨著待分解整數比特數目增多,更容易受到退相干噪聲的影響,其成功率隨著T1,T2變化而波動的幅度相對更大.圖10 則是MSE與T1,T2的關系.

圖10 中白色區域是沒有數據的點.其他區域里顏色越深代表該T1,T2條件下的MSE 越高.隨著T1,T2增大,成功率也逐漸增大,對應的MSE逐漸降低.

5 總結與展望

本文將Shor 算法測量得到預期結果的概率之和作為Shor 算法整數分解的成功率,發現概率之和與均方誤差的高低能夠準確評估Shor 算法中量子線路的運行結果的優劣,在此基礎上開展了一系列針對不同類型的噪聲與成功率關系的研究.分別研究了去極化通道、狀態制備與測量通道、熱退相干通道的噪聲對Shor 算法的影響,并且在經典計算機上開展模擬Shor 算法分解整數的實驗.對于任一通道,設置了不同噪聲大小,得到了不同噪聲大小與算法成功率的數值關系.模擬結果表明,在去極化通道中成功率隨著噪聲增大呈指數降低.受量子線路搭建方式的影響,成功率隨雙比特門去極化噪聲增大而降低的趨勢快于單比特門去極化噪聲.而狀態制備與測量通道中的噪聲對于成功率的影響是線性的.相同噪聲大小情況下,隨著待分解的整數比特位數增多,需要的量子線路更加復雜,線路深度以及寬度都將增加,導致成功率隨噪聲增大而下降得更快.在真實量子計算機中運行Shor算法時,必須使用一系列的糾錯手段進行糾錯,并且需要將糾錯重點放在去極化噪聲中.此外,對于Shor 算法的量子線路進行優化與改進能夠有效地降低線路復雜度,并且有助于減弱算法運行時各類噪聲對量子線路的影響,如使用近似QFT 代替精確QFT 或者使用加窗以及陪集表示等方式都能夠降低線路復雜度,從而減弱因噪聲引起的誤差.未來我們將針對優化后的線路進行糾錯,探究在使用糾錯算法的基礎上量子線路的復雜度以及噪聲對線路的影響.

檸檬果醋的L值、a值和b值使用色差計進行測定。色差計使用前需要用較厚的白紙進行校準。ΔL值表示亮度；Δa值正值偏向紅色，負值偏向綠色；Δb值正值偏向黃色，負值偏向藍色。通過公式ΔE=(ΔL2+Δa2+Δb2)1/2來計算總色差。ΔE在0～0.5時，色差可以忽略，肉眼很難辨認；ΔE在0.5～1.0時，色差值很低，只有長期訓練的人才能觀察出；ΔE在1.0～1.5時，色差值屬于中等；ΔE>1.5時，色差嚴重。

感謝中國電子科技集團公司第三十二研究所量子創新中心的陳鑫淼與高薪凱對搭建Shor 算法量子線路的討論,同時感謝邢耀文以及姚曉梅對量子噪聲建模提供的思考以及對論文撰寫提供的指導.

附錄A

附錄A 詳述了連分數(continuous fraction)的原理,記作 Fraction() .在測量得到l后,需要計算 F raction(l/j),結果記作k/r,其中k是正整數,r是a的階.有限項的常規連分數(簡稱連分數)滿足以下的約束條件:?N∈N,?k∈N:aN+k=0,因此也可以寫成如下形式:

在Shor 算法中,將l/j記作g,根據(A1)式可以將任意一個小于1 的正有理數其寫成如下形式:

其中g1,g2,···,gM是正整數,如果在某一個gi將其截斷,舍棄掉一些小數,便可以得到該數的一個收斂,如

隨著gi的增加,被舍棄的部分越來越小,這些收斂值也越來越近g.在Shor 算法中,需要找到一組收斂[g1,g2,g3,···,gi],使得i足夠大的同時滿足有理數的分母gi也要小于N.最后得到的分母可能就是Shor 算法量子部分的最后結果r,即 1/[g1+1/(···+1/gi)]=k/r.

附錄B

圖B1 和圖 B2 給出了分解N=15,N=21,N=35 的實驗中Ps和MSE 與去極化通道中單比特門噪聲的關系.

圖B3 和圖 B4 給出了分解N=15,N=21,N=35 的實驗中Ps和MSE 與去極化通道中雙比特門噪聲的關系.

圖B1 分解實驗中 Ps 與去極化通道中單比特門噪聲的關系 (a) N=15;(b) N=21;(c) N=35Fig.B1.Effect of noise of one-qubit gate in DC on Ps of factoring:(a) N=15;(b) N=21;(c) N=35.

圖B5 和圖 B6 給出了分解N=15,N=21,N=35 的實驗中Ps和MSE 與狀態制備與測量通道中噪聲的關系.

圖B7 和圖 B8 給出了分解N=15,N=21,N=35 的實驗中成功率和MSE 與退相干通道中噪聲的關系.

表B1 給出了分解所有(N,a)組合的線路參數以及在不同噪聲的環境下的成功率.