姜瑤瑤 張文彬 初鵬程 馬鴻洋?

1)(青島理工大學理學院,青島 266033)

2)(青島理工大學信息與控制工程學院,青島 266033)

在量子計算科學中,如何更好地構建量子搜索算法一直以來受到學者們的廣泛關注,并且基于量子行走尋找新的搜索算法也仍吸引著學者們不斷深入研究與探索.本文從減少搜索過程中的時間消耗、增加算法搜索的準確性和可控性等多方面進行考慮,提出了一種基于置換群的多粒子量子行走搜索算法.首先分析得到置換群在空間中可看成一個閉環(huán),定義了置換集合,并且通過同構映射將數(shù)據(jù)點所在數(shù)據(jù)集映射到定義的置換集,使得置換集合中元素數(shù)據(jù)點形成一一對應的關系.其次,根據(jù)給定初始態(tài)和硬幣算符,在數(shù)據(jù)點集與置換集合張成的搜索空間中利用多粒子的量子行走在環(huán)上進行目標數(shù)據(jù)搜索.最后,根據(jù)函數(shù) Φ(w)=1 找到目標數(shù)據(jù),并用量子態(tài)存儲數(shù)值,用于形成搜索算法的反饋控制;同時通過控制硬幣算符從而控制量子行走在環(huán)上的行走方向,增加搜索的可操作性與準確性.本文利用多粒子的量子行走進行搜索,分析得到粒子數(shù)量參數(shù)j 與時間復雜度呈非線性負相關;提出的量子行走搜索算法符合零點條件與下確界條件,且不受變量數(shù)j 的影響;通過數(shù)值分析得到量子行走搜索算法的時間復雜度等價于,相比于Grover 搜索算法提高了搜索效率.

1 引言

量子行走作為經(jīng)典行走的推廣,是量子計算的基礎,被視為實現(xiàn)量子計算的一種主要工具.量子行走利用量子態(tài)的疊加性,能夠實現(xiàn)同時行走在不同線路上的可能性,因此與經(jīng)典行走相比,量子行走的效率有著指數(shù)級的增長.并且行走者位置的概率分布也與經(jīng)典行走有著截然不同的形式,這些性質都有利于量子算法的實現(xiàn).量子行走最初是由Aharonov 等[1]及Farhi 和Gutmann[2]提出的.其中Aharonov 等[1]提出了離散時間狀態(tài)下的量子行走算法;Farhi 和Gutmann[2]提出了連續(xù)時間狀態(tài)下的量子行走算法.與經(jīng)典行走相比,這兩種行走方法都提供了加速效果.Godsil 等[3]和Bose[4]展示了如何將圖論的思想應用到量子行走中來實現(xiàn)更好的狀態(tài)傳輸;Childs[5]證明了量子行走可以實現(xiàn)普適的量子計算.這些成果都體現(xiàn)了量子行走在實際應用中的重要性.此外,基于量子行走的許多搜索算法都體現(xiàn)了量子行走在算法領域具有獨特的優(yōu)勢[6-12].

在搜索算法中,Grover 算法是第二個量子革命的一個里程碑[13].除了數(shù)據(jù)庫搜索,它還可以用于求解特征值問題,這是目前最熱門的課題之一.2010 年Childs[14]提出基于連續(xù)時間量子漫步的算法,在黑箱問題中量子行走成功實現(xiàn)了指數(shù)級的加速.Shenvi 等[15]也在超立方體的拓撲知識的基礎上提出了基于離散時間量子漫步的搜索算法,實現(xiàn)了多項式加速效果.由于搜索算法以及可轉化為搜索問題的算法具有廣泛適用性的特點,在這些開創(chuàng)性的工作之后,學者們又進行了深入的研究[14,16-23].在國內,Long 等[24-26]不斷完善優(yōu)化Grover 搜索算法,他們研究的算法是所有優(yōu)化的Grover 算法中最優(yōu)的,又稱龍算法[26];Zhou 等[27-30]和Sheng等[31,32]也分別在量子搜索算法和量子計算領域做出了貢獻.考慮到量子計算的優(yōu)勢,學者們期待大量新的量子算法的出現(xiàn),但事實證明這項任務很難,值得繼續(xù)研究和探索.

