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

原标题：Grover量子搜索算法的原理与应用
【Grover量子搜索算法的原理与应用】

文章图片
量子计算机，顾名思义，就是实现量子计算的机器。是一种使用量子逻辑进行通用计算的设备。不同于传统电子计算机，量子计算用来存储数据的对象是量子比特，它使用量子算法来进行数据操作。量子计算机里面有一种著名的量子并行计算的随机搜索“Grover软件算法” ，是由Grover于1996年提出的平方根加速的随机数据库量子搜索算法。搜索算法常用于从N个未分类的记录中找出某个特定的记录。
01
量子随机搜索算法的应用
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算法的其中一个应用。
02
Grover算法
Grover量子搜索算法可以对随机数据库相对经典搜索平方根加速，为了实现这样的加速， Grover算法主要依赖于量子态的叠加。
假设我们有N个未经排序的数据。如果使用经典算法寻找其中的某个数据x ，条件是它（并且只有它）满P(x)=TRUE ，比方说x代表一个人的工号， P(x)是看他是不是现任CEO 。那么你只能从第一个数据开始，一个一个地看它是不是CEO的工号，直到你瞎猫碰上死耗子。使用经典算法寻找其中的某个数据x的方法图解如下图1-32所示。
在这种算法中，计算复杂度是O(N) 。

文章图片
▍图1-32使用经典算法寻找其中的某个数据x
在Grover算法中，我们可以将N个数据同时储存在log2N个量子比特中，然后同时计算N个函数P()的取值，也就是同时看它是不是CEO的工号。图解见下图1-33所示。

文章图片
▍图1-33Grover算法将N个数据同时储存在log2N个量子比特中
在N个计算结果中，必然有1个结果是CEO的工号，其他结果都不是。但如果你这个时候贸然去“读取”结果，就会发现，每个结果发生的概率都是1/N 。图解见下图1-34所示。
这就好比你用↑偏振镜去测量↗光子，得到↑和→的概率各为1/2 。

文章图片
▍图1-34贸然去“读取”结果，每个结果发生的概率都是1/N
Grover算法的思想是，同时计算了N个P()的取值后，先不要读取，而是通过量子操作略微增加结果为CEO工号的那个数据发生的概率。图解见下图1-35所示。

文章图片
▍图1-35同时计算了N个P()的取值后，先不要读取