验证与迭代

1998年，Cuang I． L． 等人利用核磁共振（NMR）技术完成了两个量子比特的Grover算法的演示性实验。当N＝4时（两个量子比特）时，在经典搜索中，平均要尝试9／4次才能成功，而NMR实验表明，量子搜索仅一次就可找到目标。

2000年，Brassard G等人利用振幅放大加速搜索过程；2006年，Phaneendr H．D等人提出了利用Grover算法攻击三重DES算法；2007年，Younes A提出了固定相位Grover算法，将成功概率提升到98％以上。

2009年，Yu Dong Zhang等人针对Grover算法成功概率随解数的增加而降低的问题，提出了基于扩大搜索空间的改进算法。2010年，叶峰在对AES算法的密钥搜索算法进行了量子线路设计，成功使用量子搜索算法攻击AES算法。

2013年，研究者将Grover算扩展到机器学习领域，如Aimeur E等人提出了快速寻找聚类算法中最大距离点的方法，该方法核心是利用Durr C等人提出的Grover变体算法，快速寻找到数据集中距离最远的两点。

2017年，Chakrabarty I等人在Grover算法的基础上，提出了一种动态的量子搜索算法，算法通过将原始的静态选择函数替换为动态选择函数来处理非结构化数据库，使Grover算法的应用扩展到随机搜索算法领域。

除了在量子计算机上可以验证Grover算法，如今量子仿真作为量子算法研究最有力的手段和工具，也成为实现Grover算法的途径之一。

2013年，吕相文等人利用GPU开展的量子仿真实验，提出了两种关于Grover算法特征的仿真工作流程方案，实现了存储空间和存储器访问的优化，仿真了最高25量子比特的Grover量子搜索算法，仿真加速比达到了23倍。

随着IBM、英特尔、微软、谷歌、阿里巴巴、百度、华为等国内外科技巨头相继发布量子计算云平台，实现Grover算法的平台和途径也在逐渐增多。

不足与缺陷

Grover算法在应用中也有它的局限性，尽管极具应用潜力，但是由于涉及重大的技术挑战，实施Grover算法仍然需要时间。第一台能够实现它的量子计算机于1998年问世，但第一台可扩展版本直到2017年才出现。

Grover量子搜索算法是一个近似算法，它的成功概率并不是100％。当搜索目标大于数据库记录数的1／4时，搜索成功的概率快速降低；当搜索的目标大于数据库记录数的一半时，搜索彻底失效。

另外，Grover自己在做相位推广时犯了错误，即允许两个相位取反为任意相位转动。

虽然学者们对其己经做了很多的研究并取得了大量成果，但仍不能满足时代的需求。现阶段主要从以下几个方面对Grover算法进行了研究：

1．针对Grover算法的缺点，提出解决这个缺点的改进算法：

就在Grover发表他的研究成果几年后，班加罗尔印度科学研究所的Apoorva Patel解释了：当有四个选择时，使用Grover算法可以在一步中区分四个选择，也就是在四个选择里搜索一个的准确率是100％。

而在其他搜索过程中，如在结构化搜索中，总的成功率是每个成分的搜索成功率的乘积，这成功率相乘下来后，失败概率就非常大了。

而Grover自己在做相位推广时做了误判，他认为将两个相位取反换成任意相角转动皆可构造量子搜索算法，但采用其他角度时效率较低，最好选择180度。

后来，清华大学龙桂鲁团队通过大量的推理论证，最终得到了与Grover推断完全相反的结果。

1999年，龙桂鲁等人指出在Grover量子搜索算法中使用任意的相位旋转时，若想以较高的概率得到想要搜索的目标项，则两次旋转相位的取值必须满足一定的匹配条件：目标项的旋转相位与非目标项的旋转相位须彼此相等。

2004年，龙桂鲁等人随后提出满足相位匹配条件的零失误率的Grover算法，该算法通过将反转相位转化为与数据库大小相关的角度，来提高算法的成功率。

2．基于Grover算法，利用新的量子工具，设计新型的量子搜索算法：

Korepin等人提出了用于部分搜索的量子算法，这个算法降低了算法的迭代次数。

周日贵等人提出了多模式高概率的量子搜索算法，该算法能以高概率解决量子神经网络中的多模式问题。

3．将Grover算法应用到其他领域，去解决类似的问题：

学者们针对不同的问题提出了很多优化，如最小值问题、排序问题、最短路径问题和图像检索等问题。

近年来，研究人员将Grover算法广泛应用于机器学习领域中，提出了很多相关的量子机器学习算法。

主要应用

Grover算法的实现相对量子傅里叶变换来说要简单得多，而且它对于无序数据集的搜索问题，如果忽略常系数，则属于最优的算法之一。

更重要的是量子系统要与外界环境耦合，极不稳定，消相干是指数级的，因此量子力学计算机对外界扰动是极其敏感的。这样一来，在存在大量噪音的环境中要想使系统正常工作，就更需要考虑算法的鲁棒性。

Grover指出，对某些扰动，他的量子搜索算法可以具有一定的鲁棒性。由于实现简单、具有鲁棒性，Grover算法现已广泛应用于各种问题。

密码破译

Grover算法不仅可应用于求解图的着色、子集和最短路径和排序等问题，还可应用于破译密码学中的DES（数据加密标准）密码体系，在搜索密码系统的密钥方面有很大的潜能。

安全通信

2010年，Wang，C等人提出了一个基于Grover量子搜索算法的量子直接通信方案。该方案采用双量子比特作为初态，秘密信息通过双量子比特酉运算进行编码和译码，并且两个通信方Alice和Bob可以直接进行信息交换。

2012年，Tseng，H．Y等人提出了基于Grover量子搜索算法的受控量子确定性安全通信协议（CDSQC），该协议具有信息传输效率高和量子存储器少等优点，而且在噪声环境下该协议也能有效抵制来自外部的窃听者。

优化问题

优化问题是一个非常普遍的领域，量子算法有望显著提高计算速度，虽然Grover算法只是得到平方增长，但是它和其推广还可用于提升优化问题的性能，包括模式匹配、全局优化、三元可满足性和最小值等问题。

这一领域的应用潜力极大，因为与物流、投资组合管理、原料计划和电信网络管理等非常广泛的业务问题紧密相关。

机器学习

现阶段Grover算法多应用于机器学习领域，衍生出非常多的新型的量子算法，例如量子分裂聚类算法、量子联想记忆、量子神经网络和量子K均值聚类等。

其中，很多量子机器学习算法以Grover算法为基础提高了经典算法的速率，并且在其他领域有着非常广泛的应用。

值得注意的是，Grover算法虽然没有使算法的时间复杂度从指数级降低为多项式级，但其加速效果仍然相当可观，并且由于搜索问题在日常生活中的广泛应用，Grover算法的前景值得期待。

－End－

1930年秋，第六届索尔维会议在布鲁塞尔召开。早有准备的爱因斯坦在会上向玻尔提出了他的著名的思想实验——“光子盒”，公众号名称正源于此。