本文最初为在下自学的手稿，后来在同学帮助下整理手写的公式成了latex图片之后一起做了ppt，正好近日要答辩整理思路并且记录为博客。引用了很多网上大佬的内容，道然很多后面的图是在下用ppt古法手搓，但是这个是之前的手稿如果引用不全还请私信我补充，感谢。引用见文末。

本文结合了很多大佬使用的几何方法和推导证明，几何方法更加适合理解，推导证明更加严谨一些，最后还有小型模拟代码的实现，因为在下脑子没有很好用，所以推导过程一般没有跳步，可能有些繁琐。

算法介绍

Grover 算法加快了无需搜索的速度，在经典计算机上要花费O(n)的复杂度的搜索室友Grover算法只需要O(根号n)

问题举例：

要从一幅画中识判断某个颜色在不在这个画中。(这里比如要找绿色)

经典计算机：

如果使用经典计算机，需要每个色块进行遍历。

运气好的话1次就找到了，运气不好的话需要n次，平均下来大概是n/2次。

所以复杂度是O(n)

量子计算机：

如果使用量子计算机，使用Grover算法借助量子叠加的特性和振幅放大的技巧。

就好像把所有色块叠加到一起，使用G函数进行迭代。

每次迭代会增加目标图层的不透明度，然后降低非目标的不透明度。

最终迭代r次之后再观测就只剩下我们的目标了。

Grover算法图示

如下:

篮框中的H门是用来制备叠加态的。

红框中的G即为每次迭代的函数

经过k次迭代后最后测得目标的概率就是100%

G门分为两个步骤分别为Uf和V来实现：

Uf门用来反转目标量子态(Oracle)

V门让组成量子态的所有基态都关于输入态的平均值反转

基础推导：

解决搜索问题：从N=2n个元素中找到目标元素w. 

满足映射关系: 则有：

细节流程图：

先看最前面的部分

一上来啥也没干，全是0态，用张量积表示

接下来是制备出来2^N搜索空间,每条路都过了H门，这里直接求N条路不方便求，先看N=2是啥情找找规律

然后再看N条路

几何方法：

加下来看Uf门和V的作用，先从几何角度看比较好理解。

镜像反转算符：

针对于Uf和V的作用，引入一个任意量子态和与其正交的量子态组成的平面，其中任意量子态|x>可表示为：

其中：

任意量子态为：

与其正交的量子态为：

接下来定义两个算符M和N

M作用与|x>：

N作用于|x>：

所以对于我们的运算符有：

VUf作用r次后逼近于目标态

这里每次都是theta是因为关于两条固定直线连续反射，等价于绕它们交点旋转一个固定角度，所以是r*theta

在VUf作用了r次之后

推导证明：

回到这张图

算符Uf

算符Uf0

运算符V

对于蓝绿部分

对于橙色部分先取n=1

电路推导第一轮迭代：

由前文S态为：

对|S>整理：

上式中，红绿蓝部分：

对|S>施加Uf得到

施加V得到

橙色部分：

第二轮迭代

施加Uf得到

同理第一次迭代，把结果整理成|S>与|w>组合

施加V得到

对比第1和第2轮迭代结果

代码实现

4qubite，在{0，1}4中寻找1111

引用：

笔记 | 第一个量子算法：Deutsch-Jozsa算法，非常好懂！ - 胡小兔 - 博客园

量子搜索算法(Grover Algorithm)-CSDN博客

量子搜索算法 Grover Algorithm - 知乎

量子计算笔记（10）-量子搜索算法（Grover算法）详解（一） - 知乎

Grover 搜索算法理论 - Azure Quantum | Microsoft Learn
量子计算（二十二）：Grover算法-CSDN博客

Attention Required! | Cloudflare

Grover搜索算法 - QuICT(opensource-docs)

传播安全知识、拓宽行业人脉——看雪讲师团队等你加入！