發(fā)布時(shí)間：2020-10-16 10:54

　　 二十一世紀(jì)是一個(gè)快速發(fā)展的信息時(shí)代,電子計(jì)算機(jī)在社會(huì)發(fā)展中起到了至關(guān)重要的作用。當(dāng)前電子計(jì)算機(jī)發(fā)展已經(jīng)進(jìn)入到一個(gè)瓶頸期：高度的電路集成導(dǎo)致漏電荷和高發(fā)熱量問題；大量的NP問題在電子計(jì)算機(jī)上無法有效的求解；信息安全面臨著威脅等等。為了解決這些問題,我們需要尋找到新的計(jì)算機(jī)模型。在許多新型計(jì)算機(jī)模型中,量子計(jì)算機(jī)是最值得人們關(guān)注的一種。量子計(jì)算機(jī)是利用量子的物理特性進(jìn)行計(jì)算的計(jì)算機(jī)：量子計(jì)算機(jī)通過對(duì)量子疊加態(tài)的酉演化,可以實(shí)現(xiàn)高度的并行計(jì)算,從而對(duì)大量經(jīng)典算法進(jìn)行指數(shù)級(jí)的加速。著名的量子算法類型有：基于量子傅里葉變換的量子算法,基于無結(jié)構(gòu)數(shù)據(jù)庫搜索的量子算法,基于量子行走的量子算法等。其中量子行走是經(jīng)典隨機(jī)行走在量子計(jì)算中的對(duì)應(yīng),又分為離散量子行走和連續(xù)量子行走,本文重點(diǎn)研究離散量子行走。離散量子行走的研究方向從總體上可以分為四類：量子行走體系結(jié)構(gòu)研究；量子行走算法研究；量子行走通用性研究；量子行走的邏輯實(shí)現(xiàn)研究。本文將工作重心放在量子行走算法和量子邏輯實(shí)現(xiàn)的研究上,從如何優(yōu)化基于量子行走的搜索算法和實(shí)現(xiàn)各種數(shù)據(jù)結(jié)構(gòu)的量子行走算法著手,取得了一定的研究成果,具體如下：1)本文基于RSE范式的演化過程提出了新的R eed-Muller展開式算法。以往的量子可逆邏輯綜合算法必須要得到全部真值表信息,而本文提出的展開式算法可以將帶大量無關(guān)項(xiàng)的電路真值表快速轉(zhuǎn)化為Reed-Mulle r展開式。在對(duì)某個(gè)特定的量子電路進(jìn)行邏輯綜合時(shí),往往不能避免帶有無關(guān)項(xiàng),因此本文提出的量子可逆邏輯綜合算法更加具備實(shí)用性。2)本文提出了低開銷的量子比較器電路。在量子計(jì)算中,往往會(huì)需要進(jìn)行Oracle操作,判定目標(biāo)態(tài)的值,這個(gè)操作是量子計(jì)算中分析查詢復(fù)雜度的原子操作,所以O(shè)racle操作本身的效率需要慎重考慮。在所有的判定計(jì)算中,比較是最常用的一種,因此實(shí)現(xiàn)量子比較器非常重要。本文提出的算法巧妙的利用編碼電路來實(shí)現(xiàn)比較器,比以前提出的算法大大降低了電路的開銷。3)本文提出了基于NCP門庫的一維量子行走可逆邏輯電路實(shí)現(xiàn)方案,根據(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ǔ)上,本文給出了多維格上的量子行走可逆邏輯綜合電路和圖上量子行走可逆邏輯綜合電路。4)本文詳細(xì)討論分析了Grover搜索算法。針對(duì)Grover搜索算法在部分?jǐn)?shù)據(jù)庫上無法進(jìn)行搜索的問題,提出了改進(jìn)均值反演算子的方法,提高了Grover搜索算法在實(shí)際數(shù)據(jù)庫搜索問題中搜索到目標(biāo)態(tài)的效率。Grover搜索算法在運(yùn)行之前需要先獲得搜索目標(biāo)的數(shù)量,否則無法計(jì)算出迭代的次數(shù)。針對(duì)這一問題,本文提出了迭代次數(shù)自適應(yīng)的Grover搜索算法,在Oracle算子和均值反演算子之間嵌入了一個(gè)相位判斷的算子,通過判斷相位和的符號(hào)是否發(fā)生變化來決策是否停止算法的迭代。本文提出的算法效率比已有的改進(jìn)算法要好,只需要多一次Oracle查詢。并且本文提出的算法在較低的搜索空間情況下有效的改進(jìn)搜索概率。5)本文給出了量子行走模擬Grover搜索算法的可擴(kuò)展圖形,并且詳細(xì)分析了這種量子行走搜索算法的概率。為了求解多目標(biāo)搜索算法,本文基于超立方體上量子行走框架提出了新的硬幣算子,通過對(duì)目標(biāo)節(jié)點(diǎn)入邊的幅度擴(kuò)大,增加測(cè)量到目標(biāo)節(jié)點(diǎn)的概率,最終解決了多目標(biāo)搜索問題。利用對(duì)鄰居節(jié)點(diǎn)的二次判定,將搜索概率提高到接近于1。本文還提出將迭代次數(shù)自適應(yīng)算法使用到了量子行走搜索算法上,得到了迭代次數(shù)自適應(yīng)的量子行走多目標(biāo)搜索算法。在接下來的工作中要繼續(xù)研究離散量子行走和連續(xù)量子行走的性質(zhì),研究如何將相位控制技術(shù)運(yùn)用到更多的量子算法中,研究如何用可逆邏輯綜合技術(shù)邏輯實(shí)現(xiàn)其他的量子算法。
【學(xué)位單位】：東南大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位年份】：2015
【中圖分類】：O413;TP38
【文章目錄】：
摘要
Abstract
專業(yè)名詞中英文對(duì)照
第一章 緒論
    1.1 研究背景和研究意義
    1.2 國內(nèi)外研究現(xiàn)狀
        1.2.1 一維離散量子行走
        1.2.2 圖上離散量子行走
        1.2.3 離散量子行走算法
        1.2.4 量子行走的實(shí)現(xiàn)
        1.2.5 連續(xù)量子行走
    1.3 論文主要貢獻(xiàn)和內(nèi)容安排
