量子算法介绍——神奇的Grover算法

作者：IT小白 | 2024-05-20 18:29:07

踩

grover算法

一、整体介绍

Grover算法，一般也叫作量子搜索算法，他是一种可以直接应用的量子算法，且有明确的二次加速。同样Grover算法也可以作为一个大类算法中的一部分，例如由Grover算法为基础的GAS算法。

Grover算法中的核心步骤是Oracle的构造，简单来说就是如何在量子态中使用极低的复杂度标记出目标状态，如何构造Oracle至关重要，而且需要针对不同的问题构造不同的Oracle，Oracle的重要程度相当于QAOA算法中的哈密顿量的构造，哈密顿量构造也是需要针对问题进行设计。

Grover算法简单的说就是先使用Oracle将答案标记出来，然后一步一步放大被标记的答案，这样我们在观测的时候就能够以很高的概率得到我们想要的答案，而放大的次数大约只需要经典遍历次数的根号级别，这就体现出了平方级的加速效果，我们主要的介绍不在于Oracle的构造，而是在于如何进行概率的放大的线路，也就是所谓的“振幅放大”。

二、振幅放大的原理推导

一般来说Grover算法是从大小为 $N=2^n$ 的空间中进行搜索的，如果不足就补上一些错误的答案使整个空间的大小成为2的次幂，所以一开始一般需要制备均匀的量子叠加态，使其充满整个空间。最简单的制备方法则是在n个量子比特上使用n个 $H$ 门即可得到我们想要的均匀叠加态：

$\left | \psi \right \rangle=\frac{1 }{\sqrt{N}}\sum_{i=0}^{N-1}\left | \ i \right \rangle$

假设这其中有 $M$ 个量子态是我们想要的答案集合 $B$ ，剩余的不是我们需要的答案，那么我们可以重新将这个均匀叠加态写成如下三角函数形式：

$\left | \psi \right \rangle=\sin\theta \left | \varphi_1 \right \rangle +\cos \theta \left | \varphi_0 \right \rangle$

其中 $\left | \varphi_0 \right \rangle=\frac{1 }{\sqrt{N-M}}\sum_{x\in B}\left | \ x\right \rangle$ ， $\left | \varphi_1 \right \rangle=\frac{1 }{\sqrt{M}}\sum_{x\in B}\left | \ x\right \rangle$ ，

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/598796