基于IBM Q平臺的量子算法研究

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

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

0 概述

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

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

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

1 IBM Q量子芯片與量子模擬器對比實驗

1.1 Grover搜索算法

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

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

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

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

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

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

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

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

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

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

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

1)在單次1 024 shots的情況下,重復(fù)運行3次上述量子Grover搜索算法。此時測量結(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。此時大概率出現(xiàn)的是|00>態(tài)。

2)在8 192 shots的情況下重復(fù)運行3次量子Grover搜索算法。測量結(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é)果對比如圖3所示。

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

下一步采用IBM Q量子模擬器運行圖2所示算法,在8 192 shots的情況下進行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量子芯片與模擬器實驗結(jié)果對比情況如圖4所示。

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

1.2 量子隨機行走算法

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

圖5 量子隨機行走算法示意圖

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

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

圖6 量子隨機行走算法電路

使用IBM Qx4量子芯片,在1 024 shots的情況下重復(fù)運行3次量子隨機行走算法,結(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ù)運行3次量子隨機行走算法,結(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é)果對比如圖7所示。

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

在IBM Qx4量子芯片和模擬器上分別運行量子隨機行走算法,在8 192 shots的情況下進行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 Qx4量子芯片與模擬器實驗結(jié)果對比情況如圖8所示。

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

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

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

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

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

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

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

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

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

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

本次模擬次數(shù)為8 192 shots。根據(jù)理論推算,其結(jié)果應(yīng)該是5 bit的均勻疊加態(tài),即32個等概率的量子態(tài):從|00000>到|11111>,概率為1/32=0.031 25。模擬器的運行結(jié)果(如圖10所示)顯示了20個結(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個量子態(tài)的概率值以一個總和的結(jié)果呈現(xiàn):0.355/12≈0.029 6。根據(jù)上述理論結(jié)果推算,模擬器結(jié)果的最大概率誤差為0.1。

圖10 5 bit量子傅里葉變換模擬計算結(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為Toffoli門,在IBM模擬器中,為CCX門。

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

Toffoli門的矩陣表示為:

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

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

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

3 結(jié)束語

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