【摘要】：絕熱量子計(jì)算是一種基于絕熱定理的全新量子計(jì)算模型,與量子線路模型相比,具有操控相對比較簡單、天然抗噪聲的優(yōu)點(diǎn),并且已被證明與線路模型等價,是未來通用量子計(jì)算的備選方案之一。而密鑰搜索則是密碼學(xué)最基本的攻擊手段之一,因此,利用絕熱計(jì)算模型的優(yōu)點(diǎn)開展絕熱量子搜索算法的研究,意義重大。本文針對絕熱量子搜索算法,從算法分析、算法加速、量子資源三個方面進(jìn)行了系統(tǒng)的研究,主要研究成果如下:一、在算法分析方面,研究了局域絕熱量子搜索算法中成功率與演化時間的定量關(guān)系,為絕熱量子搜索算法實(shí)現(xiàn)時演化時間的選擇提供指導(dǎo)。局域絕熱量子搜索算法中成功率與演化時間的定量關(guān)系研究。在實(shí)際演化過程中,絕熱算法必須在有限時間內(nèi)運(yùn)行完畢,從而可能發(fā)生能級躍遷,如何求局域絕熱量子搜索算法的成功率?目前沒有解析的解,而成功率與演化時間的定量關(guān)系可以為算法實(shí)現(xiàn)時最優(yōu)演化時間的選擇提供指導(dǎo)。我們在等價的二能級系統(tǒng)中分析絕熱量子搜索算法的量子動力學(xué),通過簡化含時薛定諤方程,得出了求解成功率的微分方程組;利用這個微分方程組,數(shù)值地給出了局域絕熱量子搜索算法中成功率與演化時間的解析表達(dá)式,該表達(dá)式給出了成功率增速變緩的臨界時間點(diǎn)并間接驗(yàn)證了局域絕熱搜索算法最優(yōu)的時間復(fù)雜度為O(N~（1/2）)。在密鑰搜索問題中,當(dāng)給定成功率時,可以依據(jù)我們給出的表達(dá)式精確的控制最優(yōu)演化時間。二、在算法加速方面,分別從絕熱捷徑技術(shù)和絕熱量子搜索算法一般化兩個方向,克服絕熱量子搜索算法要求系統(tǒng)緩慢演化的的弱點(diǎn),并從能量的角度定量分析了算法取得加速的代價。1、局域絕熱量子搜索算法中的無躍遷量子驅(qū)動研究。局域絕熱量子搜索算法的時間復(fù)雜度已經(jīng)為O(N~（1/2）),而無躍遷量子驅(qū)動可以通過抑制原系統(tǒng)的能級躍遷來加速演化過程,兩者相結(jié)合會不會得到更優(yōu)量級的時間復(fù)雜度?我們將無躍遷量子驅(qū)動方法應(yīng)用于局域絕熱量子搜索算法,給出了局域絕熱量子搜索算法中應(yīng)添加的驅(qū)動哈密頓量,理論上證明了在系統(tǒng)能量可以任意大的前提下,當(dāng)添加無躍遷量子驅(qū)動時,對于任意長的演化時間,算法成功率都可以為1;我們對加速原因和實(shí)現(xiàn)難度進(jìn)行了分析,指出算法獲得加速的原因是添加驅(qū)動項(xiàng)后算法基態(tài)與第一激發(fā)態(tài)之間的瞬時能隙在演化過程中增大到了O(N~（1/2）)的規(guī)模,在實(shí)際中,系統(tǒng)能量不可能任意大,所以算法的演化時間不能任意小,但是無躍遷量子驅(qū)動仍然對算法有很好的加速作用并在離子阱系統(tǒng)上得到了演示驗(yàn)證。2、絕熱量子搜索算法一般化及其加速研究。一般化絕熱量子搜索算法的演化可以是非絕熱的并且可以選擇任意的插值函數(shù),判斷算法是否有效的依據(jù)是末了時刻算法的成功率是否符合要求,但是在一般化的絕熱搜索算法中,成功率難以解析給出。我們利用無躍遷量子驅(qū)動來構(gòu)造具有解析成功率的一般化絕熱量子搜索算法,給出了更一般的驅(qū)動哈密頓量形式;求出成功率的解析表達(dá)式并給出了一個確保成功率為1的充分條件,在能量可以任意大的前提下,當(dāng)插值函數(shù)滿足這個條件時,算法可以在任意演化時間下成功率為1,對于不滿足條件的插值函數(shù),也可以根據(jù)成功率公式選擇更優(yōu)的參數(shù)。該工作將無躍遷驅(qū)動的應(yīng)用拓展到了一般化的絕熱搜索算法,事實(shí)上,對于現(xiàn)有基于哈密頓量演化的量子搜索算法,都可以用給出的方法進(jìn)行加速。3、絕熱量子搜索算法中時間與能量的定量關(guān)系研究。目前,絕熱量子搜索算法的復(fù)雜度一般是指算法的演化時間,而Das算法和絕熱捷徑都能以常數(shù)的演化時間完成搜索,其代價是要在演化過程中增加能量,因此,在絕熱量子搜索算法中,衡量算法的復(fù)雜度必須綜合考慮時間和能量。我們提出了絕熱量子搜索算法中定量刻畫能量復(fù)雜度的方法;在給出的方法下,計(jì)算出了不同絕熱量子搜索算法的能量復(fù)雜度并證明綜合考慮時間復(fù)雜度和能量復(fù)雜度時,絕熱量子搜索算法的復(fù)雜度至少為O(N~（1/2）)量級;此外,定量分析了Das算法中時間和能量的關(guān)系,在實(shí)驗(yàn)允許的前提下,可以根據(jù)時間和能量的定量關(guān)系選擇參數(shù)使得演化時間最短。值得一提的是,本文提出的能量復(fù)雜度刻畫方法也適用于其它的絕熱算法。三、在量子資源方面,研究了相干在絕熱量子搜索算法中的作用,定量分析了相干對算法成功率和算法效率的影響。絕熱量子搜索算法中相干的作用研究。研究相干在量子算法中的作用對分析量子加速的原理具有重要意義,我們利用相干的聯(lián)合熵量化方法系統(tǒng)地分析了相干在絕熱量子搜索算法中的作用。在理想和非理想情況下,定量的分析了相干隨著時間的變化并給出了相干與成功率的解析關(guān)系式;對比研究了全局絕熱量子搜索算法、局域絕熱量子搜索算法、Das算法中相干的變化,指出要想實(shí)現(xiàn)常數(shù)演化時間的搜索,系統(tǒng)的相干必須指數(shù)的減少;更重要的是,以絕熱捷徑為例說明了可以通過合適的方法加快系統(tǒng)相干的消耗來提高絕熱量子搜索算法的效率,這一思想可以推廣到其它的絕熱算法,為提升絕熱算法的效率找到了一個新的方向。
【圖文】：

