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

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

【相似文獻】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本文編號：2843158