培训
你当前正在访问 Microsoft Azure Global Edition 技术文档网站。 如果需要访问由世纪互联运营的 Microsoft Azure 中国技术文档网站,请访问 https://docs.azure.cn。
Grover 搜索算法理论
本文从理论角度详细说明了支持 Grover 算法运作的数学原理。
有关 Grover 算法解决数学问题的实用实现,请参阅 Implement Grover 的搜索算法。
Grover 的算法加快了非结构化数据搜索(或 搜索问题)的解决方案,以比任何经典算法更少的步骤运行搜索。 任何搜索任务都可以使用抽象函数
事实上,任何允许检查给定值
- 布尔可满足性问题:布尔值
解释(值赋给变量)是否满足给定布尔公式? - 旅行推销员问题:x
? - 数据库搜索问题:数据库表是否包含记录
? - 整数分解问题:固定数字 N
可见?
Grover 算法旨在解决的任务可以表示如下:给定经典函数
假设搜索任务有
- 从以状态
初始化的 个量子比特的寄存器开始。 - 通过向寄存器中的每个量子比特应用
,准备将寄存器均匀叠加: - 将以下操作应用于寄存器
时间:- 为求解项应用条件相移为
的相位黑盒 。 - 向寄存器中的每个量子比特应用
。 - 应用于除
之外的每个计算基础状态的条件相移 。 这可以由单一运算 表示,因为 只表示对 的条件相移。 - 向寄存器中的每个量子比特应用
。
- 为求解项应用条件相移为
- 度量寄存器以获取具有很高概率为解的项的索引。
- 检查它是否为有效的解。 如果不是,则再次开始运算。
$N_\text{optimal}=\left\lfloor \frac{\pi}{{4}\sqrt{\frac{N}{M}}-\frac{1}{{2}\right\rfloor$ 是最佳的迭代次数,它将最大程度地增加通过测量寄存器获得正确项的概率。
备注
步骤 3.b、3.c 和 3.d 的联合应用通常被称为 Grover 的扩散运算符。
向寄存器应用的整个单一运算为:
为说明此过程,我们将跟踪一个简单情况下的寄存器状态的数学转换,其中只有两个量子比特,并且有效元素为
寄存器的启动状态为:
向每个量子比特应用
后,寄存器的状态转变为 $$|\text{register}\rangle=\frac{{1}{\sqrt{{4}}\sum_{i \in \{0,1\}^2}|i\rangle=\frac12(\ket{00}+\ket{01}+\ket{10}+\ket{11})$$然后,应用相位黑盒以获取:$$|\text{register}\rangle=\frac12(\ket{{00}-\ket{{01}+\ket{{10}+\ket{{11})$$
然后
再次作用于每个量子比特,得到 $$|\text{register}\rangle=\frac12(\ket{{00}+\ket{{01}-\ket{{10}+\ket{{11})$$现在对除
以外的每个状态应用条件相移:$$|\text{register}\rangle=\frac12(\ket{{00}-\ket{{01}+\ket{{10}-\ket{{11})$$最后再次应用
,结束第一次 Grover 迭代,得到:$$|\text{register}\rangle=\ket{{01}$$执行上述步骤,可以在单个迭代中找到有效项。 如后所述,这是因为对于 N=4 和单个有效项,
。
为说明 Grover 算法为何有效,我们将从几何角度研究此算法。 让
$$\ket{\text{bad}}=\frac{{1}{\sqrt{N-M}}\sum_{x:f(x)=0}\ket{x}$$
将状态
$$\ket{\text{good}}=\frac{{1}{\sqrt{M}}\sum_{x:f(x)=1}\ket{x}$$
由于 good 和 bad 是互斥集(因为一个项不能既有效又无效),因此状态
现在,假设
其中
它被称为关于
如果将运算符
运算符
在 Grover 算法中,第一次向每个量子比特应用
因此此状态在平面中存在。 请注意,从相等叠加测量时获取正确结果的概率只是
黑盒
同样,条件相移
$$O_0 = R_{\ket{0}}= -2\ket{{0}\bra{0} + \mathcal{I}$$
了解这个事实后,很容易查明,Grover 扩散运算
$$-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 算法的每一次迭代都由
每个 Grover 迭代产生的综合效应是逆时针旋转的角度
寄存器的状态与
$$\gamma (k) =\frac{\pi}{2}-\theta -k2\theta =\frac{\pi}{{2} -(2k + 1) \theta $$
因此,成功的概率是:
由于成功概率可以表示为迭代次数的函数,因此,可通过计算使成功概率函数(接近)最大化的最小正整数,找到最佳的迭代次数
已知
$$\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)$$
在最后一步中,
因此,可以选择$N_N_\text{最佳\text{}$$=\left}\lfloor \frac{\pi}{{4}\sqrt{\frac{N}{M}}-{1}{2}\frac{\right\rfloor。$
通过前面的分析,需要查询黑盒
算法的总体复杂性最终取决于 oracle
若要继续了解 Grover 算法,可以访问以下资源:
- Lov K. Grover 的原创论文
- 尼尔森的量子搜索算法部分, M. A. &放大 器;庄,洛杉矶(2010年)。 《量子计算和量子信息》。
- Arxiv.org 上的 Grover 算法