衛(wèi) 佳,倪 明,周 明,江文兵

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

0 概述

近年來(lái),隨著多比特超導(dǎo)量子技術(shù)的發(fā)展[1]以及量子模擬器的相繼推出,量子算法的研究獲得高速發(fā)展。文獻(xiàn)[2]提出Shor因子分解算法,在量子計(jì)算領(lǐng)域具有里程碑式的意義。Shor因子分解算法只需多項(xiàng)式步長(zhǎng)計(jì)算就能完成一個(gè)整數(shù)的因子分解,其設(shè)計(jì)核心是量子傅里葉變換。量子傅里葉變換應(yīng)用較廣泛[3],其不僅在密碼領(lǐng)域有豐富的應(yīng)用,還在信號(hào)處理等領(lǐng)域有著舉足輕重的地位。在多項(xiàng)式時(shí)間內(nèi)部分經(jīng)典算法不能解決的問(wèn)題,可用量子傅里葉變換來(lái)解決,如求階問(wèn)題、隱含子群?jiǎn)栴}、離散對(duì)數(shù)問(wèn)題等。只要解決了求階問(wèn)題,RSA加密算法就非常容易被破解。

量子隨機(jī)行走算法[8]既有經(jīng)典隨機(jī)行走的背景,又具備量子計(jì)算的并行性[9]。在解決一些實(shí)際問(wèn)題,比如尋找三角形、區(qū)分元素時(shí),量子隨機(jī)行走算法相比經(jīng)典計(jì)算有更快的多項(xiàng)式分解速度。近年來(lái),量子隨機(jī)行走算法實(shí)現(xiàn)了搜索算法、模擬退火算法、公式估計(jì)[10]等,其被認(rèn)為是其他量子算法的設(shè)計(jì)工具之一,原因是經(jīng)典隨機(jī)行走在經(jīng)典算法中有很重要的地位,很多數(shù)學(xué)問(wèn)題都可以歸結(jié)為經(jīng)典隨機(jī)行走問(wèn)題。

IBM于2016年開(kāi)放量子云計(jì)算平臺(tái)[11]并上線5 bit超導(dǎo)量子芯片,研究者可以通過(guò)互聯(lián)網(wǎng)使用該量子平臺(tái)進(jìn)行算法研究、模擬以及量子芯片運(yùn)行。本文在IBM Q的5 bit超導(dǎo)量子芯片上分別以1 024 shots和8 192 shots的次數(shù)運(yùn)行2 bit Grover搜索算法和2 bit量子隨機(jī)行走算法,比較測(cè)量次數(shù)對(duì)真實(shí)量子計(jì)算機(jī)運(yùn)行結(jié)果的影響。然后在該平臺(tái)上用模擬器以8 192 shots分別運(yùn)行2 bit Grover搜索算法和2 bit量子隨機(jī)行走算法,并與上述量子芯片運(yùn)行結(jié)果作比較。最后采用IBM Q的量子模擬器運(yùn)行5 bit量子傅里葉變換算法和3 bit Grover搜索算法,并與數(shù)學(xué)分析結(jié)果進(jìn)行比較。

1 IBM Q量子芯片與量子模擬器對(duì)比實(shí)驗(yàn)

1.1 Grover搜索算法

Grover搜索算法的設(shè)計(jì)流程[12]如圖1所示。

圖1Grover搜索算法設(shè)計(jì)流程

Grover搜索算法具體步驟如下:

步驟2將目標(biāo)位態(tài)|x0>進(jìn)行旋轉(zhuǎn),使其獲得一個(gè)π相位,即Uf|x0>=-|x0>,其他量子態(tài)不受影響。在量子計(jì)算機(jī)中,這個(gè)變換可以由量子黑盒(Oracle)來(lái)執(zhí)行,命名為O,Oracle電路通過(guò)改變解的相位標(biāo)記來(lái)搜索問(wèn)題的解,由圖2中的實(shí)線框?qū)崿F(xiàn)電路。

步驟3執(zhí)行Hadamard變換H?n,即對(duì)每個(gè)比特進(jìn)行如下操作:

