量子計算的新特點

量子計算的新特點

1光子計算機的應用計算方程的過程是算子系統(tǒng)的量化子態(tài)的演化過程。由于量子態(tài)具有量子干涉和量子糾纏性質,使量子計算有許多不同于經典計算的新特點。經典上不同的物理態(tài)可以干涉疊加形式存在于量子計算機中,量子位之間的糾纏建立了量子“信道”,使量子計算可以沿著經典上許多不同的路徑并行進行。巧妙地利用量子計算機的這些性質,可以做出經典計算機不可能做到的事。旅行售貨員問題(TSP問題)一個典型的、易于描述的卻難以處理的NP完全問題。假定有N個城市,旅行推銷員希望找出一條行遍所有城市的路線,使總旅程最小。解這個問題的一個方法是列出連結N個城市的所有路線,從中挑出最短的一條。這種做法在當N比較小時還可行得通。事實上,對N個城市,可以有N!條旅行路線,由于,列出所有可能的路線就導致一個指數(shù)時間算法。2．態(tài)分布的意義在數(shù)學上TSP問題可用一個函數(shù)g=min(N,E)表示,其中N代表城市,E為路徑,g代表所求的最短旅程。ei為第i條邊的值,共有m條邊,將每一邊的值轉換成因此,。假設一個量子系統(tǒng)由N個粒子組成,分別由許多不同的態(tài)矢|φi>,i=1,2,3Λ,m描寫的子系統(tǒng)構成,每個子系統(tǒng)在該系統(tǒng)中以確定的概率出現(xiàn),因此這個系統(tǒng)可以通過指定各子系統(tǒng)的態(tài)矢|φi>,以及這個子系統(tǒng)在系統(tǒng)中出現(xiàn)的概率描述(|φ1>,p1)、(|φ2>,P2)…(|φi>,pi)…(|φm<,pm)其中,概率pi對應于邊的值,這m個態(tài)矢{|φi>,}構成正交歸一集,由它們可以構成一個疊加態(tài)Ci為展開系數(shù)。TSP問題變成在所有可能的疊加態(tài)|ψ>中搜索一個特定的疊加態(tài)|g>的過程。下面論證這種變換的合理性。求解TSP問題是將m維輸入表象A與n維的輸出表象B的變換。A表象基矢為{|am>},B表象基矢為{|bn>},由上面的處理可知A表象中滿足的完備性條件,現(xiàn)考慮任意態(tài)矢|Φ>在這兩個表象中的聯(lián)系。上式也可寫為Φ(B)=SΦ(A),其中Ф(B)、Ф(A)分別是|Φ>在A表象、B表象中的表示,S是L行N列的矩陣,矩陣元Smn=<bn|am>,由于,所以這表明態(tài)矢在不同表象之間的變換是通過么正變換進行的,且維數(shù)可以不同。假設每一種可能的態(tài)矢為|x>。給出一個量子黑盒,當找到這個態(tài)g時,g=1,當結果不是g時,g=0。假設黑盒是量子的,它可以接受疊加形式的輸入態(tài),并做出響應。這個黑盒執(zhí)行么正變換Ug其中|x>是n位態(tài),|y>是單量子態(tài)。我們可以選擇單量子位態(tài),從而量子黑盒的作用是可以得出Ug|x>=(-1)g|x>,所以Ug的作用是改變態(tài)g的位相π,但對任何與|g>正交的態(tài)不作用。這一變換可用投影算子記為Ug=1-2|g><g|,這一變換有簡單幾何解釋,Ug作用到2n維Hilbert空間中的任一矢量|x>上,就是相對與|g>垂直的超平面反射這一矢量,即態(tài)|x>在超平面上的分量保持不變,但改變沿|g>的分量符號。我們只知道黑盒對某一特殊的計算基|g>執(zhí)行這一反射,但對|g>的值并不知道,我們的任務就是以最少的運算次數(shù)求出g的值。3gro經營迭代算法為求得g值,從第1步對初始態(tài)為|0…0>的n量子們施用H(n)=H?H?Λ?H(共n個),得到所有計算基的等權重疊加態(tài)。我們雖然不知道|g>態(tài)的值,但確實知道|g>是一個計算基態(tài)。所以這表明,如果這時將|s>投影到計算基上,得到態(tài)|g>的概率僅為。Grover迭代算法就是通過反復迭代放大要找的態(tài)|g>的概率幅,同時抑制|x≠g>態(tài)的概率幅。由于態(tài)|s>已知,利用|s>可以構造一個反射Us=2|s><s|-1,它保持態(tài)|s>不變,但反轉任何與|s>正交態(tài)的符號。在幾何上它保持態(tài)|s>的分量不變,但改變與|s>垂直的超平面上的分量符號。結合Ug和Us可構造一個么正變換考慮這個變換對|g>、|s>張開的平面上任一矢量的作用。由于|s>可以看做是由平面上與|g>垂直的矢量|g⊥>轉過θ角。平面上的輸入態(tài)|s>經T次迭代后,將被轉動到與|g⊥>軸成θ+2Tθ角位置上,為了在最后測量時以高的概率得到|g>態(tài),這個角度應接近90°,即對于足夠大的N,,代入上式得經過T次迭代后,向計算基投影測得所求態(tài)|g>的概率是因此得出結論,只需大約次迭代,就可找到最短路徑?？梢缘玫街笖?shù)級的加速。4法的未來研究展望綜上所述可知,TSP問題的核心就是把傳統(tǒng)的找最短路徑轉化為量子環(huán)境下找特定態(tài)矢的問題,從而可以利用量子環(huán)境下特殊性質把時間復雜度由傳統(tǒng)的降低到,這僅僅是量子算法在TSP問題上的一個應用,但它帶來的卓越性能和超常規(guī)的運算速度已經使人興奮不已。雖然真正的量子計算機還沒有出現(xiàn),但通過上面的討論,已經可以看到其美好的前景。目前量子算法的研究正處于一個重大突破的前夜,因為量子計算機的研制在技術上還存在很大障礙。但是,可以預測,由于傳