Grover's algorithm

$$ U_O=2|x_0\rangle\langle x_0|-I $$
$$ \begin{aligned}
U_S&=H(2|0\rangle\langle 0|-I)H \
&=2|s\rangle\langle s|-I
\end{aligned}

$$ (s = superposition) $$ |s\rangle = \frac{1}{\sqrt{N}}\sum_x |x\rangle$$ 注意到我们还有$\langle x_0|s\rangle =\langle s|x_0\rangle=\sqrt{1/N}$ $|x_0\rangle+\sum |x\neq x_0\rangle$ ## 子空间 定义$\{x_0, x_1\}$为一组矢量，存在变换A作用在$x_0$和$x_1$上后，运算封闭，即 $A x_0=u_{00} x_0 + u_{01} x_1$ $A x_1=u_{10} x_0 + u_{11} x_1$ 则$\{x_0, x_1\}$构成子空间，并且A是这个子空间上的一个变换，可以写出矩阵形式 $$

A = \begin{pmatrix}
u_{00} & u_{01}\
u_{10} & u_{11}
\end{pmatrix}

$$ ### 子空间性质 - 子空间的特征矢量、特征值？ - 子空间矢量的线性组合 - $x_0$和$x_1$不正交如何处理？ - 寻找正交（归一）基 ## Grover算法 ### 理论 **Lemma 1**. 在$ U_O$ 和$U_S $下， $|x_0\rangle$ 和 $|s\rangle$ 构成一个子空间，但是不正交 - Part 1. 显然易得$U_O$对于$|x_0\rangle$运算封闭，$U_S$ 对于 $|s\rangle$ 运算封闭 - Part 2. 因为$U_O|s\rangle=2|x_0\rangle\langle x_0|s\rangle-|s\rangle=\frac{2}{\sqrt N}|x_0\rangle-|s\rangle$，所以$U_O$对于$|x_0\rangle$和$|s\rangle$运算封闭 - Part 3. 因为$U_S|x_0\rangle=2|s\rangle\langle s|x_0\rangle-|x_0\rangle=\frac{2}{\sqrt N}|s\rangle-|x_0\rangle$，所以$U_S$对于$|x_0\rangle$和$|s\rangle$运算封闭 Q.E.D. **Lemma 2**. $|x_0\rangle$, $|x_0^\perp\rangle$是上述子空间的一组正交归一基，其中$|x_0^\perp\rangle=\frac{\sqrt{N}|s\rangle-|x_0\rangle}{\sqrt{N-1}}$ - $\langle x_0|\sqrt{N}|s\rangle-|x_0\rangle=1-1=0$，因此正交 - 归一化同样容易证明 Q.E.D. **Corollary 3**. $U_OU_S$对于上述子空间运算封闭 - 已经显然 **Theorem 4**. 证明$U_OU_S$是上述子空间的一组旋转变换，变换的矩阵可以写为 $$\begin{pmatrix} 1-2/N & -2\sqrt{N-1}/N \\ 2\sqrt{N-1}/N & 1-2/N \end{pmatrix}=\begin{pmatrix} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{pmatrix}, $$

其中$\theta=\arcsin \frac{2\sqrt{N-1}}{N}$. (QCQI Eqn. 6.13~6.14)

Theorem 5. $\langle x_0|(U_OU_S)^T|s\rangle\sim \sin{T\theta}$

我们有
$$|s\rangle=\frac{1}{\sqrt{N}}|x_0\rangle+\frac{\sqrt{N-1}}{\sqrt{N}}|x_0^\perp\rangle$$
且
$$(U_OU_S)^T=\begin{pmatrix}
\cos T\theta & -\sin T\theta \
\sin T\theta & \cos T\theta
\end{pmatrix}$$

因此$\langle x_0|(U_OU_S)^T|s\rangle=\frac{\cos T\theta}{\sqrt{N}}+\frac{\sqrt{N-1}\sin T\theta}{\sqrt{N}}$

由于我们有$\sqrt{N-1}>>1$，因此$\langle x_0|(U_OU_S)^T|s\rangle\sim \frac{\sqrt{N-1}}{\sqrt{N}}\sin T\theta\sim \sin T\theta$

Corollary 6. 选取$T=\pi/2\theta\sim O(\sqrt{N})$时，$(U_OU_S)^T$将$|s\rangle$以较大概率变换到$|x_0\rangle$

从Grover到振幅放大

Derandomization

Grover = 去随机化

Why amplitude amplification?

