格罗弗算法

在量子计算中，Grover算法，也称为量子搜索算法，是指用于非结构化搜索的量子算法，该算法高概率地找到产生特定输出值的黑盒函数的唯一输入，仅使用仅${\displaystyle O({\sqrt {N}})}$)函数的评估，其中${\displaystyle n}$是函数域的大小。它是由Lov Grover在1996年设计的。

经典计算中的类似问题不能在少于${\displaystyle O(N)}$评估(因为平均而言，必须检查一半的域才能获得50%的机会找到正确的输入)。Charles H. Bennett，Ethan Bernstein，Gilles Brassard和Umesh Vazirani证明，该问题的任何量子解决方案都需要评估函数${\displaystyle \Omega ({\sqrt {N}})}$次，所以格罗弗的算法是渐近最优的。 由于NP完全问题的经典算法需要指数级的许多步骤，并且Grover算法最多提供非结构化搜索的经典解决方案的二次加速，这表明Grover算法本身不会为NP完全问题提供多项式时间解(因为指数函数的平方根是指数函数，而不是多项式函数)。

与其他量子算法不同，其他量子算法可能比经典算法提供指数加速，Grover的算法仅提供二次加速。然而，即使是二次加速比在以下情况下也是相当大的${\displaystyle n}$N很大，Grover的算法可以应用于加速广泛的算法类别。 Grover的算法可以在大约264次迭代中暴力破解128位对称加密密钥，或者在大约2128次迭代中暴力破解256位密钥。因此，有时有人建议将对称密钥长度加倍以防止未来的量子攻击。

应用和限制

Grover的算法，以及振幅放大等变体，可用于加速广泛的算法。特别是，NP完全问题的算法通常包含穷举搜索作为子例程，这可以通过Grover算法加速。目前3SAT的最佳算法就是这样一个例子。通用约束满足问题也见格罗弗的二次加速这些算法不要求以预言机的形式给出输入，因为Grover的算法是与显式函数一起应用的，例如检查一组位是否满足3SAT实例的函数。

Grover算法还可以为量子查询复杂性中的黑盒问题提供可证明的加速，包括元素独特性和碰撞问题(用Brassard-Høyer-Tapp算法解决)。在这些类型的问题中，将预言机函数f视为数据库，目标是尽可能少地使用该函数的量子查询。

密码学

格罗弗的算法本质上解决了函数反演的任务。粗略地说，如果我们有一个函数${\displaystyle y=f(x)}$可以在量子计算机上进行评估，格罗弗的算法允许我们计算${\displaystyle x}$给予时${\displaystyle y}$.因此，Grover的算法为对称密钥密码学上的多种暴力攻击提供了广泛的渐近加速，包括碰撞攻击和前像攻击。然而，这可能不一定是最有效的算法，因为，例如，并行rho算法能够比Grover算法更有效地找到SHA2中的碰撞。

限制

Grover的原始论文将该算法描述为数据库搜索算法，这种描述仍然很常见。这个类比中的数据库是所有函数输出的表，由相应的输入索引。但是，此数据库未显式表示。相反，调用预言机来按索引评估项目。逐项读取完整的数据库并将其转换为这样的表示形式可能比 Grover 的搜索花费更长的时间。为了解释这种效应，Grover的算法可以被视为求解方程或满足约束。在此类应用程序中，oracle 是一种检查约束的方法，与搜索算法无关。这种分离通常会阻止算法优化，而传统的搜索算法通常依赖于此类优化并避免详尽搜索。

从Grover算法实例化加速的主要障碍是，实现的二次加速比太小，无法克服近期量子计算机的巨大开销。然而，具有更好硬件性能的后代容错量子计算机可能能够实现实际数据实例的这些加速。

问题描述

作为格罗弗算法的输入，假设我们有一个函数${\displaystyle f\colon \{0,1,\ldots ,N-1\}\to \{0,1\}}$.在“非结构化数据库”类比中，域表示数据库的索引，并且 f(x) = 1 当且仅当 x 指向的数据满足搜索条件。我们还假设只有一个索引满足 f(x) = 1，我们称之为索引 ω。我们的目标是识别ω。