第二章 量子行走理論基礎(chǔ)
    2.1 量子力學(xué)基本假設(shè)
        2.1.1 量子力學(xué)第一假設(shè)
        2.1.2 量子力學(xué)第二假設(shè)
        2.1.3 量子力學(xué)第三假設(shè)
        2.1.4 量子力學(xué)第四假設(shè)
    2.2 一些量子算法
        2.2.1 Deutsch算法
        2.2.2 相位估計(jì)算法
        2.2.3 Grover搜索算法
    2.3 量子行走簡(jiǎn)介
        2.3.1 格上量子行走
        2.3.2 超立方體上的量子行走
        2.3.3 SKW算法
    2.4 小結(jié)
第三章 量子行走的邏輯實(shí)現(xiàn)
    3.1 帶無關(guān)項(xiàng)的量子可逆邏輯綜合算法
        3.1.1 現(xiàn)有求解RM展開式算法簡(jiǎn)介
        3.1.2 根據(jù)RSE范式直接求解RM展開式
        3.1.3 全項(xiàng)的討論分析
        3.1.4 矩陣相乘算法與RSE范式求解算法比較
    3.2 格上量子行走量子可逆邏輯綜合
        3.2.1 H行走的可逆邏輯電路綜合
        3.2.2 多維格無偏量子行走的可逆邏輯電路綜合
    3.3 超立方體上量子行走的可逆邏輯綜合
    3.4 小結(jié)
第四章 迭代次數(shù)自適應(yīng)的多目標(biāo)搜索算法
    4.1 基于完全圖的量子行走搜索算法
    4.2 基于超立方體的多目標(biāo)量子行走搜索算法
        4.2.1 基于超立方體的新量子行走算子
        4.2.2 基于超立方體的量子行走搜索算法分析
    4.3 迭代次數(shù)自適應(yīng)的搜索算法
        4.3.1 迭代次數(shù)自適應(yīng)的Grover搜索算法
        4.3.2 迭代次數(shù)自適應(yīng)的量子行走搜索算法
    4.4 小結(jié)
第五章 總結(jié)與展望
    5.1 主要工作總結(jié)
    5.2 后續(xù)工作展望
附錄A 量子行走分析
    a.1 阿貝爾群上的量子行走
    a.2 環(huán)上行走的分析方法
    a.3 超立方體上行走分析方法
        a.3.1 超立方體的平均混合時(shí)間
        a.3.2 從某個(gè)點(diǎn)出發(fā)走了t步以后回到出發(fā)點(diǎn)的概率
        a.3.3 對(duì)超立方體混合時(shí)間的分析
    a.4 小結(jié)
附錄B 基于量子算法的數(shù)據(jù)庫搜索研究
    b.1 用于數(shù)據(jù)庫檢索的新均值反演算子的研究
    b.2 用于數(shù)據(jù)庫檢索的Oracle算子的可逆邏輯綜合研究
0的可逆邏輯電路'>        b.2.1 函數(shù)C₀的可逆邏輯電路
1的可逆邏輯電路'>        b.2.2 函數(shù)C₁的可逆邏輯電路
        b.2.3 可逆比較器可逆邏輯電路
        b.2.4 可逆比較器代價(jià)分析
    b.3 小結(jié)
