原文：
towardsdatascience.com/grovers-quantum-search-algorithm-54c427315768
·发表于 Towards Data Science ·阅读时间 16 分钟·2023 年 5 月 23 日
--
量子计算机 IBM 低温冷却系统的特写图像。图像来源：IBM/Graham Carlow。
Grover 算法 是最早提出的量子算法之一，它展示了量子相对于经典算法的优势，在这种情况下是二次‘加速’。该算法由洛夫·格罗弗 [1] 在 1996 年开发，是量子计算领域的一项突破，继类似算法如 Shor 算法 和 Deutsch-Jozsa 算法 之后。在本文中，我们将通过视觉方式解释 Grover 算法的工作原理，并通过数学展示它相对于最佳经典搜索算法的量子‘加速’。
首先，让我们介绍一下 Grover 算法所解决的问题。假设我们有一个无结构数据库，或列表，其中包含 N 元素，每个元素由一个唯一的 n 位字符串 ID 代表 x。因此，该列表最多可以包含 N = 2ⁿ 个元素。我们的任务是从数据库中找到一个特定的***“标记”***元素，其位字符串为 x₀。
N 元素数据库的简化示意图，其中标记的元素用红色标出。图像来源：作者。
为了找到标记的元素，我们需要通过查询数据库来获取数据库中某个元素的 ID 号 x 并检查它是否等于目标 ID 号 x₀。如果它相等，那么我们通过一次查询就成功找到了标记的元素！
然而，被查询的元素很可能不会在第一次尝试时与我们寻找的目标匹配，尤其是当数据库中包含很多元素（即 N 很大）时。因此，我们将不得不继续反复查询数据库，直到出现匹配的 x = x₀，并成功找到目标元素。
注意： 在“检查”元素的 ID 号时，我们不知道目标 ID x₀是什么。我们只是有一些方法来确定查询的 ID 号 x 是否等于 x₀。因此，“找到标记元素”也等同于确定 x₀ 实际上是什么。
为了“检查”某个元素的 ID 号 x，假设我们可以访问一个函数 f(x)，该函数接收一个 n 位字符串 x，如果它不等于目标比特串，则输出 ‘0’，如果相等则输出 ‘1’。由于我们不知道目标比特串 x₀ 实际上是什么，函数被描述为黑箱函数。我们可以如下定义该函数：
现在，为了找到标记元素，我们逐个查询数据库中的每个元素，并应用 f(x) 来检查它是否是目标。
-
在最佳情况下，我们在一次查询后找到目标。
-
在最坏情况下，我们必须查询数据库 N 次，即我们必须查询数据库中的每个元素。
-
平均而言，我们必须进行 N/2 次查询才能找到标记元素。
一般来说，我们可以说，如果我们对数据库进行 k 次不同查询，那么找到标记元素的概率是：
因此，如果我们希望以 𝝐 的概率成功，那么我们必须进行 k ≥ 𝝐N 次查询。总体而言，我们可以使用 Big-O 记法定义经典搜索算法的查询复杂度为：
在这一部分，我们将深入探讨 Grover 量子搜索算法如何在一个无结构的数据库中找到标记元素的理论，其查询复杂度为：
该算法描述了如何在量子电路上对初始处于零态的 n 个量子比特应用一组量子算符或 量子门。
量子电路将初始的 n 量子比特状态转化为最终的 n 量子比特状态，该状态等于目标量子态，并且具有高概率。然后，测量最终量子状态将返回目标 ID 比特串 x₀（具有高概率）。
预言算子是经典算法中黑箱函数 f(x) 的量子门等效物。预言算子将作用于 n 量子比特态 |x⟩ 上，并且如果它等于目标态 |x₀⟩ 则添加负相位**，否则保持不变：
要了解这如何与黑箱函数 f(x) 相关，我们还可以将预言操作表示为：
如果我们仔细考虑，可以发现预言算子等同于对角单位算子(在矩阵形式中只有对角项等于 1)，其对应于目标态 **|x₀⟩ 的元素具有负号。因此，我们可以将预言算子写为：
通过快速检查可以验证该表示确实等于上述的两个表示。
预言算子是算法的核心，定义了解决的计算问题。本质上，它只是验证给定问题的潜在解决方案。因此，Grover 算法可以用来解决任何可以用黑箱函数表示的问题，所以它不仅限于无结构搜索问题。
相位反转算子类似于预言算子，不同之处在于，如果状态等于目标态 |*x₀⟩，它会添加负相位；如果状态等于n-量子比特零态* |0⟩，它会添加负相位。其他情况下，状态保持不变。
相位反转算子也可以表示为对角单位算子，其对应于零态的元素具有负相位：
Grover 的算子 D 通过在应用相位反转算子之前和之后对所有 n 个量子比特应用一个Hadamard 算子 并添加负相位，即添加负号，从而获得。它可以表达为：
其中 Hadamard 算子将所有 n 个量子比特置于等概率叠加的可能 N = 2ⁿ 状态。我们可以代入相位反转算子的替代表示，以获得：
在零态的单个量子比特上，Hadamard 操作的效果是将其置于以下单量子比特叠加态：
为了更清晰、更直观地理解预言算符、相位倒置算符和 Grover 的 D 算符对 n 量子比特状态的作用，让我们首先稍作绕行，探讨两类一般算符，即倒置和反射算符。
正如你可能猜到的，倒置和反射算符执行对某个其他量子状态 |𝜓⟩ 的***‘倒置’或‘反射’***。它们表示如下：
为了观察这两种形式的算符对状态的作用，让我们考虑它们对一个任意状态的作用，该状态被分解为正交组件：
很容易检查，将倒置算符应用于上述任意状态会得到以下结果：
我们可以看到，状态的 |𝜓⟩ 组件前面的符号被翻转了。这对应于对整体状态 |𝜙⟩ 关于正交状态 |𝜓⟩ 的***‘反射’***。我们可以如下可视化：
任意状态 |𝜙⟩ 上的倒置操作动画。黄色轴表示反射轴。Gif 作者提供。
同样，如果我们将反射算符应用于任意状态，则会得到：
我们现在发现正交组件的符号被翻转了。这种符号翻转对应于对整体状态 |𝜙⟩ 关于 |𝜓⟩ 状态的反射。我们可以如下可视化：
任意状态 |𝜙⟩ 上的反射操作动画。黄色轴表示反射轴。Gif 作者提供。
基于我们对倒置和反射算符的新理解，让我们将预言算符、相位倒置算符和 Grover 的 D 算符表示如下：
现在我们已经对 Grover 算法涉及的核心概念和量子算符有了深入的理解，我们可以开始研究算法的工作原理。完整算法描述如下：
描述该算法的完整 单位算符 因此是：
因此，算法结束时我们 n 量子比特所处的最终量子状态是：
如果我们的算法正常工作，则最终状态应该等于目标状态 *|*x₀⟩，具有较高的概率。然后，测量每个量子比特的最终状态应该给我们目标 ID 比特串 x₀。
代表该算法的量子电路如下所示：
对应于 Grover 算法的量子电路图。图片作者提供。
每个 T ‘Grover 迭代’ 对 n-qubit 状态的作用由括号中的算符描述。我们将它们组合成一个 Grover 算符 G：
我们可以用 反演和反射算符 来表达：
其中，倒数第二项表示对正交的 |+ⁿ**⟩** 状态的反射。我们可以说 |x₀**⟩** 和 |+ⁿ**⟩** 状态 张成了 Hilbert 空间的二维子空间 (我们 n-qubits 的总 N = 2ⁿ 状态空间)，每次 Grover 迭代中的反射操作都发生在这个二维子空间中。
让我们考虑每次 Grover 迭代 G 在二维子空间中对任意状态 |𝜁⟩ 的作用，该子空间由 |x₀**⟩** 和 |+ⁿ**⟩** 张成。我们可以将任意状态 |𝜁⟩ 表达为状态 |+ⁿ**⟩** 及其正交对应物：
同样，目标状态 |x₀**⟩** 可以写成：
初始状态 |𝜁⟩ 和目标状态 |x₀**⟩** 可以在表示正交 |+ⁿ**⟩** 组件的二维子空间图中绘制。下图展示了状态之间的相关角度。
展示由某些初始状态和目标状态张成的二维子空间。图片作者提供。
如果我们检查 Grover 迭代算符：
每次 Grover 迭代对某些初始状态的作用可以通过图形化的方式理解如下：
-
|𝜁⟩ 状态关于 |x₀**⟩** 状态的 反射。
-
结果状态关于正交轴的 反射。
因此，如果我们初始状态和目标状态之间的角度为 𝜽，我们首先需要在 |x₀**⟩** 状态关于的 反射 后 减去 -2𝜽，然后在关于垂直正交轴的反射后 加上 +2(𝜽 — 𝛾)。最终角度因此由下式给出：
换句话说：
每次 Grover 迭代中 n-qubit 量子状态 |𝜁⟩ 和目标状态 |x₀**⟩** 之间的角度减少 2𝛾。
使用下面的动画可以更清楚地理解这一点：
Grover 迭代对某些初始任意状态的作用动画。Gif 作者提供。
因此，为了将初始量子状态 |𝜁⟩ 转换为目标状态 |x₀**⟩，我们只需 反复应用 Grover 迭代，然后在状态 |𝜁⟩ 尽可能接近 目标状态 |x₀⟩** 时停止。
然而，如前所述，我们并不是从某个初始任意态 |𝜁⟩ 开始，并应用我们的 Grover 迭代。如 步骤 1 和 2 所示，我们实际上从初始状态开始：
初始状态 |𝜁⟩ 和目标状态 |x₀**⟩** 之间的 初始角度 𝜽 通过 内积 找到：
类似地，我们还可以很容易地展示目标状态 |x₀**⟩** 与正交轴之间的角度 𝛾 如下所示：
因此，随着数据库大小 N 的增加，即 在非常大的集合大小 N 的极限下， 我们得到如下结果：
类似地，我们也可以说 (使用 小角度近似) 在大 N 的极限下：
那么，使用这些初始角度，大约需要多少次 Grover 迭代才能使初始状态接近或尽可能接近目标状态 |x₀⟩?
由于每次 Grover 迭代都将状态与目标状态之间的角度减少 2𝛾，而初始角度为 𝜋/2，我们可以展示：
其中 T 代表 Grover 迭代次数，因此也代表 对 oracle 的查询次数 k。然而，我们应该注意这 只是一个近似值。关于 Grover 迭代次数的更精确推导将在接下来的章节中介绍。不过，查询复杂度 可以用 大 O 符号*** 表示：***
相对于经典查询复杂度的二次加速！下图比较了经典查询复杂度与量子查询复杂度，并指出了量子优势的点。
经典查询复杂度与量子查询复杂度，量子优势点用黄色标出。图片由作者提供。
然而，成功到达目标状态 |x₀**⟩** 的概率强烈依赖于总系统大小 N 和应用的 Grover 迭代次数 T。
实际上，成功概率并不会随着 Grover 迭代次数的增加而趋近于 1，而是 振荡! 要了解原因，我们首先考虑最终状态 |𝜁⟩ 在 目标状态 |x₀**⟩** 中的概率：
我们知道 内积 可以用更为熟悉的几何形式表示：
使用最终角度，即状态|𝜁⟩与目标状态|x₀**⟩**之间的角度，在T次 Grover 迭代后。我们也已经知道这个角度由以下公式给出：
使用以下关系：
给出以下最终角度的表达式：
我们可以将其代入内积公式得到：
最终给出以下成功将最终状态置于目标状态的概率表达式：
使用这个方程，我们可以绘制成功概率作为 Grover 迭代次数的函数，对于某些系统规模N，以观察成功概率是否确实存在振荡。
成功概率作为 Grover 迭代次数的函数。图像由作者提供。
为了理解这种振荡现象，我们可以再次将状态|𝜁⟩和目标状态|x₀**⟩绘制在图上，并应用许多 Grover 迭代，以观察状态在多次T迭代中的行为**。
状态在多次 Grover 迭代中的行为动画。Gif 由作者提供。
我们可以看到，当状态以每次 Grover 迭代 2𝛾的角速度接近目标状态时，实际上会达到一个最小点，此时状态与目标状态之间的角度符号发生反转。因此，状态开始“螺旋”远离目标状态。
在每个系统规模N下，都存在一个最大化成功概率的最优 Grover 迭代次数T。
我们可以通过将成功概率设为 1 并重新排列以找到T来确定这个最优数字。
然而，这个最优的迭代次数必须是整数值，因此通常会因舍入到最近整数而存在一些小的截断误差。
我们可以通过绘制成功概率作为集合大小 N 的函数并使用四舍五入到最近整数的最优 Grover 迭代次数来观察这种截断误差的影响。
使用最近整数的最优 Grover 迭代次数T值作为系统规模 N 的函数的成功概率。图像由作者提供。
其中蓝色曲线显示了成功概率，红色曲线显示了成功概率的包络线近似，作为集合大小 N 的函数。如图所示，成功概率的变化规律如下：
因此，随着集合大小N增大，成功概率接近于 1！
如果我们再次绘制成功概率的振荡图像，作为 Grover 迭代次数的函数，但这次仅显示T的整数值，我们或许能更清楚地理解成功概率为何出现这种趋势。对于集大小N=7，我们得到以下结果：
成功概率作为截断的最接近整数 Grover 迭代次数的函数，设定集大小 N=7。图像由作者提供。
我们可以看到，成功概率的***振荡‘频率’***是这样的，在上述第一个振荡周期中，最接近整数的 Grover 迭代次数（垂直线）与振荡的峰值不对齐。因此，成功概率无法达到 1。
然而，如果我们对集大小N=100进行相同的操作，我们得到以下结果：
成功概率作为截断的最接近整数 Grover 迭代次数的函数，设定集大小 N=100。图像由作者提供。
增加集大小N有效地降低了振荡的‘频率’，使得最优的最接近整数 Grover 迭代次数可以更接近振荡的峰值。 如果我们进一步增加集大小到N=800，这种模式会变得更加明显，如下所示：
成功概率作为截断的最接近整数 Grover 迭代次数的函数，设定集大小 N=800。图像由作者提供。
因此，随着N趋向于无穷大，最优的最接近整数 Grover 迭代次数 T 接近振荡的峰值，而成功概率趋向于 1。
在这篇文章中，我们详细探讨了 Grover 量子搜索算法如何实现比传统经典搜索算法更快的二次加速的理论。然而，理论上 Grover 算法可以应用于比非结构化搜索更广泛的算法。更一般地说，该算法可以加速任何黑箱问题，这涉及到满足一些由 oracle 操作符检查的约束，或任何固有地涉及穷举搜索的问题。因此，该算法的一个潜在应用是量子密码学，特别是 Grover 算法可能为许多暴力攻击算法中固有的穷举搜索提供量子加速。
然而，Grover 算法的查询复杂性只有在特定系统规模 N 实现后才会超过其经典对手。目前，近期的量子计算机远未能够提供实现这种量子优势所需的大量无噪声量子比特。不过，随着未来几十年量子计算和量子工程领域的持续进展，长期的容错量子计算机似乎有可能达到实现 Grover 量子搜索算法承诺所需的复杂性和精密度。
感谢阅读！ 如果你喜欢这篇文章并想阅读更多关于物理学、量子力学和量子计算的内容，请关注我并查看我的其他文章！如果你真的喜欢这篇文章，你还可以在 bmc.link/danjackho5 请我喝一杯咖啡（如果你愿意的话），我会非常感激！
如果你想继续在 Medium 上阅读关于数学和物理的内容，那么为什么不通过以下链接注册成为 Medium 会员呢？medium.com/@danjackho/membership。
量子物理学 101：薛定谔方程的各种形式 [## 量子谐振子：狄拉克的研究方法
量子谐振子：狄拉克的研究方法 [## 量子传送的数学解释
[1] Grover, Lov K. “一种快速的量子机械算法用于数据库搜索。” 第二十八届年度 ACM 计算理论研讨会论文集。1996 年。
[2] Linden, Noah. 讲义, “量子计算”。2022 年。