Grover量子搜索算法的原理与应用

量子计算机，顾名思义，就是实现量子计算的机器。是一种使用量子逻辑进行通用计算的设备。不同于传统电子计算机，量子计算用来存储数据的对象是量子比特，它使用量子算法来进行数据操作。量子计算机里面有一种著名的量子并行计算的随机搜索“Grover软件算法”，是由 Grover 于 1996 年提出的平方根加速的随机数据库量子搜索算法。搜索算法常用于从 N 个未分类的记录中找出某个特定的记录。

量子随机搜索算法的应用

Grover提出的量子搜寻算法是一种量子计算的经典算法，它适用于解决如下问题：从 N个未分类的客体中寻找出某个特定的客体。

经典算法只能是一个接一个地搜寻，直到找到所要的客体为止，这种算法平均地讲要寻找 N／2次，成功几率为1／2,而采用Grover的量子算法则只需要 Nkk√次（即N开kk次方）。

例如，要从有着100万个号码的电话本中找出某个指定号码，该电话本是以姓名为顺序编排的。经典方法是一个个找，平均要找50万次，才能以 1／2几率找到所要电话号码。Grover的量子算法是每查询一次可以同时检查所有100万个号码。

由于100万量子比特处于叠加态，量子干涉的效应会使前次的结果影响到下一次的量子操作，这种干涉生成的操作运算重复1000（即 N √ ，N开根号）次后，获得正确答案的几率为1／2。但若再多重复操作几次，那么找到所需电话号码的几率接近于1。

Grover算法的用途很广，可以寻找最大值、最小值、平均值等，也可以用于下棋。最有趣的是可有效地攻击密码体系，如 DES体系，这个问题的实质是从n=256≈7×1016个可能的密钥中寻找一个正确的密钥。若以每秒100万密钥的运算速率操作，经典计算需要1000年，而采用Grover算法的量子计算机则只需小于4分钟的时间。

针对对称（私钥）加密，如AES加密算法，只能进行暴力破解，而传统计算机的破解时间为指数时间，更准确地说，是依据其中密钥的长度。而量子计算机可以利用Grover算法进行更优化的暴力破解，其效率更高，量子计算机暴力破解AES-256加密的效率跟传统计算机暴力破解AES-128是一样的。

展开全文

更广泛而言，Grover算法是一种量子数据库搜索算法，相比传统的算法，达到同样的效果，它的请求次数要少得多。对称加密算法的暴力破解仅仅是Grover算法的其中一个应用。

Grover 算法

Grover量子搜索算法可以对随机数据库相对经典搜索平方根加速，为了实现这样的加速，Grover算法主要依赖于量子态的叠加。

假设我们有N个未经排序的数据。如果使用经典算法寻找其中的某个数据x，条件是它（并且只有它）满P(x)=TRUE，比方说x代表一个人的工号，P(x)是看他是不是现任CEO。那么你只能从第一个数据开始，一个一个地看它是不是CEO的工号，直到你瞎猫碰上死耗子。使用经典算法寻找其中的某个数据x的方法图解如下图1-32所示。

在这种算法中，计算复杂度是O(N)。