改進(jìn)的量子搜索算法在grove算法中的應(yīng)用

改進(jìn)的量子搜索算法在grove算法中的應(yīng)用

0經(jīng)典算法的應(yīng)用自20世紀(jì)90年代提出以來(lái)，該算法迅速發(fā)表，解決了許多困難的算法。從計(jì)算復(fù)雜性理論到通信保密技術(shù)，從基礎(chǔ)研究到日常生活的經(jīng)濟(jì)和人民生活，它具有廣闊的應(yīng)用前景。費(fèi)曼1權(quán)益的概率在量子系統(tǒng)中,每一個(gè)n位量子比特表示的量子態(tài)|ψ〉都可以看作是2|ψ〉可以由2其中,c將基態(tài)分為兩個(gè)部分———目標(biāo)態(tài)|α〉和非目標(biāo)態(tài)|β〉:其中,N=2則:則|ψ〉可以寫(xiě)成:如圖1所示,Grover的兩個(gè)反射把|ψ〉變換成:每次Grover迭代就相當(dāng)于增加2θ,從而測(cè)得β〉的概率增加。K次迭代后,2相位旋轉(zhuǎn)改進(jìn)算法到目前為止,圍繞如何提高Grover算法的成功概率,國(guó)內(nèi)外的學(xué)者進(jìn)行了很多有益的探索,先后提出了很多改進(jìn)措施,如基于π/2相位旋轉(zhuǎn)改進(jìn)算法,自適應(yīng)相位旋的Grover算法,基于固定相位旋轉(zhuǎn)的Grover算法2.1基于/2條件的個(gè)相移算子Grover算法中的兩次相位旋轉(zhuǎn)大小相同,都等于π。這樣相位旋轉(zhuǎn)的結(jié)果是:調(diào)用一次Grover迭代,使系統(tǒng)狀態(tài)相位增加將Grover算法的兩個(gè)相移算子寫(xiě)成外積形式,即將Grover算子作用于系統(tǒng)態(tài)|φ〉,整理的測(cè)量目標(biāo)態(tài)的概率為當(dāng)α=-β=π/2時(shí),式(10)簡(jiǎn)化為由式(11)有如下結(jié)論:(1)當(dāng)0<λ<1/3時(shí)態(tài),改進(jìn)算法的成功概率低于Grover算法成功概率。(2)當(dāng)λ=1/3時(shí),改進(jìn)算法的成功概率等于Grover算法的成功概率。(3)當(dāng)1/3<λ<1時(shí),改進(jìn)算法的成功概率高于基本Grover算法的成功概率。最低的成功概率為25/27。2.2基于自適應(yīng)相位旋轉(zhuǎn)的算法根據(jù)相關(guān)文獻(xiàn),Grover算法的搜索引擎可描述為旋轉(zhuǎn)相位α的確定直接關(guān)系到算法的搜索效率?；谧赃m應(yīng)相位旋轉(zhuǎn)改進(jìn)算法的基本思想是:α的大小根據(jù)搜索目標(biāo)數(shù)M和狀態(tài)總數(shù)N的比值λ=M/N來(lái)自適應(yīng)確定。(1)當(dāng)1/4≤λ≤1,時(shí),存在唯一確定的α=arccos((2λ-1)/2λ),只需一次Grover迭代,搜索成功概率P=1。2.3基于改進(jìn)算法的計(jì)算及搜索迭代次數(shù)埃及亞歷山大大學(xué)Younes于2007年4月提出了基于固定相位的旋轉(zhuǎn)的Grover算法由以上幾個(gè)改進(jìn)算法可知,這些改進(jìn)算法的出發(fā)點(diǎn)都是提高原始Grover算法的成功概率。經(jīng)過(guò)理論計(jì)算和模擬仿真,這些改進(jìn)算法的計(jì)算量相比于Grover算法沒(méi)有降低,甚至有所提高。在λ=M/N<0.001時(shí)Grover算法的搜索迭代次數(shù)仍然相當(dāng)可觀。如何在保證成功概率的基礎(chǔ)上,降低Grover算法的迭代次數(shù),是本文的出發(fā)點(diǎn)。3本文改進(jìn)了算法分析3.1gro經(jīng)營(yíng)算法目前提出的各種改進(jìn)算法,都是在如何進(jìn)一步提高算法的搜索成功概率上進(jìn)行研究探討,很少有學(xué)者對(duì)如何進(jìn)一步降低算法的計(jì)算量進(jìn)行研究。Grover算法是一種用于大規(guī)模數(shù)據(jù)庫(kù)搜索的算法。當(dāng)數(shù)據(jù)規(guī)模很大時(shí),Grover算法的計(jì)算量也是很大的,這時(shí)如何進(jìn)一步降低算法的復(fù)雜度?本文提出了一種改進(jìn)型算法,該算法能夠在保證搜索成功概率93%以上,將計(jì)算量降低到約為原來(lái)算法的1/3。3.2種標(biāo)態(tài)和非目標(biāo)態(tài)第1步同樣先應(yīng)用WalshHadamard變換作用在|000…0〉上,狀態(tài)初始化:將系統(tǒng)態(tài)分為目標(biāo)態(tài)和非目標(biāo)態(tài)兩部分,在定義歸一化狀態(tài)后,非目標(biāo)態(tài)為:目標(biāo)態(tài)為:從而初始態(tài)|ψ〉可以表示成:第2步對(duì)|ψ〉運(yùn)用Grover算子變換,記變換后的態(tài)為第3步參考U可以證明U第4步重復(fù)執(zhí)行算子O,U第5步測(cè)量,經(jīng)過(guò)上述迭代后,目標(biāo)態(tài)的概率幅達(dá)到最大,測(cè)量時(shí)最有可能獲得要搜索的目標(biāo)態(tài)。當(dāng)用O,U3.3基于改進(jìn)算法和groper算法的迭代次數(shù)比較在量子系統(tǒng)中,所有的變換都必須是幺正變換。改進(jìn)算法中的O算子顯然是幺正算子。對(duì)于U對(duì)于本改進(jìn)算法,初態(tài)|ψ〉旋轉(zhuǎn)改進(jìn)算法比Grover算法迭代次數(shù)節(jié)省了次。在[0,0.001]區(qū)間,改進(jìn)算法和Grover算法的成功概率比較如圖4所示。改進(jìn)算法和Grover算法的迭代次數(shù)比較如圖5所示。由以上的理論推導(dǎo)過(guò)程可知,改進(jìn)算法在[0,0.001]區(qū)間內(nèi),在保證搜索的成功概率在0.99以上的同時(shí),能夠降低迭代的次數(shù)至約等于基本Grover算法的1/3。4基于數(shù)據(jù)庫(kù)的方法利用本文改進(jìn)算法和Grover算法對(duì)一個(gè)數(shù)據(jù)庫(kù)(數(shù)據(jù)庫(kù)大小為2由表1可知,該改進(jìn)型算法在[0,0.001]區(qū)間上能明顯降低計(jì)算量,且能將搜索的成功概率保持在0.93以上。5基于改進(jìn)算法的groper算法仿真依照量子并行計(jì)算的優(yōu)勢(shì),在遍歷搜索問(wèn)題中運(yùn)用Grover算法可以大大減少搜索的運(yùn)算次數(shù)。本文對(duì)進(jìn)一步降低Grover算法進(jìn)行了探索,并提出了改進(jìn)算法