基于Cirq的Grover搜索算法的電路實(shí)現(xiàn)

吳 希,李志強(qiáng)

(揚(yáng)州大學(xué)信息工程學(xué)院,江蘇 揚(yáng)州 225100)

0 引言

Grover量子搜索算法[1]是經(jīng)典的量子算法之一,體現(xiàn)了量子計算的優(yōu)勢和廣闊的應(yīng)用前景。它利用量子的并行性,將傳統(tǒng)計算機(jī)的搜索算法從O(N)的復(fù)雜度降為,很大程度上提高了搜索效率。然而,Grover算法也存在局限性,當(dāng)搜索的目標(biāo)數(shù)超過搜索總數(shù)的1/4時,搜索的成功率會迅速下降,當(dāng)目標(biāo)數(shù)超過1/2時,算法就會失效[2]。為了讓Grover算法有更多的應(yīng)用前景,研究人員在算法的改進(jìn)與優(yōu)化方面做了大量研究,主要的改進(jìn)方式有以下三種[3-5]:(1)改變一些步驟或變換算子;(2)改變運(yùn)算算子的相位旋轉(zhuǎn)角度;(3)尋找更一般的初始態(tài)幅值來解決尋找中值、最小值等特定問題。其中,從相位角度的改進(jìn)效果最好。

當(dāng)前還沒有研制出成熟的量子計算機(jī),所以對量子算法進(jìn)行模擬實(shí)驗(yàn)具有重要意義。Cirq[6]是谷歌發(fā)布的一款基于Python的開源框架,用于模擬NISQ(Noisy Intermediate-Scale Quantum)計算機(jī)上的電路,使研究人員能在特定的處理器上編寫量子算法,解決實(shí)際的計算問題,對復(fù)雜的細(xì)節(jié)進(jìn)行研究。本文通過Cirq框架實(shí)現(xiàn)Grover算法的量子電路模擬,根據(jù)實(shí)驗(yàn)?zāi)M結(jié)果驗(yàn)證了Grover算法的正確性,同時也證明了該算法存在的不足。并且介紹了基于改變相位旋轉(zhuǎn)角度的精準(zhǔn)算法[7],對算法進(jìn)行量子電路模擬實(shí)現(xiàn),驗(yàn)證了精準(zhǔn)算法的有效性。由此可見,Cirq為量子電路的模擬提供了技術(shù)支持,使人們對理論的研究更具現(xiàn)實(shí)意義。

1 Grover基本算法實(shí)現(xiàn)

1.1 算法步驟和幾何描述

假設(shè)要在N=2n個無結(jié)構(gòu)的搜索元素中尋找M個目標(biāo)解,1≤M≤N,找到M中的任意一個解都算成功。于是元素指標(biāo)可以存儲在n個量子比特中[8]。

首先介紹Grover算法中的一個重要操作:Oracle操作。定義一個f(x),x是搜索的元素,當(dāng)滿足f(x)=1,x是搜索問題的解,反之則不是解。在搜索的過程中將注意力放在元素的索引上,搜索范圍就是0～2n-1。Oracle是一個能夠識別出搜索問題目標(biāo)解的酉算子,被定義為|x,q〉→|x,q⊕f(x)〉,其中:|x〉存儲搜索元素的索引,|q〉是一個單量子比特,⊕表示模2加。把|q〉初始化為|-〉,當(dāng)f(x)=1時,狀態(tài)的概率幅進(jìn)行翻轉(zhuǎn)變成負(fù)的;反之則不變。由于在Oracle作用前后|q〉并沒有發(fā)生變化,所以該操作可以化簡為O:|x〉→ (-1)f(x)|x〉。

1.2 電路實(shí)現(xiàn)

用一個示例來說明Grover算法在2-qubit搜索空間中的具體電路。其中Oracle的相位翻轉(zhuǎn)操作用受控Z門來實(shí)現(xiàn)。如圖1所示,滿足f(x0)=1的四個電路由上至下分別對應(yīng)x0=0,1,2,3的情況。每個電路的右邊給出了對應(yīng)的真值表,由表可以看出,電路能夠?qū)崿F(xiàn)O:|x〉→(-1)f(x)|x〉的操作。

圖1 Oracle電路以及目標(biāo)位(a)00,(b)01,(c)10,(d)11的真值表Fig.1 Oracle circuit and truth table of target bits(a)00,(b)01,(c)10,(d)11

假設(shè)目標(biāo)解是|11〉,那么2-qubit的Grover電路如圖2所示,實(shí)線框中是|11〉對應(yīng)的Oracle操作,虛線框中是擴(kuò)散操作,只需進(jìn)行一次Grover迭代。

圖2 2-qubit的Grover算法電路Fig.2 Circuit of 2-qubit Grover algorithm

將電路擴(kuò)展至n-qubit,通過基于python3.7的Cirq框架,在聯(lián)想V3000上實(shí)現(xiàn)n-qubit的Grover量子電路,實(shí)現(xiàn)的部分代碼如下:

