量子搜索Grover算法与滑块碰撞的相似性

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李开玮.利用速度相图法求解多次连