可逆计算中的不可逆操作 - e.g. 量子线性求解器

$Ax=b \longleftrightarrow |x\rangle=A^{-1}|b\rangle$

e.g.

$A|x\rangle \mapsto |y\rangle$

然而$A^{-1}$通常非幺正、不可逆，否则$A=A^\dagger$

• 在量子计算中实现不可逆操作的方法：增加“垃圾”

$$U_{A^{-1}}|b\rangle|0\rangle = \sqrt{p}|x\rangle|0\rangle+\sqrt{1-p}|\rm garbage\rangle|1\rangle$$

其中$|x\rangle$和$|\rm garbage\rangle$已经归一化

当第2个寄存器测到$|0\rangle$，说明算法成功，且成功率$p$。通常我们需要$O(1/p)$次测量以获取正确的结果。

Grover与振幅放大的关系

可以把Grover的搜索任务视作一个振幅放大任务，即给出下述Oracle
$$O|s\rangle|0\rangle=\sqrt{p}|x_i\rangle|0\rangle+\sqrt{1-p}|x\neq x_i\rangle|1\rangle$$
目标是找到$|x_i\rangle$，其中$\sqrt{p}=1/\sqrt{N}$.

$$|s\rangle = \frac{1}{\sqrt{4}}(|0\rangle+|1\rangle+|2\rangle+|3\rangle)$$
$$|x_0\rangle = |1\rangle$$
$$|x_0^\perp\rangle = \frac{1}{\sqrt{3}}(|0\rangle+|2\rangle+|3\rangle)$$
$$|s\rangle = \frac{1}{\sqrt{4}}(|0\rangle|0\rangle+|1\rangle|1\rangle+|2\rangle|0\rangle+|3\rangle|0\rangle)$$

显然Grover任务是振幅放大任务的子集。我们可以得知需要重复上述步骤$O(1/\sqrt{N})$次后，我们可以以较高概率得到$|x_i\rangle$. 这相对于$O(N)$次，加速到了$O(\sqrt{N})$次.

理论

Proposition 1 给出Oracle $U$，有$U|0,0\rangle = |\psi\rangle = \sqrt{p}|\mathrm{good}\rangle|0\rangle+\sqrt{1-p}|\mathrm{bad}\rangle|1\rangle$，我们可以通过$O(1/\sqrt{p})$次对$U$的调用，以较高概率制备$|\mathrm{good}\rangle$

注意 振幅放大算法不是$|\psi\rangle \rightarrow |\mathrm{good}\rangle|0\rangle$
而是$|0,0\rangle \rightarrow |\mathrm{good}\rangle|0\rangle$

振幅放大是一个基于U的过程，把U视作一个子过程，然后在一个更大的算法中进行$O(1/\sqrt{p})$次对$U$的调用，从而制备$|\mathrm{good}\rangle$

Lemma 2 $|\mathrm{good}\rangle|0\rangle$和$|\mathrm{bad}\rangle|1\rangle$构成一组正交归一化的子空间，且$U_S$和$U_O$对于它们运算封闭（是子空间上的变换）

• 对于$U_O$显然有这一点

• 对于$U_S$，我们有

  $$ \begin{aligned} U_S|\mathrm{good},0\rangle&=2|\psi\rangle\langle \psi|\mathrm{good},0\rangle-|\mathrm{good},0\rangle\\ &=2\sqrt{p}|\psi\rangle-|\mathrm{good},0\rangle\\ &=(2p-1)|\mathrm{good},0\rangle+2\sqrt{p}|\mathrm{bad},1\rangle \end{aligned} $$

$$ \begin{aligned} U_S|\mathrm{bad},1\rangle&=2|\psi\rangle\langle \psi|\mathrm{bad},1\rangle-|\mathrm{bad},1\rangle\\ &=2\sqrt{1-p}|\psi\rangle-|\mathrm{bad},1\rangle\\ &=(2\sqrt{(1-p)p})|\mathrm{good},0\rangle+(1-2p)|\mathrm{bad},1\rangle \end{aligned} $$

Q.E.D

Lemma 3 $U_OU_S$构成了在$|\mathrm{good}\rangle|0\rangle$和$|\mathrm{bad}\rangle|1\rangle$上的一组旋转矩阵，其中旋转角为$\theta \sim \arcsin \sqrt p\sim \sqrt{p}$

Theorem 4 当$n=\pi /2\theta\sim \pi/2\sqrt{p}$时，以较大概率得到$|\mathrm{good},0\rangle$.