本文關(guān)鍵詞：高概率量子隨機(jī)行走搜索算法研究，由筆耕文化傳播整理發(fā)布。

【摘要】：量子信息技術(shù)的迅猛發(fā)展對(duì)現(xiàn)代密碼體制產(chǎn)生了巨大沖擊,量子搜索算法以其強(qiáng)大的計(jì)算能力成為量子計(jì)算中的重要研究方向。但量子計(jì)算算法在實(shí)現(xiàn)過程中產(chǎn)生的誤差不可避免,從而影響量子計(jì)算算法的有效性,并且搜索空間也可能會(huì)含有多個(gè)目標(biāo)解。因此,研究誤差對(duì)量子搜索算法的影響和多目標(biāo)解條件下的量子搜索算法有重要的理論意義和實(shí)際應(yīng)用價(jià)值。量子隨機(jī)行走是近年來量子計(jì)算算法中研究的熱點(diǎn)問題之一,其主要原因是：基于量子隨機(jī)行走構(gòu)造的搜索算法,不僅能解決無序的數(shù)據(jù)庫搜索問題,還能解決Grover算法不能有效解決的問題(如空間搜索,元素區(qū)分),因此,基于量子隨機(jī)行走的搜索算法引起了廣泛關(guān)注。2003年,Shenvi, Kempe和Whaley共同提出了一個(gè)基于超立方體上量子隨機(jī)行走的搜索算法,簡稱SKW算法。2008年,Potocek又在SKW算法的基礎(chǔ)上提出了高概率SKW算法。本文主要對(duì)高概率SKW算法進(jìn)行了深入研究,主要研究成果如下：1.基于Grover擴(kuò)散算子的高概率SKW算法系統(tǒng)相位誤差的研究。通過對(duì)高概率SKW算法幾何描述,建立了含有相位誤差的算法模型；對(duì)給定規(guī)模的數(shù)據(jù)庫,刻畫了算法成功率、迭代次數(shù)和相位誤差之間的關(guān)系；對(duì)給定大小的相位誤差,給出了算法所能達(dá)到的最大成功率、所需迭代次數(shù)以及對(duì)誤差的容忍度；分析和數(shù)值模擬表明,對(duì)相同大小的相位誤差,高概率SKW算法的成功率比Grover算法的成功率變化更小,表明高概率SKW算法對(duì)誤差的魯棒性更強(qiáng)。2.高概率SKW算法中的退相干研究。超立方體上鏈接會(huì)隨機(jī)斷裂,從而在高概率SKW算法運(yùn)行時(shí)產(chǎn)生退相干,通過引入包含斷裂鏈接的轉(zhuǎn)移算子,提出了含有退相干的高概率SKW算法；通過數(shù)值模擬和采樣分析,對(duì)給定的退相干率,給出了算法所能達(dá)到的最大成功率和所需迭代次數(shù)；針對(duì)退相干會(huì)減少算法迭代次數(shù)但也會(huì)降低算法最大成功率,給出算法存在退相干時(shí)的概率復(fù)雜度(迭代次數(shù)/概率),并得到退相干率的兩個(gè)臨界值,當(dāng)退相干率在它們之間變化時(shí),刻畫了退相干率與概率復(fù)雜度之間的關(guān)系。3.多目標(biāo)解條件下的高概率SKW算法研究。通過數(shù)學(xué)歸納法,給出了多解條件下量子隨機(jī)行走通用搜索算法的計(jì)算復(fù)雜度求解方法,解決了量子隨機(jī)行走通用搜索算法的多解搜索問題；通過證明多解條件下SKW算法就是超立方體上的量子隨機(jī)行走通用搜索算法,給出了多目標(biāo)解條件下高概率SKW算法的計(jì)算復(fù)雜度；通過數(shù)值模擬和分析,得到關(guān)于目標(biāo)解占搜索空間比例的一個(gè)臨界值,當(dāng)目標(biāo)解的比例不大于這個(gè)臨界值,刻畫了高概率SKW算法的成功率與迭代次數(shù)、解的比例之間的關(guān)系。
【關(guān)鍵詞】：量子搜索算法 量子隨機(jī)行走 相位誤差 魯棒性 退相干 多目標(biāo)解 通用搜索算法
【學(xué)位授予單位】：解放軍信息工程大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：O413;TP391.3
【目錄】：

• 摘要4-5
• Abstract5-9
• 第一章 引言9-13
• 第二章 基礎(chǔ)知識(shí)13-23
• 2.1 量子計(jì)算基本概念13-15
• 2.1.1 量子比特13
• 2.1.2 線性算子13-14
• 2.1.3 張量積14
• 2.1.4 量子并行性14-15
• 2.2 隨機(jī)行走15-20
• 2.2.1 經(jīng)典隨機(jī)行走15-17
• 2.2.2 量子隨機(jī)行走17-20
• 2.3 超立方體上量子隨機(jī)行走搜索算法20-22
• 2.3.1 SKW算法20-21
• 2.3.2 高概率SKW算法21-22
• 2.4 本章小結(jié)22-23
• 第三章 高概率量子隨機(jī)行走搜索算法中的系統(tǒng)相位誤差研究23-37
• 3.1 高概率SKW算法的幾何描述23-27
• 3.2 含有相位誤差的算法模型27-30
• 3.2.1 模型建立27-29
• 3.2.2 算法分析29-30
• 3.3 數(shù)值模擬30-35
• 3.4 本章小結(jié)35-37
• 第四章 高概率量子隨機(jī)行走搜索算法中的退相干研究37-47
• 4.1 隨機(jī)鏈接斷裂退相干37-39
• 4.2 產(chǎn)生退相干的高概率SKW算法39-41
• 4.2.1 算法描述39
• 4.2.2 算法特性39-41
• 4.3 數(shù)值模擬及分析41-46
• 4.4 本章小結(jié)46-47
• 第五章 多目標(biāo)解條件下高概率量子隨機(jī)行走搜索算法47-61
• 5.1 量子隨機(jī)行走通用搜索算法47-49
• 5.2 多解條件下量子隨機(jī)行走通用搜索算法49-52
• 5.3 多解條件下高概率SKW算法分析52-55
• 5.4 數(shù)值模擬55-58
• 5.5 本章小結(jié)58-61
• 第六章 總結(jié)與展望61-62
• 致謝62-63
• 參考文獻(xiàn)63-67
• 作者簡歷67

【參考文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前6條

1 Fada Li;Wansu Bao;Xiangqun Fu;;A quantum algorithm for the dihedral hidden subgroup problem based on lattice basis reduction algorithm[J];Chinese Science Bulletin;2014年21期

2 LIU Yang;;Deleting a marked state in quantum database in a duality computing mode[J];Chinese Science Bulletin;2013年24期

3 ;t-bit semiclassical quantum Fourier transform[J];Chinese Science Bulletin;2012年01期

4 ;A quantum algorithm for searching a target solution of fixed weight[J];Chinese Science Bulletin;2011年06期

5 ;An N/4 fixed-point duality quantum search algorithm[J];Science China(Physics,Mechanics & Astronomy);2010年09期

6 ;Quantum mechanical meet-in-the-middle search algorithm for Triple-DES[J];Chinese Science Bulletin;2010年03期

  本文關(guān)鍵詞：高概率量子隨機(jī)行走搜索算法研究，由筆耕文化傳播整理發(fā)布。

，

本文編號(hào)：304024