- 相關推薦
量子算法與量子計算實驗
論文關鍵詞:量子算法 量子計算 量子比特 糾纏
論文摘要:本文介紹了量子計算糾纏和量子比特的基本概念,系統闡述了幾種主要的量子算法:Shor算法———大數質因子分解的量子算法;Grover搜索———無序數據庫的搜索;Hogg搜索———高度結構化搜索。在對量子計算基本理論和量子算法有一定認識的基礎上,進一步介紹了在量子計算實驗方面起重要作用的二種體系:核磁共振、腔與原子體系。
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
量子計算是量子物理與計算機科學交匯而生的一門新興學科。它的出現實質上是量子物理學向物質、能量和信息這三大領地的最后一塊信息領域的進軍。
一、量子計算的基本理論
1、糾纏
1935年,Schr dinger首先給出了糾纏態的定義:由空間分離的兩個子系統構成的純態,如果系統波函數不能分解為兩個子系統波函數的乘積,那么這樣的波函數表示的態稱作兩個粒子的糾纏量子態。1935年,Einstein,Podolsky和Rosen首先討論了一個具體的兩粒子糾纏量子態。在這個著名的實驗中,兩粒子的糾纏量子態為:|Ψ〉=∑a,bδ(a+b-c0)|a|b〉
其中a,b分別為粒子1和粒子2的位置或動量,C0為常數。這個糾纏態的一個最明顯的特征是:其中任何一個子系統的物理量的觀測值(位置或動量)都是不確定的。但是,如果其中的一個子系統的物理量的觀測值處于一個確定的值,那么我們就可以確定另外一個子系統的相應物理量觀測值。
2、量子比特
量子比特有微觀體系表征,如原子、核自旋或光子等。|1>和|0>可以由原子的兩個能級來表示,也可以由核自旋或光子的不同極化方向來表征。與經典比特顯著不同的是,量子比特|1>和|0>之間存在著許多中間態,即|1>和|0>的不同迭加態,例如12(|0>+|1>)表示一個兩子比特同時存儲著0和1。因此,對于位數相同的n個比特,量子比特可以存儲2n倍的經典比特所能存儲的信息。對于兩個量子比特的體系,其完備基由四個布爾態|00>、|01>、|10>和|11>組成�？紤]它們之間的迭加,我們可以發現,|10>+|11>=|1>(|0>+|1>),這是由兩個量子比特構成的直積空間。而|11>+|00>或|01>+|10>則不能再寫成直積形式。后面這種情況就是前面提到的糾纏。對于一個處于糾纏狀態的體系,我們不能確切地指出其中某一個量子比特是處于|1>還是|0>。更一般的糾纏態是處于2n個布爾態的n個經典比特組成的迭加態。|Ψ〉=∑11…1x=00…0Cx|x〉其中Cx可以是復數并且滿足∑x|Cx|2=1。當Cx=12n時,稱為等幅迭加態。這種等幅迭加態在以下要介紹的各量子算法中經常被用作初態。從上式也能看出,|Ψ>是一個2n維的Hilbert空間中的一個單位矢量。它所在空間的維數是隨n呈指數型增長,這明顯區別于經典體系中隨n呈線性增長的態空間。在一個孤立的量子體系中,對態的操作應是幺正的、可逆的。因此,我們構造的量子邏輯門也應滿足這個特征。
二、量子算法
1、Shor算法———大數質因子分解的量子算法
用經典計算機來進行大數質因子分解,隨著N的增大,所需比特數(即內存)是呈指數倍的增長。按照組合數學理論,當計算規模隨著問題的難度呈多項式型增長時,該問題為P(Polynomial)問題。對于P問題,我們在有限的時間內總能找到辦法求得它的解。對于我們在有限的時間內不可能找到辦法求得解的問題稱之為NP(Non-Polynomial)問題。目前世界上應用最廣也是最成功的加密方法-公開密鑰RSA系統的核心思想就是利用大數在有限時間內不可有效質因子化這一結論。1995年,P.W.Shor提出一種量子算法,能將這一著名的NP問題化為P問題,矛頭直指RSA方法,從而在全球掀起了量子計算的研究熱浪。在Shor算法中,尋找一個大數的質因子問題被轉化為尋找其余因子函數的周期。只要該周期被找到,并且為一個偶數,那么利用剩余定理,就能得到該大數的質因子。給定整數N,選取一個與N互質的數a(a 不難看出,fa,N(x)的變化是有規律的,其變化周期為r=4。知道了這個周期,就可以利用孫子定理:設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被成功地質因子化。Shor算法的關鍵在于求出大數N的余因子函數的周期r。不過,由于余因子函數的周期r不能在量子計算中被有效測出,因此在Shor算法中需借助量子離散傅立葉變換,將余因子函數的周期換成另一個可測的周期。
2、Grover搜索:無序數據庫的搜索
Grover提出了一種算法:利用量子態的糾纏特性和量子并行計算原理,可以用最多n步的搜索尋找到所需項。Grover算法的思想極為簡單,可用一句話“振幅平均后翻轉”來概括。具體說來是以下幾個基本步驟:
①初態的制備。運用Hadamard門將處于態|0>和|1>的各量子比特轉化為等幅迭加態。
②設數據庫為T[1,2,,N]共,n項。設其中滿足我們要求的那一項標記為A。于是在T中搜索A類似于求解一個單調函數的根。運用量子并行計算可以將A所在態的相位旋轉180°,其余各態保持不變。即當T[i]=A時,增加一個相位eiπ。
③相對各態的振幅的平均值作翻轉。這一操作由幺正矩陣k1,k2…knD完成,其表達式為Dij=2/N,Dij=-1+2/N。
④以上②③兩步可以反復進行,每進行一次,稱為一次搜索�？梢宰C明,最多只需搜索N次,便能以大于0.5的幾率找到我們要找的數據項。Grover算法提出之后,引起了眾人極大的興趣。Grover算法中的翻轉方法不僅被證明是最優化的搜索方式,而且也是抗干擾能力極強的方法。
3、Hogg搜索:高度結構化搜索
前面介紹過的NP問題中有一類名為可滿足性問題(Satisfiability Problem,簡稱SA T問題)。一個典型的SA T問題是包括有n個變量的一個邏輯公式,要求給予其中每個變量一個賦值使邏輯公式為真。數學上已證明,解決SAT問題的代價是隨著變量數的增加而呈指數型增長。然而對于某些簡單的情況,人們可以利用問題中具有的規則結構來迅速準確地搜索出問題的解。例如對于1-SAT問題,用經典試探法進行搜索,找出解的代價為最多需用n步。對于量子計算而言,由于能進行量子并行計算,因而可以僅以一步的代價找出1-SAT問題的解。下面以有m個邏輯子句的1-SAT問題為例。與Grover搜索相似,我們先在n個量子比特上制備一個等幅迭加態作為初始態,即|Ψ〉=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稱為Hamming距離,d=d(r,s)=|r|+|s|-2|r∧s|,其中|r|和|s|分別表示r字節串和s字節串中含有比特為1的個數。|r∧s|表示r和s中共同含有比特為1的個數。
對于以上1-SAT問題,顯然有m個變量是約束的,而剩余的n-m個非約束的變量則對應于2n-m個解。對于1-SAT問題,用Hogg算法能決定性地一步找到解。如果通過一步邏輯操作未能明確地發現解,則意味著該
問題無解。不難看出,Hogg搜索的效率遠高于上節介紹的Grover搜索。這兩種搜索的差別在于,Hogg搜索利用了數據庫的結構信息,因而能將一個NP問題轉化為P問題。而Grover算法解決不了N P問題,它相對于經典搜索只是提高了搜索效率。Hogg搜索的另一個優勢在于具有強的抗消相干能力。由于它的邏輯步數少,因而消相干效應對其影響非常小。
三、量子計算實驗
與量子計算理論方面的飛速進展相比,量子計算的實驗進展則要慢得多。本章主要介紹二種體系:核磁共振和腔與原子體系。
1、核磁共振(NMR)
核磁共振技術是目前在量子計算領域使用最為頻繁的實驗手段。運用這一技術手段,操作作用在1023數量級的分子系綜的自旋態上,通過測量,得到這些分子的平均自旋態。雖然每個分子的自旋都可能不盡相同,但通過spin-e2cho技術可以按我們的意愿改變個別分子的自旋方向。由于核磁共振體系實質上是一個宏觀系綜,因而外部環境對它的消相干的影響極小。且樣品的核自旋處于近獨立的狀態,幾乎不受電子和分子的熱運動的干擾。但是,宏觀系綜原則上沒有量子特性,只有純粹的量子系綜才具有量子純態的特征。只有當它被制備到一個特殊狀態—贗純態時,才能完成量子計算的工作。下面舉例介紹實現兩量子比特的Grover搜索的實驗。實驗中所用樣品為C-13同位素標記的氯仿HCCL3。實驗中用碳和氫的核自旋來標記|1>和|0>,其中13C的中心共振頻率約為125MHz,1H的中心共振頻率約為500M Hz。實驗體系的哈氏量為H=2πnhJ ICZ IHZ+PH,所以各步驟如Grover搜索所介紹的那樣。比較實驗和理論,可以發現實驗中存在一些誤差。這些誤差主要來自磁場和射頻場的不均勻、初始時間的校正和信號衰減等。
2、腔與原子體系
腔量子電動力學(C-QED)體系是另外一種可以進行量子計算的量子系統。腔量子電動力學體系之所以可以實現對兩位量子信息進行處理量子系統,一個重要原因就是腔中的輻射場與原子具有很強的非線性相互作用,這種相互作用的演化導致腔場和原子體系的本征態處于糾纏態。腔量子電動力學體系包含光腔和微波腔。這里我們主要介紹微波腔體系中應用Rydberg原子與微波腔相互作用實現的條件量子相移門(QPG)。條件量子相移門(QPG)需要對兩量子位的如下變換:
|a,b〉→ex p(i<δa,1δb,1)|a,b〉其中|a>,|b>分別代表兩量子位的基矢|0>或|1>,而δa,1,δb,1為通常的克隆尼克符號。條件量子相移門(QPG)在兩個量子態都處在|1>時,產生一個<角相移,而在其他情況下均保持不變。由于其他任何操作可以應用條件量子相移門(QPG)和單個量子位的旋轉來實現,因而,條件量子相移門(QPG)是一個通用量子邏輯門。我們這里介紹的條件量子相移門(QPG)是用包含0個光子或1個光子的腔場和單個Rydberg原子作為量子位來實現的。控制量子位是0個光子腔場|a>=|0>或1個光子的腔場|a>=|1>而,目標量子位是Rydberg原子的兩個能級|i>(定義|b>=|0>)和|g>(定義為|b>=|1>)。
實驗中應用的Rb原子的能級除了目標量子位兩個Ry2dberg原子的能級|i>和|g>以外,還包括一個相關的能級|e>。三個相關的Rydberg原子態分別代表Rb原子的主量子數n=51(|e>),n=50(|g>)和n=49(|i>)。原子的能級|e>和|g>與微波腔場發生共振相互作用,而原子能級|g>和|i>之間通過另外的微波場產生耦合。當原子處于能級|i>或者腔場處于|0>,原子與腔場的系統狀態不發生變化,而當原子腔場的初始處于|g,1>態時,控制原子的速度使原子|g>與|e>量子態在腔場中經歷一個2π的拉比振蕩,|g,1>態演化為-|g,1>=exp(πi)|g,1>。因而系統的演化可以描述為:|a,b〉→ex p(iπδa,1δ
b,1)|a,b〉這個過程實際實現了相移為π的條件量子相移門(Q P G)。
參考文獻:
①L.Isaac,G.Neil,K.Mark.Experimental Implemen2tation of Fast Quantum Searching[J].Phys.Rev.Lett.1998,
80:3408-3411.
②A.Salomaa著,丁存生,單煒娟譯.公鑰密碼學[M].北京:國防大學出版社,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
【量子算法與量子計算實驗】相關文章：
量子糾纏及其度量03-07
腔量子電動力學中的量子隱形傳態方案03-07
論量子化學的應用03-16
量子力學對經典科學世界圖景的變革03-05
腔量子電動力學中的密集編碼方案研究03-07
自由空間量子通信誤碼率和傳輸率分析03-07