步驟4構(gòu)造酉算子Us=2|0><0|-I,執(zhí)行條件相移,實(shí)現(xiàn)|x>→-(-1)f(x)|x>,如圖2中的虛線框所示。例如,該步驟對(duì)|x>態(tài)進(jìn)行旋轉(zhuǎn),使得|x>態(tài)的相位在原來(lái)的基礎(chǔ)上增加π,此時(shí)|x>態(tài)變成-|x>態(tài)。

步驟5執(zhí)行Hadamard變換H?n。

圖2 Grover搜索算法電路示意圖

在圖2的Grover搜索算法量子電路中,算法目標(biāo)是從|00>、|01>、|10>、|11> 4個(gè)量子態(tài)中尋找|00>態(tài)出現(xiàn)的概率。該算法電路由一系列單比特門(mén)和多比特門(mén)構(gòu)成。單比特門(mén)有H門(mén)、S門(mén)(相位門(mén))、X門(mén),雙比特門(mén)主要是CNOT門(mén)。各量子門(mén)的矩陣表示分別為:

在Grover搜索算法量子電路中:首先,量子比特q0和q1經(jīng)過(guò)H門(mén),形成量子疊加態(tài)|s>,幅值都相等且為正值,再通過(guò)由S門(mén)、H門(mén)以及CNOT門(mén)組成的量子黑盒,獲得一個(gè)π相位,使得|00>態(tài)(目標(biāo)位態(tài))的幅值為負(fù)值,從而降低平均幅度;然后,通過(guò)由H門(mén)、酉算子Us=2|0><0|-I、H門(mén)構(gòu)成的2|s>的振幅提升到其原始值的3倍左右,從而能以大概率測(cè)量出|00>量子態(tài);最后,以2個(gè)時(shí)隙作為測(cè)量門(mén)分別測(cè)量q0和q1的狀態(tài),得到測(cè)量結(jié)果直方圖。

本文使用IBM Qx2量子芯片,可通過(guò)選擇不同的次數(shù)運(yùn)行電路得到結(jié)果:

1)在單次1 024 shots的情況下,重復(fù)運(yùn)行3次上述量子Grover搜索算法。此時(shí)測(cè)量結(jié)果為:|00>態(tài)出現(xiàn)的概率分別為0.816、0.888、0.927,平均概率為0.877;|01>態(tài)出現(xiàn)的概率分別為0.092、0.027、0.032,平均概率為0.050;|10>態(tài)出現(xiàn)的概率分別為0.061、0.074、0.020,平均概率為0.052;|11>態(tài)出現(xiàn)的概率分別為0.031、0.011、0.021,平均概率為0.021。此時(shí)大概率出現(xiàn)的是|00>態(tài)。

2)在8 192 shots的情況下重復(fù)運(yùn)行3次量子Grover搜索算法。測(cè)量結(jié)果為:|00>態(tài)出現(xiàn)的概率分別為0.872、0.920、0.917,平均概率為0.903;|01>態(tài)出現(xiàn)的概率分別為0.064、0.033、0.034,平均概率為0.044;|10>態(tài)出現(xiàn)的概率分別為0.042、0.024、0.028,平均概率為0.031;|11>態(tài)出現(xiàn)的概率分別為0.021、0.023、0.021,平均概率為0.022。數(shù)據(jù)結(jié)果對(duì)比如圖3所示。

圖3 在IBM Qx2量子芯片上運(yùn)行Grover搜索算法結(jié)果

下一步采用IBM Q量子模擬器運(yùn)行圖2所示算法,在8 192 shots的情況下進(jìn)行3次模擬,結(jié)果為:|00>態(tài)出現(xiàn)的概率分別為1、1、1,平均概率為1;|01>態(tài)出現(xiàn)的概率分別為0、0、0,平均概率為0;|10>態(tài)出現(xiàn)的概率分別為0、0、0,平均概率為0;|11>態(tài)出現(xiàn)的概率分別為0、0、0,平均概率為0。IBM Qx2量子芯片與模擬器實(shí)驗(yàn)結(jié)果對(duì)比情況如圖4所示。

