基于置換群的多粒子環(huán)上量子行走的反饋搜索算法*

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

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

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

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

1 引言

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

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

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

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

2 相關(guān)工作

2.1 置換群S3

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

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

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

2.2 環(huán)上行走

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

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

3 量子行走搜索算法

3.1 初始化階段

步驟1應(yīng)用置換群的對(duì)稱運(yùn)算

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

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

圖1 置換群 S3 中每個(gè)元素的旋轉(zhuǎn)方位圖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)}.

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

圖2 在每個(gè)子群中各個(gè)元素之間的旋轉(zhuǎn)關(guān)系圖Fig.2.Diagram of the rotation relationship between the elements in each subgroup.

3.2 構(gòu)造行走搜索空間

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

步驟2構(gòu)建置換群元素新集合

定義3.1 (數(shù)據(jù)集):由數(shù)據(jù)點(diǎn)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)通過旋轉(zhuǎn)一定角度變成元素p(i,j,k+1),并且集合P中的元素?cái)?shù)量大于等于數(shù)據(jù)集D中的元素?cái)?shù)量.

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

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

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

又因?yàn)?/p>

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

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

假設(shè)映射F

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

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

又因?yàn)閐a/=db(a/=b),由元素的唯一性得到p(i,j,c)/=p(i,j,d),所以映射F是同構(gòu)映射.

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

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

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

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

圖3 集合W,W-1 和 Wλ 元素之間的對(duì)應(yīng)關(guān)系Fig.3.Corresponding relationship between elements of the sets W,W-1 and Wλ .

集合W中的元素和集合W-1中的元素滿足下列關(guān)系:

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

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

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

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

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

3.4 行走過程

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

步驟6置換群上量子行走

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

其中,轉(zhuǎn)移算子的作用是

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

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

對(duì)群元素進(jìn)行傅里葉變換[35],算子的形式如下:

其中,χg為群的特征標(biāo),.

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

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

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

3.4.1 構(gòu)造Hilbert 空間

步驟7構(gòu)造Hilbert 空間并檢測(cè)合理性

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

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

根據(jù)構(gòu)建的Hilbert 空間,檢驗(yàn)轉(zhuǎn)移算子T、轉(zhuǎn)換算子Θ和迭代算子Ui是酉算子,其中i=1,2,3.推導(dǎo)結(jié)果如下:

因?yàn)檗D(zhuǎn)換算子

得到

又因?yàn)?/p>

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

因此通過上述驗(yàn)證過程得出轉(zhuǎn)移算子T、轉(zhuǎn)換算子Θ和迭代算子Ui是酉算子.

3.4.2 執(zhí)行行走過程

步驟8分析量子行走路徑

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

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

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

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

3.5 儲(chǔ)存數(shù)值結(jié)果

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

當(dāng)Φ作用于元素w(dm,pm(i,j,k))時(shí),得到函數(shù)的值δ=1或 0,并將數(shù)值存儲(chǔ)在量子態(tài)中.其中對(duì)于量子態(tài)|1〉,表示所對(duì)應(yīng)的數(shù)據(jù)d正是目標(biāo)數(shù)據(jù)dtar.為了形成含有數(shù)值結(jié)果的量子態(tài)集合,讓?duì)奶鎿QW-1集合中的-1.

更換過程如下:

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

φi是矩陣并滿足

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

3.6 反饋結(jié)果判定方向

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

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

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

4 復(fù)雜度分析

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

其中,M表示目標(biāo)點(diǎn)的數(shù)量.

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

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

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

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

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

令

于是得到

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

其中,當(dāng)tout為偶數(shù)時(shí):

當(dāng)tout為奇數(shù)時(shí):

θk滿足.

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

得到:

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

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

5 數(shù)值仿真

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

圖5 兩種搜索算法時(shí)間按復(fù)雜度的對(duì)比Fig.5.Comparison of the time complexity of two search algorithms.

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

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

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

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

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

6 總結(jié)