基于離散時間量子行走模型的搜索算法研究.pdf

1、作為設計隨機算法的一個有力的數(shù)學工具，經(jīng)典隨機行走為因式分解、k-SAT、圖同構(gòu)等問題提供了一系列最廣為人知的算法。量子行走提供了加速經(jīng)典隨機行走的可能性，近年來設計基于量子行走的搜索算法成為量子計算領域的研究熱點。研究的核心問題之一是搜索算法在何種圖結(jié)構(gòu)上的行走能實現(xiàn)量子加速。算法的分析是其中的難點，量子迭代算法分析的關鍵是求得演化算子的特征譜，從而確定算法的演化過程。早期成功的搜索算法普遍采用Grover算子作為算法的演化算子，當圖

2、滿足某種性質(zhì)時，如正則性、對稱性，將算法的演化空間限定在坍縮圖對應的子空間中加以分析。抽象搜索算法和算子擾動理論是基于離散時間量子行走搜索算法的兩種主要分析手段。本文在以下方面做出了探索:
　　(1)搜索算法在商圖上的演化算子的計算是搜索算法分析的一個重要步驟。演化算子包含移位算子和硬幣算子。以超立方體為例，構(gòu)造出Grover硬幣算子在商圖上對應的矩陣形式，并給出了其正確性證明。由于商圖上的移位算子可由原圖上的移位算子直接導出，從

3、而確定了使用Grover算子作為硬幣的量子行走在商圖上的演化算子。超立方體商圖上的硬幣算子形式可以推廣至其他圖上，如完全圖、強正則圖等。
　　(2)圖上結(jié)構(gòu)發(fā)生改變稱之為結(jié)構(gòu)異常。完全圖有外接圖稱之為外部結(jié)構(gòu)異常;內(nèi)部結(jié)構(gòu)發(fā)生改變成為內(nèi)部結(jié)構(gòu)異常?；谏⑸淞孔有凶咴O計搜索算法定位完全圖上的結(jié)構(gòu)異常。利用完全圖的對稱性，將算法的搜索空間限定在一個低維的坍縮圖空間。利用算子擾動理論證明只要完全圖和外接圖的連接度足夠小，則完全圖外接任意

4、圖均可以在O（√N）時間步內(nèi)解決。用類似的方法證明完全圖缺失邊和有多余自環(huán)邊時搜索算法也有二次加速。
　　(3)基于散射量子行走設計強正則圖上的搜索算法研究圖的對稱性對搜索算法性能的影響。對于較大的N強正則圖不具有全局對稱性，但可以利用局部對稱性將搜索空間限制在對應坍縮圖的低維子空間中。當k與N同階時，利用Cottrell提出的基本配對定理量化算法的性能;當k與√N同階時不滿足該定理，使用算子擾動理論分析。結(jié)果表明，在兩類強正則圖