基于量子行走尋找新的算法仍然是持續(xù)努力的方向,本文提出了一種基于置換群的空間量子行走搜索算法,將置換群作為搜素算法和量子行走相結合的橋梁,目的是減少搜索時間,提高目標搜索的精度,提高空間內的搜索效果.根據(jù)置換群中的元素在幾何中可以形成環(huán)的性質,將量子行走應用到置換群中,從而實現(xiàn)在置換群中的量子搜索.首先通過設置同構映射,將數(shù)據(jù)點集合映射到由多個置換群組成的置換集合中的元素,為了能夠實現(xiàn)環(huán)上的量子行走,在同構映射的作用下使數(shù)據(jù)點集合和置換集合具有一對一的對應關系.然后,構造Hilbert 空間,通過控制硬幣算子,給定初始狀態(tài),將搜索空間中的元素作為節(jié)點,進行量子行走.接著根據(jù)函數(shù)Φ(w)=1 得到目標點,并用量子態(tài)存儲函數(shù)值.最后根據(jù)函數(shù)的數(shù)值形成算法的反饋控制,以此來判斷量子行走的方向以及確定行走的狀態(tài).本文有3 個創(chuàng)新點:1)將數(shù)據(jù)集同構到置換集,實現(xiàn)了置換群上的量子行走;2)多粒子受控的量子行走;3)增加了反饋控制,增強算法的可操作性與可控性.

本文結構如下:第2 節(jié)簡要介紹置換群S3以及環(huán)上的量子行走;第3 節(jié)分析并實現(xiàn)量子行走搜索算法,其中包括10 個步驟;第4 節(jié)對量子行走搜索算法進行時間復雜度分析;第5 節(jié)根據(jù)時間復雜度進行數(shù)值仿真,直觀明了地體現(xiàn)數(shù)值結果;第6 節(jié)對算法進行總結.

2 相關工作

2.1 置換群S3

定義2.1 (置換群):有限集合到自身的一一映射稱為一個置換.有限集合S上的一些置換組成的集合,在置換的乘法下所組成的群,稱為置換群[33].任何一個有限群都同構于一個置換群.因此,可以把一切有限群都看成置換群.任一置換可表示成若干不相交循環(huán)的乘積,如(a1,a2,···,an)=稱為置換的循環(huán)表示.由于每個循環(huán)首尾相連,因此可以看成是一個閉環(huán).

本文置換群的選擇是根據(jù)搜索空間中目標態(tài)的維數(shù)決定的.由于本文提出的搜索算法是在三維空間中進行的,因此只對置換群S3進行研究,若搜索空間是n維,可以換成置換群Sn,置換群的選擇并不會影響算法的時間復雜度.其中

S3={(e),(ab),(ac),(bc),(abc),(acb)}.

2.2 環(huán)上行走

假設群G是有限群,S是該群的生成集合,環(huán)A和群G存在一一對應關系,若節(jié)點g和g′滿足g′=gh,則存在一條邊 (g,g′),其中g∈G,h∈S.將環(huán)A中元素量子化:

其中,HS為硬幣算符所在的Hilbert 空間,HG為量子行走所處的位置空間.環(huán)上量子行走的演化算符為U=T(C?I),I為位置空間的單位算符,C為硬幣算符,T為轉移算符,具體定義如下:

3 量子行走搜索算法

3.1 初始化階段

步驟1應用置換群的對稱運算

在介紹量子行走搜索算法之前首先利用對稱運算證明置換群S3的每個子群在空間中形成一個閉環(huán),并且根據(jù)旋轉角度,規(guī)定群內元素的次序.為了便于下文解釋說明,將群中元素a,b,c替換為1,2,3.

對于置換群S3,有如下保持三角形不變的對稱運算:(e)是一個恒等變化;(123),(132)分別為繞中心點逆時針旋轉;(12),(13),(23)分別為圍繞x,y,z軸逆時針旋轉π.每個元素旋轉情況如圖1 所示.同時可以得到置換群S3的4 個子群:

圖1 置換群 S3 中每個元素的旋轉方位圖Fig.1.Diagram of the rotation position of each element in the permutation group S3.

H1={e,(12)},H2={e,(13)},

H3={e,(123),(132)},H4={e,(23)}.

按照元素的旋轉角度,以單位元為起點,規(guī)定每個子群的元素排列順序.例如在子群H1中,第一個元素是e,第二個元素是 (12).同理可得其他子群元素之間的排列順序.置換群S3的每個子群內,各元素在三維空間中的旋轉關系如圖2 所示.在圖2中,對于子群H1,元素e繞X軸逆時針旋轉π 到達 (12)的位置,同樣地,元素 (12)繞X軸逆時針旋轉π 到達e的位置;同理可得其他子群元素之間位置的旋轉關系.從圖2 還可看出,置換群S3中每個子群元素之間通過置換群特有的對稱運算,形成了一個閉環(huán).

圖2 在每個子群中各個元素之間的旋轉關系圖Fig.2.Diagram of the rotation relationship between the elements in each subgroup.

