離散量子行走研究.pdf

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

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

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

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

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

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

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