阅读 452 次 , 阅读 1 次
Grover 算法
Grover算法是由Lov Grover提出的基于量子Oracle的算法[1]。该问题定义为在给定Oracle访问函数 的情况下,在包含 个项目的列表中搜索一个项目。该函数具有以下定义属性:如果 是我们要查找的项目,则 ;否则, 。针对这个黑盒搜索问题,提出了一种量子算法,它以高概率执行 次Oracle查询来找到答案,而任何经典算法都需要 次查询。
构建Oracle
对于本教程中的示例,我们的”数据库”由量子位所有可能的计算基态组成。例如,如果我们有3个量子位,我们的列表就是态
(即态 )。
Grover算法求解的是给解答态添加负相位的Oracle。即对于计算基中的任意态 :
这个Oracle将是一个对角矩阵,其中对应于被标记项目的条目将有一个负相位。例如,如果我们有三个量子位且 ,我们的Oracle矩阵为:
Grover算法如此强大,原因在于将问题转化为这种形式的Oracle非常容易。在许多计算问题中,找到解答很困难,但验证解答却相对容易。对于这些问题,我们可以创建一个函数 ,它接受一个提议的解 ,如果 不是解( )则返回 ,对于有效的解( )返回 。然后我们的Oracle可以描述为:
Oracle的矩阵将是如下形式的对角矩阵:
振幅放大
那么算法是如何工作的呢?在查看项目列表之前,我们不知道被标记的项目在哪里。因此,任何猜测其位置的尝试都与其他一样有效,这可以用均匀叠加态来表示: 。
如果在这一点上,我们按标准基 进行测量,这个叠加态会以 的相同概率坍缩到任何一个基态。因此我们猜对正确值 的概率为 ,正如预期的那样。因此,平均而言,我们需要尝试大约 次才能猜到正确的项目。
接下来是振幅放大过程,这就是量子计算机显著提高这个概率的方法。该过程拉伸(放大)被标记项目的振幅,同时压缩其他项目的振幅,从而以接近确定性的概率测量到最终态时能返回正确的项目。
该算法在两个反射的几何解释方面有一个很好的几何解释,它们在二维平面内生成旋转。我们需要考虑的唯一两个特殊态是目标态 和均匀叠加态 。这两个向量在向量空间 中张成一个二维平面。它们并不完全正交,因为 也以 的振幅出现在叠加态中。但是,我们可以引入一个额外的态 ,它位于这两个向量的张成空间中,与 正交,并通过移除 并重新归一化从 获得。
步骤1:振幅放大过程从均匀叠加态 开始,它可以很容易地从 构造出来。
左图对应于由正交向量 和 张成的二维平面,它允许将初始态表示为 ,其中 。右图是态 的振幅条形图。
步骤2:我们将Oracle反射 应用于态 。
几何上这对应于态 关于 的反射。这个变换意味着 态前面的振幅变为负值,这反过来意味着平均振幅(用虚线表示)已经降低。
步骤3:现在我们应用关于态 的额外反射( ): 。该变换将态映射到 并完成变换。
两个反射总是对应于一个旋转。变换 将初始态 旋转得更接近目标态 。在振幅条形图中,反射 的作用可以理解为关于平均振幅的反射。由于第一个反射降低了平均振幅,该变换将 的负振幅提升到原来的大约三倍,同时降低其他振幅。然后我们回到步骤2重复应用。这个过程将重复多次以锁定目标态。
经过 步,我们将处于态 ,其中: 。
我们需要应用旋转多少次?事实证明,大约 次旋转就足够了。当观察态 的振幅时,这一点变得很清楚。我们可以看到 的振幅随着应用次数线性增长 。然而,由于我们处理的是振幅而不是概率,向量空间的维度作为平方根出现。因此,在这个过程中被放大的是振幅,而不仅仅是概率。
在有多个解 的情况下,可以证明大约需要 次旋转。
示例:2个量子比特
让我们首先来看一下使用2个量子比特实现的 Grover 算法在 的情况[2]。在这种特殊情况下,只需要一次旋转就可以将初始态 旋转到获胜态 :
- 按照上述介绍,在 的情况下,我们有:
- 经过 步后,我们得到:
其中:
3. 为了获得 ,我们需要 。将 代入上式可得 。这意味着经过 次旋转就可以找到目标元素。
下面我们将通过一个使用特定 Oracle 的示例来详细说明。
() 的 Oracle:
我们来看 的情况。此时 Oracle 的作用如下:
或者用矩阵形式表示为:
你可能会认出这就是受控-Z 门。因此,在这个例子中,我们的 Oracle 就是一个受控-Z 门:
c:\Users\HP\.conda\envs\dq\lib\site-packages\qiskit\visualization\circuit\matplotlib.py:266: FutureWarning: The default matplotlib drawer scheme will be changed to "iqp" in a following release. To silence this warning, specify the current default explicitly as style="clifford", or the new default as style="iqp".
self._style, def_font_ratio = load_style(self._style)
反射 ():
为了完成电路,我们还需要实现额外的反射 。由于这是关于 的反射,我们希望对每个与 正交的态都加一个负相位。
实现这一点的一种方法是使用将态 转换为 的操作,我们已知对每个量子比特施加 Hadamard 门即可实现:
然后我们再施加一个电路,对所有与 正交的态都加一个负相位:
即除了 以外,其他每个态的符号都被翻转了。
最后,我们再做一次将态 转换为态 的操作(再次使用 H 门):
的完整电路如下所示:
() 的完整电路:
由于在 的特殊情况下只需要一次旋转,因此我们可以将上述组件组合起来,构建 Grover 算法在 情况下的完整电路:
让我们在模拟中运行这个电路。首先,我们可以验证我们得到了正确的态向量:
正如预期的那样,除了 以外所有态的振幅都是 0,这意味着我们有 100% 的概率测量到 :
tensor([[0.0000+0.j],
[0.0000+0.j],
[0.0000+0.j],
[1.0000+0.j]])
Grover算法总结
- 初始化状态:算法起始于全状态。通过对每个量子比特应用Hadamard门操作,我们得到一个均等叠加状态,为接下来的步骤打下基础。
-
Grover迭代:算法的核心在于重复执行以下两个步骤,这一过程被称为Grover迭代:
- 对当前状态相对于状态进行反射;
- 接着,对当前状态相对于状态进行反射。
这一迭代过程的重复次数为:
- 测量与验证:经过上述迭代后,进行测量,以不低于的概率得到搜索问题的解。随后,使用搜索黑盒检验测量结果,以确认其是否为问题的解答。若是,则算法成功完成;若不是,则需要重新运行算法。
通过这一系列步骤,量子搜索算法能以次操作,在含有个元素的搜索空间中高效地定位被搜索的元素。此算法不仅提高了搜索效率,同时也展示了量子计算在处理复杂问题时的潜力。
参考文献
[1] Grover L K. A fast quantum mechanical algorithm for database search[C]//Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. 1996: 212-219.
[2] Nielsen M A, Chuang I L. Quantum computation and quantum information[M]. Cambridge university press, 2010.