量子算法可以根据所使用的技术进行分类。它们分类如下:
- 基于相位估计的算法——包括 Shor 算法、HHL 算法等。
- 基于振幅放大的算法——包括 Grover 算法、Oblivious Amplitude Amplification 等。
- 基于量子游走的算法——这一系列算法包括搜索算法、哈密顿模拟算法等。
- 绝热算法——这类算法包括许多用于搜索、求解线性系统等的算法。
- 混合量子经典算法——这个系列包括VQE, QAOA, VQLS等变分算法。
本文将重点介绍Grover算法,它实际上是基于振幅放大算法中的一种。
Grover 的搜索问题
Grover算法处理的问题如下:假设您有一个包含 个项目的非结构化列表,这意味着该列表未排序并且缺少任何类型的模式或结构。我们想在这个列表中搜索一个元素,那么已知的经典解决方案是什么?
由于列表是非结构化的,我们能做的最好的就是线性搜索,在最坏的情况下它会花费 时间。但用Grover的算法,我们可以在 范围内完成。因此,Grover 的算法给出了二次加速,当我们使用包含多个元素的列表时,这一点变得非常重要。
现在我们来看看 Grover 算法背后的技巧,以及它为什么会这样做的答案。
Grover算法涉及的主要概念
正如您想象的那样,分析 Grover 的算法比描述它更困难。分析时,考虑平面中的反射和旋转会有所帮助。
反射
这是向量 关于线 的反射:

旋转
向量 逆时针旋转一个角度 :

现在,假设我们有两条线 和 ,它们之间的角度是 。那么对于 的任何选择,如果您将 反射到 上,然后再反射到 上,效果将与旋转 角相同。由此可知,两次反射相当于一次旋转。

所以现在我们知道了这两个概念对于我们理解算法的重要性。
Grover 算法的描述
让我们将要查找的元素表示为 。现在我们定义两个函数 和 。

它们分别被实现为预言机 和扩散算子 。 在 之前应用负号并保持其他所有状态不变, 将负号应用到与状态 正交的所有状态。
这些运算符在数学上的定义为:


在 Grover 的算法中,我们从一个状态开始,它是所有 量子比特状态的叠加,我们称这个状态为 ,然后应用 和 。
, 和 可以写作:




从上图我们可以理解运算符对 的影响。让我们假设一个二维子空间,其中 轴是向量 , 轴表示与 正交的所有向量。 与 轴形成 的角度。
我们当前的状态是 ,我们想要的状态是 。所以我们可以说我们想要旋转向量 并且旋转后的向量应该与 轴对齐。我们已经看到两次反射和一次旋转是如何等价的。在这里,我们将使用这个事实来放大我们的结果。
我们首先应用 算子,它反映关于 轴的状态 ,并给出状态 ,然后我们应用的 算子反映关于 的状态。
我们将初始向量旋转了角度 。怎样才能使角度进一步增大呢?我们只是重复这个过程!
振幅放大
在该算法中,通过幅值放大使状态 达到我们想要找到的的概率密度,并在每次迭代后同时降低其他状态的概率密度。现在,从上面提到的二维子空间图我们可以证明,在圆上的任何一点上,纵坐标值都是恒定的,等于非结构化列表的平均值(即 )。
因此我们可以写作

和

其中 是与 正交的向量,即在上面的二维子空间中表示的 轴。
现在, 的共轭可以写成:

并且,


搜索算法从 状态开始,然后应用 将给出状态:

然后在应用运算符 后,我们得到状态:

通过归纳很容易验证,Grover 迭代器 从状态 开始经过 次迭代之后,我们得到,

为了以高概率获得 ,我们必须选择 使得 ,这意味着我们希望 ,因此

这意味着,我们只需 次迭代即可获得所需的结果,并且 的数量级为 ,因此 Grover 算法的时间复杂度为 !
原文链接:https://medium.com/@qcgiitr/grovers-algorithm-a-simplified-interpretation-dcf04228bc9d
---煤油灯科技victorlamp.com翻译整理---









