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

衛 佳,倪 明,周 明,江文兵

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

0 概述

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

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

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

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

1.1 Grover搜索算法

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

圖1Grover搜索算法設計流程

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

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

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

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

步驟5執行Hadamard變換H?n。

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

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

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

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

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

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

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

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

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

1.2 量子隨機行走算法

本文所研究的量子隨機行走算法是基于圖的隨機行走。圖上的隨機行走是指定一個圖和一個起始點,隨機選擇一個相鄰節點,轉移到相鄰節點上后把該節點設定為新的起始點,不斷重復上述過程,由隨機行走經過的節點序列即構成一個隨機行走過程[15]。2個量子比特隨機行走算法示意圖如圖5所示。

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

在圖5中,設定起始點為|00>,經過第1次隨機行走后為|01>或|10>,再經過第2次隨機行走后變為|11>,第3次依然為|01>或|10>,第4次隨機行走之后回到|00>。

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

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

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

在8 192 shots的情況下重復運行3次量子隨機行走算法,結果為:|00>態出現的概率分別為0.830、0.832、0.830,平均概率為0.830;|01>態出現的概率分別為0.070、0.069、0.068,平均概率為0.069;|10>態出現的概率分別為0.076、0.077、0.076,平均概率為0.076 3;|11>態出現的概率分別為0.024、0.021、0.026,平均概率為0.024。上述2種情況的數據結果對比如圖7所示。

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

在IBM Qx4量子芯片和模擬器上分別運行量子隨機行走算法,在8 192 shots的情況下進行3次實驗,結果為:|00>態出現的概率分別為1、1、1,平均概率為1;|01>態出現的概率分別為0、0、0,平均概率為0;|10>態出現的概率分別為0、0、0,平均概率為0;|11>態出現的概率分別為0、0、0,平均概率為0。IBM Qx4量子芯片與模擬器實驗結果對比情況如圖8所示。

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

在IBM的5 bit超導量子芯片運行結果(圖3、圖7所示)中,測量次數增加(shots增大),測試結果并沒有隨之優化。這是因為量子比特的狀態與測量環境有關,每次的測量狀態不完全相同。但是,在測量次數更多時結果的穩定性更好。

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

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

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

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

量子傅里葉變換由2個基本門操作實現:一位門操作H門和兩位控制U門操作CUa,b。其中,b為控制位,a為目標位。當且僅當第b量子位為|1>態時,才對第a位施加幺正變換Ua,b。在a、b兩量子位Hilbert空間的計算機下,有:

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

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

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

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

圖10 5 bit量子傅里葉變換模擬計算結果

2.2 3 bit Grover搜索算法

3 bit Grover搜索算法模擬電路如圖11所示。3 bit Grover搜索算法的目標是從<000|到<111|的狀態中尋找|110>量子態,其算法思路如前文所述。在圖11中,C、B、A為Toffoli門,在IBM模擬器中,為CCX門。

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

Toffoli門的矩陣表示為:

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

圖12 3 bit Grover搜索算法模擬計算結果

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

3 結束語

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