量子算法與量子計算實(shí)驗

　　論文關(guān)鍵詞:量子算法　量子計算　量子比特　糾纏

　　論文摘要:本文介紹了量子計算糾纏和量子比特的基本概念,系統闡述了幾種主要的量子算法:Shor算法———大數質(zhì)因子分解的量子算法;Grover搜索———無(wú)序數據庫的搜索;Hogg搜索———高度結構化搜索。在對量子計算基本理論和量子算法有一定認識的基礎上,進(jìn)一步介紹了在量子計算實(shí)驗方面起重要作用的二種體系:核磁共振、腔與原子體系。

　　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
　量子計算是量子物理與計算機科學(xué)交匯而生的一門(mén)新興學(xué)科。它的出現實(shí)質(zhì)上是量子物理學(xué)向物質(zhì)、能量和信息這三大領(lǐng)地的最后一塊信息領(lǐng)域的進(jìn)軍。

　　一、量子計算的基本理論
　　1、糾纏
　　1935年,Schr dinger首先給出了糾纏態(tài)的定義:由空間分離的兩個(gè)子系統構成的純態(tài),如果系統波函數不能分解為兩個(gè)子系統波函數的乘積,那么這樣的波函數表示的態(tài)稱(chēng)作兩個(gè)粒子的糾纏量子態(tài)。1935年,Einstein,Podolsky和Rosen首先討論了一個(gè)具體的兩粒子糾纏量子態(tài)。在這個(gè)著(zhù)名的實(shí)驗中,兩粒子的糾纏量子態(tài)為:|Ψ〉=∑a,bδ(a+b-c0)|a|b〉
　　其中a,b分別為粒子1和粒子2的位置或動(dòng)量,C0為常數。這個(gè)糾纏態(tài)的一個(gè)最明顯的特征是:其中任何一個(gè)子系統的物理量的觀(guān)測值(位置或動(dòng)量)都是不確定的。但是,如果其中的一個(gè)子系統的物理量的觀(guān)測值處于一個(gè)確定的值,那么我們就可以確定另外一個(gè)子系統的相應物理量觀(guān)測值。
　　2、量子比特
　　量子比特有微觀(guān)體系表征,如原子、核自旋或光子等。|1>和|0>可以由原子的兩個(gè)能級來(lái)表示,也可以由核自旋或光子的不同極化方向來(lái)表征。與經(jīng)典比特顯著(zhù)不同的是,量子比特|1>和|0>之間存在著(zhù)許多中間態(tài),即|1>和|0>的不同迭加態(tài),例如12(|0>+|1>)表示一個(gè)兩子比特同時(shí)存儲著(zhù)0和1。因此,對于位數相同的n個(gè)比特,量子比特可以存儲2n倍的經(jīng)典比特所能存儲的信息。對于兩個(gè)量子比特的體系,其完備基由四個(gè)布爾態(tài)|00>、|01>、|10>和|11>組成�？紤]它們之間的迭加,我們可以發(fā)現,|10>+|11>=|1>(|0>+|1>),這是由兩個(gè)量子比特構成的直積空間。而|11>+|00>或|01>+|10>則不能再寫(xiě)成直積形式。后面這種情況就是前面提到的糾纏。對于一個(gè)處于糾纏狀態(tài)的體系,我們不能確切地指出其中某一個(gè)量子比特是處于|1>還是|0>。更一般的糾纏態(tài)是處于2n個(gè)布爾態(tài)的n個(gè)經(jīng)典比特組成的迭加態(tài)。|Ψ〉=∑11…1x=00…0Cx|x〉其中Cx可以是復數并且滿(mǎn)足∑x|Cx|2=1。當Cx=12n時(shí),稱(chēng)為等幅迭加態(tài)。這種等幅迭加態(tài)在以下要介紹的各量子算法中經(jīng)常被用作初態(tài)。從上式也能看出,|Ψ>是一個(gè)2n維的Hilbert空間中的一個(gè)單位矢量。它所在空間的維數是隨n呈指數型增長(cháng),這明顯區別于經(jīng)典體系中隨n呈線(xiàn)性增長(cháng)的態(tài)空間。在一個(gè)孤立的量子體系中,對態(tài)的操作應是幺正的、可逆的。因此,我們構造的量子邏輯門(mén)也應滿(mǎn)足這個(gè)特征。

