User:Subgradient/葛羅佛算法

Grover算法 是一种 量子算法 ；它只需要执行O({\sqrt {N}}) 次某个黑盒函数，就能以很高的概率的概率找到使黑盒函数找到产生某个特定输出的输入（N是黑盒函数的定义域大小）。它由 Lov Grover 在1996年提出。

经典计算机不能在不到 O(N)次执行内解决类似的问题（因为在最坏的情况中，第N个定义域的成员才是正确的解）。在Grover发表算法的大约同一时间，Bennett，Bernstein，Brasard以及Vazirani证明了，没有量子算法可以在 ${\displaystyle }$ 次执行内解决这个问题；因此Grover算法是 渐进的最佳的。

已经证明，非局域隐变量的量子计算机可以用至多 {\displaystyle O({\sqrt[{3}]{N}})}步实现对有N个元素的数据库的搜索。 这比Grover算法所需要的 ${\displaystyle }$ 步要快。

以上的两种搜索方法都不能让量子计算机在多项式时间内解决 NP-完全问题。 不同于其他可以提供指数加速的量子算法，Grover的算法，只提供了平方级的加速。 然而，平方级的加速在 ${\displaystyle }$ 很大的时候也是可观的。 Grover的算法可以在大约2^{64} 次迭代 暴力破解 128位对称加密密钥，或者在大约2^{128} 次迭代内破解256位的密钥。 因此，对称加密密钥被有时被建议将称密钥长度增加一倍，以防止未来的量子攻击。

像许多的量子算法一样，Grover算法（在提供正确答案的 概率 小于1的意义上）是概率性的。 尽管技术上来说，获得正确答案所需的重复次数没有上界，但是重复的数量的数学期望是一个不会随 ${\displaystyle }$。 Grover在原始的论文中将其描述为数据库搜索算法；这个说法仍然是常见的。 这个比喻中的数据库指的是一个包含函数所有输出、以相应输入为索引的表。

应用

虽然目的Grover的算法通常被描述为"搜索数据库"，就可以更准确地将它描述为"反转功能的"。 大致说来，如果我们有一个功能 ${\displaystyle }$ 可评估的量子计算机，Grover的算法我们可以计算 ${\displaystyle }$ 当给 ${\displaystyle }$中。 反转功能是有关搜索的数据库，因为我们可以想出了一个功能，产生一个特定的价值 ${\displaystyle }$ ("真正的"为例)，如果 ${\displaystyle }$ 匹配所需的条目数据库中，而另一个的价值 ${\displaystyle }$ ("虚假")，用于其他价值观的 ${\displaystyle }$中。

Grover算法还可用于估计一组数字的 平均 和 中位数 ，以及解决 碰撞问题。如果有多个解，并且解的数量已知，这个算法可以进一步优化。 Grover的算法也可用来破解密码。

注意到

[[Category:量子演算法]] [[Category:搜尋演算法]]