我们可以使用一个子例程(有时称为预言机)以酉运算符 Uω 的形式访问 f，其作用如下：

$${\displaystyle {\begin{cases}U_{\omega }|x\rangle =-|x\rangle &{\text{for }}x=\omega {\text{, 即, }}f(x)=1,\\U_{\omega }|x\rangle =|x\rangle &{\text{for }}x\neq \omega {\text{, 即, }}f(x)=0.\end{cases}}}$$

这使用${\displaystyle n}$-维状态空间 ${\displaystyle {\mathcal {H}}}$，由寄存器提供${\displaystyle n=\lceil \log _{2}N\rceil }$ 量子比特。 这通常写为

$${\displaystyle U_{\omega }|x\rangle =(-1)^{f(x)}|x\rangle .}$$

格罗弗算法输出 ω 的概率至少为 1/2，使用${\displaystyle O({\sqrt {N}})}$Uω的应用通过多次运行 Grover 算法，可以任意放大此概率。如果运行 Grover 算法直到找到 ω，则预期的应用程序数量仍然是${\displaystyle O({\sqrt {N}})}$，因为它平均只会运行两次。

替代预言机定义

本节比较上述预言机${\displaystyle U_{\omega }}$与预言机${\displaystyle U_{f}}$.

Uω 不同于函数 f 的标准量子预言机。这个标准的预言机，在这里表示为 Uf，使用辅助量子比特系统。然后，该操作表示主系统上的反转(NOT 门)，该反转(NOT 门)由辅助系统的 f(x) 值调节：

$${\displaystyle {\begin{cases}U_{f}|x\rangle |y\rangle =|x\rangle |\neg y\rangle &{\text{for }}x=\omega {\text{, 即, }}f(x)=1,\\U_{f}|x\rangle |y\rangle =|x\rangle |y\rangle &{\text{for }}x\neq \omega {\text{, 即, }}f(x)=0,\end{cases}}}$$

或简单地说，

$${\displaystyle U_{f}|x\rangle |y\rangle =|x\rangle |y\oplus f(x)\rangle .}$$

这些预言机通常使用非计算来实现。

如果我们给定 U f 作为我们的预言机，那么我们也可以实现 U ω，因为当辅助量子比特处于状态时，U ω 是 U f${\displaystyle |-\rangle ={\frac {1}{\sqrt {2}}}{\big (}|0\rangle -|1\rangle {\big )}=H|1\rangle }$:

$${\displaystyle {\begin{aligned}U_{f}{\big (}|x\rangle \otimes |-\rangle {\big )}&={\frac {1}{\sqrt {2}}}\left(U_{f}|x\rangle |0\rangle -U_{f}|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 |0\rangle +|x\rangle |1\rangle \right)&{\text{if }}f(x)=1,\\{\frac {1}{\sqrt {2}}}\left(|x\rangle |0\rangle -|x\rangle |1\rangle \right)&{\text{if }}f(x)=0\end{cases}}\\&=(U_{\omega }|x\rangle )\otimes |-\rangle \end{aligned}}}$$

因此，无论给出哪个预言机，Grover的算法都可以运行。 如果给定 Uf，那么我们必须在状态中维护一个额外的量子比特${\displaystyle |-\rangle }$并用 Uf 代替 Uω。

算法

Grover算法的步骤如下：

• 1. 将系统初始化为所有状态的均匀叠加 $${\displaystyle |s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}|x\rangle .}$$
• 2.执行以下“格罗弗迭代”${\displaystyle r(N)}$次：
  • 1.应用运算符${\displaystyle U_{\omega }}$
  • 2.应用格罗弗扩散运算符${\displaystyle U_{s}=2\left|s\right\rangle \left\langle s\right|-I}$
• 3.在计算基础中测量生成的量子态。

