無序數(shù)據(jù)的量子檢索

汪 明

（華東交通大學(xué)，江西 南昌 330013）

Grover檢索法的基礎(chǔ)是量子測(cè)量.首先，定義一個(gè)量子測(cè)量算符Mm，以及他的集合{Mm}，相應(yīng)于N個(gè)需要測(cè)量的值，m=1,2,,,,N.這樣的算符有兩個(gè)要求：（1）所有的算符積都是幺正的，（2）滿足完全性關(guān)系.

這樣就可以得出兩個(gè)結(jié)果：（1）在使用測(cè)量算符Mm測(cè)量到第m個(gè)值的概率是測(cè)量后的態(tài)為.可以使用量子測(cè)量算符中測(cè)量到態(tài)|xm>的概率是p（m）.測(cè)量后的態(tài)是可以忽略[1].

設(shè)定基矢Vn={|0>，|1>}，有|Ψ>=α|0>+β|1>，這是一個(gè)量子比特狀態(tài).

|α|2+|β|2=1，兩個(gè)投影算符M0=|0><0|，M1=|1><1|.當(dāng)使用M0來測(cè)量系統(tǒng)的時(shí)候，|Ψ>投射到（或者說塌縮到，測(cè)量到）基態(tài)|0>的概率是|α|2，（使用M0時(shí)肯定是塌縮不到|1>態(tài)的），那么還有1-|α|2的概率塌縮到了什么樣的狀態(tài)呢？

一般來說，當(dāng)我們使用一個(gè)投射測(cè)量算符Mm的時(shí)候，并不能肯定地說就塌縮到相應(yīng)的狀態(tài)|xm>中，塌縮到相應(yīng)的狀態(tài)|xm>中（即成功的測(cè)量）的概率僅僅是|xm|2，當(dāng)這個(gè)塌縮沒有發(fā)生（概率為1-|xm|2），這個(gè)時(shí)候什么也沒有檢測(cè)到，即測(cè)量失敗，原來的量子狀態(tài)泯滅，原來的量子狀態(tài)中所含的信息不可逆的消失了，定義這時(shí)測(cè)量后的狀態(tài)為|

Grover量子檢索就是基于這樣一個(gè)原理，將一個(gè)厄米算符的n個(gè)本征態(tài)與n個(gè)要檢索的信息一一對(duì)應(yīng)，然后用更好的設(shè)計(jì)的算符來測(cè)量，提高成功的測(cè)量的概率.

Grover算法的描述如下：

設(shè)數(shù)據(jù)庫的大小為N=2n,n是個(gè)非零整數(shù)，定義一個(gè)算符Ω，Ω 有N個(gè)正交的本征態(tài)|x〉，|x〉=|0〉，|1〉，，，|N-1〉，及相應(yīng)的本征值λ0，λ1，，，λN-1.

然后將一個(gè)本征態(tài)或本征值與數(shù)據(jù)庫中一個(gè)數(shù)據(jù)項(xiàng)目聯(lián)系起來，做到本征態(tài)或本征值與數(shù)據(jù)項(xiàng)目的一一對(duì)應(yīng)（|m〉或λm圮數(shù)據(jù)項(xiàng)目m）.現(xiàn)在數(shù)據(jù)搜索問題就變成了搜索我們需要的本征值λm，即搜索|m〉的問題.

定義一個(gè)單位算符Uw=I-2|m〉〈m|,有

將UW作用在|S〉上，得到

可見，UW的作用是將|S〉中|m〉的概率幅符號(hào)改變；也可以理解為將|S〉態(tài)矢轉(zhuǎn)變一個(gè)角度θ，即

當(dāng)N很大時(shí)，角度θ 很小.再定義第二個(gè)算符US，

由此得到Grover算符G=USUW,將Grover算符作用在|S〉上（稱次作用為Grover迭代），得

可以看出，Grover算符G作用在|S〉上的效果是增加本征態(tài)組分|m〉的概率幅，這也可以從角度旋轉(zhuǎn)θ'表示，相應(yīng)的旋轉(zhuǎn)角度為

從上面（7）式的計(jì)算看出，角度θ，θ'的絕對(duì)值相等.現(xiàn)在來計(jì)算|ψ〉與|ψ1〉的角度：

由θ"=2θ 得出，|ψ〉與|ψ1〉是由|S〉矢量處各自向相反方向旋轉(zhuǎn)相同的角度θ 的.現(xiàn)計(jì)算在|ψ1〉態(tài)中基矢|m〉的概率幅,則在態(tài)|ψ1〉中測(cè)量到λm，即系統(tǒng)塌縮到|m〉的概率為

算符UW與G作用在|S〉上的圖形表示.

現(xiàn)在將Grover算符G多次迭代，迭代一次相當(dāng)于將|S〉矢量向|m〉矢量旋轉(zhuǎn)了θ 角度，迭代一次相當(dāng)于增加了成功測(cè)量到λm值得概率.設(shè)k次Grover算符G迭代后|S〉態(tài)變?yōu)閨ψk〉.為了得到|ψk〉，將態(tài)|S〉的表達(dá)式中的|m〉態(tài)分離出來，改寫為

|S〉態(tài)改寫為上述形式后，k次Grover算符G迭代后態(tài)變?yōu)?/p>

（13）式表明，k次Grover算符G迭代后態(tài)矢|S〉向基矢|m〉旋轉(zhuǎn)了角度kθ，在旋轉(zhuǎn)后的態(tài)Gk|S〉中用算符Mm=|m〉〈m|測(cè)量到本征值λm即態(tài)|m〉的概率是

在迭代次數(shù)達(dá)到k=kmax時(shí)，p（m）≈1.這時(shí)，在旋轉(zhuǎn)后的態(tài)Gkmax|S〉中用算符Mm=|m〉〈m|去測(cè)量得到本征值λm的概率接近于1[5].例如數(shù)據(jù)量N≈16000時(shí)，用kmax≈100次的Grover算符G迭代后，再進(jìn)行一次測(cè)量，就能搜索到需要的數(shù)據(jù)項(xiàng)目，計(jì)算復(fù)雜度為比經(jīng)典的數(shù)據(jù)檢索算法的計(jì)算復(fù)雜度為0（N）要降低很多.

〔1〕德敘維勒（Emmanuel Desurvire）經(jīng)典與量子信息論(英文版)[M].北京：科學(xué)出版社，2013.220–236.

〔2〕龍桂魯.Grover 量子搜索算法及改進(jìn)[J].原子核物理評(píng)論,2004(3):114-116.

〔3〕陳洪光，等.逼近全概率Grover 算法的搜索次數(shù)計(jì)算[J].計(jì)算機(jī)編程與應(yīng)用,2004(3):56-61.

〔4〕Nielsen M A,CHUANG I L.量子計(jì)算和量子信息-量子計(jì)算部分[M].北京:清華火學(xué)出版社,2004.

〔5〕Grover L.K, Quantum Mechanics Helps in Searching for a Needle in a Haystack,Phys.Rev.Lett.1997.