第 1 頁圖 1.1 單個芯片中晶體管數(shù)目增長趨勢遵循摩爾定律子計(jì)算是一種基于量子效應(yīng)的新型計(jì)算方式[1]，其基本原理是：以量子比特和存儲的基本單元，通過大量量子比特的受控演化來完成計(jì)算任務(wù)。相比經(jīng)子計(jì)算機(jī)在信息編碼載體、邏輯運(yùn)算基礎(chǔ)和運(yùn)行方式上都發(fā)生了顛覆性的改變曼首次提出了量子計(jì)算機(jī)的概念[2]，1985 年，Deutsch 基于經(jīng)典圖靈機(jī)模型靈機(jī)模型[3]。1992 年，Deutsch 和 Josza 一起提出了 Deutsch-Josza 算法[4]，在

1arctan 1 2 1 arctan 12 1Nt N s NN arctan 為反正切函數(shù)。令 s 1，， 得到1arctan 11NT NN arctan 11NN ，演化就是絕熱的并且成功率大于等于21- 。演化時間T 的關(guān)系，包括1arctan 11NT NN ，所以我們 tan 2 / 1 arctan 1 12 1t T N Ns tN 后我們稱之為局域演化路徑。顯然，它滿足邊界條件：當(dāng) t 當(dāng) t T時， s 1且 pH s H。局域演化路徑與全局演化路徑
【學(xué)位授予單位】：戰(zhàn)略支援部隊(duì)信息工程大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2018
【分類號】：O413;TP301.6

【相似文獻(xiàn)】

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

1 李學(xué)貴;許少華;李娜;張強(qiáng);;基于渦流搜索算法的支持向量機(jī)分類模型[J];化工自動化及儀表;2016年12期

2 王保民;;基于和聲搜索算法的電力系統(tǒng)經(jīng)濟(jì)調(diào)度[J];科技資訊;2014年06期

3 杜永峰;李萬潤;李慧;唐少玉;;和聲搜索算法在結(jié)構(gòu)有限元模型修正中的應(yīng)用[J];蘭州理工大學(xué)學(xué)報(bào);2013年05期

4 李陽;;基于改進(jìn)的群搜索算法求解分類規(guī)則[J];無線互聯(lián)科技;2012年10期

5 李冉;褚雪松;李亮;;動態(tài)和聲搜索算法在土坡穩(wěn)定分析中的應(yīng)用[J];人民黃河;2011年02期

6 李紅;彭方;;窮舉式搜索算法及其應(yīng)用[J];福建電腦;2007年05期

7 王士同;;S模下啟發(fā)式圖搜索算法A~的研究[J];微電子學(xué)與計(jì)算機(jī);1988年03期

8 王士同;隨機(jī)產(chǎn)生式系統(tǒng)的啟發(fā)式圖搜索算法RA~*及其若干性質(zhì)[J];鎮(zhèn)江船舶學(xué)院學(xué)報(bào);1988年01期

9

本文編號：2635969