Grover量子搜索算法与应用

濮荣强，居水荣，李艳午

（1.江苏信息职业技术学院 微电子学院，江苏 无锡 214153；2.芜湖职业技术学院 基础部，安徽 芜湖 241003）

0 引言

通常经典算法从N个排序随机的数据库查找标记项数据，采用遍历搜索直到找到标记项数据为止，平均寻找N/2次、成功概率仅为1/2，算法时间复杂度为O(N)，而Grover 量子搜索算法只需寻找次搜索、成功概率却为1，时间复杂度仅为，相对遍历算法有平方级的加速［1-2］。

Grover量子搜索算法属非结构化数据搜索，相对遍历式搜索的经典算法有二次加速功能，其解决从N个随机排序的数据库快速查找标记项数据问题，如在数据库里查找特定的IP地址、棋牌游戏的最优策略与破译DES密码等，除搜索时间远短于经典搜索算法外，其强大之处在也适用于矩阵和图形处理、机器学习优化与数据挖掘应用等［3］。

Grover量子搜索算法特征是忽略被搜索数据的通用性质，把注意力放在标记项数据上，通过制备量子态、对标记项数据进行相位翻转并放大概率振幅，从初始状态出发，迭代重复多次变换，让系统逐次逼近标记项数据；因为Grover量子搜索算法采用符合验证条件的方式而不是线性查找的方式，最后能以很高的概率得到正确结果［4］。

为理解Grover量子搜索算法实现的二次加速功能机制，这里对Grover量子搜索算法里的幺正增幅矩阵构造与特性进行完备论证，应用幺正增幅算符对2 位量子比特进行标记项数据的搜索，详尽地讨论Grover 量子搜索算法的门线路实现与存在问题，凝炼总结Grover 量子搜索算法特性与在非结构化数据搜索上潜在应用。

1 Grover量子搜索算法的特性

在量子力学的幺正演化框架内，幺正变换的特征是既不改变算符的本征值也不改变相应矩阵的迹；幺正矩阵U满足UU+=U+U=I，其共轭转置U+也是其的逆矩阵U-，幺正算符的乘积是幺正算符，任何幺正变换可用有限个基本量子逻辑门组合来构造，幺正变换的逆变换也是系统的幺正变换，属无信息擦除信道，除使量子计算系统具有可逆性，其能耗理论上为零。

1.1 幺正增幅矩阵D 的构造与特性论证

针对vi的情况，讨论如下：

当vi＜0 时，则V的第i个分量的增量为Δvi=DVi-vi=2A-2vi ＞0，此时意味着V的第i个分量的符号取相反数后，几率幅增加。

当vi ＞0 时，再分2种情况，一方面若vi ＜A，则V的第i个分量的增量为Δvi=DVi-vi=2(A-vi)＞0；另一方面，若vi ＞A ＞0，则V的第i个分量的增量为Δvi=DVi-vi=2(A-vi)＜0，此时DVi=A+A-vi的振幅小于A的振幅，从而小于vi的振幅。

综上，只要向量的分量是负值，经过矩阵D作用后其振幅必然被增大；如向量的分量为正值，且这个分量小于平均值的时候，经过矩阵D作用后其振幅也可以被增大。

1.2 Grover量子搜索算法的应用

这里可以看出在反相算符中，-1是处在矩阵的第2行第2列；

4）被搜索态的Grove幺正算符：

尽管输入态是随机排序的态叠加，但量子操作平行化处理的特征，保证一次化量子操作可同时作用到叠加态上，体现量子计算巨大威力。

2 Grove量子搜索算法的实现

输入信息比特个数n=log2N由随机排序的数据库容量N决定，Grover量子搜索算法的实现如图1：

图1 Grover量子搜索算法的实现

这里把n个1位信息比特的输入，先通过Hadamard门变换为N=2n个的2位量子比特输出：

引入基于Python的开源框架Cirq，其数据结构被专门优化，能让开发者充分地利用NISQ架构，在专用处理器上实现Grover量子搜索算法门线路模拟，可以为量子门线路的优化提供技术支持与保证［12-13］。

量子相干性是指量子态之间叠加或纠缠关联，而退相干却易使系统的量子态变迁为经典态，因量子态存在的微观界至少是宏观界10-6数量级，而量子计算则需N个量子态，如何制备出相干时间可任意长、错误率小于阈值的容错量子态，提高量子系统的鲁棒性，是量子计算目前面临的最大挑战。鉴核自旋与外部环境相性已可保持时间1.4 ms，使Grover量子搜索算法可在核磁共振（NMR）系统中实现，在NMR中已制备出赝纯态，使得在失去量子相干性之前，可通过量子门操作完成量子计算［14］。

Grover提出的固定点量子搜索算法，因存在量子纠缠加速因素，使得无论迭代多少次，量子态始终向目标态收敛，尤其在精确Grover量子搜索算法被提出后，它作为原始Grover算法的扩展，在保持平方加速的同时，最终能以100%的概率输出标记项［15］。

3 总结

量子计算云是提供算力服务的平台，量子计算软件作为连接量子硬件与用户的界面，其中幺正操作需按既定的量子算法进行量子化编程，对量子态进行操控、观测、模拟演化过程，如IBM Qiskit、Google Cirq等。Grover 量子搜索算法提出后，也进行如量子振幅放大、图上量子游走搜索、不动点量子搜索的扩展，除具备巨大的平行处理能力，Grover量子搜索算法特征是：因搜索概率本身是波动函数，当搜索次数N继续增加，使搜索概率先减少，然后再上升而反复波动，因此存在最佳搜索次数，这也是与遍历型经典搜索算法最为特色的不同点。

通过对量子态进行幺正变换，放大被搜索态的量子振幅值、再反复迭代，使得在观测时候可以很大的概率得到被搜索态，Grover量子搜索算法解决无序排列的非结构化数据库搜索问题。从Grover量子搜索算法衍生出幅度放大思想，提供遍历型经典搜索算法无法有效解决的非结构化数据搜索的希望，现今无论是基于连续变量的不动点量子搜索算法还是基于离散变量的多层量子搜索算法，都是精确Grover量子搜索算法研究的重要内容。