量子搜索算法（知晓解的个数）_量子算法 量子穷举搜索

1.问题描述：

需要特别说明的是，在这里我们考虑的是已知在无结构的数据中存在几个问题的解，也只需要找出一个满足条件的问题的解就可以。搜索问题转换成经典的问题考虑就是，对于一个输入x，其中x属于[0,N-1]并且是一个整数，如果x是函数f(x)的解那么，f(x)=1,否则f(x)=0。

在经典问题问题里面我们需要逐个判断，但是在量子计算里面我们可以利用量子计算的并行性，将问题的复杂度降低到根号下N/M，下面看一下算法的基本核心：
（1）、标记解；

（2）、对解进行幅度放大

解的标记过程就用到了一个非常神奇的盒子，我们称之为Oracle盒。对于满足f(x)=1的输入值，经过这个盒子操作后就会发生相位变化。在《Quantum Computation and Quantum Information》这本书中是这样进行描述的：

简单对这段文字进行一下总结就是，这个神奇的黑盒，对于输入|x>|->并且x满足f(x)=1可以实现相位变换，转换成-|x>|->。这里用到的就是Deustch算法中的Uf变换思想以及利用|x>|->这个小技巧很容易地把满足条件的解标记了出来。

我们希望制备所有地址的叠加态，通过调用Qracle把目标和非目标以相位进行区分开，通过相位取反把目标标记出来，然后再想办法将目标元素进行幅度放大。那么这个神奇的盒子是如何构造出来的呢？具体过程如下：

我个人理解的LOAD就是把x所在的数据地址加载到量子态里面，后期利用我们所提到过的Uf操作让f(x)也参与进来，之所以让目标地址参与进来是因为后期我们要对满足条件的解进行地址标记。***（这一段纯属个人理解，有错误的话还请指正。）***
那如何测出解呢，具体步骤如下：

下面是我对于这整个过程中每一步的理解：
步骤1,2：制备均匀的叠加态是为了利用量子计算的并行性。在我学习的过程中曾经看到这么一句话“第一个量子比特是叠加态，可以实现并行计算”，结合那两个经典的量子并行算法，细细琢磨一下确实是这样的；
在第二步中已经将解自动分为了目标位和非目标位，前面的幅度就是目标位和非目标位的概率。

步骤3：这一步就是通过黑盒操作标记解，利用相位取反，真正的将目标元和非目标元区分开来；
步骤4：前面说过将解标记出来之后，我们就要想办法对解进行幅度放大操作，而这一步就是利用酉操作来进行幅度放大，每进行一次幅度放大操作，目标元前面对应的角度θ就会增加2θ，直到目标元前面的幅度接近1才停止这一步骤，在知晓M数值的情况下，幅度放大重复执行的次数大约为k次。
需要特别说明的是，我们在迭代结束但没有测量之前量子态是所有目标元的叠加态，但是一旦我们对这个叠加态进行测量，量子态就会塌缩，我们就能够得到一个目标元素。

通过图表的方式具体解释一下为什么每经过一次幅度放大，角度会增加2θ：

这是我自己推导的u为什么是酉操作，U也是Hermite算子哟：