離散量子行走研究.pdf

1、二十一世紀(jì)是一個快速發(fā)展的信息時代，電子計算機在社會發(fā)展中起到了至關(guān)重要的作用。當(dāng)前電子計算機發(fā)展已經(jīng)進入到一個瓶頸期:高度的電路集成導(dǎo)致漏電荷和高發(fā)熱量問題;大量的NP問題在電子計算機上無法有效的求解;信息安全面臨著威脅等等。為了解決這些問題，我們需要尋找到新的計算機模型。在許多新型計算機模型中，量子計算機是最值得人們關(guān)注的一種。
　　量子計算機是利用量子的物理特性進行計算的計算機:量子計算機通過對量子疊加態(tài)的酉演化，可以實現(xiàn)高

2、度的并行計算，從而對大量經(jīng)典算法進行指數(shù)級的加速。著名的量子算法類型有:基于量子傅里葉變換的量子算法，基于無結(jié)構(gòu)數(shù)據(jù)庫搜索的量子算法，基于量子行走的量子算法等。其中量子行走是經(jīng)典隨機行走在量子計算中的對應(yīng)，又分為離散量子行走和連續(xù)量子行走，本文重點研究離散量子行走。離散量子行走的研究方向從總體上可以分為四類:量子行走體系結(jié)構(gòu)研究;量子行走算法研究;量子行走通用性研究;量子行走的邏輯實現(xiàn)研究。本文將工作重心放在量子行走算法和量子邏輯實現(xiàn)的

3、研究上，從如何優(yōu)化基于量子行走的搜索算法和實現(xiàn)各種數(shù)據(jù)結(jié)構(gòu)的量子行走算法著手，取得了一定的研究成果，具體如下:
　　1)本文基于RSE范式的演化過程提出了新的Reed-Muller展開式算法。以往的量子可逆邏輯綜合算法必須要得到全部真值表信息，而本文提出的展開式算法可以將帶大量無關(guān)項的電路真值表快速轉(zhuǎn)化為Reed-Muller展開式。在對某個特定的量子電路進行邏輯綜合時，往往不能避免帶有無關(guān)項，因此本文提出的量子可逆邏輯綜合算法更

4、加具備實用性。
　　2)本文提出了低開銷的量子比較器電路。在量子計算中，往往會需要進行Oracle操作，判定目標(biāo)態(tài)的值，這個操作是量子計算中分析查詢復(fù)雜度的原子操作，所以O(shè)racle操作本身的效率需要慎重考慮。在所有的判定計算中，比較是最常用的一種，因此實現(xiàn)量子比較器非常重要。本文提出的算法巧妙的利用編碼電路來實現(xiàn)比較器，比以前提出的算法大大降低了電路的開銷。
　　3)本文提出了基于NCP門庫的一維量子行走可逆邏輯電路實現(xiàn)方

5、案，根據(jù)一維量子行走的特點，將電路劃分為投擲量子硬幣和根據(jù)量子硬幣進行隨機行走的S操作兩個部分;詳細(xì)分析了S操作，并對S操作進行了數(shù)學(xué)建模，巧妙的利用可控加減電路實現(xiàn)了S操作。本文提出的電路描述了一維量子行走的最基本操作，并且將其模塊化，使得一維量子行走算法從理論到實現(xiàn)前進了一步;利用原始遞歸給出了一維量子行走中每一步的數(shù)學(xué)表達式，便于以后更加深入的對一維量子行走算法的研究。在此基礎(chǔ)上，本文給出了多維格上的量子行走可逆邏輯綜合電路和圖上

6、量子行走可逆邏輯綜合電路。
　　4)本文詳細(xì)討論分析了Grover搜索算法。針對Grover搜索算法在部分?jǐn)?shù)據(jù)庫上無法進行搜索的問題，提出了改進均值反演算子的方法，提高了Grover搜索算法在實際數(shù)據(jù)庫搜索問題中搜索到目標(biāo)態(tài)的效率。Grover搜索算法在運行之前需要先獲得搜索目標(biāo)的數(shù)量，否則無法計算出迭代的次數(shù)。針對這一問題，本文提出了迭代次數(shù)自適應(yīng)的Grover搜索算法，在Oracle算子和均值反演算子之間嵌入了一個相位判斷的算

7、子，通過判斷相位和的符號是否發(fā)生變化來決策是否停止算法的迭代。本文提出的算法效率比已有的改進算法要好，只需要多一次Oracle查詢。并且本文提出的算法在較低的搜索空間情況下有效的改進搜索概率。
　　5)本文給出了量子行走模擬Grover搜索算法的可擴展圖形，并且詳細(xì)分析了這種量子行走搜索算法的概率。為了求解多目標(biāo)搜索算法，本文基于超立方體上量子行走框架提出了新的硬幣算子，通過對目標(biāo)節(jié)點入邊的幅度擴大，增加測量到目標(biāo)節(jié)點的概率，最終