圖4 在IBM Qx2量子芯片和模擬器上運(yùn)行Grover搜索算法結(jié)果對(duì)比(8 192 shots)

1.2 量子隨機(jī)行走算法

本文所研究的量子隨機(jī)行走算法是基于圖的隨機(jī)行走。圖上的隨機(jī)行走是指定一個(gè)圖和一個(gè)起始點(diǎn),隨機(jī)選擇一個(gè)相鄰節(jié)點(diǎn),轉(zhuǎn)移到相鄰節(jié)點(diǎn)上后把該節(jié)點(diǎn)設(shè)定為新的起始點(diǎn),不斷重復(fù)上述過(guò)程,由隨機(jī)行走經(jīng)過(guò)的節(jié)點(diǎn)序列即構(gòu)成一個(gè)隨機(jī)行走過(guò)程[15]。2個(gè)量子比特隨機(jī)行走算法示意圖如圖5所示。

圖5 量子隨機(jī)行走算法示意圖

在圖5中,設(shè)定起始點(diǎn)為|00>,經(jīng)過(guò)第1次隨機(jī)行走后為|01>或|10>,再經(jīng)過(guò)第2次隨機(jī)行走后變?yōu)閨11>,第3次依然為|01>或|10>,第4次隨機(jī)行走之后回到|00>。

量子隨機(jī)行走算法的量子電路如圖6所示。

圖6 量子隨機(jī)行走算法電路

使用IBM Qx4量子芯片,在1 024 shots的情況下重復(fù)運(yùn)行3次量子隨機(jī)行走算法,結(jié)果為:|00>態(tài)出現(xiàn)的概率分別為0.857、0.834、0.845,平均概率為0.845;|01>態(tài)出現(xiàn)的概率分別為0.058、0.065、0.083,平均概率為0.069;|10>態(tài)出現(xiàn)的概率分別為0.064、0.074、0.051,平均概率為0.063;|11>態(tài)出現(xiàn)的概率分別為0.021、0.026、0.021,平均概率為0.023。

在8 192 shots的情況下重復(fù)運(yùn)行3次量子隨機(jī)行走算法,結(jié)果為:|00>態(tài)出現(xiàn)的概率分別為0.830、0.832、0.830,平均概率為0.830;|01>態(tài)出現(xiàn)的概率分別為0.070、0.069、0.068,平均概率為0.069;|10>態(tài)出現(xiàn)的概率分別為0.076、0.077、0.076,平均概率為0.076 3;|11>態(tài)出現(xiàn)的概率分別為0.024、0.021、0.026,平均概率為0.024。上述2種情況的數(shù)據(jù)結(jié)果對(duì)比如圖7所示。

圖7 在IBM Qx4量子芯片上運(yùn)行量子隨機(jī)行走算法結(jié)果

在IBM Qx4量子芯片和模擬器上分別運(yùn)行量子隨機(jī)行走算法,在8 192 shots的情況下進(jìn)行3次實(shí)驗(yàn),結(jié)果為:|00>態(tài)出現(xiàn)的概率分別為1、1、1,平均概率為1;|01>態(tài)出現(xiàn)的概率分別為0、0、0,平均概率為0;|10>態(tài)出現(xiàn)的概率分別為0、0、0,平均概率為0;|11>態(tài)出現(xiàn)的概率分別為0、0、0,平均概率為0。IBM Qx4量子芯片與模擬器實(shí)驗(yàn)結(jié)果對(duì)比情況如圖8所示。

圖8 在IBM Qx4量子芯片和模擬器上運(yùn)行量子隨機(jī)行走算法結(jié)果對(duì)比(8 192 shots)

在IBM的5 bit超導(dǎo)量子芯片運(yùn)行結(jié)果(圖3、圖7所示)中,測(cè)量次數(shù)增加(shots增大),測(cè)試結(jié)果并沒(méi)有隨之優(yōu)化。這是因?yàn)榱孔颖忍氐臓顟B(tài)與測(cè)量環(huán)境有關(guān),每次的測(cè)量狀態(tài)不完全相同。但是,在測(cè)量次數(shù)更多時(shí)結(jié)果的穩(wěn)定性更好。

