絕熱量子搜索算法研究.pdf

1、Shor大整數(shù)因子分解算法、Grover算法等量子算法已經(jīng)證明了量子計(jì)算具有比經(jīng)典計(jì)算更強(qiáng)大的計(jì)算能力。然而，設(shè)計(jì)快速的量子算法是困難的，主要有兩方面的原因。一方面，算法設(shè)計(jì)者的直覺植根于經(jīng)典世界之中，算法設(shè)計(jì)者必須設(shè)法避開直覺的干擾才能設(shè)計(jì)出優(yōu)越的量子算法。另一方面，設(shè)計(jì)者所設(shè)計(jì)的量子算法必須超出所有的經(jīng)典算法，否則很難引起廣泛興趣。絕熱量子計(jì)算是繼基于量子快速傅里葉變換量子算法研究及Grover算法研究之后的另一量子算法研究領(lǐng)域。它

2、以量子絕熱定理為理論基礎(chǔ)，具有與生俱來的抵抗量子噪聲的能力，本質(zhì)上屬于連續(xù)時(shí)間量子計(jì)算，不同于基于離散幺正變換序列的量子計(jì)算模型――量子線路模型。無序數(shù)據(jù)庫搜索問題是量子搜索算法包括Grover算法研究的核心問題，也是量子計(jì)算研究的熱點(diǎn)問題。利用絕熱量子模型研究、解決該問題有助于理解絕熱量子計(jì)算乃至量子計(jì)算的本質(zhì)，具有重要的理論意義。
　　 從表面來看，全局絕熱量子計(jì)算模型采用線性由線性插值法給定，它的時(shí)間復(fù)雜度制約公式是由絕熱

3、條件作用于整個(gè)時(shí)間區(qū)間而得到；局部絕熱量子計(jì)算模型的絕熱路徑及時(shí)間復(fù)雜度制約公式由絕熱條件作用于無窮小的時(shí)間區(qū)間而得到；部分絕熱量子計(jì)算模型也采用線性插值法給出系統(tǒng)哈密頓量，但其只在使系統(tǒng)基態(tài)和第一激發(fā)態(tài)之間的能隙最小的時(shí)間點(diǎn)附近執(zhí)行絕熱演化。然而，對絕熱量子算法的研究發(fā)現(xiàn)，全局、局部以及部分絕熱量子算法本質(zhì)區(qū)別在于演化路徑的不同。
　　 絕熱量子系統(tǒng)的核心要素是系統(tǒng)哈密頓量。給定了系統(tǒng)哈密頓量，就給定了整個(gè)量子系統(tǒng)的演化過程。

4、在絕熱量子計(jì)算中，給定初始哈密頓量、末態(tài)哈密頓量以及路徑參數(shù)就給定了系統(tǒng)哈密頓量。絕熱量子計(jì)算的核心問題是系統(tǒng)基態(tài)和第一激發(fā)態(tài)之間的最小能隙問題。一般情況下，系統(tǒng)哈密頓量的能譜及該最小能隙是難以求解的。但在特殊情況下，可以采用降維的方法，把系統(tǒng)工作的N（一般設(shè)為N=2n）維希爾伯特空間降至相對較小的維數(shù)，再采用近似或解析的方法求解系統(tǒng)基態(tài)和第一激發(fā)態(tài)之間的最小能隙。例如，把Grover問題看做SAT問題的特例，可以把N維降為n+1維，再

5、采用近似方法求解系統(tǒng)基態(tài)和第一激發(fā)態(tài)之間的最小能隙。
　　 已有研究表明Grover算法是基于Oracle調(diào)用的最優(yōu)量子算法，其時(shí)間復(fù)雜度為O(√N(yùn))；全局絕熱量子搜索算法只能得到和經(jīng)典暴力搜索一樣的時(shí)間復(fù)雜度；局部絕熱量子搜索算法具有和Grover算法一樣的時(shí)間復(fù)雜度；部分絕熱量子算法在匹配搜索條件的數(shù)據(jù)庫條目數(shù)M=1的情況下，具有和Grover算法一樣的時(shí)間復(fù)雜度，但在M> 1的情況下，其時(shí)間復(fù)雜度要快O(√M)。對Grov

6、er算法和局部絕熱量子搜索算法的最優(yōu)性證明目前僅限于M=1（M為標(biāo)識態(tài)的數(shù)目）的情況。通過修改不同末態(tài)之間的度量，利用絕熱條件可以證明局部絕熱量子搜索算法在M> 1的情況下也是最優(yōu)的，即不存在其他絕熱演化路徑，得到更優(yōu)的絕熱量子搜索算法。值得一提的是，該證明并不包含部分絕熱量子搜索算法。絕熱量子計(jì)算本質(zhì)上是連續(xù)時(shí)間量子計(jì)算，把它轉(zhuǎn)化為量子線路模型一般遵守兩步法則：第一步，對量子算法的運(yùn)行時(shí)間進(jìn)行分片，在每一個(gè)小的時(shí)間片內(nèi)，用一個(gè)幺正變換