Grover算法與滑塊碰撞的相似性

李開瑋

(廣東理工學(xué)院 智能制造學(xué)院，廣東 肇慶 526100)

量子搜索中，Grover算法是一個非常重要的搜索算法，相對于經(jīng)典搜索算法而言，有平方加速的效果，在量子計算中，量子態(tài)處于一些基態(tài)(基矢量)的疊加態(tài)中，在運(yùn)算時會同時對整個疊加態(tài)作矩陣運(yùn)算，測量時只能有一定的概率得到想要的基態(tài)，Grover算法的核心是不斷增大想要的基態(tài)概率幅，減小其他基態(tài)概率幅，當(dāng)目標(biāo)基態(tài)的概率幅接近1時，再作測量就可以精確得到搜索結(jié)果[1].對量子態(tài)作矩陣運(yùn)算，其過程非常類似于滑塊碰撞中的處理方法[2-3].接下來首先分析Grover算法，再比較其與滑塊碰撞的相似特點(diǎn).

1 Grover算法

對于n個量子比特的非結(jié)構(gòu)化數(shù)據(jù)庫中，有N=2n個量子基態(tài)|i〉，i=1,2,…,N，其中有一個目標(biāo)態(tài)|τ〉滿足黑盒(Oracle)函數(shù)f(i)=1，量子搜索算法即是以盡可能大的概率找到目標(biāo)態(tài)|τ〉，Grover算法的步驟是這樣的，首先制備均勻態(tài)，使每個基態(tài)的概率幅相等

(1)

然后利用Oracle識別并給目標(biāo)態(tài)|τ〉標(biāo)記，使|τ〉的概率幅取反，Oracle算符為：

(2)

其次利用G算符將疊加態(tài)關(guān)于|φ〉翻轉(zhuǎn)，使所有基態(tài)的概率幅關(guān)于概率幅均值翻轉(zhuǎn)，目標(biāo)態(tài)的概率幅將會增大，其他基態(tài)的概率幅減小，G算符為：

(3)

接下來重復(fù)迭代(2)、(3)若干次將會以幾乎為1的概率測得目標(biāo)態(tài)|τ〉.

為了方便描述，如圖1所示，將非目標(biāo)態(tài)加起來，將

圖構(gòu)造的正交坐標(biāo)系

(4)

(5)

圖迭代運(yùn)算圖像

2 與滑塊碰撞的巧合

經(jīng)典力學(xué)中滑塊碰撞問題如如圖3所示，水平光滑的地面上放置小木塊m和大木塊M，左端是固定的墻壁，初始時刻m靜止，M以初速度v0向左運(yùn)動，將與m發(fā)生碰撞，之后m獲得速度向左運(yùn)動，將與墻壁發(fā)生碰撞反彈，假設(shè)所有碰撞均沒有能量損失，求碰撞次數(shù).

圖3 滑塊碰撞示意圖

圖4 兩滑塊連續(xù)碰撞速度坐標(biāo)變換

3 結(jié)語