对于正确选择的值${\displaystyle r}$，输出将为${\displaystyle |\omega \rangle }$N ≫ 1 的概率接近 1。分析表明，此最终值为${\displaystyle r(N)}$满足${\displaystyle r(N)\leq {\Big \lceil }{\frac {\pi }{4}}{\sqrt {N}}{\Big \rceil }}$.

实现此算法的步骤可以使用量子比特数线性的门数来完成。 因此，该算法的门复杂度为${\displaystyle O(\log(N)r(N))}$或${\displaystyle O(\log(N))}$每次迭代。

正确性的几何证明

格罗弗算法有一个几何解释，根据观察，格罗弗算法的量子态在每一步后都停留在二维子空间中。考虑跨越的平面${\displaystyle |s\rangle }$和${\displaystyle |\omega \rangle }$;等价地，跨越的平面由${\displaystyle |\omega \rangle }$和垂直的 ket ${\displaystyle \textstyle |s'\rangle ={\frac {1}{\sqrt {N-1}}}\sum _{x\neq \omega }|x\rangle }$.

格罗弗算法从初始 ket 开始${\displaystyle |s\rangle }$，位于子空间中。操作员${\displaystyle U_{\omega }}$是正交的超平面处的反射${\displaystyle |\omega \rangle }$对于跨越的平面中的向量${\displaystyle |s'\rangle }$和${\displaystyle |\omega \rangle }$，即它充当跨${\displaystyle |s'\rangle }$.这可以通过写作看到${\displaystyle U_{\omega }}$以基本反射器的形式：

$${\displaystyle U_{\omega }=I-2|\omega \rangle \langle \omega |.}$$

操作员${\displaystyle U_{s}=2|s\rangle \langle s|-I}$是一种反思${\displaystyle |s\rangle }$.两个运算符${\displaystyle U_{s}}$和${\displaystyle U_{\omega }}$取跨越的平面中的状态${\displaystyle |s'\rangle }$和${\displaystyle |\omega \rangle }$到飞机中的状态。因此，Grover 的算法在整个算法中都停留在这个平面上。

检查操作员是否简单${\displaystyle U_{s}U_{\omega }}$每个 Grover 迭代步骤将状态向量旋转的角度${\displaystyle \theta =2\arcsin {\tfrac {1}{\sqrt {N}}}}$. 因此，通过足够的迭代，可以从初始状态旋转${\displaystyle |s\rangle }$到所需的输出状态${\displaystyle |\omega \rangle }$.初始 ket 接近正交的状态${\displaystyle |\omega \rangle }$:

$${\displaystyle \langle s'|s\rangle ={\sqrt {\frac {N-1}{N}}}.}$$

在几何术语中，角度${\displaystyle \theta /2}$之间${\displaystyle |s\rangle }$和${\displaystyle |s'\rangle }$由

$${\displaystyle \sin {\frac {\theta }{2}}={\frac {1}{\sqrt {N}}}.}$$

当状态向量接近${\displaystyle |\omega \rangle }$;在此之后，后续迭代将状态向量旋转远离${\displaystyle |\omega \rangle }$，降低了获得正确答案的概率。测量正确答案的确切概率是

$${\displaystyle \sin ^{2}\left({\Big (}r+{\frac {1}{2}}{\Big )}\theta \right),}$$

其中 r 是 Grover 迭代的(整数)次数。因此，我们获得接近最佳测量值的最早时间是${\displaystyle r\approx \pi {\sqrt {N}}/4}$.

代数正确性证明

为了完成代数分析，我们需要找出当我们反复应用时会发生什么${\displaystyle U_{s}U_{\omega }}$.一种自然的方法是对矩阵进行特征值分析。请注意，在整个计算过程中，算法的状态是${\displaystyle s}$和${\displaystyle \omega }$.我们可以写下动作${\displaystyle U_{s}}$和${\displaystyle U_{\omega }}$在跨越的空间中${\displaystyle \{|s\rangle ,|\omega \rangle \}}$如：

$${\displaystyle U_{s}：a|\omega \rangle +b|s\rangle \mapsto [|\omega \rangle \,|s\rangle ]{\begin{bmatrix}-1&0\\2/{\sqrt {N}}&1\end{bmatrix}}{\begin{bmatrix}a\\b\end{bmatrix}}.}$$ $${\displaystyle U_{\omega }：a|\omega \rangle +b|s\rangle \mapsto [|\omega \rangle \,|s\rangle ]{\begin{bmatrix}-1&-2/{\sqrt {N}}\\0&1\end{bmatrix}}{\begin{bmatrix}a\\b\end{bmatrix}}.}$$

所以在基础${\displaystyle \{|\omega \rangle ,|s\rangle \}}$(既不是正交的，也不是整个空间的基础)动作${\displaystyle U_{s}U_{\omega }}$申请数量${\displaystyle U_{\omega }}$其次${\displaystyle U_{s}}$由矩阵给出

$${\displaystyle U_{s}U_{\omega }={\begin{bmatrix}-1&0\\2/{\sqrt {N}}&1\end{bmatrix}}{\begin{bmatrix}-1&-2/{\sqrt {N}}\\0&1\end{bmatrix}}={\begin{bmatrix}1&2/{\sqrt {N}}\\-2/{\sqrt {N}}&1-4/N\end{bmatrix}}.}$$

这个矩阵恰好有一个非常方便的乔丹形式。如果我们定义${\displaystyle t=\arcsin(1/{\sqrt {N}})}$将上式改写为（所谓Jordan form）

$${\displaystyle U_{s}U_{\omega }=M{\begin{bmatrix}e^{2it}&0\\0&e^{-2it}\end{bmatrix}}M^{-1}}$$

where

$${\displaystyle M={\begin{bmatrix}-i&i\\e^{it}&e^{-it}\end{bmatrix}}.}$$

因此，矩阵的第 r 次幂(对应于 r 迭代)为

$${\displaystyle (U_{s}U_{\omega })^{r}=M{\begin{bmatrix}e^{2rit}&0\\0&e^{-2rit}\end{bmatrix}}M^{-1}.}$$

使用这种形式，我们可以使用三角恒等式来计算上一节提到的 r 迭代后观察到 ω 的概率，

$${\displaystyle \left|{\begin{bmatrix}\langle \omega |\omega \rangle &\langle \omega |s\rangle \end{bmatrix}}(U_{s}U_{\omega })^{r}{\begin{bmatrix}0\\1\end{bmatrix}}\right|^{2}=\sin ^{2}\left((2r+1)t\right).}$$

或者，人们可以合理地想象，当角度2 rt和-2rt尽可能远时，区分的接近最佳时间是，这对应于${\displaystyle 2rt\approx \pi /2}$或$r=\pi /4t=\pi /4\arcsin(1/{\sqrt {N}})\approx \pi {\sqrt {N}}/4$.然后系统处于状态

$${\displaystyle [|\omega \rangle \,|s\rangle ](U_{s}U_{\omega })^{r}{\begin{bmatrix}0\\1\end{bmatrix}}\approx [|\omega \rangle \,|s\rangle ]M{\begin{bmatrix}i&0\\0&-i\end{bmatrix}}M^{-1}{\begin{bmatrix}0\\1\end{bmatrix}}=|\omega \rangle {\frac {1}{\cos(t)}}-|s\rangle {\frac {\sin(t)}{\cos(t)}}.}$$

现在，简短的计算表明，观测结果产生正确答案 ω 并有误差${\displaystyle O\left({\frac {1}{N}}\right)}.$

扩展和变体

多个匹配条目

如果有 k 个匹配条目，而不是 1 个匹配条目，则相同的算法有效，但迭代次数必须${\textstyle {\frac {\pi }{4}}{\left({\frac {N}{k}}\right)^{1/2}}}$而不是${\textstyle {\frac {\pi }{4}}{N^{1/2}}.}$

如果 k 未知，有几种方法可以处理这种情况。 一个简单的解决方案在恒定因子下以最佳方式执行：对于越来越小的 k 值重复运行 Grover 算法，例如，取 k = N， N/2， N/4， …，依此类推，取${\displaystyle k=N/2^{t}}$迭代 T，直到找到匹配的条目。

以足够高的概率，将通过迭代找到标记的条目${\displaystyle t=\log _{2}(N/k)+c}$对于一些常数 c。因此，所经历的迭代总数最多为

$${\displaystyle {\frac {\pi }{4}}{\Big (}1+{\sqrt {2}}+{\sqrt {4}}+\cdots +{\sqrt {\frac {N}{k2^{c}}}}{\Big )}=O{\big (}{\sqrt {N/k}}{\big )}.}$$

该算法的一个版本用于解决碰撞问题。

量子部分搜索

格罗弗算法的修改称为量子部分搜索，由格罗弗和拉达克里希南在2004年描述。在部分搜索中，人们不感兴趣的是找到目标项目的确切地址，只找到地址的前几位数字。等价地，我们可以考虑将搜索空间“分块”为块，然后询问“目标项在哪个块中？在许多应用程序中，如果目标地址包含所需的信息，则此类搜索会产生足够的信息。例如，使用L. K. Grover给出的例子，如果一个人有一个按班级排名组织的学生名单，我们可能只对学生是否处于较低的25%，25-50%，50-75%或75-100%百分位感兴趣。

为了描述部分搜索，我们认为将数据库分为${\displaystyle K}$块，每个大小${\displaystyle b=N/K}$.部分搜索问题更容易。考虑一下我们经典采用的方法——我们随机选择一个块，然后对其余块进行正常搜索(在集合论语言中，补语)。如果我们没有找到目标，那么我们知道它就在我们没有搜索的块中。平均迭代次数从${\displaystyle n/2}$不适用自${\displaystyle (N-b)/2}$.

格罗弗算法需要${\textstyle {\frac {\pi }{4}}{\sqrt {N}}}$迭 代。部分搜索将因取决于块数的数字因素而更快${\displaystyle K}$.部分搜索用途${\displaystyle n_{1}}$全局迭代和${\displaystyle n_{2}}$本地迭代。指定全局格罗弗操作员${\displaystyle G_{1}}$并指定了当地的格罗弗操作员${\displaystyle G_{2}}$.

全局格罗弗运算符作用于块。本质上，它给出如下：

• 1.执行${\displaystyle j_{1}}$对整个数据库进行标准 Grover 迭代。
• 2.执行${\displaystyle j_{2}}$本地格罗弗迭代。局部 Grover 迭代是每个块的 Grover 迭代的直接总和。
• 3.执行一次标准格罗弗迭代。
  的最优值${\displaystyle j_{1}}$和${\displaystyle j_{2}}$在Grover和Radhakrishnan的论文中进行了讨论。人们可能还想知道，如果以不同的“分辨率”级别应用连续的部分搜索会发生什么。弗拉基米尔·科列宾(Vladimir Korepin)和徐(Xu)详细研究了这个想法，他们称之为二进制量子搜索。他们证明，这实际上并不比执行单个部分搜索更快。

最优性

格罗弗算法在子常数因子下是最优的。也就是说，任何仅使用运算符 Uω 访问数据库的算法都必须应用 Uω 至少${\displaystyle 1-o(1)}$是格罗弗算法的几倍。将格罗弗算法扩展到k个匹配条目，(π(N/k)^(1/2))/4，也是最优的。这一结果对于理解量子计算的局限性非常重要。

如果 Grover 搜索问题可以通过 Uω 的对数c N 应用来解决，这意味着 NP 包含在 BQP 中，通过将 NP 中的问题转换为 Grover 类型的搜索问题。Grover算法的最优性表明量子计算机无法在多项式时间内解决NP-完全问题，因此NP不包含在BQP中。

已经表明，一类非局部隐变量量子计算机可以实现对${\displaystyle n}$-最多在项目数据库中${\displaystyle O({\sqrt[{3}]{N}})}$步骤。这比${\displaystyle O({\sqrt {N}})}$格罗弗算法采取的步骤。

原文地址：
https://en.wikipedia.org/wiki/Grover%27s_algorithm

在知识共享 署名-相同方式共享 3.0协议之条款下提供