　　二、量子算法
　　1、Shor算法———大數質(zhì)因子分解的量子算法
　　用經(jīng)典計算機來(lái)進(jìn)行大數質(zhì)因子分解,隨著(zhù)N的增大,所需比特數(即內存)是呈指數倍的增長(cháng)。按照組合數學(xué)理論,當計算規模隨著(zhù)問(wèn)題的難度呈多項式型增長(cháng)時(shí),該問(wèn)題為P(Polynomial)問(wèn)題。對于P問(wèn)題,我們在有限的時(shí)間內總能找到辦法求得它的解。對于我們在有限的時(shí)間內不可能找到辦法求得解的問(wèn)題稱(chēng)之為NP(Non-Polynomial)問(wèn)題。目前世界上應用最廣也是最成功的加密方法-公開(kāi)密鑰RSA系統的核心思想就是利用大數在有限時(shí)間內不可有效質(zhì)因子化這一結論。1995年,P.W.Shor提出一種量子算法,能將這一著(zhù)名的NP問(wèn)題化為P問(wèn)題,矛頭直指RSA方法,從而在全球掀起了量子計算的研究熱浪。在Shor算法中,尋找一個(gè)大數的質(zhì)因子問(wèn)題被轉化為尋找其余因子函數的周期。只要該周期被找到,并且為一個(gè)偶數,那么利用剩余定理,就能得到該大數的質(zhì)因子。給定整數N,選取一個(gè)與N互質(zhì)的數a(a　　不難看出,fa,N(x)的變化是有規律的,其變化周期為r=4。知道了這個(gè)周期,就可以利用孫子定理:設A=ar/2+1,B=a
r/2-1,其中r必須為偶數,且ar/2mod(N)≠1。求出A、B之后,再分別求A、N和B、N的最大公約數(gcd)。設C=gcd
(A,N),D=gcd(B,N)那么一定有C×D=N,即N被成功地質(zhì)因子化。Shor算法的關(guān)鍵在于求出大數N的余因子函數的周期r。不過(guò),由于余因子函數的周期r不能在量子計算中被有效測出,因此在Shor算法中需借助量子離散傅立葉變換,將余因子函數的周期換成另一個(gè)可測的周期。
　　2、Grover搜索:無(wú)序數據庫的搜索
　　Grover提出了一種算法:利用量子態(tài)的糾纏特性和量子并行計算原理,可以用最多n步的搜索尋找到所需項。Grover算法的思想極為簡(jiǎn)單,可用一句話(huà)“振幅平均后翻轉”來(lái)概括。具體說(shuō)來(lái)是以下幾個(gè)基本步驟:
①初態(tài)的制備。運用Hadamard門(mén)將處于態(tài)|0>和|1>的各量子比特轉化為等幅迭加態(tài)。
②設數據庫為T(mén)[1,2,,N]共,n項。設其中滿(mǎn)足我們要求的那一項標記為A。于是在T中搜索A類(lèi)似于求解一個(gè)單調函數的根。運用量子并行計算可以將A所在態(tài)的相位旋轉180°,其余各態(tài)保持不變。即當T[i]=A時(shí),增加一個(gè)相位eiπ。
③相對各態(tài)的振幅的平均值作翻轉。這一操作由幺正矩陣k1,k2…knD完成,其表達式為Dij=2/N,Dij=-1+2/N。
④以上②③兩步可以反復進(jìn)行,每進(jìn)行一次,稱(chēng)為一次搜索�？梢宰C明,最多只需搜索N次,便能以大于0.5的幾率找到我們要找的數據項。Grover算法提出之后,引起了眾人極大的興趣。Grover算法中的翻轉方法不僅被證明是最優(yōu)化的搜索方式,而且也是抗干擾能力極強的方法。

　　3、Hogg搜索:高度結構化搜索
　　前面介紹過(guò)的NP問(wèn)題中有一類(lèi)名為可滿(mǎn)足性問(wèn)題(Satisfiability Problem,簡(jiǎn)稱(chēng)SA T問(wèn)題)。一個(gè)典型的SA T問(wèn)題是包括有n個(gè)變量的一個(gè)邏輯公式,要求給予其中每個(gè)變量一個(gè)賦值使邏輯公式為真。數學(xué)上已證明,解決SAT問(wèn)題的代價(jià)是隨著(zhù)變量數的增加而呈指數型增長(cháng)。然而對于某些簡(jiǎn)單的情況,人們可以利用問(wèn)題中具有的規則結構來(lái)迅速準確地搜索出問(wèn)題的解。例如對于1-SAT問(wèn)題,用經(jīng)典試探法進(jìn)行搜索,找出解的代價(jià)為最多需用n步。對于量子計算而言,由于能進(jìn)行量子并行計算,因而可以?xún)H以一步的代價(jià)找出1-SAT問(wèn)題的解。下面以有m個(gè)邏輯子句的1-SAT問(wèn)題為例。與Grover搜索相似,我們先在n個(gè)量子比特上制備一個(gè)等幅迭加態(tài)作為初始態(tài),即|Ψ〉=2-n/2∑n-1s=0|S〉。另外,我們需設計好兩種幺正操作R和U,其中R為對角矩陣,其歸一化對角元為Rss=2cos[(2c-1)π/4]　m=偶數ic　　　　
　　　m=奇數。(3.3.1)式中的c(0　(3.3.2)其中d稱(chēng)為Hamming距離,d=d(r,s)=|r|+|s|-2|r∧s|,其中|r|和|s|分別表示r字節串和s字節串中含有比特為1的個(gè)數。|r∧s|表示r和s中共同含有比特為1的個(gè)數。

對于以上1-SAT問(wèn)題,顯然有m個(gè)變量是約束的,而剩余的n-m個(gè)非約束的變量則對應于2n-m個(gè)解。對于1-SAT問(wèn)題,用Hogg算法能決定性地一步找到解。如果通過(guò)一步邏輯操作未能明確地發(fā)現解,則意味著(zhù)該
問(wèn)題無(wú)解。不難看出,Hogg搜索的效率遠高于上節介紹的Grover搜索。這兩種搜索的差別在于,Hogg搜索利用了數據庫的結構信息,因而能將一個(gè)NP問(wèn)題轉化為P問(wèn)題。而Grover算法解決不了N P問(wèn)題,它相對于經(jīng)典搜索只是提高了搜索效率。Hogg搜索的另一個(gè)優(yōu)勢在于具有強的抗消相干能力。由于它的邏輯步數少,因而消相干效應對其影響非常小。
　　三、量子計算實(shí)驗
　　與量子計算理論方面的飛速進(jìn)展相比,量子計算的實(shí)驗進(jìn)展則要慢得多。本章主要介紹二種體系:核磁共振和腔與原子體系。
　　1、核磁共振(NMR)
　　核磁共振技術(shù)是目前在量子計算領(lǐng)域使用最為頻繁的實(shí)驗手段。運用這一技術(shù)手段,操作作用在1023數量級的分子系綜的自旋態(tài)上,通過(guò)測量,得到這些分子的平均自旋態(tài)。雖然每個(gè)分子的自旋都可能不盡相同,但通過(guò)spin-e2cho技術(shù)可以按我們的意愿改變個(gè)別分子的自旋方向。由于核磁共振體系實(shí)質(zhì)上是一個(gè)宏觀(guān)系綜,因而外部環(huán)境對它的消相干的影響極小。且樣品的核自旋處于近獨立的狀態(tài),幾乎不受電子和分子的熱運動(dòng)的干擾。但是,宏觀(guān)系綜原則上沒(méi)有量子特性,只有純粹的量子系綜才具有量子純態(tài)的特征。只有當它被制備到一個(gè)特殊狀態(tài)—贗純態(tài)時(shí),才能完成量子計算的工作。下面舉例介紹實(shí)現兩量子比特的Grover搜索的實(shí)驗。實(shí)驗中所用樣品為C-13同位素標記的氯仿HCCL3。實(shí)驗中用碳和氫的核自旋來(lái)標記|1>和|0>,其中13C的中心共振頻率約為125MHz,1H的中心共振頻率約為500M Hz。實(shí)驗體系的哈氏量為H=2πnhJ ICZ IHZ+PH,所以各步驟如Grover搜索所介紹的那樣。比較實(shí)驗和理論,可以發(fā)現實(shí)驗中存在一些誤差。這些誤差主要來(lái)自磁場(chǎng)和射頻場(chǎng)的不均勻、初始時(shí)間的校正和信號衰減等。
　　2、腔與原子體系
　　腔量子電動(dòng)力學(xué)(C-QED)體系是另外一種可以進(jìn)行量子計算的量子系統。腔量子電動(dòng)力學(xué)體系之所以可以實(shí)現對兩位量子信息進(jìn)行處理量子系統,一個(gè)重要原因就是腔中的輻射場(chǎng)與原子具有很強的非線(xiàn)性相互作用,這種相互作用的演化導致腔場(chǎng)和原子體系的本征態(tài)處于糾纏態(tài)。腔量子電動(dòng)力學(xué)體系包含光腔和微波腔。這里我們主要介紹微波腔體系中應用Rydberg原子與微波腔相互作用實(shí)現的條件量子相移門(mén)(QPG)。條件量子相移門(mén)(QPG)需要對兩量子位的如下變換:
　　|a,b〉→ex p(i<δa,1δb,1)|a,b〉其中|a>,|b>分別代表兩量子位的基矢|0>或|1>,而δa,1,δb,1為通常的克隆尼克符號。條件量子相移門(mén)(QPG)在兩個(gè)量子態(tài)都處在|1>時(shí),產(chǎn)生一個(gè)<角相移,而在其他情況下均保持不變。由于其他任何操作可以應用條件量子相移門(mén)(QPG)和單個(gè)量子位的旋轉來(lái)實(shí)現,因而,條件量子相移門(mén)(QPG)是一個(gè)通用量子邏輯門(mén)。我們這里介紹的條件量子相移門(mén)(QPG)是用包含0個(gè)光子或1個(gè)光子的腔場(chǎng)和單個(gè)Rydberg原子作為量子位來(lái)實(shí)現的�？刂屏孔游皇�0個(gè)光子腔場(chǎng)|a>=|0>或1個(gè)光子的腔場(chǎng)|a>=|1>而,目標量子位是Rydberg原子的兩個(gè)能級|i>(定義|b>=|0>)和|g>(定義為|b>=|1>)。
實(shí)驗中應用的Rb原子的能級除了目標量子位兩個(gè)Ry2dberg原子的能級|i>和|g>以外,還包括一個(gè)相關(guān)的能級|e>。三個(gè)相關(guān)的Rydberg原子態(tài)分別代表Rb原子的主量子數n=51(|e>),n=50(|g>)和n=49(|i>)。原子的能級|e>和|g>與微波腔場(chǎng)發(fā)生共振相互作用,而原子能級|g>和|i>之間通過(guò)另外的微波場(chǎng)產(chǎn)生耦合。當原子處于能級|i>或者腔場(chǎng)處于|0>,原子與腔場(chǎng)的系統狀態(tài)不發(fā)生變化,而當原子腔場(chǎng)的初始處于|g,1>態(tài)時(shí),控制原子的速度使原子|g>與|e>量子態(tài)在腔場(chǎng)中經(jīng)歷一個(gè)2π的拉比振蕩,|g,1>態(tài)演化為-|g,1>=exp(πi)|g,1>。因而系統的演化可以描述為:|a,b〉→ex p(iπδa,1δ
b,1)|a,b〉這個(gè)過(guò)程實(shí)際實(shí)現了相移為π的條件量子相移門(mén)(Q P G)。

參考文獻:
①L.Isaac,G.Neil,K.Mark.Experimental Implemen2tation of Fast Quantum Searching[J].Phys.Rev.Lett.1998,
80:3408-3411.
②A(yíng).Salomaa著(zhù),丁存生,單煒娟譯.公鑰密碼學(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

【量子算法與量子計算實(shí)驗】相關(guān)文章：

量子糾纏及其度量03-07

腔量子電動(dòng)力學(xué)中的量子隱形傳態(tài)方案03-07

論量子化學(xué)的應用03-16

量子力學(xué)對經(jīng)典科學(xué)世界圖景的變革03-05

量子思維方式的產(chǎn)生、特征及其對當代社會(huì )的啟示03-14

量子關(guān)聯(lián)從雙模光場(chǎng)到電子干涉器件轉移的研究03-07

作業(yè)成本計算法與傳統成本計算法的比較與運用03-22

腔量子電動(dòng)力學(xué)中的密集編碼方案研究03-07

自由空間量子通信誤碼率和傳輸率分析03-07