- 相關(guān)推薦
量子算法與量子計(jì)算實(shí)驗(yàn)
論文關(guān)鍵詞:量子算法 量子計(jì)算 量子比特 糾纏
論文摘要:本文介紹了量子計(jì)算糾纏和量子比特的基本概念,系統(tǒng)闡述了幾種主要的量子算法:Shor算法———大數(shù)質(zhì)因子分解的量子算法;Grover搜索———無序數(shù)據(jù)庫的搜索;Hogg搜索———高度結(jié)構(gòu)化搜索。在對量子計(jì)算基本理論和量子算法有一定認(rèn)識的基礎(chǔ)上,進(jìn)一步介紹了在量子計(jì)算實(shí)驗(yàn)方面起重要作用的二種體系:核磁共振、腔與原子體系。
Abstract:In this thesis,several basic conceptions of quantum computation are introduced,such as entanglement,quantum bit.Several kinds
of main quantum algorit hms are illustrated,such as Shor algorit hm-t he quantum algorit hm for factoring,Grover search-t he search for t he disordering
database,Hogg search-high structurization search.On t he basis of knowledge of basic t heories of quantum computation computing and quantum algo
2
rit hm,two kinds of systems which play important role in t he experiment of quantum computation was introduced,Nuclear magnetic resonance and cavi
2
ty atom system.
Key words:Quantum algorithm Quantum computation Quantum bit Entanglement
量子計(jì)算是量子物理與計(jì)算機(jī)科學(xué)交匯而生的一門新興學(xué)科。它的出現(xiàn)實(shí)質(zhì)上是量子物理學(xué)向物質(zhì)、能量和信息這三大領(lǐng)地的最后一塊信息領(lǐng)域的進(jìn)軍。
一、量子計(jì)算的基本理論
1、糾纏
1935年,Schr dinger首先給出了糾纏態(tài)的定義:由空間分離的兩個(gè)子系統(tǒng)構(gòu)成的純態(tài),如果系統(tǒng)波函數(shù)不能分解為兩個(gè)子系統(tǒng)波函數(shù)的乘積,那么這樣的波函數(shù)表示的態(tài)稱作兩個(gè)粒子的糾纏量子態(tài)。1935年,Einstein,Podolsky和Rosen首先討論了一個(gè)具體的兩粒子糾纏量子態(tài)。在這個(gè)著名的實(shí)驗(yàn)中,兩粒子的糾纏量子態(tài)為:|Ψ〉=∑a,bδ(a+b-c0)|a|b〉
其中a,b分別為粒子1和粒子2的位置或動量,C0為常數(shù)。這個(gè)糾纏態(tài)的一個(gè)最明顯的特征是:其中任何一個(gè)子系統(tǒng)的物理量的觀測值(位置或動量)都是不確定的。但是,如果其中的一個(gè)子系統(tǒng)的物理量的觀測值處于一個(gè)確定的值,那么我們就可以確定另外一個(gè)子系統(tǒng)的相應(yīng)物理量觀測值。
2、量子比特
量子比特有微觀體系表征,如原子、核自旋或光子等。|1>和|0>可以由原子的兩個(gè)能級來表示,也可以由核自旋或光子的不同極化方向來表征。與經(jīng)典比特顯著不同的是,量子比特|1>和|0>之間存在著許多中間態(tài),即|1>和|0>的不同迭加態(tài),例如12(|0>+|1>)表示一個(gè)兩子比特同時(shí)存儲著0和1。因此,對于位數(shù)相同的n個(gè)比特,量子比特可以存儲2n倍的經(jīng)典比特所能存儲的信息。對于兩個(gè)量子比特的體系,其完備基由四個(gè)布爾態(tài)|00>、|01>、|10>和|11>組成。考慮它們之間的迭加,我們可以發(fā)現(xiàn),|10>+|11>=|1>(|0>+|1>),這是由兩個(gè)量子比特構(gòu)成的直積空間。而|11>+|00>或|01>+|10>則不能再寫成直積形式。后面這種情況就是前面提到的糾纏。對于一個(gè)處于糾纏狀態(tài)的體系,我們不能確切地指出其中某一個(gè)量子比特是處于|1>還是|0>。更一般的糾纏態(tài)是處于2n個(gè)布爾態(tài)的n個(gè)經(jīng)典比特組成的迭加態(tài)。|Ψ〉=∑11…1x=00…0Cx|x〉其中Cx可以是復(fù)數(shù)并且滿足∑x|Cx|2=1。當(dāng)Cx=12n時(shí),稱為等幅迭加態(tài)。這種等幅迭加態(tài)在以下要介紹的各量子算法中經(jīng)常被用作初態(tài)。從上式也能看出,|Ψ>是一個(gè)2n維的Hilbert空間中的一個(gè)單位矢量。它所在空間的維數(shù)是隨n呈指數(shù)型增長,這明顯區(qū)別于經(jīng)典體系中隨n呈線性增長的態(tài)空間。在一個(gè)孤立的量子體系中,對態(tài)的操作應(yīng)是幺正的、可逆的。因此,我們構(gòu)造的量子邏輯門也應(yīng)滿足這個(gè)特征。
二、量子算法
1、Shor算法———大數(shù)質(zhì)因子分解的量子算法
用經(jīng)典計(jì)算機(jī)來進(jìn)行大數(shù)質(zhì)因子分解,隨著N的增大,所需比特?cái)?shù)(即內(nèi)存)是呈指數(shù)倍的增長。按照組合數(shù)學(xué)理論,當(dāng)計(jì)算規(guī)模隨著問題的難度呈多項(xiàng)式型增長時(shí),該問題為P(Polynomial)問題。對于P問題,我們在有限的時(shí)間內(nèi)總能找到辦法求得它的解。對于我們在有限的時(shí)間內(nèi)不可能找到辦法求得解的問題稱之為NP(Non-Polynomial)問題。目前世界上應(yīng)用最廣也是最成功的加密方法-公開密鑰RSA系統(tǒng)的核心思想就是利用大數(shù)在有限時(shí)間內(nèi)不可有效質(zhì)因子化這一結(jié)論。1995年,P.W.Shor提出一種量子算法,能將這一著名的NP問題化為P問題,矛頭直指RSA方法,從而在全球掀起了量子計(jì)算的研究熱浪。在Shor算法中,尋找一個(gè)大數(shù)的質(zhì)因子問題被轉(zhuǎn)化為尋找其余因子函數(shù)的周期。只要該周期被找到,并且為一個(gè)偶數(shù),那么利用剩余定理,就能得到該大數(shù)的質(zhì)因子。給定整數(shù)N,選取一個(gè)與N互質(zhì)的數(shù)a(a 不難看出,fa,N(x)的變化是有規(guī)律的,其變化周期為r=4。知道了這個(gè)周期,就可以利用孫子定理:設(shè)A=ar/2+1,B=a
r/2-1,其中r必須為偶數(shù),且ar/2mod(N)≠1。求出A、B之后,再分別求A、N和B、N的最大公約數(shù)(gcd)。設(shè)C=gcd
(A,N),D=gcd(B,N)那么一定有C×D=N,即N被成功地質(zhì)因子化。Shor算法的關(guān)鍵在于求出大數(shù)N的余因子函數(shù)的周期r。不過,由于余因子函數(shù)的周期r不能在量子計(jì)算中被有效測出,因此在Shor算法中需借助量子離散傅立葉變換,將余因子函數(shù)的周期換成另一個(gè)可測的周期。
2、Grover搜索:無序數(shù)據(jù)庫的搜索
Grover提出了一種算法:利用量子態(tài)的糾纏特性和量子并行計(jì)算原理,可以用最多n步的搜索尋找到所需項(xiàng)。Grover算法的思想極為簡單,可用一句話“振幅平均后翻轉(zhuǎn)”來概括。具體說來是以下幾個(gè)基本步驟:
①初態(tài)的制備。運(yùn)用Hadamard門將處于態(tài)|0>和|1>的各量子比特轉(zhuǎn)化為等幅迭加態(tài)。
②設(shè)數(shù)據(jù)庫為T[1,2,,N]共,n項(xiàng)。設(shè)其中滿足我們要求的那一項(xiàng)標(biāo)記為A。于是在T中搜索A類似于求解一個(gè)單調(diào)函數(shù)的根。運(yùn)用量子并行計(jì)算可以將A所在態(tài)的相位旋轉(zhuǎn)180°,其余各態(tài)保持不變。即當(dāng)T[i]=A時(shí),增加一個(gè)相位eiπ。
③相對各態(tài)的振幅的平均值作翻轉(zhuǎn)。這一操作由幺正矩陣k1,k2…knD完成,其表達(dá)式為Dij=2/N,Dij=-1+2/N。
④以上②③兩步可以反復(fù)進(jìn)行,每進(jìn)行一次,稱為一次搜索�？梢宰C明,最多只需搜索N次,便能以大于0.5的幾率找到我們要找的數(shù)據(jù)項(xiàng)。Grover算法提出之后,引起了眾人極大的興趣。Grover算法中的翻轉(zhuǎn)方法不僅被證明是最優(yōu)化的搜索方式,而且也是抗干擾能力極強(qiáng)的方法。
3、Hogg搜索:高度結(jié)構(gòu)化搜索
前面介紹過的NP問題中有一類名為可滿足性問題(Satisfiability Problem,簡稱SA T問題)。一個(gè)典型的SA T問題是包括有n個(gè)變量的一個(gè)邏輯公式,要求給予其中每個(gè)變量一個(gè)賦值使邏輯公式為真。數(shù)學(xué)上已證明,解決SAT問題的代價(jià)是隨著變量數(shù)的增加而呈指數(shù)型增長。然而對于某些簡單的情況,人們可以利用問題中具有的規(guī)則結(jié)構(gòu)來迅速準(zhǔn)確地搜索出問題的解。例如對于1-SAT問題,用經(jīng)典試探法進(jìn)行搜索,找出解的代價(jià)為最多需用n步。對于量子計(jì)算而言,由于能進(jìn)行量子并行計(jì)算,因而可以僅以一步的代價(jià)找出1-SAT問題的解。下面以有m個(gè)邏輯子句的1-SAT問題為例。與Grover搜索相似,我們先在n個(gè)量子比特上制備一個(gè)等幅迭加態(tài)作為初始態(tài),即|Ψ〉=2-n/2∑n-1s=0|S〉。另外,我們需設(shè)計(jì)好兩種幺正操作R和U,其中R為對角矩陣,其歸一化對角元為Rss=2cos[(2c-1)π/4] m=偶數(shù)ic
m=奇數(shù)。(3.3.1)式中的c(0 (3.3.2)其中d稱為Hamming距離,d=d(r,s)=|r|+|s|-2|r∧s|,其中|r|和|s|分別表示r字節(jié)串和s字節(jié)串中含有比特為1的個(gè)數(shù)。|r∧s|表示r和s中共同含有比特為1的個(gè)數(shù)。
對于以上1-SAT問題,顯然有m個(gè)變量是約束的,而剩余的n-m個(gè)非約束的變量則對應(yīng)于2n-m個(gè)解。對于1-SAT問題,用Hogg算法能決定性地一步找到解。如果通過一步邏輯操作未能明確地發(fā)現(xiàn)解,則意味著該
問題無解。不難看出,Hogg搜索的效率遠(yuǎn)高于上節(jié)介紹的Grover搜索。這兩種搜索的差別在于,Hogg搜索利用了數(shù)據(jù)庫的結(jié)構(gòu)信息,因而能將一個(gè)NP問題轉(zhuǎn)化為P問題。而Grover算法解決不了N P問題,它相對于經(jīng)典搜索只是提高了搜索效率。Hogg搜索的另一個(gè)優(yōu)勢在于具有強(qiáng)的抗消相干能力。由于它的邏輯步數(shù)少,因而消相干效應(yīng)對其影響非常小。
三、量子計(jì)算實(shí)驗(yàn)
與量子計(jì)算理論方面的飛速進(jìn)展相比,量子計(jì)算的實(shí)驗(yàn)進(jìn)展則要慢得多。本章主要介紹二種體系:核磁共振和腔與原子體系。
1、核磁共振(NMR)
核磁共振技術(shù)是目前在量子計(jì)算領(lǐng)域使用最為頻繁的實(shí)驗(yàn)手段。運(yùn)用這一技術(shù)手段,操作作用在1023數(shù)量級的分子系綜的自旋態(tài)上,通過測量,得到這些分子的平均自旋態(tài)。雖然每個(gè)分子的自旋都可能不盡相同,但通過spin-e2cho技術(shù)可以按我們的意愿改變個(gè)別分子的自旋方向。由于核磁共振體系實(shí)質(zhì)上是一個(gè)宏觀系綜,因而外部環(huán)境對它的消相干的影響極小。且樣品的核自旋處于近獨(dú)立的狀態(tài),幾乎不受電子和分子的熱運(yùn)動的干擾。但是,宏觀系綜原則上沒有量子特性,只有純粹的量子系綜才具有量子純態(tài)的特征。只有當(dāng)它被制備到一個(gè)特殊狀態(tài)—贗純態(tài)時(shí),才能完成量子計(jì)算的工作。下面舉例介紹實(shí)現(xiàn)兩量子比特的Grover搜索的實(shí)驗(yàn)。實(shí)驗(yàn)中所用樣品為C-13同位素標(biāo)記的氯仿HCCL3。實(shí)驗(yàn)中用碳和氫的核自旋來標(biāo)記|1>和|0>,其中13C的中心共振頻率約為125MHz,1H的中心共振頻率約為500M Hz。實(shí)驗(yàn)體系的哈氏量為H=2πnhJ ICZ IHZ+PH,所以各步驟如Grover搜索所介紹的那樣。比較實(shí)驗(yàn)和理論,可以發(fā)現(xiàn)實(shí)驗(yàn)中存在一些誤差。這些誤差主要來自磁場和射頻場的不均勻、初始時(shí)間的校正和信號衰減等。
2、腔與原子體系
腔量子電動力學(xué)(C-QED)體系是另外一種可以進(jìn)行量子計(jì)算的量子系統(tǒng)。腔量子電動力學(xué)體系之所以可以實(shí)現(xiàn)對兩位量子信息進(jìn)行處理量子系統(tǒng),一個(gè)重要原因就是腔中的輻射場與原子具有很強(qiáng)的非線性相互作用,這種相互作用的演化導(dǎo)致腔場和原子體系的本征態(tài)處于糾纏態(tài)。腔量子電動力學(xué)體系包含光腔和微波腔。這里我們主要介紹微波腔體系中應(yīng)用Rydberg原子與微波腔相互作用實(shí)現(xiàn)的條件量子相移門(QPG)。條件量子相移門(QPG)需要對兩量子位的如下變換:
|a,b〉→ex p(i<δa,1δb,1)|a,b〉其中|a>,|b>分別代表兩量子位的基矢|0>或|1>,而δa,1,δb,1為通常的克隆尼克符號。條件量子相移門(QPG)在兩個(gè)量子態(tài)都處在|1>時(shí),產(chǎn)生一個(gè)<角相移,而在其他情況下均保持不變。由于其他任何操作可以應(yīng)用條件量子相移門(QPG)和單個(gè)量子位的旋轉(zhuǎn)來實(shí)現(xiàn),因而,條件量子相移門(QPG)是一個(gè)通用量子邏輯門。我們這里介紹的條件量子相移門(QPG)是用包含0個(gè)光子或1個(gè)光子的腔場和單個(gè)Rydberg原子作為量子位來實(shí)現(xiàn)的。控制量子位是0個(gè)光子腔場|a>=|0>或1個(gè)光子的腔場|a>=|1>而,目標(biāo)量子位是Rydberg原子的兩個(gè)能級|i>(定義|b>=|0>)和|g>(定義為|b>=|1>)。
實(shí)驗(yàn)中應(yīng)用的Rb原子的能級除了目標(biāo)量子位兩個(gè)Ry2dberg原子的能級|i>和|g>以外,還包括一個(gè)相關(guān)的能級|e>。三個(gè)相關(guān)的Rydberg原子態(tài)分別代表Rb原子的主量子數(shù)n=51(|e>),n=50(|g>)和n=49(|i>)。原子的能級|e>和|g>與微波腔場發(fā)生共振相互作用,而原子能級|g>和|i>之間通過另外的微波場產(chǎn)生耦合。當(dāng)原子處于能級|i>或者腔場處于|0>,原子與腔場的系統(tǒng)狀態(tài)不發(fā)生變化,而當(dāng)原子腔場的初始處于|g,1>態(tài)時(shí),控制原子的速度使原子|g>與|e>量子態(tài)在腔場中經(jīng)歷一個(gè)2π的拉比振蕩,|g,1>態(tài)演化為-|g,1>=exp(πi)|g,1>。因而系統(tǒng)的演化可以描述為:|a,b〉→ex p(iπδa,1δ
b,1)|a,b〉這個(gè)過程實(shí)際實(shí)現(xiàn)了相移為π的條件量子相移門(Q P G)。
參考文獻(xiàn):
①L.Isaac,G.Neil,K.Mark.Experimental Implemen2tation of Fast Quantum Searching[J].Phys.Rev.Lett.1998,
80:3408-3411.
②A.Salomaa著,丁存生,單煒娟譯.公鑰密碼學(xué)[M].北京:國防大學(xué)出版社,1998
③M.R.Garey,D.S.Johnson.Computers and in2tractability[M]:A Guide to t he t heory of N P-Completeness.
San Francisco:Freeman Press,1997
④J.I.Cirac,Parkins.Schemes for atomic-state tele2portation[J].Phys.Rev.A.1994,50:R4441-R4444.
⑤R.Schack.Using a quantum computer to investigatequantum chaos[J].Phys.Rev.A,1998
【量子算法與量子計(jì)算實(shí)驗(yàn)】相關(guān)文章：
數(shù)據(jù)關(guān)聯(lián)算法綜述及其性能評估05-05
物理實(shí)驗(yàn)論文11-03
新課程實(shí)驗(yàn)課題開題報(bào)告09-01
重視數(shù)學(xué)實(shí)驗(yàn)的解題的幾個(gè)技巧11-02
初中物理實(shí)驗(yàn)教學(xué)探討06-12
物理實(shí)驗(yàn)論文 15篇11-03