量子搜索Grover算法與滑塊碰撞的相似性

1、量子搜索Grover算法與滑塊碰撞的相似性李開(kāi)瑋 張智明廣東理工學(xué)院 智能制造學(xué)院，廣東 肇慶 526100摘要：Grover算法是量子搜索計(jì)算中一個(gè)重要的算法，自提出來(lái)后受到廣泛的關(guān)注和應(yīng)用， Grover算法的計(jì)算迭代次數(shù)近似為，而在經(jīng)典力學(xué)中一個(gè)滑塊碰撞問(wèn)題中，碰撞次數(shù)近似為，兩個(gè)結(jié)果中均有，計(jì)算過(guò)程存在許多相似之處，本文分析對(duì)比兩種計(jì)算過(guò)程，使學(xué)生增加對(duì)量子計(jì)算的理解。關(guān)鍵詞：Grover算法；迭代次數(shù)；滑塊碰撞量子搜索中，Grover算法是一個(gè)非常重要的搜索算法，相對(duì)于經(jīng)典搜索算法而言，有平方加速的效果，在量子計(jì)算中，量子態(tài)處于一些基態(tài)（基矢量）的疊加態(tài)中，在運(yùn)算時(shí)會(huì)同時(shí)對(duì)整個(gè)疊加態(tài)

2、作矩陣運(yùn)算，測(cè)量時(shí)只能一定的概率得到我們想要的基態(tài)，Grover算法的核心是不斷增大我們想要的基態(tài)的概率幅，減小其他基態(tài)的概率幅，當(dāng)目標(biāo)基態(tài)的概率幅接近1時(shí)，再作測(cè)量就可以精確的得到我們的搜索結(jié)果1。在對(duì)量子態(tài)作矩陣運(yùn)算，其過(guò)程非常類似與滑塊碰撞中的處理方法2,3。接下來(lái)首先分析Grover算法，再比較其與滑塊碰撞的相似特點(diǎn)。1 Grover算法對(duì)于n個(gè)量子比特的非結(jié)構(gòu)化數(shù)據(jù)庫(kù)中，有個(gè)量子基態(tài)，其中有一個(gè)目標(biāo)態(tài)滿足黑盒（Oracle）函數(shù)，量子搜索算法即是以盡可能大的概率找到目標(biāo)態(tài)，Grover算法的步驟是這樣的，首先制備均勻態(tài)，使每個(gè)基態(tài)的概率幅相等 （1）然后利用Oracle識(shí)別并給目標(biāo)態(tài)

3、標(biāo)記，使的概率幅取反，Oracle算符為 （2）然后利用G算符將疊加態(tài)關(guān)于翻轉(zhuǎn)，使所有基態(tài)的概率幅關(guān)于概率幅均值翻轉(zhuǎn)，目標(biāo)態(tài)的概率幅將會(huì)增大，其他基態(tài)的概率幅減小，G算符為 （3）接下來(lái)重復(fù)迭代（2），（3）若干次將會(huì)以幾乎為1的概率測(cè)得目標(biāo)態(tài)。為了方便描述，如圖1所示，將非目標(biāo)態(tài)加起來(lái)，與聯(lián)合建立一個(gè)二維正交坐標(biāo)系，初始態(tài)與，幾何關(guān)系如圖所示，其中， （4）式（2），式（3）的算符均為酉矩陣，在迭代運(yùn)算過(guò)程中，量子疊加態(tài)始終在圓上運(yùn)動(dòng)，設(shè)某時(shí)刻疊加態(tài)為，經(jīng)過(guò)Oracle算符后 （5）在圖像上效果為關(guān)于水平坐標(biāo)軸的翻轉(zhuǎn)，接下來(lái)作用G算符，關(guān)于翻轉(zhuǎn)，如圖2所示，這樣一次迭代之后等效于將逆時(shí)針旋轉(zhuǎn)

4、，經(jīng)過(guò)若干次迭代，將逼近，迭代次數(shù)為。圖1 ，構(gòu)造的正交坐標(biāo)系圖2 迭代運(yùn)算圖像由式（4）可得，代入迭代次數(shù)的式子，當(dāng)N非常大時(shí)，迭代次數(shù)近似為。2 與滑塊碰撞的比較如圖3所示為滑塊碰撞兩物體的速度變換圖像2，橫坐標(biāo)代表重滑塊，縱坐標(biāo)代表輕滑塊，初始狀態(tài)為A點(diǎn)，靜止，以初速度向左運(yùn)動(dòng)，在運(yùn)動(dòng)過(guò)程中，兩滑塊總能量始終不變，因此碰撞發(fā)生時(shí)，兩滑塊坐標(biāo)在圓上移動(dòng)，虛線表示，其斜率為，當(dāng)兩滑塊間發(fā)生碰撞，如AB，CD，碰撞前后兩點(diǎn)關(guān)于虛線對(duì)稱，當(dāng)與墻壁發(fā)生碰撞，如BC，碰撞前后兩點(diǎn)關(guān)于水平軸堆成，由圖像可以知道，滑塊間，滑塊與墻壁發(fā)生碰撞（A-B-C）后位置矢量沿順時(shí)針旋轉(zhuǎn)了。該過(guò)程與量子搜索是極其相

5、似的，對(duì)應(yīng)著，目標(biāo)態(tài)對(duì)應(yīng)，量子態(tài)關(guān)于的翻轉(zhuǎn)對(duì)應(yīng)輕滑塊與墻壁的碰撞，量子態(tài)關(guān)于的翻轉(zhuǎn)對(duì)應(yīng)兩滑塊間的碰撞，碰撞問(wèn)題中的截止條件為到達(dá)圖3陰影區(qū)域，碰撞不再發(fā)生，量子搜索的問(wèn)題截止在到達(dá)縱坐標(biāo)最大位置即，兩個(gè)問(wèn)題的運(yùn)算方法是一致的，具有相通性。圖3 兩滑塊連續(xù)碰撞速度坐標(biāo)變換3 討論與結(jié)語(yǔ)Grover算法與經(jīng)典力學(xué)中滑塊碰撞問(wèn)題的計(jì)算具有相通的特點(diǎn)，這說(shuō)明了物理中不同領(lǐng)域的知識(shí)具有一定的關(guān)聯(lián)，方法工具具有某種一致性。在滑塊碰撞問(wèn)題中，目標(biāo)是得到碰撞次數(shù)和最終的狀態(tài)，通過(guò)不斷的迭代計(jì)算和截止條件的判斷，總能得到答案，但在Grover算法中，目標(biāo)是找到搜索結(jié)果，使的概率逼近1，而與不一定是整數(shù)倍關(guān)系，成功率并不是100%，清華大學(xué)的龍桂魯在Grover算法上作了一些改進(jìn)，使搜索成功率達(dá)到了100%4。參考文獻(xiàn)1Grover L. A fast quantum mechanical algorithm for database search. In: Proc. 28th annual ACM Symposium on Theory of Computing, ACM, New York, 1996. 212-219.2李開(kāi)瑋.滑塊碰撞次數(shù)與圓周率的聯(lián)系J.物理教師,2021,42(01):63-64.3李開(kāi)瑋.利用速度相圖法求解多次連