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

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

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

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

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

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