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

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

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