import cirq def make-Oracle(q,qn-1,x-bits): ?Oracle操作yield(cirq.X(q)for(q,bit)in zip(q,x-bits)if not bit)yield cirq.Z(q[len(q)-1]).controlled-by(*qn-1)yield(cirq.X(q)for(q,bit)in zip(q,x-bits)if not bit)def make-Grover(q,qn-1): ?Grover算子yield cirq.H.on-each(*q)yield cirq.X.on-each(*q)yield cirq.Z(q[len(q)-1]).controlled-by(*qn-1)yield cirq.X.on-each(*q)yield cirq.H.on-each(*q)def main():q=[cirq.GridQubit(i,0)for i in range(n)]?n位量子比特qn-1=[cirq.GridQubit(i,0)for i in range(n-1)]?前n-1位量子比特x=random.sample(range(0,2**n),m) ?隨機(jī)生成m個目標(biāo)數(shù)count=int((math.pi/4)*(2**n/m)**0.5) ?迭代次數(shù)circuit=cirq.Circuit(cirq.H.on-each(*q)) ?準(zhǔn)備疊加態(tài)的電路for-in range(0,count): ?Grover迭代電路for i in x-bitsM:circuit.append(make-Oracle(q,qn-1,i))circuit.append(make-Grover(q,qn-1))circuit.append(cirq.measure(*q,key=’result’)) ?測量simulator=cirq.Simulator() ?模擬器result=simulator.run(circuit,repetitions=100000) ?測量結(jié)果

1.3 實(shí)驗(yàn)結(jié)果及分析

對電路進(jìn)行測試,輸入3位量子位數(shù)和1個目標(biāo)元素,對電路進(jìn)行100000次測量,對測量結(jié)果進(jìn)行采樣。運(yùn)行結(jié)果如圖3所示,電路圖中第一個虛線框是Oracle操作,第二個框是擴(kuò)散操作,進(jìn)行了兩次Grover迭代。隨機(jī)產(chǎn)生的一個目標(biāo)元素是5,采樣結(jié)果根據(jù)次數(shù)由高到低顯示,測量得到5的次數(shù)最多,為94519次;測量到其他數(shù)的次數(shù)在800左右。根據(jù)結(jié)果可知算法正確的概率大約為94.5%。

圖3 3-qubit的實(shí)驗(yàn)結(jié)果Fig.3 Experimental results of 3-qubit

對目標(biāo)數(shù)占搜索總數(shù)的1/2這一情況進(jìn)行實(shí)驗(yàn),測試結(jié)果如表1所示。時刻表示所有在同一抽象時間段內(nèi)執(zhí)行的操作的集合。例如圖3的三個用于初始化的H門表示一個時刻數(shù)。從表1可以看出,當(dāng)目標(biāo)元素為總搜索數(shù)的1/2時,不論數(shù)量有多大,搜索的成功率都為50%。當(dāng)運(yùn)行到13個量子位時,輸出的電路會出現(xiàn)錯誤,原因是電路的復(fù)雜度達(dá)到上限,但測量得到的結(jié)果是準(zhǔn)確的。若將13個量子位的目標(biāo)數(shù)改為2048,則可以輸出正確的電路,說明Oracle查詢的復(fù)雜度對電路復(fù)雜度的影響很大。目標(biāo)數(shù)成倍增加伴隨著Oracle查詢越復(fù)雜,所需時刻數(shù)與門數(shù)也趨于成倍增加,運(yùn)行時間也就越長。

表1 目標(biāo)數(shù)為1/2時的實(shí)驗(yàn)結(jié)果Table 1 Experimental results when the number of targets accounted for 1/2 of the total

以固定的1024個搜索總數(shù)為例驗(yàn)證算法的性能,實(shí)驗(yàn)結(jié)果記錄在表2中。隨機(jī)生成無序的搜索目標(biāo)并且不斷增大目標(biāo)元素的數(shù)量,分析目標(biāo)元素與搜索總數(shù)的比值λ對Grover迭代次數(shù)R以及搜索成功概率P的影響。

表2 Grover算法成功率實(shí)驗(yàn)結(jié)果Table 2 Experimental results of the success probability rate of Grover algorithm

從表2可以看出,當(dāng)0.3＜λ＜0.5時,算法的成功率迅速下降,迭代的次數(shù)始終是1;當(dāng)λ＞0.5時,算法的成功率甚至低于失敗率。傳統(tǒng)的搜索方法是目標(biāo)元素越多,成功率則越高,而量子Grover算法卻是在搜索數(shù)較少時有較高的成功率。除此以外,傳統(tǒng)的搜索方法總能得到百分百的正確率,基本Grover算法由于其測量特性,可能需要進(jìn)行多次搜索才能達(dá)到預(yù)期效果。

2 精準(zhǔn)Grover算法的實(shí)現(xiàn)

