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

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

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

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

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