3.2 構造行走搜索空間

本節(jié)將數(shù)據(jù)點集與置換群元素通過同構映射實現(xiàn)一一對應,從而構建量子行走的搜索空間.

步驟2構建置換群元素新集合

定義3.1 (數(shù)據(jù)集):由數(shù)據(jù)點d1,d2,···,dN生成的集合稱為數(shù)據(jù)集D,其中n表示量子態(tài)數(shù)量,N=2n.

定義3.2 (置換集):集合P{p(i,j,k)},i,j,k∈Z是由元素p(i,j,k)生成的,稱為置換集.其中元素p(i,j,k)通過旋轉一定角度變成元素p(i,j,k+1),并且集合P中的元素數(shù)量大于等于數(shù)據(jù)集D中的元素數(shù)量.

構建置換集的具體過程:由置換群的子群Hi衍生出子群族.對于固定的i,j,子群由p(i,j,k)元素生成.其中i=1,2,3,j∈Z.對于子群,j表示第j個子群Hi,k∈Z表示子群第k個元素.對于同一個i的值,只要j1/=j2,則.同理,只要k1/=k2,則p(i,j,k1)/=p(i,j,k2).

對于集合P和每個子群,即使包含的元素數(shù)與元素的性質相同,我們也規(guī)定,只要j是不同的,就被認為是不同的子群.此外,對于同一個元素(如e),只要子群不同,就被認為是不同的元素.并且每個子群的元素順序是逆時針方向.如對于子群,指定第一個元素為e,第二個元素為(12).對于的子群,元素e標記為p(1,j,1),(12)標記為p(1,j,2).集合P=p(i,j,k)中的每個元素都可以唯一地表示.元素在置換集中的分布如表1 所列.

表1 置換集合元素分布情況Table 1. Distribution of the elements in permutation set.

又因為

因此得到置換集中的元素數(shù)滿足N==2n,其中ji表示Hi的子群數(shù),ki表示元素數(shù).

步驟3建立置換集與數(shù)據(jù)集同構

假設映射F

pm(i,j,k)上標中的m無意義,只是為了方便區(qū)分說明,其中m=1,2,···,N.接下來證明,映射F是同構的.

證明令F(da)=pa(i,j,c),F(db)=pb(i,j,d).由于pm(i,j,d)的位置只對應于數(shù)據(jù)點dm,因此當a/=b時,p(i,j,c)/=p(i,j,d)?da/=db.證得F是單射.

又因為da/=db(a/=b),由元素的唯一性得到p(i,j,c)/=p(i,j,d),所以映射F是同構映射.

步驟4建立量子行走搜索空間

定義3.3 (搜索空間):空間W是W=D×P集合生成,其元素定義為w(dm,pm(i,j,k))∈W,被稱為搜索空間W.每個元素w(dm,pm(i,j,k))包含排列集中的數(shù)據(jù)點dm和相應的位置pm(i,j,k).

重新構造搜索函數(shù)Φ(w)=Φ(d)={0,1}.由于pm(i,j,k)只充當w(dm,pm(i,j,k))中的位置坐標,該函數(shù)對pm(i,j,k)不作用.這樣,通過函數(shù)Φ(w)=1得到wtar(dtar,ptar(i,j,k)),從而得到目標數(shù)據(jù)dtar.

定義3.4 (集合W-1):搜索空間W中定義了一個集合W-1={w-1(-1,p(i,j,k))}.該集合與W的集合相比,在相同位置p(i,j,k)上,集合W-1中的數(shù)據(jù)d=1.集合W與W-1的元素對應關系如圖3 所示.

圖3 集合W,W-1 和 Wλ 元素之間的對應關系Fig.3.Corresponding relationship between elements of the sets W,W-1 and Wλ .

集合W中的元素和集合W-1中的元素滿足下列關系:

其中Ω0是轉化函數(shù);φ0是矩陣并滿足

3.3 確定行走粒子數(shù)量

步驟5確定量子行走粒子數(shù)量

根據(jù)置換集合對應的子集數(shù)目,確定量子行走過程中粒子的數(shù)量.再根據(jù)前面的假設,得到子集數(shù)j1+j2+j3+j4.為了方便計算,選擇j1+j2+j3+j4的最大值 4×max{j1,j2,j3,j4}.在不失一般性的情況下,令j=max{j1,j2,j3,j4}.得到j1+j2+j3+j4≤4×max{j1,j2,j3,j4}=4×j.

因此,得到子集的數(shù)目是 4×j,即量子行走過程中粒子的數(shù)目是 4×j,其中 0≤j≤N/4.

3.4 行走過程

