量子计算（七）——振幅放大与振幅估计

零、声明

这篇文章基于Brassard的论文Quantum amplitude amplification and estimation [1] 写成，大致概括了其中的算法思路，并具体计算了其中一些内容。因此这篇文章的主题就是数学计算，难度相比之前会有较大的跃升。但之后会回到原先基础算法的简单讲解。

事实上，如果读完了这篇文章，基本就相当于理解了 Grover 算法的原理。笔者原准备讲述完 Grover 算法之后再发出这篇文章，但现在笔者正在思考是否应该在下一篇文章中更细致地讲 Grover 算法。

另外，请读者务必注意：

注 1.

文章中符号众多，并且在后面再次提及时不会重新解释其含义，因此请读者在阅读过程中务必直接记住各符号的含义。

一、振幅放大的问题背景

1.问题引入

这个算法要解决的问题就是在解空间中寻找符合标准的解。设每个解都可以表示为二进制字符串，并且已知某种能够确定解空间中各个解的好坏的标准。

也就是给出布尔函数 $𝒳︀$ ，它将解空间中的解 $𝑥$ 映射到 ${0, 1}$ ：

𝒳︀ (𝑥) = {\begin{cases} 0 & , if 𝑥 is bad \\ 1 & , if 𝑥 is good \end{cases}

这个目标基本和 Grover 算法要解决的问题是一致的。事实上， Grover 算法中的核心算法就是振幅放大，这篇论文就是对 Grover 算法的总结推广，使得任意无测量量子算法也可以使用。

2.量子化

显然，由于解空间被表示为二进制串，因而解空间可以作为一个希尔伯特空间，从而允许量子算法的运行。而解的好坏，则将其划分为两个子空间——称为好空间与坏空间。于是解空间的任意纯态 $| 𝜓 ⟩$ 都可以被分解表示为：

| 𝜓 ⟩ = | 𝜓_{0} ⟩ + | 𝜓_{1} ⟩

其中 $| 𝜓_{0} ⟩$ 表示落入坏空间的部分，相应地 $| 𝜓_{1} ⟩$ 表示落入好空间的部分。于是 $𝑏_{𝜓} = ⟨ 𝜓_{0} | 𝜓_{0} ⟩$ 表示了对这个纯态测量后得到坏结果的概率， $𝑎_{𝜓} = ⟨ 𝜓_{1} | 𝜓_{1} ⟩$ 则是得到好结果的概率，以后简记为 $𝑎$ 。显然 $𝑎_{𝜓} + 𝑏_{𝜓} = 1$ 。

到这一步，我们的目标就已经清晰明朗了：只要让好空间部分的 $| 𝜓_{1} ⟩$ 振幅变大，就提高了测到好结果的概率。之后只需要代入 $𝒳︀$ 判定其是否确实是好结果即可。

二、振幅放大的构建

1.振幅放大算符 $𝐐$

假定 $𝑛$ 是解空间的二进制串的长度。假设无测量量子算法 $𝒜︀$ 是作用到解空间上的酉矩阵，并假设纯态 $| Ψ ⟩$ 是由其作用到初始零态的结果即 $| Ψ ⟩ = 𝒜︀ | 0^{𝑛} ⟩$ 。那么如下构建的算符 $𝐐$ 即可实现振幅放大：

𝐐 = 𝐐 (𝒜︀, 𝒳︀) = - 𝒜︀ 𝐒_{0} {𝒜︀}^{- 1} 𝐒_{𝒳︀}

其中， $𝐒$ 代表这个矩阵算符会改变振幅的符号，而下标表示改变的条件：

𝐒_{0} | 𝑥 ⟩ = {\begin{cases} - | 𝑥 ⟩ & , if 𝑥 = 0^{𝑛} \\ | 𝑥 ⟩ & , if 𝑥 \neq 0^{𝑛} \end{cases}

𝐒_{𝒳︀} | 𝑥 ⟩ = {\begin{cases} - | 𝑥 ⟩ & , if 𝒳︀ (𝑥) = 1 \\ | 𝑥 ⟩ & , if 𝒳︀ (𝑥) = 0 \end{cases}

显然可以将 $𝐒_{0}$ 写为 $𝐼 - 2 | 0^{𝑛} ⟩ ⟨ 0^{𝑛} |$ ，于是：

\begin{aligned} 𝒜︀ 𝐒_{0} {𝒜︀}^{- 1} & = 𝒜︀ (𝐼 - 2 | 0^{𝑛} ⟩ ⟨ 0^{𝑛} |) {𝒜︀}^{- 1} \\ = 𝐼 - 2 𝒜︀ | 0^{𝑛} ⟩ ⟨ 0^{𝑛} | {𝒜︀}^{- 1} \\ = 𝐼 - 2 | Ψ ⟩ ⟨ Ψ | \end{aligned}

现在我们来研究算符 $𝐐$ 作用到任意态上会发生什么。由于在这个问题中纯态被分解为好纯态和坏纯态，因此研究此算符分别作用到好坏纯态上的结果。首先是坏纯态 $| Ψ_{0} ⟩$ ：

\begin{aligned} 𝐐 | Ψ_{0} ⟩ & = - 𝒜︀ 𝐒_{0} {𝒜︀}^{- 1} 𝐒_{𝒳︀} | Ψ_{0} ⟩ \\ = - 𝒜︀ 𝐒_{0} {𝒜︀}^{- 1} | Ψ_{0} ⟩ \\ = - (𝐼 - 2 | Ψ ⟩ ⟨ Ψ |) | Ψ_{0} ⟩ \\ = - | Ψ_{0} ⟩ + 2 (1 - 𝑎) | Ψ ⟩ \\ = (1 - 2 𝑎) | Ψ_{0} ⟩ + 2 (1 - 𝑎) | Ψ_{1} ⟩ \end{aligned}

同理对于好纯态 $| Ψ_{1} ⟩$ ：

\begin{aligned} 𝐐 | Ψ_{1} ⟩ & = - 𝒜︀ 𝐒_{0} {𝒜︀}^{- 1} 𝐒_{𝒳︀} | Ψ_{1} ⟩ \\ = (𝐼 - 2 | Ψ ⟩ ⟨ Ψ |) | Ψ_{1} ⟩ \\ = | Ψ_{1} ⟩ - 2 𝑎 | Ψ ⟩ \\ = - 2 𝑎 | Ψ_{0} ⟩ + (1 - 2 𝑎) | Ψ_{1} ⟩ \end{aligned}

2.振幅如何被放大

计算可得 $| Ψ ⟩$ 被施加 $𝑘$ 次 $𝐐$ 算符后得到：

𝐐^{𝑘} | Φ ⟩ = \frac{1}{\sqrt{1 - 𝑎}} cos ((2 𝑘 + 1) 𝜃) | Φ_{0} ⟩ + \frac{1}{\sqrt{𝑎}} sin ((2 𝑘 + 1) 𝜃) | Φ_{1} ⟩

即测得好纯态的概率是 ${sin}^{2} ((2 𝑘 + 1) 𝜃)$ 。得到的结果中出现了角度参数，这意味着算法在几何上一定有直观的表现。

证明. 假设对 $| Ψ ⟩$ 施加 $𝑘 - 1$ 次 $𝐐$ 算符后：

𝐐^{𝑘 - 1} | Ψ ⟩ = 𝑆_{𝑘} | Ψ_{0} ⟩ + 𝑇_{𝑘} | Ψ_{1} ⟩

也就是好纯态的振幅变为 $𝑇_{𝑘}$ ，显然可以得到下列递推式：

{\begin{cases} 𝑆_{𝑘 + 1} = (1 - 2 𝑎) 𝑆_{𝑘} - 2 𝑎 𝑇_{𝑘} \\ 𝑇_{𝑘 + 1} = (2 - 2 𝑎) 𝑆_{𝑘} + (1 - 2 𝑎) 𝑇_{𝑘} \end{cases}, {\begin{cases} 𝑆_{1} = 1 \\ 𝑇_{1} = 1 \end{cases}

为了解出上式，首先计算 $𝑆_{𝑘}$ 与 $𝑇_{𝑘}$ 的线性组合：

𝑥 𝑆_{𝑘 + 1} + 𝑦 𝑇_{𝑘 + 1} = [𝑥 (1 - 2 𝑎) + 𝑦 (2 - 2 𝑎)] 𝑆_{𝑘} + [- 2 𝑎 𝑥 + 𝑦 (1 - 2 𝑎)] 𝑇_{𝑘}

上式能成为等比递推式的条件是：

𝜆 = \frac{𝑥 (1 - 2 𝑎) + 𝑦 (2 - 2 𝑎)}{𝑥} = \frac{- 2 𝑎 𝑥 + 𝑦 (1 - 2 𝑎)}{𝑦}

显然可取 $𝑥 = \sqrt{𝑎 - 1}, 𝑦 = \sqrt{𝑎}$ 从而 $𝜆 = 1 - 2 𝑎 - 2 \sqrt{𝑎 (𝑎 - 1)}$ 。记 $𝑢_{𝑘} = \sqrt{𝑎 - 1} 𝑆_{𝑘} + \sqrt{𝑎} 𝑇_{𝑘}$ ，则 $𝑢_{1} = \sqrt{𝑎 - 1} + \sqrt{𝑎}$ ，则 $𝑢_{𝑘} = 𝜆^{𝑘 - 1} 𝑢_{1}$ 。于是：

𝑆_{𝑘} = \frac{𝜆^{𝑘 - 1} 𝑢_{1}}{\sqrt{𝑎 - 1}} - \sqrt{\frac{𝑎}{𝑎 - 1}} 𝑇_{𝑘}

代入递推方程组之第二式得：

𝑇_{𝑘 + 1} = (1 - 2 𝑎 + 2 \sqrt{𝑎 (𝑎 - 1)}) 𝑇_{𝑘} - \frac{2 \sqrt{𝑎 - 1} 𝑢_{1}}{𝜆} 𝜆^{𝑘}

记 $𝐴 = 1 - 2 𝑎 + 2 \sqrt{𝑎 (𝑎 - 1)}$ ， $𝐵 = \frac{2 \sqrt{𝑎 - 1} 𝑢_{1}}{𝜆}$ ， $𝐶 = 𝜆 = 1 - 2 𝑎 - 2 \sqrt{𝑎 (𝑎 - 1)}$ 。已知递推形式 $𝑎_{𝑛 + 1} = 𝐴 𝑎_{𝑛} + 𝐵 𝐶^{𝑛}$ 在 $𝐴 \neq 𝐶$ 时具有通项：

𝑎_{𝑛} = 𝑎_{1} 𝐴^{𝑛 - 1} + 𝐵 𝐶 \frac{𝐴^{𝑛 - 1} - 𝐶^{𝑛 - 1}}{𝐴 - 𝐶}

代入可得：

\begin{aligned} 𝑇_{𝑘} & = \frac{\sqrt{𝑎} - \sqrt{𝑎 - 1}}{2 \sqrt{𝑎}} {(1 - 2 𝑎 + 2 \sqrt{𝑎 (𝑎 - 1)})}^{𝑘 - 1} \\ + \frac{\sqrt{𝑎} + \sqrt{𝑎 - 1}}{2 \sqrt{𝑎}} {(1 - 2 𝑎 - 2 \sqrt{𝑎 (𝑎 - 1)})}^{𝑘 - 1} \end{aligned}

或者说，对于 $𝐐^{𝑘} | Ψ ⟩$ ，若记 $𝑎 = {sin}^{2} 𝜃$ 且不等于 $0$ 或 $1$ 且限定 $𝜃 \in (0, \frac{𝜋}{2}]$ ，那么其好纯态的振幅是：

\begin{aligned} 𝑇_{𝑘 + 1} & = \frac{\sqrt{𝑎} - \sqrt{𝑎 - 1}}{2 \sqrt{𝑎}} {(1 - 2 𝑎 + 2 \sqrt{𝑎 (𝑎 - 1)})}^{𝑘} \\ + \frac{\sqrt{𝑎} + \sqrt{𝑎 - 1}}{2 \sqrt{𝑎}} {(1 - 2 𝑎 - 2 \sqrt{𝑎 (𝑎 - 1)})}^{𝑘} \\ = \frac{sin 𝜃 - i cos 𝜃}{2 \sqrt{𝑎}} {(1 - 2 {sin}^{2} 𝜃 + i 2 sin 𝜃 cos 𝜃)}^{𝑘} \\ + \frac{sin 𝜃 + i cos 𝜃}{2 \sqrt{𝑎}} {(1 - 2 {sin}^{2} 𝜃 - i 2 sin 𝜃 cos 𝜃)}^{𝑘} \\ = \frac{- e^{i (\frac{𝜋}{2} + 𝜃)}}{2 \sqrt{𝑎}} {(cos 2 𝜃 + i sin 2 𝜃)}^{𝑘} + \frac{e^{i (\frac{𝜋}{2} - 𝜃)}}{2 \sqrt{𝑎}} {(cos 2 𝜃 - i sin 2 𝜃)}^{𝑘} \\ = \frac{- e^{i (\frac{𝜋}{2} + (2 𝑘 + 1) 𝜃)}}{2 \sqrt{𝑎}} + \frac{e^{i (\frac{𝜋}{2} - (2 𝑘 + 1) 𝜃)}}{2 \sqrt{𝑎}} \\ = \frac{1}{\sqrt{𝑎}} \cdot sin ((2 𝑘 + 1) 𝜃) \end{aligned}

□

3.算符 $𝐐$ 的几何意义

首先显然易见的是 $| Ψ_{0} ⟩$ 与 $| Ψ_{1} ⟩$ 是正交的，因此完全可以将这两个态作为平面坐标系的两个轴，并将 $| Ψ ⟩$ 标注其中(而 $𝑎 = {sin}^{2} 𝜃$ 中的 $𝜃$ ，就是 $| Ψ ⟩$ 与 $| Ψ_{0} ⟩$ 的张角)：

现在我们将算符 $𝐐$ 拆开为两部分： $𝐒_{𝒳︀}$ 与 $- 𝒜︀ 𝐒_{0} {𝒜︀}^{- 1} = 2 | Ψ ⟩ ⟨ Ψ | - 𝐼$ 。不妨首先观察 $𝐒_{𝒳︀}$ ，对于任意能够被拆分为好纯态与坏纯态的态 $| Ψ ⟩ = | Ψ_{0} ⟩ + | Ψ_{1} ⟩$ ：

𝐒_{𝒳︀} | Ψ ⟩ = | Ψ_{0} ⟩ - | Ψ_{1} ⟩

这意味着将 $| Ψ ⟩$ 以 $| Ψ_{0} ⟩$ 为轴做了一次对称，即：

而在此基础上再作用一次 $2 | Ψ ⟩ ⟨ Ψ | - 𝐼$ ：

\begin{aligned} (2 | Ψ ⟩ ⟨ Ψ | - 𝐼) (| Ψ_{0} ⟩ - | Ψ_{1} ⟩) \\ = & (2 (1 - 𝑎) | Ψ ⟩ - | Ψ_{0} ⟩) - (2 𝑎 | Ψ ⟩ - | Ψ_{1} ⟩) \\ = & (1 - 4 𝑎) | Ψ_{0} ⟩ + (3 - 4 𝑎) | Ψ_{1} ⟩ \\ = & 𝐐 | Ψ ⟩ \end{aligned}

不妨计算 $𝐐 | Ψ ⟩$ 与 $𝐒_{𝒳︀} | Ψ ⟩$ 的中点坐标：

(\frac{1 + (1 - 4 𝑎)}{2}, \frac{- 1 + (3 - 4 𝑎)}{2}) = (1 - 2 𝑎, 1 - 2 𝑎)

此时我们发现，此坐标正好在 $| Ψ ⟩$ 的射线上！这意味着再作用一次 $2 | Ψ ⟩ ⟨ Ψ | - 𝐼$ 是将 $𝐒_{𝒳︀} | Ψ ⟩$ 以 $| Ψ ⟩$ 为轴再做一次对称，也就是：

因此，作用一次算符 $𝐐$ 就相当于将原来的态向 $| Ψ_{1} ⟩$ 靠近 $2 𝜃$ 。加上原先就存在的一个 $𝜃$ ，就形成了 $(2 𝑘 + 1) 𝜃$ 。这也是好纯态振幅中 $sin ((2 𝑘 + 1) 𝜃)$ 的来历。

4.算符 $𝐐$ 作用的次数

显然我们希望测得好纯态的概率越大越好，这就要求 ${sin}^{2} ((2 𝑘 + 1) 𝜃) \to 1$ ，即 $(2 𝑘 + 1) 𝜃 \to \frac{𝜋}{2}$ ，即 $𝑘 = \frac{𝜋}{4 𝜃} - \frac{1}{2} \to ⌊ \frac{𝜋}{4 𝜃} ⌋$ 。以后记 $\tilde{𝑚} = \frac{𝜋}{4 𝜃} - \frac{1}{2}, 𝑚 = ⌊ \frac{𝜋}{4 𝜃} ⌋$ 。

此时重新计算测得好纯态的概率：

\begin{aligned} {sin}^{2} ((2 𝑚 + 1) 𝜃) & \approx {sin}^{2} ((⌊ \frac{𝜋}{2 𝜃} ⌋ + 1) 𝜃) \\ \approx {sin}^{2} (⌊ \frac{𝜋}{2} ⌋ + 𝜃) \\ \geq {sin}^{2} (\frac{𝜋}{2} + 𝜃) \\ = 1 - {sin}^{2} 𝜃 \\ = 1 - 𝑎 \end{aligned}

¹¹ 虽然 ${sin}^{2} ((2 𝑚 + 1) 𝜃) \geq 1 - 𝑎$ 这一结论是正确的，但上式的证明是稍有问题的，即 ${sin}^{2} (1 + 𝜃) \geq {sin}^{2} (\frac{𝜋}{2} + 𝜃)$ 这一步。但至少在 $𝜃 \in [0.2854, 1.8562]$ 范围内是正确的。错误的根本原因在于向下取整符号内的分母不能与外部直接约分。要想完美证明，接下来只需证 $𝜃 \in [0, 0.2854]$ 内成立即可，这里不再证明。论文中的证明是引用另一篇文章[2] ，请自行观阅。也就是说测量到好纯态的概率是大于 $1 - 𝑎$ 的；同时由于本就是对好纯态振幅的放大，因此这个概率也大于 $𝑎$ 。因此最后测到好纯态的概率至少是 $max {𝑎, 1 - 𝑎}$ 。

然而这引申出一个问题：之所以能要求让 $𝐐$ 作用 $⌊ \frac{𝜋}{4 𝜃} ⌋$ 次，是因为我们已知了 $𝜃$ 值，即已知了 $𝑎$ 值，即已知在最初的时候能够测得好纯态的概率，例如 Grover 算法中就是如此。但在实际问题中，很多时候这个值具有置信度，甚至完全未知，此时则不能确定 $𝐐$ 作用的次数。因此，我们有必要从 Grover 搜索算法进一步推广。

5.算符 $𝐐$ 的特征值与特征向量

除了数列递推外，我们也可以通过将 $𝐐$ 对角化后，简便地得到 $𝐐^{𝑘}$ 。为此假设：

𝐐 (𝑥 | Ψ_{0} ⟩ + 𝑦 | Ψ_{1} ⟩) = 𝜆 (𝑥 | Ψ_{0} ⟩ + 𝑦 | Ψ_{1} ⟩)

显然有方程：

𝜆 = \frac{𝑥 (1 - 2 𝑎) + - 2 𝑎 𝑦}{𝑥} = \frac{𝑥 (2 - 2 𝑎) + 𝑦 (1 - 2 𝑎)}{𝑦}

这与之前数列递推所得方程很像，但并没有必然联系。相似的步骤可得特征值与特征向量为：

{\begin{cases} 𝜆_{\pm} = 1 - 2 𝑎 \pm 2 \sqrt{𝑎 (𝑎 - 1)} = e^{\pm i 2 𝜃} \\ | Ψ_{\pm} ⟩ = \frac{1}{\sqrt{2}} (\frac{i}{\sqrt{1 - 𝑎}} | Ψ_{0} ⟩ + \frac{1}{\sqrt{𝑎}} | Ψ_{1} ⟩) \end{cases}

²² 在论文[1] 中，导出 $𝐐^{𝑘} | Φ ⟩ = \frac{1}{\sqrt{1 - 𝑎}} cos ((2 𝑘 + 1) 𝜃) | Φ_{0} ⟩ + \frac{1}{\sqrt{𝑎}} sin ((2 𝑘 + 1) 𝜃) | Φ_{1} ⟩$ 这个结论正是通过求 $𝐐$ 的特征值与特征向量得出的。读者可以自行尝试。

三、量子算法的去随机化

由上节我们已经知道，在已知 $𝑎$ 的情况下，使用 $𝐐^{𝑚} 𝒜︀ | 0^{𝑛} ⟩$ 即可使我们得到好纯态的概率为 ${sin}^{2} ((2 𝑚 + 1) 𝜃) \geq max {𝑎, 1 - 𝑎}$ 。然而我们依然有可能使这个概率为 $1$ ，这就是量子算法的去随机化。论文中给出两种方法：

1. $𝜃$ 微调

当 $𝑚 = \tilde{𝑚}$ 时，也就是 $\frac{𝜋}{4 𝜃} - \frac{1}{2}$ 恰是整数，那么 $𝐐^{𝑚} 𝒜︀ | 0^{𝑛} ⟩$ 就自然完全得到好纯态。另一方面，若记，那么次迭代又稍微多了点，因此不妨使角度 $𝜃$ 更小点，取。因此，只要调整算法的初始准确率至，那么次迭代就恰恰好了。

于是问题转化为如何使算法 $𝒜︀$ 的初始准确率从 $𝑎$ 变为。这很简单：只要构建另一个算法 $ℬ︀$ 使得其作用在单个量子位上时：

然后同时应用算法 $𝒜︀, ℬ︀$ ，那么当 $𝒜︀$ 输出为好结果且 $ℬ︀$ 的输出为 $| 1 ⟩$ 时，那么我们获得的结果就必定是好结果。

2. $𝐐$ 算符的改进(相位附加)

现在我们改进算符 $𝐐$ ，使其在符合条件的情况下不是改变符号，而是附加相位：

𝐐 = 𝐐 (𝒜︀, 𝒳︀, 𝜙, 𝜑) = - 𝒜︀ 𝐒_{0} (𝜙) {𝒜︀}^{- 1} 𝐒_{𝒳︀} (𝜑)

其中相位 $𝜙, 𝜑 \in [0, 2 𝜋]$ ，并且：

𝐒_{0} (𝜙) | 𝑥 ⟩ = {\begin{cases} e^{i 𝜙} | 𝑥 ⟩ & , if 𝑥 = 0^{𝑛} \\ | 𝑥 ⟩ & , if 𝑥 \neq 0^{𝑛} \end{cases}

𝐒_{𝒳︀} (𝜑) | 𝑥 ⟩ = {\begin{cases} e^{i 𝜑} | 𝑥 ⟩ & , if 𝒳︀ (𝑥) = 1 \\ | 𝑥 ⟩ & , if 𝒳︀ (𝑥) = 0 \end{cases}

显然：

\begin{aligned} 𝐒_{0} (𝜙) & = \sum | {result}_{𝑖} ⟩ ⟨ 𝑖 | \\ = e^{i 𝜙} | 0^{𝑛} ⟩ ⟨ 0^{𝑛} | + \sum_{𝑖 = 1}^{2^{𝑛} - 1} | 𝑖 ⟩ ⟨ 𝑖 | \\ = \sum_{𝑖 = 0}^{2^{𝑛} - 1} | 𝑖 ⟩ ⟨ 𝑖 | + (e^{i 𝜙} - 1) | 0^{𝑛} ⟩ ⟨ 0^{𝑛} | \\ = 𝐼 + (e^{i 𝜙} - 1) | 0^{𝑛} ⟩ ⟨ 0^{𝑛} | \end{aligned}

于是：

\begin{aligned} 𝒜︀ 𝐒_{0} (𝜙) {𝒜︀}^{- 1} & = 𝒜︀ \dot{𝐼 + (e^{i 𝜙} - 1) | 0^{𝑛} ⟩ ⟨ 0^{𝑛} |} \cdot {𝒜︀}^{- 1} \\ = 𝐼 + (e^{i 𝜙} - 1) 𝒜︀ | 0^{𝑛} ⟩ ⟨ 0^{𝑛} | {𝒜︀}^{- 1} \\ = 𝐼 + (e^{i 𝜙} - 1) | Ψ ⟩ ⟨ Ψ | \end{aligned}

于是：

\begin{aligned} 𝐐 | Ψ_{0} ⟩ & = - 𝒜︀ 𝐒_{0} (𝜙) {𝒜︀}^{- 1} 𝐒_{𝒳︀} (𝜑) | Ψ_{0} ⟩ \\ = - (𝐼 + (e^{i 𝜙} - 1) | Ψ ⟩ ⟨ Ψ |) | Ψ_{0} ⟩ \\ = - | Ψ_{0} ⟩ + (1 - e^{i 𝜙}) (1 - 𝑎) | Ψ ⟩ \\ = (𝑎 (e^{i 𝜙} - 1) - e^{i 𝜙}) | Ψ_{0} ⟩ + (1 - e^{i 𝜙}) (1 - 𝑎) | Ψ_{1} ⟩ \end{aligned}

\begin{aligned} 𝐐 | Ψ_{1} ⟩ & = - e^{i 𝜑} (𝐼 + (e^{i 𝜙} - 1) | Ψ ⟩ ⟨ Ψ |) | Ψ_{1} ⟩ \\ = - e^{i 𝜑} | Ψ_{1} ⟩ - e^{i 𝜑} (e^{i 𝜙} - 1) 𝑎 | Ψ ⟩ \\ = e^{i 𝜑} (1 - e^{i 𝜙}) 𝑎 | Ψ_{0} ⟩ + e^{i 𝜑} ((1 - e^{i 𝜙}) 𝑎 - 1) | Ψ_{1} ⟩ \end{aligned}

于是在作用 $⌊ \tilde{𝑚} ⌋$ 次 $𝐐 (𝒜︀, 𝒳︀, 𝜋, 𝜋)$ 后，系统处于叠加态：

\frac{1}{\sqrt{1 - 𝑎}} cos ((2 ⌊ \tilde{𝑚} ⌋ + 1) 𝜃) | Ψ_{0} ⟩ + \frac{1}{\sqrt{𝑎}} sin ((2 ⌊ \tilde{𝑚} ⌋ + 1) 𝜃) | Ψ_{1} ⟩

之后再作用一次 $𝐐 (𝒜︀, 𝒳︀, 𝜙, 𝜑)$ ，但要求相位 $𝜙, 𝜑$ 符合下式：

\frac{1}{\sqrt{1 - 𝑎}} cos (\dots) (𝑎 (e^{i 𝜙} - 1) - e^{i 𝜙}) + \sqrt{𝑎} sin (\dots) e^{i 𝜑} (1 - e^{i 𝜙}) = 0

也就是在这次作用之后， $| Ψ_{0} ⟩$ 的振幅为 $0$ ，那么 $| Ψ_{1} ⟩$ 的振幅自然就为 $1$ 了。于是问题转换为最后一次作用时应当如何选取 $𝜙, 𝜑$ 。如何选取并不是论文中的重要内容，但其存在性是可以保证的。

四、 QSearch 算法

在 $𝑎$ 未知的情况下， Grover 算法不能发挥太大的作用，因为不知道算符 $𝐐$ 应当作用的次数，使得测得好纯态的概率偏离最优值。为此，我们推广其至 QSearch 算法。

1.算法流程

int l = 1;  
float c = random(start=1, end=2);     // c 不等于 1 或 2。
l++;    
int M = (int)pow(c, l) + 1;

// 将 A 作用于初始零态 ket(0^n)，并测量得到 ket(x)。

if (X(x) == 1) return x;    // 如果是好结果，即 X(x)=1 ，那么return x;
else ket(Psi) = A ket(0^n);    // 否则，记录 ket(Psi)= A ket(0^n)$ 。

int j = (int)random(1, M);

// 将算符 Q 作用到 ket(Psi) 上 j 次，即 Q^j ket(Psi)。测量结果得到 ket(x)。

if (X(x) == 1) return x;    // 如果是好结果，即 X(x)=1 ，那么return x;
else goto step3;    // 否则，goto step3。

尽管这个算法看起来比已知 $𝑎$ 的搜索算法的时间规模更大，但可以证明其依然是 $𝑂 (\sqrt{𝑁})$ 的。

2.启发式经典算法的植入

然而很多启发式经典算法也可以做到 $𝑂 (\sqrt{𝑁})$ ，这导致我们之前讨论的量子算法看起来没多少优势。但是如果考虑将这些启发式算法改造为量子算法，那不就可以在 $\sqrt{𝑁}$ 的基础上再取一次根号么！可以证明，如果经典算法解决问题的期望时间是 $𝑇$ ，那么将其改造为量子算法后再使用 QSearch 算法，规模是 $𝑂 (\sqrt{𝑇})$ 的。

五、振幅估计

1.振幅估计的问题引入

振幅放大是为了寻找解，但这却不能告诉我们解空间中有多少解是好的。振幅估计就是为了解决这个问题。记 $𝑡 = | (𝑥) | 𝒳︀ (𝑥) = 1 |$ ，由于 $𝑎$ 是首次运行 $𝒜︀$ 后测量得到好纯态的概率，因此 $𝑎 = \frac{𝑡}{𝑁}$ 。因此，只要我们能估计振幅 $𝑎$ ，就能估计好解的数量。

另一方面，振幅放大算法的有效运行本就要求 $𝑎$ 是已知的(除非使用 Qsearch 算法)。那么既然能够通过振幅估计得到 $𝑎$ 的估计值，我们当然也就可以利用上振幅放大算法了。

注意到 $𝑎 = {sin}^{2} 𝜃$ ，现在问题转化为估计 $𝜃$ 。注意到算符 $𝐐$ 及其作用次数使得好纯态与坏纯态的振幅形成了三角函数，因此估计这些三角函数的最大周期 $\frac{𝜋}{𝜃}$ 亦可。另一方面，注意到算符 $𝐐$ 的特征根是 $e^{\pm i 2 𝜃}$ ，利用量子计算（六）——量子傅里叶变换与相位估计中的相位估计来获得 $𝐐$ 的特征根也是一种可行的方法。

2.利用相位估计的振幅估计

将相位估计中的 $𝑈$ 矩阵替换为 $𝐐$ 即可，如下图所示：

于是 $𝑦$ 就代表了 $𝐐$ 特征值中的相位，对比 $𝐐$ 的特征值可得 $i 2 𝜃 = i 2 𝜋 \frac{𝑦}{𝑛}$ 即 $𝜃 = 𝜋 \frac{𝑦}{𝑛}$ ，从而可以得到 $𝑎$ 的一个估计值：

\tilde{𝑎} = {sin}^{2} (𝜋 \cdot \frac{𝑦}{𝑛})

于是得到好解的数量的估计值为 $\tilde{𝑡} = 𝑁 \tilde{𝑎}$ 。

我们记振幅估计的算法为 $AmpEst$ ，其所需参数显然为 $(𝒜︀, 𝒳︀, 𝑛)$ 。而得到好解的数量的估计算法为 $Count$ ，显然这个算法只需计算 $𝑁 \times AmpEst (\dots)$ 。此时 $AmpEst$ 所使用的参数则是 $(QFT, 𝒳︀, 𝑛)$ ，因此 $Count$ 的参数列表是 $(𝒳︀, 𝑛)$ 。

3.误差分析

首先做点数学上的准备工作。假如已知相位误差 $| \tilde{𝜃} - 𝜃 | \leq 𝜖$ ，那么 $| \tilde{𝑎} - 𝑎 | = | {sin}^{2} \tilde{𝜃} - {sin}^{2} 𝜃 |$ 的上界应是什么？只需要利用和差化积，一方面：

\begin{aligned} {sin}^{2} \tilde{𝜃} - {sin}^{2} 𝜃 & \leq {sin}^{2} (𝜃 + 𝜖) - {sin}^{2} 𝜃 \\ = \frac{1}{2} cos (2 𝜃) - \frac{1}{2} cos (2 𝜃 + 2 𝜖) \\ = sin (2 𝜃 + 𝜖) sin 𝜖 \\ = (sin (2 𝜃) cos 𝜖 + sin 𝜖 cos (2 𝜃)) sin 𝜖 \\ = 2 \sqrt{𝑎 (1 - 𝑎)} cos 𝜖 sin 𝜖 + (1 - 2 𝑎) {sin}^{2} 𝜖 \\ = \sqrt{𝑎 (1 - 𝑎)} sin 2 𝜖 + (1 - 2 𝑎) {sin}^{2} 𝜖 \\ \leq 2 𝜖 \sqrt{𝑎 (1 - 𝑎)} + 𝜖^{2} \end{aligned}

另一方面：

\begin{aligned} {sin}^{2} 𝜃 - {sin}^{2} \tilde{𝜃} & \leq {sin}^{2} 𝜃 - {sin}^{2} (𝜃 - 𝜖) \\ = \sqrt{𝑎 (1 - 𝑎)} sin 2 𝜖 + (2 𝑎 - 1) {sin}^{2} 𝜖 \\ \leq 2 𝜖 \sqrt{𝑎 (1 - 𝑎)} + 𝜖^{2} \end{aligned}

因此 $| \tilde{𝑎} - 𝑎 | \leq 2 𝜖 \sqrt{𝑎 (1 - 𝑎)} + 𝜖^{2}$ 。如果我们希望误差最小，即取 $𝜖 = \frac{𝜋}{𝑛}$ (因为 $𝑦$ 是离散的整数值)，那么显然此时 $𝑎$ 的误差上限是：

| \tilde{𝑎} - 𝑎 | \leq \frac{2 𝜋}{𝑛} \sqrt{𝑎 (1 - 𝑎)} + \frac{𝜋^{2}}{𝑛^{2}}

$𝑡$ 的误差上限是：

\begin{aligned} | \tilde{𝑡} - 𝑡 | & = 𝑁 | \tilde{𝑎} - 𝑎 | \\ \leq \frac{2 𝑁 𝜋}{𝑛} \sqrt{𝑎 (1 - 𝑎)} + \frac{𝑁 𝜋^{2}}{𝑛^{2}} \\ = \frac{2 𝜋}{𝑛} \sqrt{𝑡 (𝑁 - 𝑡)} + \frac{𝑁 𝜋^{2}}{𝑛^{2}} \end{aligned}

并且由相位估计中的结论，正确的概率至少是 $\frac{8}{𝜋^{2}}$ 。如果允许更大的误差，例如取 $𝜖 = \frac{𝑘 𝜋}{𝑛}$ ，那么正确的概率会更大，即 $1 - \frac{1}{2 (𝑘 - 1)}$ 。

在最小误差下，应取 $𝑛 = ⌈ \sqrt{𝑁} ⌉$ (至于为什么，论文中尚未说明)。此时进一步得到 $𝑡$ 的误差上限是：

\begin{aligned} | \tilde{𝑡} - 𝑡 | & \leq \frac{2 𝜋}{𝑛} \sqrt{𝑡 (𝑁 - 𝑡)} + \frac{𝑁 𝜋^{2}}{𝑛^{2}} \\ = 2 𝜋 \sqrt{\frac{𝑡 (𝑁 - 𝑡)}{𝑁}} + 𝜋^{2} \\ = 2 𝜋 \sqrt{\frac{𝑡 (𝑁 - 𝑡)}{𝑁}} + 11 \end{aligned}

4.给定误差时的好解数量估计算法

假定要求 $| \tilde{𝑡} - 𝑡 | \leq 𝜖 𝑡, 𝜖 \in (0, 1]$ ，那么我们使用算法 $BasicApproxCount (𝒳︀, 𝑛)$ ，其步骤是：

int l = 0;
l++;
int tilde_t = Count(X, 2^l);
if ( (tilde_t == 0) && (2^l < 2 * sqrt(N)) )
    goto step2;
n = ceil(frac(20 pi^2, epsilon)2^l);
tilde_t = Count(X, n);
return t;   // 要求 abs(t- tilde(t)) <= frac(2, 3)

根据这个思想，当我们对 $𝑡$ 没有任何先验估计时，我们可以使用另一算法 $ExactCount (𝒳︀)$ ：

int tilde_t_1 = Count(X, ceil(14 pi sqrt(N)));
int M_i = ceil(30 * sqrt((tilde_t_i + 1) * (N - tilde_t_i + 1)));
int M = min(M_1, M_2);
int t_apostrophe = Count(cal(X),M);
return t;   // 要求 abs(t-t') <= frac(2, 3)

[1] G. Brassard, P. Høyer, M. Mosca, and A. Tapp, “Quantum amplitude amplification and estimation.” [Online]. Available: http://dx.doi.org/10.1090/conm/305/05215
[2] M. Boyer, G. Brassard, P. Høyer, and A. Tapp, “Tight Bounds on Quantum Searching,” Fortschritte der Physik, vol. 46, no. 4–5, pp. 493–505, Jun. 1998, doi: 10.1002/(sici)1521-3978(199806)46:4/5<493::aid-prop493>3.0.co;2-p.