量子芯片將量子線路集成在芯片上,在極限低溫下構(gòu)建量子物理系統(tǒng),同時(shí)對(duì)量子物理系統(tǒng)進(jìn)行調(diào)控,其間遵守量子動(dòng)力學(xué)規(guī)律。量子模擬器基于經(jīng)典計(jì)算機(jī)的架構(gòu)模擬量子系統(tǒng)。在IBM量子芯片與模擬器的對(duì)比測(cè)試結(jié)果(圖4、圖8所示)中,模擬器計(jì)算結(jié)果的準(zhǔn)確度明顯優(yōu)于量子芯片。在真實(shí)芯片測(cè)量環(huán)境下,單比特門(mén)與雙比特門(mén)的保真度不高。例如,稀釋制冷機(jī)中沒(méi)有完全隔絕的熱噪聲會(huì)影響原子躍遷,微波系統(tǒng)測(cè)量精確度不足將導(dǎo)致最后的結(jié)果偏差,每次測(cè)量時(shí)量子比特的隨機(jī)坍縮等都是影響其保真度的因素。

2 量子傅里葉變換算法與Grover搜索算法

2.1 5 bit量子傅里葉變換算法

量子傅里葉變換即作用在空間C2n中的離散傅里葉變換。離散傅里葉變換是有限長(zhǎng)序列傅里葉變換的有限點(diǎn)離散采樣,而量子傅里葉變換把一組標(biāo)準(zhǔn)正交基{|x>}用另一組標(biāo)準(zhǔn)正交基{|y>}表示:Y=UX。此處的U就是量子傅里葉變換的核心,即作用在Hilbert空間中任意矢量上的變換矩陣UQFT,該矩陣可以拆分成一系列邏輯門(mén)。一個(gè)量子比特的量子傅里葉變換就是H門(mén)操作,在多量子位態(tài)空間上的傅里葉變換是上述單量子位H變換的推廣。簡(jiǎn)而言之,量子傅里葉變換就是將任意單量子態(tài)制備成疊加量子態(tài),從而進(jìn)行酉變換并完成指數(shù)級(jí)加速。

量子傅里葉變換由2個(gè)基本門(mén)操作實(shí)現(xiàn):一位門(mén)操作H門(mén)和兩位控制U門(mén)操作CUa,b。其中,b為控制位,a為目標(biāo)位。當(dāng)且僅當(dāng)?shù)赽量子位為|1>態(tài)時(shí),才對(duì)第a位施加幺正變換Ua,b。在a、b兩量子位Hilbert空間的計(jì)算機(jī)下,有:

其中,相移θa,b=2πxb/2a-b+1。

5量子位的傅里葉變換可以用圖9所示的電路實(shí)現(xiàn),該網(wǎng)絡(luò)對(duì)輸入態(tài)|x>=|x4x3x2x1x0>從左到右依次執(zhí)行變換[16]:H0U1,0H1(U2,0U2,1)H2(U3,0U3,1U3,2)H3(U4,0U4,1U4,2U4,3)H4。其中,門(mén)H的下標(biāo)指明它作用的量子位。CU1在IBM Q量子云平臺(tái)中表示沿Z軸旋轉(zhuǎn)一定角度的受控Z門(mén),其是一個(gè)雙比特門(mén)。而在IBM量子云平臺(tái)中,使用CU1門(mén)來(lái)實(shí)現(xiàn)該操作。其中,Pi/2代表沿Z軸轉(zhuǎn)動(dòng)π/2的角度,對(duì)于U0,1來(lái)說(shuō),當(dāng)且僅當(dāng)q[1]為|1>態(tài)時(shí),才對(duì)q[0]施加幺正變換U0,1,使之沿Z軸轉(zhuǎn)動(dòng)π/2,以此類(lèi)推。

圖9 5 bit量子傅里葉變換模擬電路