前文得出置換群S3的每個子群在空間中形成一個閉環(huán),并且置換群也與Zn的加法群同構.根據(jù)已經(jīng)提出的基于Cayley 圖的量子行走算法[34],可以得到置換群S3上的量子行走.

步驟6置換群上量子行走

將置換群看成是閉環(huán),則它的數(shù)學描述如下:假設G是一個有限群,S是該群的生成集合,置換群S3的元素和群G的元素之間存在一一對應關系.并且如果兩個節(jié)點g和g′滿足g′=gh,其中g ∈G和h∈S,則這兩個節(jié)點之間存在一條邊 (g,gh).將置換群的元素量子化,則置換群上的量子行走可以有如下定義:假設HS是硬幣算子所在的Hilbert空間,它是由態(tài)|h〉,h∈S生成的;HG是行走者的位置空間,它是由態(tài)|g〉,g∈G生成,則演化算符U=T(C?I)的硬幣算子C和轉移算子T分別定義為

其中,轉移算子的作用是

從(9)式可以得到,在置換群上進行量子行走時,以g為起點位置,當硬幣算符為h1時,行走者會由節(jié)點位置g轉移到相鄰節(jié)點gh1,其中gh1=g′.根據(jù)相鄰節(jié)點的關系,可以得到:

其中⊕是模 2加運算或模 3 加運算(在H3中).

對群元素進行傅里葉變換[35],算子的形式如下:

其中,χg為群的特征標,.

其中,轉移算符對傅里葉基態(tài)作用后的形式為

可以證明傅里葉基態(tài)下,轉移算符只改變基態(tài)的振幅.

最后,得到傅里葉基態(tài)下t時刻的振幅為,通過逆傅里葉變換求解離散時間的振幅:

3.4.1 構造Hilbert 空間

步驟7構造Hilbert 空間并檢測合理性

確定硬幣算符C,通過硬幣算符控制每一步行走.這一步的目標是保證量子行走的方向一致,不會往返.然后通過迭代算子U=T(C?I)?Θ,進而通過迭代的方法得出迭代算子的數(shù)值解.其中當算子Θ作用到元素w(dm,pm(i,j,k))時,可以得到數(shù)值δ={1,0}.根據(jù)硬幣算子C在本文中的作用,其被定義為

其中S={-1,1}.并且令:

根據(jù)構建的Hilbert 空間,檢驗轉移算子T、轉換算子Θ和迭代算子Ui是酉算子,其中i=1,2,3.推導結果如下:

因為轉換算子

得到

又因為

根據(jù)U=T(C?I)?Θ,得到:

因此通過上述驗證過程得出轉移算子T、轉換算子Θ和迭代算子Ui是酉算子.

3.4.2 執(zhí)行行走過程

步驟8分析量子行走路徑

Ui=ψt=1=|-1〉?|-i〉?|δ〉,

從而控制了在置換群中的量子行走方向.整個量子行走過程如圖4 所示.

圖4 量子行走的過程Fig.4.Process of quantum walk.

圖4 中黃色的圓點表示數(shù)據(jù)點,綠色的球體表示空間,標有數(shù)字 1,2,3 的藍色圓圈表示數(shù)據(jù)點pm(i,j,1),pm+1(i,j,2),pm+2(i,j,3),位置在某個子群中.紅色的虛線表示運動軌跡,從1→2→3都是利用反饋控制繼續(xù)前進的.當 3→1 時,運動軌跡就是黑色箭頭所表示的方向,通過反饋控制,發(fā)現(xiàn)此方向是被禁止的,于是設定硬幣算符為,隨機選擇行走方向(橙色箭頭),進行下一個子群中進行的量子行走.

3.5 儲存數(shù)值結果

步驟9存儲函數(shù)結果形成反饋控制

當Φ作用于元素w(dm,pm(i,j,k))時,得到函數(shù)的值δ=1或 0,并將數(shù)值存儲在量子態(tài)中.其中對于量子態(tài)|1〉,表示所對應的數(shù)據(jù)d正是目標數(shù)據(jù)dtar.為了形成含有數(shù)值結果的量子態(tài)集合,讓δ替換W-1集合中的-1.

更換過程如下:

其中,Ωi(Θi)表示轉換函數(shù),使得數(shù)據(jù)d=-1(d)成為δ,表示Hi中的一個元素,表示wmi在函數(shù)Φ的作用下的函數(shù)值,i=1,2,3,4.φi是矩陣并滿足

φi是矩陣并滿足

