量子搜索算法Grover核心概要

煤油灯科技2022-08-19 09:55

量子算法可以根据所使用的技术进行分类。它们分类如下:

  • 基于相位估计的算法——包括 Shor 算法、HHL 算法等。
  • 基于振幅放大的算法——包括 Grover 算法、Oblivious Amplitude Amplification 等。
  • 基于量子游走的算法——这一系列算法包括搜索算法、哈密顿模拟算法等。
  • 绝热算法——这类算法包括许多用于搜索、求解线性系统等的算法。
  • 混合量子经典算法——这个系列包括VQE, QAOA, VQLS等变分算法。

本文将重点介绍Grover算法,它实际上是基于振幅放大算法中的一种。

Grover 的搜索问题

Grover算法处理的问题如下:假设您有一个包含NN 个项目的非结构化列表,这意味着该列表未排序并且缺少任何类型的模式或结构。我们想在这个列表中搜索一个元素,那么已知的经典解决方案是什么?

由于列表是非结构化的,我们能做的最好的就是线性搜索,在最坏的情况下它会花费O(N)O\left(N\right) 时间。但用Grover的算法,我们可以在O(N)O\left(\sqrt{N}\right) 范围内完成。因此,Grover 的算法给出了二次加速,当我们使用包含多个元素的列表时,这一点变得非常重要。

现在我们来看看 Grover 算法背后的技巧,以及它为什么会这样做的答案。

Grover算法涉及的主要概念

正如您想象的那样,分析 Grover 的算法比描述它更困难。分析时,考虑平面中的反射和旋转会有所帮助。

反射

这是向量 ∣ψ⟩\rvert\psi\rangle 关于线LL 的反射:

旋转

向量∣ψ⟩\rvert\psi\rangle 逆时针旋转一个角度θθ :

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

所以现在我们知道了这两个概念对于我们理解算法的重要性。

Grover 算法的描述

让我们将要查找的元素表示为∣x0⟩|x₀\rangle 。现在我们定义两个函数f(x)f(x) 和f0(x)f⁰\left(x\right) 。

它们分别被实现为预言机(Rf)\left(R_f\right) 和扩散算子(RD)\left(R_D\right) 。RfR_f 在∣x0⟩|x₀\rangle 之前应用负号并保持其他所有状态不变,RDR_D 将负号应用到与状态∣00…0⟩|00…0\rangle 正交的所有状态。

这些运算符在数学上的定义为:

在 Grover 的算法中,我们从一个状态开始,它是所有nn 量子比特状态的叠加,我们称这个状态为∣D>|D> ,然后应用RfR_f 和RDR_D 。

∣D⟩|D\rangle ,RfR_f 和RDR_D 可以写作:

从上图我们可以理解运算符对∣D⟩|D\rangle 的影响。让我们假设一个二维子空间,其中yy 轴是向量∣x0⟩|x₀\rangle ,xx 轴表示与∣x0⟩|x₀\rangle 正交的所有向量。∣D⟩|D\rangle 与xx 轴形成θ/2θ/2 的角度。

我们当前的状态是∣D⟩|D\rangle ,我们想要的状态是∣x0⟩|x₀\rangle 。所以我们可以说我们想要旋转向量∣D⟩|D\rangle 并且旋转后的向量应该与yy 轴对齐。我们已经看到两次反射和一次旋转是如何等价的。在这里,我们将使用这个事实来放大我们的结果。

我们首先应用RfR_f 算子,它反映关于xx 轴的状态∣D⟩|D\rangle ,并给出状态RfR_f ∣D⟩|D\rangle ,然后我们应用的RDR_D 算子反映关于∣D⟩|D\rangle∣D⟩|D\rangle 的状态。

我们将初始向量旋转了角度θθ 。怎样才能使角度进一步增大呢?我们只是重复这个过程!

振幅放大

在该算法中,通过幅值放大使状态∣x0⟩|x₀\rangle 达到我们想要找到的的概率密度,并在每次迭代后同时降低其他状态的概率密度。现在,从上面提到的二维子空间图我们可以证明,在圆上的任何一点上,纵坐标值都是恒定的,等于非结构化列表的平均值(即 1/√N1/√N )。

因此我们可以写作

和

其中∣xb⟩|xb\rangle 是与∣x0⟩|x₀\rangle 正交的向量,即在上面的二维子空间中表示的xx 轴。

现在,∣D⟩|D\rangle 的共轭可以写成:

并且,

搜索算法从∣D⟩|D\rangle 状态开始,然后应用RfR_f 将给出状态:

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

通过归纳很容易验证,Grover 迭代器(U=RD⋅Rf)\left(U=R_D\cdot R_f\right) 从状态∣D>=H∣00…..0⟩|D>=H|00…..0\rangle 开始经过kk 次迭代之后,我们得到,

为了以高概率获得∣x0⟩|x₀\rangle ,我们必须选择kk 使得sin⁡((2k+1)θ)≈1\sin\left(\left(2k+1\right)θ\right)\approx1 ,这意味着我们希望(2k+1)θ≈π/2\left(2k+1\right)θ\approxπ/2 ,因此

这意味着,我们只需kk 次迭代即可获得所需的结果,并且kk 的数量级为N\sqrt{N} ,因此 Grover 算法的时间复杂度为O(N)O\left(\sqrt{N}\right) !




原文链接:https://medium.com/@qcgiitr/grovers-algorithm-a-simplified-interpretation-dcf04228bc9d


---煤油灯科技victorlamp.com翻译整理---

你可能也喜欢这些文章