本次模擬次數(shù)為8 192 shots。根據(jù)理論推算,其結(jié)果應(yīng)該是5 bit的均勻疊加態(tài),即32個(gè)等概率的量子態(tài):從|00000>到|11111>,概率為1/32=0.031 25。模擬器的運(yùn)行結(jié)果(如圖10所示)顯示了20個(gè)結(jié)果的狀態(tài),其中,橫坐標(biāo)1#～20#代表不同的量子態(tài),分別為|10101>、|10110>、|11010>、|11011>、|01011>、|10111>、|00011>、|11100>、|01000>、|01110>、|10011>、|00101>、|10100>、|10000>、|00010>、|00111>、|01100>、|11001>、|11110>、|00000>。余下12個(gè)量子態(tài)的概率值以一個(gè)總和的結(jié)果呈現(xiàn):0.355/12≈0.029 6。根據(jù)上述理論結(jié)果推算,模擬器結(jié)果的最大概率誤差為0.1。

圖10 5 bit量子傅里葉變換模擬計(jì)算結(jié)果

2.2 3 bit Grover搜索算法

3 bit Grover搜索算法模擬電路如圖11所示。3 bit Grover搜索算法的目標(biāo)是從<000|到<111|的狀態(tài)中尋找|110>量子態(tài),其算法思路如前文所述。在圖11中,C、B、A為T(mén)offoli門(mén),在IBM模擬器中,為CCX門(mén)。

圖11 3 bit Grover搜索算法模擬電路

Toffoli門(mén)的矩陣表示為:

采用IBM量子模擬器在8 192 shots情況下進(jìn)行測(cè)量,結(jié)果如圖12所示。其中,橫坐標(biāo)代表量子態(tài)。由圖12可以看出,搜索到目標(biāo)量子|110>的概率為0.944,相比于2 bit的Grover搜索算法模擬結(jié)果而言,誤差相對(duì)較大。造成該現(xiàn)象的原因是量子邏輯門(mén)運(yùn)行時(shí)會(huì)有一定的噪聲,在本次實(shí)驗(yàn)中,采用了Toffoli 3 bit的邏輯門(mén),從而造成明顯誤差。此外,量子比特?cái)?shù)增多、量子線路變長(zhǎng)也會(huì)引起誤差增加[17]。

圖12 3 bit Grover搜索算法模擬計(jì)算結(jié)果

采用模擬器對(duì)單比特門(mén)進(jìn)行模擬后可知,單比特門(mén)的模擬結(jié)果也存在誤差。對(duì)于H門(mén),最優(yōu)計(jì)算結(jié)果是均勻疊加態(tài),即|0>和|1>的測(cè)量概率相等,均為0.5,但模擬計(jì)算結(jié)果為0.502和0.498,誤差范圍在0.01以內(nèi)。

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

本文基于IBM Q云計(jì)算平臺(tái),針對(duì)3種典型量子算法——Grover搜索算法、量子隨機(jī)行走算法、量子傅里葉變換算法,分別采用量子芯片和量子模擬器進(jìn)行測(cè)試。結(jié)果表明,增加測(cè)試次數(shù)并不能提高量子芯片的保真度,而相比量子芯片,模擬器的計(jì)算結(jié)果準(zhǔn)確度較高。此外,本文設(shè)計(jì)并運(yùn)行5 bit量子傅里葉變換算法和3 bit Grover搜索算法,分別采用IBM Q模擬器進(jìn)行8 192 shots情況下的測(cè)量。結(jié)果表明,量子模擬結(jié)果和數(shù)學(xué)理論推導(dǎo)結(jié)果在誤差范圍內(nèi)一致。本文最后將經(jīng)典計(jì)算機(jī)量子模擬結(jié)果與數(shù)學(xué)分析結(jié)果作對(duì)比,分別對(duì)單比特門(mén)和多比特門(mén)的誤差產(chǎn)生進(jìn)行分析。下一步將針對(duì)更高量子比特的算法,在設(shè)計(jì)與實(shí)現(xiàn)的過(guò)程中使運(yùn)算結(jié)果更接近所求解的目標(biāo)值,以進(jìn)一步減小誤差,提高保真度。