當函數(shù)Ωi(圖3 中簡稱為Ω)在進行數(shù)據(jù)更新時,存儲函數(shù)值的量子態(tài)會出現(xiàn)3 個數(shù)值,分別是|1〉,|0〉和|-1〉.為了方便說明,用量子態(tài)|λ〉表示,并且建立集合Wλ={(λ,p(i,j,k))}(W-1→Wλ),其中λ=0,1,-1.集合W,W-1和Wλ三者之間的關系變化如圖3 所示.

3.6 反饋結果判定方向

步驟10根據(jù)反饋結果判定后續(xù)方向

當量子行走進行到某步時,設此時的迭代次數(shù)是t.當?shù)螖?shù)是t+1 時,判斷量子行走過程是否繼續(xù)或者停止.判斷過程如下:

當行走到位置pm(i,j,k)時,判斷相應集合Wλ對應的數(shù)據(jù)λ,如果λ＜0,量子行走在此環(huán)(置換群)中繼續(xù)進行;如果λ≥0,量子行走將在此置換群中停止,設定硬幣算符為,隨機行走到其他置換群的位置.

4 復雜度分析

本文采取多粒子的量子行走,這樣時間復雜度取決于數(shù)據(jù)點的數(shù)量N和量子行走的數(shù)量j,即時間復雜度t=tin+tout最終取決于參數(shù)j和N.

其中,M表示目標點的數(shù)量.

分析時間復雜度tin,根據(jù)C=∑h|-1〉〈h|,h∈S可以得到每一步的硬幣算符是

C1=|-1〉〈1|,C2=|-1〉〈-1|,C3=|-1〉〈-1|,

其中,兩個正交向量|1〉和|-1〉可以用來表示硬幣的狀態(tài).|1〉表示順時針方向,|-1〉表示逆時針方向.

通過迭代方法,可以得到:

由于本文選擇的是置換群S3,因此完成一次置換群上行走次數(shù)為t≤3.又因為在在置換群中完成一次量子行走時,才進行一次硬幣算符為C*的量子行走.即完成一次更換需要的時間t=tin+tout≤3+1=4,因此完成所有行走過程時間復雜度為t=tin+tout≤4tout,得到t=4tout.所以只需要計算時間復雜度tout即可.

令

于是得到

令迭代算符U=T(C*?I)?Θ作用到量子態(tài)|χ〉,通過計算離散量子行走時刻連續(xù)疊加態(tài)的振幅得到時間復雜度tout和參數(shù)N的關系.

其中,當tout為偶數(shù)時:

當tout為奇數(shù)時:

θk滿足.

搜索目的是為了找遍空間中所有子群,即搜索到目標數(shù)據(jù)點的概率等于M/N.

得到:

由于參數(shù)j與N有關,若取.求解方程(28)可得

得出關于變量N的數(shù)值表達式tout(N)=,即得到關于變量N的數(shù)值表達式t(N)=.

5 數(shù)值仿真

將本文提出的量子行走搜索算法與Grover 搜索算法關于時間復雜度進行對比,設定參數(shù)M=10,N=200,得到圖5 所示的對比曲線.從圖5(a)得到量子行走搜索算法所用時間要比Grover 搜索算法所用時間短,即量子行走搜索算法的速率更高;從圖5(b)得到量子行走搜索算法是滿足原點條件和下確界條件的,即滿足當N=0時,t=0;N=1時,t=1.

圖5 兩種搜索算法時間按復雜度的對比Fig.5.Comparison of the time complexity of two search algorithms.

為了直觀地體現(xiàn)算法的高效性,下面用兩種不同算法進行舉例比較:一個采用標準的Grover-Long 算法[36],一個采用本文提出的量子行走搜索算法.N=64時,Grover-Long 算法需要=8次搜索,采用本文的方法,最多需要=4次搜索.

進而又對參數(shù)j對搜索的時間復雜度的影響進行了分析.選取了參數(shù)M=10,N=200 分別對參數(shù)j=1,j=2,j=3 三條曲線進行分析,得到圖6 所示曲線.從圖6(a)得到參數(shù)j與時間復雜度呈負相關,即參數(shù)j的取值越大,所用時間越短,搜索速率越快;從圖6(b)得到參數(shù)j不影響量子行走搜索算法,且滿足原點條件和下確界條件.

圖6 參數(shù)j 對搜索算法時間復雜度的影響Fig.6.Influence of parameter j on the time complexity of search algorithm.

最后分析了變量參數(shù)j,N與時間復雜度t的關系,得到數(shù)值仿真結果如表2 所列.從表中數(shù)據(jù)進一步得出,參數(shù)與時間復雜度不是呈負線性關系.

表2 數(shù)據(jù)仿真結果Table 2.Numerical simulation results.

6 總結