你当前正在访问 Microsoft Azure Global Edition 技术文档网站。 如果需要访问由世纪互联运营的 Microsoft Azure 中国技术文档网站,请访问 https://docs.azure.cn

Grover 搜索算法理论

本文从理论角度详细说明了支持 Grover 算法运作的数学原理。

有关 Grover 算法解决数学问题的实用实现,请参阅 Implement Grover 的搜索算法

问题陈述

Grover 的算法加快了非结构化数据搜索(或 搜索问题)的解决方案,以比任何经典算法更少的步骤运行搜索。 任何搜索任务都可以使用抽象函数 f(x) 表示,该函数接受搜索项 x。 如果项 x 是搜索任务的解,则 f(x)=1。 如果项 x 不是解,则 f(x)=0。 搜索问题包括查找使 f(x0)=1 的任何项 x0

事实上,任何允许检查给定值 x 是否为有效解决方案的问题(一个 "是或没有问题&商;)可以在搜索问题方面制定。 下面是一些示例:

  • 布尔可满足性问题:布尔值 x 解释(值赋给变量)是否满足给定布尔公式?
  • 旅行推销员问题:x
  • 数据库搜索问题:数据库表是否包含记录 x
  • 整数分解问题:固定数字 Nx 可见?

Grover 算法旨在解决的任务可以表示如下:给定经典函数 f(x):{0,1}n{0,1},其中 n 是搜索空间的比特大小,找到使 f(x0)=1 的输入 x0。 此算法的复杂度是通过函数 f(x) 的使用次数衡量的。 传统上,在最糟糕的情况下,需要总共计算 f(x) N1 次,其中 N=2n,以尝试所有可能性。 N1 个元素之后,它肯定是最后一个元素。 Grover 量子算法能够更快速地解决此问题,实现了二次加速。 此处的“二次”表示,只需大约 N 次计算,而不是 N 次。

算法概述

假设搜索任务有 N=2n 个符合条件的项,并且为每个项目分配一个从 0N1 的整数来为它们编制索引。 此外,假设有 M 个不同的有效输入,也就是说,有 M 个输入的 f(x)=1。 这样一来,算法的步骤如下所示:

  1. 从以状态 |0 初始化的 n 个量子比特的寄存器开始。
  2. 通过向寄存器中的每个量子比特应用 H,准备将寄存器均匀叠加:|register=1Nx=0N1|x
  3. 将以下操作应用于寄存器 N最佳 时间:
    1. 为求解项应用条件相移为 1 的相位黑盒 Of
    2. 向寄存器中的每个量子比特应用 H
    3. 应用于除 |0 之外的每个计算基础状态的条件相移 1。 这可以由单一运算 O0 表示,因为 O0 只表示对 |0 的条件相移。
    4. 向寄存器中的每个量子比特应用 H
  4. 度量寄存器以获取具有很高概率为解的项的索引。
  5. 检查它是否为有效的解。 如果不是,则再次开始运算。

$N_\text{optimal}=\left\lfloor \frac{\pi}{{4}\sqrt{\frac{N}{M}}-\frac{1}{{2}\right\rfloor$ 是最佳的迭代次数,它将最大程度地增加通过测量寄存器获得正确项的概率。

备注

步骤 3.b、3.c 和 3.d 的联合应用通常被称为 Grover 的扩散运算符。

向寄存器应用的整个单一运算为:

(HnO0HnOf)NoptimalHn

逐步跟踪寄存器的状态

为说明此过程,我们将跟踪一个简单情况下的寄存器状态的数学转换,其中只有两个量子比特,并且有效元素为 |01

  1. 寄存器的启动状态为:|register=|00

  2. 向每个量子比特应用 H 后,寄存器的状态转变为 $$|\text{register}\rangle=\frac{{1}{\sqrt{{4}}\sum_{i \in \{0,1\}^2}|i\rangle=\frac12(\ket{00}+\ket{01}+\ket{10}+\ket{11})$$

  3. 然后,应用相位黑盒以获取:$$|\text{register}\rangle=\frac12(\ket{{00}-\ket{{01}+\ket{{10}+\ket{{11})$$

  4. 然后 H 再次作用于每个量子比特,得到 $$|\text{register}\rangle=\frac12(\ket{{00}+\ket{{01}-\ket{{10}+\ket{{11})$$

  5. 现在对除 |00 以外的每个状态应用条件相移:$$|\text{register}\rangle=\frac12(\ket{{00}-\ket{{01}+\ket{{10}-\ket{{11})$$

  6. 最后再次应用 H,结束第一次 Grover 迭代,得到:$$|\text{register}\rangle=\ket{{01}$$

    执行上述步骤,可以在单个迭代中找到有效项。 如后所述,这是因为对于 N=4 和单个有效项, N最佳=1

几何学解释

为说明 Grover 算法为何有效,我们将从几何角度研究此算法。 让 |bad 作为非搜索问题的解的所有状态的叠加。 假设有 M 个有效的解:

$$\ket{\text{bad}}=\frac{{1}{\sqrt{N-M}}\sum_{x:f(x)=0}\ket{x}$$

将状态 |good 定义为是搜索问题的解的所有状态的叠加

$$\ket{\text{good}}=\frac{{1}{\sqrt{M}}\sum_{x:f(x)=1}\ket{x}$$

由于 good 和 bad 是互斥集(因为一个项不能既有效又无效),因此状态 |good|bad 是正交的。 两种状态构成了向量空间中平面的正交基。 人们可以通过此平面将此算法可视化。

由正交好向量和坏向量投影的 Bloch 球体中的平面图。

现在,假设 |ψ 是跨越 |good|bad 的平面中的一个任意的状态。 该平面中的任何状态都可表示为:

|ψ=α|good+β|bad

其中 αβ 是实数。 接下来,我们介绍反射运算符 R|ψ,其中 |ψ 是此平面中的任意量子比特状态。 此运算符定义为:

R|ψ=2|ψψ|I

它被称为关于 |ψ 的反射运算符,因为在几何上可以将它解释为关于 |ψ 的方向的反射。 请获取 |ψ 和其正交互补 |ψ 所形成的平面的正交基,以便于理解这一点。 此平面的任何状态 |ξ 都可以基于此进行分解:

|ξ=μ|ψ+ν|ψ

如果将运算符 R|ψ 应用到 |ξ

R|ψ|ξ=μ|ψν|ψ

运算符 R|ψ 将与 |ψ 正交的分量反转,但保留 |ψ 分量不变。 因此,R|ψ 是关于 |ψ 的反射。

有关平面中可视化的量子状态的反射运算符的绘图。

在 Grover 算法中,第一次向每个量子比特应用 H 后,会开始将所有状态均匀叠加。 这可表示为:

|all=MN|good+NMN|bad

起始状态的图作为飞机中好坏状态的叠加。

因此此状态在平面中存在。 请注意,从相等叠加测量时获取正确结果的概率只是 ||所有|2=M/N,这是你期望随机猜测的结果。

黑盒 Of 向搜索问题的任意解添加一个负相。 因此,它可以表示为关于 |bad 轴的反射:

Of=R|bad=2|badbad|I

同样,条件相移 O0 就是状态 |0 的反转反射:

$$O_0 = R_{\ket{0}}= -2\ket{{0}\bra{0} + \mathcal{I}$$

了解这个事实后,很容易查明,Grover 扩散运算 HnO0Hn 也是状态 |all 的反射。 只需执行:

$$-H^{\otimes n} O_0 H^{\otimes n}=2H^{\otimes n}\ket{0}\bra{{0}H^{\otimes n} -H^{\otimes n}\mathcal{I}H^{\otimes n}= 2\ket{\text{all}}\bra{\text{all}} - \mathcal{I}= R_{\ket{\text{all}}}$$

刚刚证明了 Grover 算法的每一次迭代都由 R|badR|all 这两个反射组成。

在平面中将 Grover 迭代可视化为两个反射序列的绘图。

每个 Grover 迭代产生的综合效应是逆时针旋转的角度 2θ。 幸运的是,这个角度 θ 很容易找到。 由于 θ 只是 |all|bad 之间的角度,可以使用标量积找到角度。 已知 cosθ=all|bad,因此需要计算 all|bad。 通过 |all|bad|good 的分解,推断出:

θ=arccos(all|bad)=arccos(NMN)

寄存器的状态与 |良好 状态之间的角度随每次迭代而减少,从而产生更高的测量有效结果的概率。 若要计算此概率,只需计算 |良好的|寄存器|2。 表示 |good|registerγ(k) 之间的角度,其中 $$ 是迭代计数:

$$\gamma (k) =\frac{\pi}{2}-\theta -k2\theta =\frac{\pi}{{2} -(2k + 1) \theta $$

因此,成功的概率是:

P(success)=cos2(γ(k))=sin2[(2k+1)arccos(NMN)]

最佳迭代次数

由于成功概率可以表示为迭代次数的函数,因此,可通过计算使成功概率函数(接近)最大化的最小正整数,找到最佳的迭代次数 Noptimal

作为 Grover 迭代函数的成功概率的正弦图。最佳迭代次数接近第一个峰值。

已知 x=π2 时,sin2x 达到其第一个最大值,因此:

$$\frac{\pi}{{2}=(2k_{\text{optimal}} +1)\arccos \left( \sqrt{\frac{N-M}{N}}\right)$$

会得到:

$$k_{\text{optimal}}=\frac{\pi}{4\arccos\left(\sqrt{1-M/N}\right)}-1/2 =\frac{\pi}{{4}\sqrt{\frac{N}{M}}-\frac{1}{2}-O\left(\sqrt\frac{M}{N}\right)$$

在最后一步中,arccos1x=x+O(x3/2)

因此,可以选择$N_N_\text{最佳\text{}$$=\left}\lfloor \frac{\pi}{{4}\sqrt{\frac{N}{M}}-{1}{2}\frac{\right\rfloor。$

复杂度分析

通过前面的分析,需要查询黑盒 Of O(NM) 次才能找到有效的项。 不过,就时间复杂度而言,此算法能否有效实现? O0 基于计算对 n 比特的布尔运算,已知可使用 O(n) 个门实现。 还有两层 n 阿达马门。 因此这两个部分每次迭代只需要 O(n) 个门。 由于 N=2n,可推断出 O(n)=O(log(N))。 这样的话,如果需要 O(NM) 次迭代,并且每次迭代需要 O(log(N)) 个门,总时间复杂度(不考虑黑盒实现)为 O(NMlog(N))

算法的总体复杂性最终取决于 oracle Of实现的复杂性。 如果函数计算在量子计算机上比经典计算复杂得多,那么整体算法运行时在量子情况下会更长,尽管从技术上而言,它使用的查询更少。

参考

若要继续了解 Grover 算法,可以访问以下资源: