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的算法的目的通常被描述为"搜索数据库"，但更准确地说，它应该被描述为"求函数的逆"。 大致说来，如果我们有一个可以在量子计算机上求值的函数 ${\displaystyle }$ ，Grover的算法可以在给定 <math>y</math> 时计算 ${\displaystyle }$ 。对函数求逆和数据库搜索有关，因为我们可以构造一个函数，如果 ${\displaystyle }$ 匹配数据库中的一个所需项目，产生一个特定的值 y (比如"真")；而对于其它的 x，返回另一个值 ${\displaystyle }$ ("假")。

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

设定

考虑一个拥有 N 个条目的无序数据库。 算法需要一个 N-维 态空间 H；这可以用 n =log₂ N 个 量子比特 提供。考虑这样一个问题：寻找满足某些标准的数据库条目的索引。 让 f 是一个将数据库条目映为0或1的函数，且 f(x)=1当且仅当 x 满足搜索标准(x = ω)。我们可以(以量子黑盒的形式)使用一个 幺正算子 U_ω ，其作用为：

${\displaystyle }$

 U_ω 的另外一种定义如下。假定存在一个 辅助量子比特 系统(如下图中的量子电路所描绘的)。 那么，这个算子表示有受主系统中 f(x)的值控制的受控非(非 门)：

${\displaystyle }$

更加简短地，

${\displaystyle }$

这是一种利用 去计算方法来实现一个二元运算的自然的方法。 需要注意的是，如果辅助量子比特初始状态为 ${\displaystyle }$门将等效于上文中的操作，同时辅助系统不再与主系统纠缠：

$U_{\omega }{\big (}|x\rangle \otimes |-\rangle {\big )}={\frac {1}{\sqrt {2}}}\left(U_{\omega }|x\rangle |0\rangle -U_{\omega }|x\rangle |1\rangle \right)={\frac {1}{\sqrt {2}}}\left(|x\rangle |f(x)\rangle -|x\rangle |1\oplus f(x)\rangle \right)={\begin{cases}{\frac {1}{\sqrt {2}}}\left(|x\rangle |1\rangle -|x\rangle |0\rangle \right)=-|x\rangle \otimes |-\rangle &{\text{if }}f(x)=1,\\{\frac {1}{\sqrt {2}}}\left(|x\rangle |0\rangle -|x\rangle |1\rangle \right)=|x\rangle \otimes |-\rangle &{\text{if }}f(x)=0\end{cases}}$

在以上两种设定中，我们的目标都是寻找 ${\displaystyle }$。

算法的步骤

表示Grover算法的量子电路

Grover算法的步骤如下。 让$|s\rangle$表示所有状态的均匀叠加态

$|s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}|x\rangle .$

那么算子

$U_{s}=2\left|s\right\rangle \left\langle s\right|-I$

记为Grover扩散算子。

以下是算法：

1. 将系统初始化为
   $|s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}|x\rangle$。
2. 执行以下"Grover迭代" r(N)次。 函数 r(N)（渐近 O(N^1/2)）将在下文中说明。
   1. 作用算子$U_{\omega }$。
   2. 作用算子$U_{s}$。
3. 执行测量Ω。 测量 的结果将以接近1的概率（在N ≫ 1时）是本征值 λ_ω 。ω 可以从λ_ω求得。

参见

• 幅度放大
• 秀尔算法
• 德布罗意–波姆理论

参考文献

• Grover L.K.: A fast quantum mechanical algorithm for database search, Proceedings, 28th Annual ACM Symposium on the Theory of Computing, (May 1996) p. 212
• Grover L.K.: From Schrödinger's equation to quantum search algorithm, American Journal of Physics, 69(7): 769-777, 2001. Pedagogical review of the algorithm and its history.
• Grover L.K.: QUANTUM COMPUTING: How the weird logic of the subatomic world could make it possible for machines to calculate millions of times faster than they do today The Sciences, July/August 1999, pp. 24–30.
• Nielsen, M.A. and Chuang, I.L. Quantum computation and quantum information. Cambridge University Press, 2000. Chapter 6.
• What's a Quantum Phone Book?, Lov Grover, Lucent Technologies
• Grover's Algorithm: Quantum Database Search, C. Lavor, L.R.U. Manssur, R. Portugal
• Grover's algorithm on arxiv.org

外部链接

• Davy Wybiral. Quantum Circuit Simulator. |author=和|last=只需其一 (帮助)
• Craig Gidney. Grover’s Quantum Search Algorithm. 2013-03-05. |author=和|last=只需其一 (帮助)
• François Schwarzentruber. Grover's algorithm. 2013-05-18. |author=和|last=只需其一 (帮助)
• Alexander Prokopenya. Quantum Circuit Implementing Grover's Search Algorithm. Wolfram Alpha. |author=和|last=只需其一 (帮助)

举web

URL

https://web.eecs.umich.edu/~imarkov/pubs/jour/cise05-grov的。pdf

标题

是量子搜索实用？

最后一名

亚历山大Prokopenya

今年的出版物

2005年

出版商

Wolfram阿尔法

网页

案62-70中

DOI

10.1109/认证的。2005年。53

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