Grover

Grover算法

搜索算法是利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况，从而求出问题的解的一种方法。现阶段一般有枚举算法、深度优先搜索、广度优先搜索、A*算法、回溯算法、蒙特卡洛树搜索、散列函数等算法。比较常见的一种应用场景就是A到B的最短耗时路径搜索，一般的传统方法我们至少要把所有的路径遍历一遍来求解，而量子Grover算法只需要$O(\sqrt(n))$的复杂度就能解决该问题。

具体而言，Grover算法是一种量子算法，于1996年由计算机科学家 Lov Grover提出。假设现在有一个未知的函数，Grover算法只需对此未知的函数做$O(\sqrt(n))$次测试，就能求得满足未知函数方程的解。下面详细介绍Grover算法的过程，首先我们定义如下的求解问题

假定$N=2^n$(后面会知道为何这样设计)的搜索空间，有M个解，且$x$从$1$~$(N-1)$的数(简化了搜索空间)，输入x对应的输出用$f(x)$表示，$\Omega$定义为可能解集合，于是搜索问题可以表示为

$f: \Omega \longrightarrow\{0,1\}$

那么现在要找满足$f(x)=1$的解$x$,假设被查找的集合为$\{|i\rangle\}=\{|0\rangle,|1\rangle, \cdots,|N-1\rangle\}$，并且量子Orcale可以识别搜素问题的解，Orcale可定义为

$|x\rangle|q\rangle \stackrel{\text { Orade }}{\longrightarrow}|x\rangle|q \oplus f(x)\rangle$

其中，$|q\rangle$是一个结果寄存器。通过Oracle, 当搜索的索引为目标结果时, 结果寄存器翻转；不是目标结果时, 结果寄存器不变。举个例子，例如当$|q\rangle$为$|0\rangle$，$f(x)=1$时，那么二者的"$\oplus$"运算就是1，会存到结果寄存器$|q\rangle$中，相对于初始为$|0\rangle$，它显然时发生了寄存器反转，因此我们通过Orcale得到了目标结果。反之当$f(x)=0$时，0和0的异或还是0，就没有发生反转，这就不是我们要求的解，同理当$|q\rangle$初始为$|1\rangle$也一样。

因此简单来说, Oracle 的大致功能可以作如下定义

$O_{\omega}|x\rangle=\left\{\begin{array}{ll} |x\rangle, & \text { if } x \neq \omega \\ -|x\rangle, & \text { if } x=\omega \end{array}\right.$

配合两个寄存器, Oracle 对量子态的具体操作为：先将初态制备在态$|0\rangle \oplus^{n}|1\rangle$上。$|0\rangle \oplus^{n}$为查询寄存器，$|1\rangle$为结果寄存器。经过 H 门操作后, 可以将查询寄存器的
量子态, 变为所有结果的叠加态, 即得到所有结果的索引, 且结果寄存器变为$H|1\rangle=(|0\rangle-|1\rangle) / \sqrt{2}$，再使其通过 Oracle, 可以对每一个索引进行检验， 若是目
标结果, 则将结果寄存器的量子态进行 0、1 翻转，即

$\frac{1}{\sqrt{2}}(|1\rangle-|0\rangle)=-\frac{1}{\sqrt{2}}(|1\rangle-|0\rangle)$

由此可见，我们通过H门处理量子比特，能够将解问题转为相位变化的问题，那么整个解空间可表示为

$|0\rangle \oplus^{n} \stackrel{\text { Hadamard }}{\longrightarrow}|\psi\rangle=\frac{1}{\sqrt{N}} \sum_{x}|x\rangle$

再将所有非搜索问题$N-M$的解定义为一个量子态$|\alpha\rang$，记为（推导方式同上）

$|\alpha\rangle=\frac{1}{\sqrt{N-M}} \sum_{x_{1}}|x\rangle$

那么, 令$|\beta\rang$为最终的量子态, 且$|\alpha\rang$与$|\beta\rang$正交, 初态可重新表示为$|\psi\rangle$

$|\psi\rangle=\sqrt{\frac{N-M}{N}}|\alpha\rangle+\sqrt{\frac{M}{N}}|\beta\rangle$

将该量子态经过H门，就相当于对$|\beta\rang$所在的最终量子态进行了反转操作，上面有说明，得到

$|\psi\rangle=\sqrt{\frac{N-M}{N}}|\alpha\rangle-\sqrt{\frac{M}{N}}|\beta\rangle$

这相当于关于$|\alpha\rang$的第一种对称操作，这时还不能将量子态$|\Psi\rang$变为$|\beta\rang$，还需要一个H门将量子态再关于$|\Psi\rang$对称(第二种对称操作)，这两个对称操作称为一次Grover迭代，假设初态$|\Psi\rang$可以表示为

$|\psi\rangle=\cos \frac{\theta}{2}|\alpha\rangle+\sin \frac{\theta}{2}|\beta\rangle$

现在的目标呢就是通过对$|\Psi\rang$进行Grover迭代，将其映射成为我们的目标解$|\beta\rang$，那么经过k次Grover迭代之后，末态为

$G^{k}|\psi\rangle=\cos \left(\frac{2 k+1}{2} \theta\right)|\alpha\rangle+\sin \left(\frac{2 k+1}{2} \theta\right)|\beta\rangle$

可见经过多次迭代，可以使末态在$|\beta\rang$上的概率足够大，最终我们希望得到的是$(2k+1)\theta=\pi/2$，这样就能够搜索到想要的方程解$|\beta\rang$。根据计算搜索到$|\beta\rang$的概率为（注意：这里$sin\theta=\sqrt{\frac{M}{N}}$,因此才有了后面的$1-O(\frac{1}{2^n})$）

$P=|<\beta| \psi_{T}>\left.\right|^{2}=\sin ^{2}(\frac{2k+1}{2} \theta)=1-O\left(\frac{1}{2^{n}}\right)$

所以量子搜索的次数为$\frac{\pi}{4} \sqrt{\frac{2^{n}}{M}}=\frac{\pi}{4}\sqrt{N/M}$，而经典搜索是$2^{n}=N$，相比之下量子搜索实现了根号级别的加速。用图片表示Grover算法的过程如下

然后本周还在准备了华为软件精英挑战赛。