新突破！造价30亿欧元的大型强子对撞机成功运行Grover算法

光子盒研究院出品

在上个月，欧洲核子研究组织（CERN）报道了一篇关于量子搜索算法在造价30亿欧元的大型强子对撞机（LHC）高能物理数据中的应用。

科学家们展示了Grover量子搜索算法的一种新应用，在CERN大型强子对撞机13 TeV开放数据下，搜索质子-质子碰撞中的罕见情况。最终，在搜索碰撞数据集过程中发现了四个轻子，这证明了Grover算法可以在未排序的数据集中可以进行正确的选择。

这一案例展示了量子计算在高能物理中的广阔前景。

CERN大型强子对撞机内部

什么是Grover量子搜索算法？

继Peter Shor于1994年提出Shor算法后，Lov Kumar Grover于1996年提出Grover算法，这一算法被认为是量子计算中的第二个主要算法（第一个是Shor算法）。

由于Grover算法没有使用具体问题的特殊结构信息,因此它是一种通用的算法，提供了一个普适的框架。

具体算法如下：

（1）初始化。应用Oracle算子 ，检验搜索元素是否是求解的实际问题中需要搜索的解。

（2）进行Grover迭代。将结果进行Hadamard门变换。

（3）结果进行运算。

（4）结果进行Hadamard门变换。

Grover量子搜索算法能够实现在未整理数据库中对满足条件的目标成功搜索，并对计算复杂度为NP的问题有重要加速作用，实现了数据检索的二次加速。

搜索数据库是计算机科学中的一项基本任务，它涉及从查找电话号码到破解密码的所有工作。因此，任何提速都是一项重大进步。

1999年，Zalka等人更是证明了Grover算法为最优量子搜索算法。

涉及到搜索问题，其主要任务是从一个巨大的无序数据库当中能高效的找到满足特定要求的元素或由某些特定元素构成的元素子集。我们知道，验证一个给定的元素或子集是否满足特定要求是相对容易的，但是从一个巨大的无序数据库当中找到这些满足特定要求的元素或子集就不是那么容易了，特别是随着数据库的增大，搜索任务会更加艰巨。

在经典算法中，要从一个无序数据库中找出满足特定要求的元素或子集，一般是对所有元素进行逐个顺序检查，把满足特定要求的元素或子集筛选出来，比如一个元素容量为N的数据库，由于经典搜索算法执行步骤n与数据库中元素数目N一般成线性正比例关系，所以要找到满足特定要求的元素，平均地需要对这个数据库进行N/2次查询，最坏的情况下，需要对这个数据库进行N次查询。这样会导致算法搜索效率不高，而且浪费计算资源。

直到Grover提出了基于量子计算并行性原理的量子搜索算法。该算法只需要对这个无序数据库进行次查询，就能以接近于100%的概率把满足特定要求的元素或子集找出来。由此可见，与经典算法相比，Grover量子搜索算法的效率是非常高的，而且随着N越大，Grover算法的优越性体现的越明显。

验证与迭代

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