參考文獻(xiàn)
致謝
攻讀博士學(xué)位期間的研究成果

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 黃帥;馬良;;多目標(biāo)0-1規(guī)劃的和聲搜索算法[J];數(shù)學(xué)的實(shí)踐與認(rèn)識(shí);2012年17期

2 雍龍泉;劉三陽;拓守恒;熊文濤;陳濤;;改進(jìn)的和聲搜索算法求絕對(duì)值方程[J];黑龍江大學(xué)自然科學(xué)學(xué)報(bào);2013年03期

3 王慧敏;賀興時(shí);盛孟龍;;一種改進(jìn)的和聲搜索算法[J];紡織高�；A(chǔ)科學(xué)學(xué)報(bào);2013年03期

4 馮遠(yuǎn)靜;俞立;馮祖仁;;蟻群協(xié)同模式搜索算法及其收斂性分析[J];控制理論與應(yīng)用;2007年06期

5 劉勇;馬良;;非線性極大極小問題的混沌萬有引力搜索算法求解[J];計(jì)算機(jī)應(yīng)用研究;2012年01期

6 金文梁;;量子搜索算法的多相位關(guān)系研究[J];計(jì)算機(jī)學(xué)報(bào);2012年07期

7 張偉;李華天;劉積仁;;線性可采納搜索算法的充要條件[J];控制與決策;1992年02期

8 李樹榮;陳國霞;雷陽;張強(qiáng);;一種多策略協(xié)同的加速和聲搜索算法[J];系統(tǒng)科學(xué)與數(shù)學(xué);2013年10期

9 余鵬;雋志才;;兩層應(yīng)急搶修系統(tǒng)選址問題的核搜索算法[J];計(jì)算機(jī)應(yīng)用研究;2013年11期

10 歐陽海濱;高立群;鄒德旋;孔祥勇;;和聲搜索算法探索能力研究及其修正[J];控制理論與應(yīng)用;2014年01期

相關(guān)博士學(xué)位論文 前9條

1 朱皖寧;離散量子行走研究[D];東南大學(xué);2015年

2 孫杰;基于絕熱演化的量子搜索算法研究[D];華中科技大學(xué);2013年

3 張映玉;絕熱量子搜索算法研究[D];華中科技大學(xué);2011年

4 閻興頔;組搜索算法研究及其應(yīng)用[D];華東理工大學(xué);2013年

5 常虹;改進(jìn)和聲搜索算法及其在低碳能源預(yù)測(cè)中的應(yīng)用[D];華東理工大學(xué);2013年

6 張欣;基于序列聯(lián)配的高效可變剪接模式搜索算法和軟件[D];上海交通大學(xué);2006年

7 吳昊;云計(jì)算環(huán)境下智能優(yōu)化算法及其在SaaS中的應(yīng)用研究[D];合肥工業(yè)大學(xué);2013年

8 王洪福;Grover量子搜索算法理論研究[D];哈爾濱工業(yè)大學(xué);2010年

9 金文梁;三維復(fù)子空間中的量子搜索和多相位匹配研究[D];西南交通大學(xué);2011年

相關(guān)碩士學(xué)位論文 前10條

1 劉曉青;高速永磁無刷直流電機(jī)的設(shè)計(jì)及優(yōu)化[D];南京信息工程大學(xué);2015年

2 許譯方;圖的極大鄰集搜索算法序列及序列終點(diǎn)的性質(zhì)研究[D];蘭州大學(xué);2015年

3 朱航;基于改進(jìn)和聲搜索算法的車間作業(yè)調(diào)度問題研究[D];南京理工大學(xué);2015年

4 郝雅雄;基于趨向變化的和聲搜索算法及其在電力負(fù)荷分配中的應(yīng)用研究[D];蘭州大學(xué);2015年

5 張小利;無導(dǎo)數(shù)最優(yōu)化中的模式搜索算法研究[D];河北大學(xué);2015年

6 顏騰威;求解VRP問題的改進(jìn)和聲搜索算法的研究[D];浙江師范大學(xué);2015年

7 高濤;面向眾核體系結(jié)構(gòu)的寬度優(yōu)先搜索算法研究[D];國防科學(xué)技術(shù)大學(xué);2013年

8 李娜;多目標(biāo)布谷鳥搜索算法及其應(yīng)用研究[D];西安工程大學(xué);2015年

9 周詩杰;基于重疊社團(tuán)劃分的道路網(wǎng)絡(luò)路由搜索算法的研究[D];浙江工業(yè)大學(xué);2015年

10 沈冬梅;基于改進(jìn)引力搜索算法的電力系統(tǒng)機(jī)組組合問題的研究[D];東華大學(xué);2016年

本文編號(hào)：2843158