上文介紹了Grover量子搜索算法的基本步驟、幾何描述以及公式推導(dǎo)。也通過在Cirq框架上對電路的模擬分析,直觀地了解到Grover算法存在的局限性。已有許多學(xué)者針對這些不足進(jìn)行了深入研究。Long等[9]最初發(fā)現(xiàn)Grover算法中的兩個相移算子可以被相位匹配關(guān)系的相位角代替,基本的Grover算法中存在兩次相位翻轉(zhuǎn),翻轉(zhuǎn)的角度都是固定的π。目前,基于兩個旋轉(zhuǎn)算子中旋轉(zhuǎn)相位匹配條件的改進(jìn),提出了許多可以提高搜索成功概率的改進(jìn)算法[10-12]。通過Cirq框架可以很容易地模擬這些改進(jìn)算法。

Long等[9]首次提出了精準(zhǔn)的量子搜索算法,使搜索的成功率達(dá)到100%。但該算法存在兩個缺陷,一是只適用于搜索一個目標(biāo)元素,二是無法解決目標(biāo)數(shù)占總搜索數(shù)1/2的情況。所以Xia等[8]在此基礎(chǔ)上進(jìn)行改進(jìn),先將相位取反,再將搜索總數(shù)這一變量引入到相位旋轉(zhuǎn)角度中,使得算法具有實(shí)時性,成功概率一直為100%。這一算法非常適合需要高精度的應(yīng)用場景中的搜索。該算法將相位旋轉(zhuǎn)角改為

通過基于google的Cirq框架模擬實(shí)現(xiàn)精準(zhǔn)算法,只需要在基本的Grover算法中添加旋轉(zhuǎn)角度這一變量,部分代碼如下:

?根據(jù)公式算出相位旋轉(zhuǎn)角度angle和迭代次數(shù)count a=(m/2**n)**0.5 bl=2*math.asin(a)J=(math.pi-bl)/(2*bl)count=math.ceil(J)t=math.sin(math.pi/(4*count+2))/a angle=2*math.asin(t)/math.pi?為旋轉(zhuǎn)Z門添加旋轉(zhuǎn)角度yield Cirq.Z(q[len(q)-1]).controlled-by(*qn-1)**angle

對3-qubit精準(zhǔn)算法進(jìn)行測試,隨機(jī)產(chǎn)生三個目標(biāo)元素,單次運(yùn)行結(jié)果如圖4所示,測量正確的概率為100%,并給出了旋轉(zhuǎn)門所需旋轉(zhuǎn)的角度為0.608。電路圖中的第一個虛線框?qū)?yīng)三個目標(biāo)元素的Oracle操作。

經(jīng)過多次實(shí)驗(yàn),模擬實(shí)現(xiàn)的結(jié)果與理論計算結(jié)果一致,算法的成功率始終是100%,驗(yàn)證了算法的有效性。用Cirq框架可以輕易地模擬出基于相位旋轉(zhuǎn)匹配改進(jìn)算法的電路。相比于文獻(xiàn)[13]中使用量子程序設(shè)計語言QCL模擬實(shí)現(xiàn),使用Cirq框架實(shí)現(xiàn)量子算法,不僅能夠看到概率性以及復(fù)數(shù)矩陣的輸出,還能看到整個算法實(shí)現(xiàn)的完整電路,這對電路的優(yōu)化起到了很大的幫助。

圖4 3-qubit精準(zhǔn)Grover算法的結(jié)果Fig.4 Results of 3-qubit accurate Grover algorithm

3 總結(jié)與展望

借助Cirq框架,對基本Grover算法及其改進(jìn)的精準(zhǔn)算法進(jìn)行了電路模擬,對測試結(jié)果進(jìn)行分析,驗(yàn)證各算法的準(zhǔn)確性以及各自存在的特點(diǎn),方便應(yīng)用于不同的情景。搜索算法的相位旋轉(zhuǎn)通過改變旋轉(zhuǎn)Z門的角度來實(shí)現(xiàn),但目前只是對其進(jìn)行模擬,還未在特定的處理器上實(shí)現(xiàn),而Cirq也提供了在實(shí)際硬件上運(yùn)行的功能,以便未來開展進(jìn)一步的優(yōu)化工作。本研究中基于相位旋轉(zhuǎn)匹配的改進(jìn)算法都是在目標(biāo)分量已知的情況下,算法的迭代次數(shù)都依賴于目標(biāo)分量的數(shù)量。當(dāng)目標(biāo)分量的數(shù)量未知時,往往需要很高的Oracle查詢復(fù)雜度,而且如何在最優(yōu)迭代次數(shù)時停止也是需要研究的問題。已有一些改進(jìn)的算法來解決這一問題[14,15],但在效率與概率方面都存在進(jìn)步空間,希望未來能夠在目標(biāo)分量未知的情況下,通過Cirq框架對算法進(jìn)行優(yōu)化、驗(yàn)證與分析。此外,通過對Cirq框架源碼的深入理解,還可以更多地擴(kuò)展其功能,為電路的模擬提供更強(qiáng)大的技術(shù)支持。