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

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

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

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

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