離散量子行走搜索算法的研究.pdf

1、1993年，Aharonov提出了量子隨機(jī)行走的概念，相比于經(jīng)典隨機(jī)行走，量子隨機(jī)行走具有更快的擴(kuò)散速度。2003年，第一個(gè)量子隨機(jī)行走搜索算法，即SKW算法，從理論上證實(shí)了量子隨機(jī)行走相對(duì)于經(jīng)典算法的優(yōu)越性，并探索了量子隨機(jī)行走算法新的應(yīng)用領(lǐng)域。近年來，若干研究者致力于量子隨機(jī)行走的行走結(jié)構(gòu)和算法的研究。
　　本文提出使用散射量子行走搜索完全圖上的結(jié)構(gòu)異常。如果在N個(gè)頂點(diǎn)的完全圖中加入一個(gè)懸掛點(diǎn)，這將破壞完全圖的對(duì)稱性。算法首先

2、給出了行走酉算子的定義，利用完全圖的對(duì)稱性，將行走空間坍縮到低維不變子空間，并確定了酉算子在該子空間中作用的形式。為了分析算法演化過程，利用微擾理論求解算子的特征值和特征向量，將算法初態(tài)用特征向量表示，并計(jì)算行走后的終態(tài)，以此分析算法的時(shí)間復(fù)雜度和成功概率。算法分析及Matlab仿真結(jié)果均表明，利用散射量子行走可以在O(√N(yùn))步內(nèi)以接近于1的概率找到異常位置，而經(jīng)典算法中使用鄰接矩陣查找該異常的時(shí)間復(fù)雜度為O(N)。因此散射量子行走搜索