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

2020-12-23 18:03

光子盒研究院出品

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

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

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

什么是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算法的优越性体现的越明显。

1 2 下一页>