量子算法基础3：相位估计¶

Phase Estimation¶

由谱定理（spectral theorem），任何幺正算符（unitary operator）\(U\) 都可以在一组正交归一基下对角化；又因为幺正算符保持向量的范数，它的本征值（eigenvalue）\(\lambda\) 的模长必须是 \(1\)。事实上，若 \(U|u\rangle=\lambda|u\rangle\)，则由 \(U^\dagger U=I\) 可得

两边约去 \(\langle u|u\rangle\) 便有 \(|\lambda|=1\)。因此每个本征值都可以写成 \(e^{i\theta}\) 的形式：

\[U|u\rangle=e^{i\theta}|u\rangle,\qquad 0\leq\theta<2\pi .\]

我们把本征态 \(|u\rangle\) 视为已知的输入，而把相位 \(\theta\) 视为待估计的未知量。为了能用有限的量子比特读出 \(\theta\)，我们把它映射成整数：取一个 \(n\) 位的计数寄存器（counting register），记 \(N=2^n\)，定义

\[\phi=\frac{N\theta}{2\pi}.\]

若 \(\phi\) 恰好落在 \(\{0,1,\dots,N-1\}\) 中的某个整数上，则我们可以把本征值方程重新写成

\[U|u\rangle=e^{2\pi i\phi/N}|u\rangle.\]

这里需要注意两点：

\(\phi\) 是整数只是一种理想化的假设；
下面的推导先按 \(\phi\) 为整数的情形处理，非整数情形的结论我们在测量一节补充说明。

相位估计的线路分为三段：Hadamard 层在计数寄存器上制备均匀叠加，受控幂级联把本征相位“编码”到计数寄存器上，最后用逆量子傅里叶变换把相位读回基矢。下面我们逐段推导。

到Controlled-U为止做了什么¶

线路中从上到下的计数比特依次记为第 \(0\) 位、第 \(1\) 位、第 \(2\) 位……第 \(j\) 位作为控制比特执行受控 \(U^{2^j}\)。

先看单个控制比特的情形。当控制比特为 \(0\) 时什么都不做，为 \(1\) 时作用一次 \(U\)，于是

\[ c\text{-}U\cdot\frac{|0\rangle|u\rangle+|1\rangle|u\rangle}{\sqrt{2}} =\frac{1}{\sqrt{2}}\left(|0\rangle|u\rangle+e^{2\pi i\phi/N}|1\rangle|u\rangle\right) =\frac{1}{\sqrt{2}}\sum_{z=0}^{1}e^{2\pi i\phi z/N}|z\rangle|u\rangle . \]

我们看到，本征相位 \(e^{2\pi i\phi/N}\) 被“踢”到了控制比特的 \(|1\rangle\) 分量上，这一机制与第 1 章的相位回踢（phase kickback）完全相同。

完整的计数寄存器经过 Hadamard 层后处于均匀叠加 \(\frac{1}{\sqrt{N}}\sum_z|z\rangle\)。以 \(3\) 位寄存器为例，逐位执行受控幂，相位按位累积：

\[\begin{split} \begin{aligned} &\frac{1}{\sqrt{8}}\sum_{z_2,z_1,z_0}|z_2z_1z_0\rangle\otimes |u\rangle\\ \rightarrow &\frac{1}{\sqrt{8}}\sum_{z_2,z_1,z_0}|z_2z_1z_0\rangle\, e^{(2\pi i\phi/N) z_0}|u\rangle\\ \rightarrow &\frac{1}{\sqrt{8}}\sum_{z_2,z_1,z_0}|z_2z_1z_0\rangle\, e^{(2\pi i\phi/N) z_0}e^{(2\pi i\phi/N) 2z_1}|u\rangle\\ \rightarrow &\frac{1}{\sqrt{8}}\sum_{z_2,z_1,z_0}|z_2z_1z_0\rangle\, e^{(2\pi i\phi/N) z_0}e^{(2\pi i\phi/N) 2z_1}e^{(2\pi i\phi/N) 4z_2}|u\rangle\\ \rightarrow &\ \cdots \end{aligned} \end{split}\]

第 \(j\) 位控制 \(U^{2^j}\)，因此贡献相位 \(e^{(2\pi i\phi/N)\,2^j z_j}\)。把所有指数相加，利用二进制展开

\[2^0 z_0+2^1 z_1+\cdots+2^{n-1}z_{n-1}=z,\qquad z=\overline{z_{n-1}\dots z_2z_1z_0},\]

级联结束后计数寄存器与本征态的联合态为

\[ \frac{1}{\sqrt{N}}\sum_{z=0}^{N-1}e^{(2\pi i\phi/N) z}|z\rangle\otimes |u\rangle . \]

也就是说，本征相位被编码成了计数寄存器上的线性相位。

QFT和iQFT¶

QFT¶

量子傅里叶变换（Quantum Fourier Transform, QFT）实现下述变换：

\[ F_N:\ |x\rangle\mapsto\frac{1}{\sqrt{N}}\sum_{y=0}^{N-1}e^{2\pi ixy/N}|y\rangle \]

这里 \(x,y\) 同为 \(n\) 位自然数，\(xy\) 是通常的整数乘法（而不是比特串的内积）。记 \(\omega=e^{2\pi i/N}\)，上式也可以紧凑地写成

\[ F_N:\ |x\rangle\mapsto\frac{1}{\sqrt{N}}\sum_{y=0}^{N-1}\omega^{xy}|y\rangle . \]

按照之前的惯例，我们把 \(F_N\) 对应的矩阵写出来：

\[\begin{split} \begin{aligned} U_{\mathrm{QFT}}=F_N&=\sum_{x=0}^{N-1}\left(\frac{1}{\sqrt{N}}\sum_{y=0}^{N-1}\omega^{xy}|y\rangle\right)\langle x|\\ &=\frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}\sum_{y=0}^{N-1}\omega^{xy}|y\rangle\langle x| . \end{aligned} \end{split}\]

可以发现它构成一个 \((y,x)\) 矩阵元恰好为 \(\frac{1}{\sqrt{N}}\omega^{xy}\) 的矩阵。

定义中的因子 \(1/\sqrt{N}\) 正是使 \(F_N\) 成为幺正矩阵的归一化因子。我们来验证这一点：第 \(x\) 行与第 \(x'\) 行的内积为

\[\begin{split} \frac{1}{N}\sum_{y=0}^{N-1}\omega^{(x-x')y}=\begin{cases}1, & x=x'\\ 0, & x\neq x'\end{cases} \end{split}\]

这一求和是后文反复出现的几何级数，我们先在这里把它算清楚。设整数 \(k\not\equiv 0\pmod N\)。由等比数列求和公式（公比为 \(\omega^k\)）得

\[ \sum_{y=0}^{N-1}\omega^{ky}=\frac{\omega^{kN}-1}{\omega^{k}-1}. \]

上式的分母不为零：\(\omega^k=e^{2\pi ik/N}=1\) 当且仅当 \(N\) 整除 \(k\)，而我们已经排除了这种情形。分子则为零：\(\omega^{kN}=(\omega^{N})^{k}=e^{2\pi ik}=1\)。因此

\[ \sum_{y=0}^{N-1}\omega^{ky}=0\qquad(k\not\equiv 0\pmod N). \]

反过来，当 \(k\equiv 0\pmod N\) 时每一项都是 \(1\)，求和为 \(N\)。回到行内积的式子：\(x=x'\) 时每一项都是 \(1\)，内积为 \(\frac{1}{N}\cdot N=1\)；\(x\neq x'\) 时 \(x-x'\) 是 \(\{-(N-1),\dots,-1,1,\dots,N-1\}\) 中的非零数，其绝对值小于 \(N\)，因此不被 \(N\) 整除，由刚证明的恒等式可知求和为 \(0\)，内积为零。于是 \(F_N\) 的各行正交归一，即 \(F_NF_N^{\dagger}=I\)，QFT 确实是幺正变换。此外，由于矩阵元 \(\omega^{xy}\) 关于 \(x,y\) 对称，矩阵还满足 \(F_N^{T}=F_N\)。

iQFT¶

iQFT 是 QFT 的逆变换，即 \(U_{\mathrm{iQFT}}=U_{\mathrm{QFT}}^{-1}=U_{\mathrm{QFT}}^{\dagger}\)。由 QFT 一节证明的对称性 \(F_N^{T}=F_N\)，转置共轭只剩下复共轭：

\[ U_{\mathrm{iQFT}}=F_N^\dagger=(F_N^{T})^{*}=F_N^{*}=\frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}\sum_{y=0}^{N-1}\omega^{-xy}|y\rangle\langle x| . \]

也就是说，iQFT 与 QFT 形式完全相同，只需把 \(\omega\) 换成它的共轭 \(\omega^{-1}=\omega^{*}\)。

相位估计 Phase estimation¶

级联后的计数寄存器处于态 \(\frac{1}{\sqrt{N}}\sum_{z=0}^{N-1}\omega^{\phi z}|z\rangle\)（对照定义可以发现它正是 \(F_N|\phi\rangle\)），因此用 iQFT 作用即可把 \(\phi\) 读回基矢。我们把这一步完整展开：

\[\begin{split} \begin{aligned} &U_{\mathrm{iQFT}}\cdot\frac{1}{\sqrt{N}}\sum_{z=0}^{N-1}\omega^{\phi z}|z\rangle\\ =&\frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}\sum_{y=0}^{N-1}\omega^{-xy}|y\rangle\langle x|\cdot\frac{1}{\sqrt{N}}\sum_{z=0}^{N-1}\omega^{\phi z}|z\rangle\\ =&\frac{1}{N}\sum_{x=0}^{N-1}\sum_{y=0}^{N-1}\sum_{z=0}^{N-1}\omega^{\phi z-xy}|y\rangle\langle x|z\rangle\\ =&\frac{1}{N}\sum_{x=0}^{N-1}\sum_{y=0}^{N-1}\omega^{\phi x-xy}|y\rangle\\ =&\sum_{y=0}^{N-1}\left(\frac{1}{N}\sum_{x=0}^{N-1}\omega^{x(\phi-y)}\right)|y\rangle \end{aligned} \end{split}\]

其中第二行代入了 iQFT 的定义与输入态；第三行利用了 \(\langle x|z\rangle=\delta_{xz}\)；第四行把 \(z=x\) 代入并合并指数 \(\phi x-xy=x(\phi-y)\)。

怎么理解这个输出态？我们逐项说明。

先明确符号的定义。\(x,y,z\) 都是取遍 \(\{0,1,\dots,N-1\}\) 的整数；\(|y\rangle\) 是整数 \(y\) 对应的计算基矢；而 \(\frac{1}{N}\sum_{x=0}^{N-1}\omega^{x(\phi-y)}\) 是分量 \(|y\rangle\) 的振幅。
再看振幅的结构。每个振幅都是 \(N\) 个模为 \(1\) 的复数之和，其中第 \(x\) 项的相位为 \(2\pi x(\phi-y)/N\)，即 \(\omega\) 的相位的 \(x(\phi-y)\) 倍。当 \(y=\phi\) 时所有项相位相同，发生相长叠加；当 \(y\neq\phi\) 时相邻两项的相位差 \(2\pi(\phi-y)/N\) 不是 \(2\pi\) 的整数倍，各项互相抵消（下面严格计算）。
把输出态按基矢顺序写成矢量形式（求和指标 \(x\) 取遍 \(0\) 到 \(N-1\)）：

\[\begin{split} \frac{1}{N} \begin{pmatrix} \sum_{x}\omega^{x(\phi-0)}\\ \sum_{x}\omega^{x(\phi-1)}\\ \sum_{x}\omega^{x(\phi-2)}\\ \vdots\\ \sum_{x}\omega^{x(\phi-(N-2))}\\ \sum_{x}\omega^{x(\phi-(N-1))} \end{pmatrix} \end{split}\]

前置系数 \(\frac{1}{N}\) 并不是额外凑出来的归一化常数，它来自两处 \(\frac{1}{\sqrt{N}}\) 的乘积：一个来自 Hadamard 层制备的均匀叠加，另一个来自 iQFT 的矩阵元。尽管出现了 \(\frac{1}{N}\)，整个矢量仍然是归一化的：iQFT 是酉变换，而它的输入态 \(\frac{1}{\sqrt{N}}\sum_z\omega^{\phi z}|z\rangle\) 已归一化（每个振幅的模都是 \(\frac{1}{\sqrt{N}}\)，共 \(N\) 项），酉变换保持范数，因此输出态的范数必然也是 \(1\)。下面的概率计算会从另一个角度再次验证这一点。
测量这个量子态，得到每个基矢 \(|y\rangle\) 的概率为

\[p_y = \frac{1}{N^2}\left|\sum_{x=0}^{N-1}\omega^{x(\phi-y)}\right|^2\]

现在我们计算这些概率。对被求和的整数 \(k=\phi-y\) 应用 QFT 一节中证明的恒等式：由于 \(\phi,y\in\{0,\dots,N-1\}\)，有 \(|k|\leq N-1\)，因此 \(k\equiv 0\pmod N\) 当且仅当 \(k=0\)，即 \(y=\phi\)。于是

当 \(y=\phi\) 时，每一项都是 \(\omega^0=1\)：

\[\begin{split} \begin{aligned} p_{y=\phi} &= \frac{1}{N^2}\left|\sum_{x=0}^{N-1}\omega^{0}\right|^2\\ &=\frac{1}{N^2}\,N^2=1 . \end{aligned} \end{split}\]

当 \(y\neq\phi\) 时，由等比数列求和公式

\[ \sum_{x=0}^{N-1}\omega^{x(\phi-y)}=\frac{(\omega^{N})^{\,\phi-y}-1}{\omega^{\,\phi-y}-1}=\frac{1-1}{\omega^{\,\phi-y}-1}=0 , \]

其中分母不为零，因为 \(\phi-y\not\equiv 0\pmod N\) 意味着 \(\omega^{\,\phi-y}\neq 1\)；分子为零，因为 \(\omega^{N}=e^{2\pi i}=1\)。因此 \(p_{y\neq\phi}=0\)。

（我们也可以从归一化反推这一结论：概率总和恒为 \(1\)，而 \(p_{y=\phi}=1\) 已经占满了全部概率，因此其余分量概率必为零。这与“酉变换保持范数”的说法是一致的。）

于是输出态就是除第 \(\phi\) 个分量外全部为零的基矢：

\[\begin{split} \begin{pmatrix} 0\\ 0\\ 0\\ \vdots\\ 1\\ \vdots\\ 0 \end{pmatrix}=|\phi\rangle . \end{split}\]

非整数情形的补充说明：当 \(\phi\) 不是整数时，同样的代数给出 \(|y\rangle\) 分量振幅的闭式

\[p_y=\frac{1}{N^2}\cdot\frac{\sin^2\!\big(\pi(\phi-y)\big)}{\sin^2\!\big(\pi(\phi-y)/N\big)},\]

这个表达式在 \(y=\phi\) 处取极限值 \(1\)，并随 \(|\phi-y|\) 增大而衰减。把最接近 \(\phi\) 的整数对应的概率记为 \(p_{\mathrm{nearest}}\)（此时 \(|\phi-y|\leq\frac{1}{2}\)），利用 \(|\sin t|\leq|t|\) 以及 \(\sin t/t\) 在 \((0,\pi]\) 上单调递减，可得

\[p_{\mathrm{nearest}}\geq\left(\frac{\sin(\pi/2)}{\pi/2}\right)^{2}=\frac{4}{\pi^{2}}\approx 0.405 ,\]

即测量以不低于 \(4/\pi^2\) 的概率返回最接近 \(\phi\) 的整数；增加若干冗余计数比特可以把成功概率任意提高到接近 \(1\)。

思考题：正文中已用等比数列求和公式证明了 \(\sum_{x=0}^{N-1}\omega^{x(\phi-y)}=0\)（\(y\neq\phi\)）。请再给出一个“配对”的证明：利用 \(\omega^{N/2}=-1\)，把第 \(x\) 项与第 \(x+N/2\) 项配对。当 \(\phi-y\) 为奇数时，两项的相位恰好相差 \(\pi\)，直接相消；当 \(\phi-y\) 为偶数时，请先提取公因子把它化归为奇数情形。

小结¶

相位估计以 \(U\)（的受控幂）作为子过程，实现了如下的整体变换：

\[|0\rangle|u\rangle \mapsto |\phi\rangle|u\rangle,\]

其中 \(|u\rangle\) 是 \(U\) 的本征态，\(\phi\) 由本征值决定，具体来说有 \(U|u\rangle=e^{2\pi i\phi/N}|u\rangle\)。计数寄存器共有 \(n\) 位，\(N=2^n\)，\(\phi\) 是一个 \(n\) 位整数；当 \(\phi\) 不是整数时，输出为最接近 \(\phi\) 的整数（成功概率不低于 \(4/\pi^2\)）。

Query complexity 访问复杂度¶

当我们认为 Hadamard 层和 iQFT 是代价较为固定的标准过程时，实现相位估计的主要复杂度集中于受控 \(U\) 幂上。这意味着我们需要执行多少次受控 \(U^k\) 决定了算法的实际复杂度。这种“调用某个子过程 \(X\) 次”的复杂度度量，称作算法对于该子过程的访问复杂度（query complexity）。

具体来说，线路需要依次实现 \(c\text{-}U^{2^0},c\text{-}U^{2^1},\dots,c\text{-}U^{2^{n-1}}\)，共 \(n\) 个受控幂，存在两种可能性：

实现 \(c\text{-}U\) 和 \(c\text{-}U^{t}\) 的复杂度无明显关系（例如二者各有独立的黑盒实现）
- 此时访问复杂度为 \(O(\log N)\)，其中 \(N=2^n\)，\(n\) 为计数寄存器的位数。
- 计数寄存器能分辨的最小相位差为整圈 \(2\pi\) 的 \(1/N\)。若把这个分辨率记为精度 \(\epsilon=\frac{1}{N}\)，那么访问复杂度为 \(O(\log 1/\epsilon)\)。
实现 \(c\text{-}U^{t}\) 等于重复 \(t\) 次 \(c\text{-}U\)
- 此时受控调用的总次数为 \(\sum_{j=0}^{n-1}2^{j}=N-1\)，访问复杂度为 \(O(N)\)；用精度 \(\epsilon\) 表示的话，写为 \(O(1/\epsilon)\)。

Amplitude estimation (Quantum counting)¶

在 Grover 搜索和振幅放大（amplitude amplification）中，我们遇到了同一类问题：给定某个过程 \(U\)，满足

\[U|0,0\rangle = \sqrt{p_\mathrm{succ}}|\mathrm{good}\rangle|0\rangle+\sqrt{1-p_\mathrm{succ}}|\mathrm{bad}\rangle|1\rangle,\]

其中第二个寄存器是标记成败的 flag 比特。振幅放大用 \(O(1/\sqrt{p_\mathrm{succ}})\) 次 \(U\) 的调用就能以较高概率制备 \(|\mathrm{good}\rangle|0\rangle\)（相比之下，经典地重复制备再测量的代价是 \(O(1/p_\mathrm{succ})\) 次）。但现在的问题是如何确定 \(p_{\rm succ}\)：因为若不知道这个概率的具体数值，我们就无法选择需要执行振幅放大循环的次数。振幅估计（amplitude estimation，也称量子计数 quantum counting）就是用相位估计来估计它的算法。

回顾Amplitude amplification¶

为书写简便，记 \(p:=p_\mathrm{succ}\)，\(|g\rangle:=|\mathrm{good}\rangle|0\rangle\)，\(|b\rangle:=|\mathrm{bad}\rangle|1\rangle\)，于是 \(|\psi\rangle:=U|0,0\rangle=\sqrt{p}\,|g\rangle+\sqrt{1-p}\,|b\rangle\)。我们在 \(|g\rangle\) 与 \(|b\rangle\) 张成的子空间上定义两个反射算符。第一个是关于“好”子空间的反射（oracle）：

\[ U_O=I-2|\mathrm{good}\rangle\langle \mathrm{good}|\otimes I \]

它把每个好数据态标记相位 \(-1\)，与第 1 章相位回踢中 \((-1)^{f(x)}\) 的约定一致（上一章把 oracle 写成 \(2|x_0\rangle\langle x_0|-I\)，即对好态标 \(+1\)；两种约定相差一个整体负号，只会使下文的旋转方向相反，不影响任何结论）。它在子空间上的作用为 \(U_O|g\rangle=-|g\rangle\)，\(U_O|b\rangle=+|b\rangle\)。第二个是关于初始态 \(|\psi\rangle\) 的反射：

\[\begin{split} \begin{aligned} U_S&=U(2|0,0\rangle\langle 0,0|-I)U^\dagger \\ &=2|\psi\rangle\langle \psi|-I \end{aligned} \end{split}\]

其中第二个等号用到了 \(U|0,0\rangle=|\psi\rangle\) 与 \(U^\dagger U=I\)。两个算符都是反射，满足 \(U_O^2=U_S^2=I\)，因此都是幺正算符；它们的乘积也是幺正算符，并且保持子空间 \(\mathrm{span}\{|g\rangle,|b\rangle\}\) 不变。我们直接计算 \(U_S\) 在这个子空间上的作用来验证封闭性：

\[\begin{split} \begin{aligned} U_S|g\rangle&=2|\psi\rangle\langle\psi|g\rangle-|g\rangle=2\sqrt{p}\,|\psi\rangle-|g\rangle=(2p-1)|g\rangle+2\sqrt{p(1-p)}\,|b\rangle,\\ U_S|b\rangle&=2|\psi\rangle\langle\psi|b\rangle-|b\rangle=2\sqrt{1-p}\,|\psi\rangle-|b\rangle=2\sqrt{p(1-p)}\,|g\rangle+(1-2p)\,|b\rangle . \end{aligned} \end{split}\]

于是在基 \(\{|g\rangle,|b\rangle\}\) 下，两个算符的矩阵为

\[\begin{split} U_S=\begin{pmatrix}2p-1 & 2\sqrt{p(1-p)}\\ 2\sqrt{p(1-p)} & 1-2p\end{pmatrix},\qquad U_O=\begin{pmatrix}-1 & 0\\ 0 & 1\end{pmatrix}, \end{split}\]

相乘便得到振幅放大的迭代算符 \(G:=U_SU_O\)：

\[\begin{split} G=U_SU_O=\begin{pmatrix}1-2p & 2\sqrt{p(1-p)}\\ -2\sqrt{p(1-p)} & 1-2p\end{pmatrix} =\begin{pmatrix}\cos \theta & \sin \theta \\ -\sin \theta & \cos \theta\end{pmatrix}, \end{split}\]

其中我们定义了角度 \(\theta\)：

\[\cos\theta=1-2p,\qquad \sin\theta=2\sqrt{p(1-p)}.\]

我们可以直接验证这确实定义了一个实角度：

\[(1-2p)^2+4p(1-p)=1-4p+4p^2+4p-4p^2=1 .\]

因此 \(G\) 是子空间上的一个旋转变换。（上一章 Grover 一节在 \(p=1/M\) 时得到的旋转矩阵与这里的矩阵互为转置，即旋转方向相反；这一差别来源于 oracle 的相位约定与两个反射的相乘顺序。无论采用哪种约定，每步转过的角度大小相同，迭代次数的结论不受影响。这里的 \(M\) 表示 Grover 数据库的大小，为避免与本章计数寄存器的 \(N=2^n\) 混淆，我们不再用 \(N\) 表示数据库。）

旋转的动力学如下。把 \(p\) 参数化为 \(p=\sin^2\alpha\)（\(0\leq\alpha\leq\pi/2\)，即 \(\sin\alpha=\sqrt{p}\)），则由倍角公式

\[\cos\theta=1-2\sin^2\alpha=\cos 2\alpha,\qquad \sin\theta=2\sin\alpha\cos\alpha=\sin 2\alpha,\]

即 \(\theta=2\alpha\)。初始态为 \(|\psi\rangle=\sin\alpha\,|g\rangle+\cos\alpha\,|b\rangle\)。利用矩阵乘法与角加法公式可以验证，每作用一次 \(G\)，角度推进 \(\theta\)：

\[G^{\,n}|\psi\rangle=\sin(\alpha+n\theta)|g\rangle+\cos(\alpha+n\theta)|b\rangle .\]

一开始 \(\alpha\) 很小，对应成功率很小的情况；每迭代一次，成功率对应的角度上升 \(\theta=2\alpha\approx 2\sqrt{p}\)。要达到 \(\alpha+n\theta\approx\pi/2\)，所需的迭代次数为

\[n\approx\frac{\pi/2-\alpha}{2\alpha}\leq\frac{\pi}{4\sqrt{p}}=O(1/\sqrt{p}),\]

这正对应了我们需要进行振幅放大的步数（Grover 搜索是 \(p=1/M\)、\(\alpha\approx 1/\sqrt{M}\) 的特例，给出 \(n\approx\frac{\pi}{4}\sqrt{M}\)）。

从振幅放大到振幅估计¶

振幅放大的迭代算符 \(G=U_SU_O\) 是两个幺正算符的乘积，因此它本身仍然是一个幺正算符。于是本章开头对一般幺正算符的讨论对它同样适用：存在一组本征态 \(|u\rangle\) 满足

\[G|u\rangle = e^{2\pi i\phi/N}|u\rangle\]

（计数寄存器仍为 \(n\) 位，\(N=2^n\)。）那么如何确定本征态 \(|u\rangle\) 和对应的相位呢？

由于 \(G\) 保持二维子空间 \(\mathrm{span}\{|g\rangle,|b\rangle\}\) 不变，我们只需对上面的 \(2\times 2\) 旋转矩阵做本征分解。列出本征方程：

\[\begin{split} \det(\lambda I-G)=\left| \begin{matrix} \lambda-\cos \theta & -\sin \theta \\ \sin \theta & \lambda-\cos \theta \end{matrix}\right|=(\lambda-\cos\theta)^2+\sin^2\theta=0 . \end{split}\]

展开得 \(\lambda^2-2\lambda\cos\theta+1=0\)，解得 \(\lambda=\cos\theta\pm i\sin\theta\)。由欧拉公式 \(\cos\theta\pm i\sin\theta=e^{\pm i\theta}\)，本征值是一对共轭相位：

\[ \lambda_1=e^{i\theta},\qquad \lambda_2=e^{-i\theta}. \]

把 \(\lambda_1\) 代回 \((\lambda I-G)v=0\)：第一行给出 \((\cos\theta+i\sin\theta-\cos\theta)v_1-\sin\theta\,v_2=0\)，即 \(i\sin\theta\,v_1=\sin\theta\,v_2\)，故 \(v_2=iv_1\)；归一化后得到

\[\begin{split} |u_1\rangle=\frac{1}{\sqrt{2}}\begin{pmatrix}1\\ i\end{pmatrix} =\frac{1}{\sqrt{2}}\left(|g\rangle+i|b\rangle\right),\qquad G|u_1\rangle=e^{i\theta}|u_1\rangle . \end{split}\]

同理，把 \(\lambda_2=e^{-i\theta}\) 代入可得 \(v_2=-iv_1\)，即

\[\begin{split} |u_2\rangle=\frac{1}{\sqrt{2}}\begin{pmatrix}1\\ -i\end{pmatrix} =\frac{1}{\sqrt{2}}\left(|g\rangle-i|b\rangle\right),\qquad G|u_2\rangle=e^{-i\theta}|u_2\rangle . \end{split}\]

我们可以用矩阵直接乘一次来验证：\(G|u_1\rangle=\frac{1}{\sqrt{2}}\begin{pmatrix}\cos\theta+i\sin\theta\\ -\sin\theta+i\cos\theta\end{pmatrix}=\frac{e^{i\theta}}{\sqrt{2}}\begin{pmatrix}1\\ i\end{pmatrix}=e^{i\theta}|u_1\rangle\)，验证无误。此外 \(\langle u_1|u_2\rangle=\frac{1}{2}(1\cdot 1+(-i)(-i))=0\)，两个本征态正交归一。

从子空间的观点来看，本征态就是 \(|\mathrm{good}\rangle|0\rangle\) 与 \(|\mathrm{bad}\rangle|1\rangle\) 的等权叠加，二者只差一个 \(\pi/2\) 的相对相位。

振幅估计 = 将振幅放大算符\(U_SU_O\)作为相位估计的算子\(U\)¶

上图是相位估计的完整线路。与标准用法稍有不同，我们把下方输入的本征态 \(|u\rangle\) 换成容易制备的 \(|\psi\rangle=\sqrt{p}\,|g\rangle+\sqrt{1-p}\,|b\rangle\)，把受控算子 \(U\) 换成 \(G=U_SU_O\)。由于 \(|\psi\rangle\) 可以写成 \(|u_1\rangle\)、\(|u_2\rangle\) 的线性组合，而相位估计是线性演化，它会分别作用于每个本征分量。

我们先把 \(|\psi\rangle\) 在本征态基上展开。由 \(|u_1\rangle\)、\(|u_2\rangle\) 的定义可以反解出

\[ |g\rangle=\frac{1}{\sqrt{2}}\left(|u_1\rangle+|u_2\rangle\right),\qquad |b\rangle=\frac{-i}{\sqrt{2}}\left(|u_1\rangle-|u_2\rangle\right). \]

（验证：\(\frac{1}{\sqrt{2}}(|u_1\rangle+|u_2\rangle)=\frac{1}{\sqrt{2}}\cdot\frac{1}{\sqrt{2}}\cdot 2|g\rangle=|g\rangle\)；\(\frac{-i}{\sqrt{2}}(|u_1\rangle-|u_2\rangle)=\frac{-i}{\sqrt{2}}\cdot\frac{1}{\sqrt{2}}\cdot 2i|b\rangle=|b\rangle\)。）代入 \(|\psi\rangle=\sqrt{p}\,|g\rangle+\sqrt{1-p}\,|b\rangle\)，得

\[\begin{split} \begin{aligned} |\psi\rangle&=\frac{\sqrt{p}}{\sqrt{2}}\left(|u_1\rangle+|u_2\rangle\right)+\frac{-i\sqrt{1-p}}{\sqrt{2}}\left(|u_1\rangle-|u_2\rangle\right)\\ &=\frac{\sqrt{p}-i\sqrt{1-p}}{\sqrt{2}}|u_1\rangle+\frac{\sqrt{p}+i\sqrt{1-p}}{\sqrt{2}}|u_2\rangle\\ &=C_1|u_1\rangle+C_2|u_2\rangle , \end{aligned} \end{split}\]

其中

\[C_1=\frac{\sqrt{p}-i\sqrt{1-p}}{\sqrt{2}},\qquad C_2=\frac{\sqrt{p}+i\sqrt{1-p}}{\sqrt{2}}.\]

两个系数的模方分别为 \(|C_1|^2=\frac{p+(1-p)}{2}=\frac{1}{2}\) 与 \(|C_2|^2=\frac{1}{2}\)，因此

\[|C_1|^2+|C_2|^2=1 ,\]

展开式是归一化的——它必须如此，因为 \(|\psi\rangle\) 与 \(\{|u_1\rangle,|u_2\rangle\}\) 都是归一化的正交态。（作为交叉验证，也可以直接用内积计算：\(C_1=\langle u_1|\psi\rangle=\frac{1}{\sqrt{2}}(\langle g|-i\langle b|)(\sqrt{p}|g\rangle+\sqrt{1-p}|b\rangle)=\frac{\sqrt{p}-i\sqrt{1-p}}{\sqrt{2}}\)，与上式一致。）

现在执行振幅估计。相位估计对每个本征分量独立作用，因此

\[\begin{split} \begin{aligned} &|0\rangle\otimes (C_1|u_1\rangle+C_2|u_2\rangle)\\ =&C_1|0\rangle|u_1\rangle+C_2|0\rangle|u_2\rangle\\ \rightarrow&C_1|\tilde{\phi}_1\rangle|u_1\rangle+C_2|\tilde{\phi}_2\rangle|u_2\rangle , \end{aligned} \end{split}\]

其中 \(|\tilde{\phi}_i\rangle\) 是测量计数寄存器后读数所对应的基矢。把本征值写成相位估计的标准形式 \(\lambda_i=e^{i\varphi_i}\)，则 \(\varphi_1=\theta\)、\(\varphi_2=2\pi-\theta\)，相位估计的目标整数为 \(\phi_i=N\varphi_i/2\pi\)，即 \(\phi_1=N\theta/2\pi\) 与 \(\phi_2=N-N\theta/2\pi\)（模 \(N\)）。当 \(\phi_i\) 恰为整数时读数精确等于 \(\phi_i\)；一般情形下，按照本章测量一节的讨论，测量以不低于 \(4/\pi^2\) 的概率返回最接近 \(\phi_i\) 的整数，增加若干冗余计数比特可以把成功概率任意提高。

当我们测量第一个寄存器时，读数以概率 \(|C_1|^2=\frac{1}{2}\) 落在 \(\phi_1\) 附近，以概率 \(|C_2|^2=\frac{1}{2}\) 落在 \(\phi_2\) 附近。把读数 \(\tilde{\phi}\) 换算回角度 \(\hat{\varphi}=2\pi\tilde{\phi}/N\in[0,2\pi)\)，两种情况分别对应 \(\theta\) 与 \(2\pi-\theta\)。由于 \(\theta=2\arcsin\sqrt{p}\approx 2\sqrt{p}\) 通常是个很小的数，\(\theta\) 对应接近 \(0\) 的读数，而 \(2\pi-\theta\) 对应接近 \(2\pi\) 的读数，二者容易区分；无论测到哪一个，我们都能还原出 \(\theta\)（若 \(\hat{\varphi}>\pi\)，则取 \(\theta=2\pi-\hat{\varphi}\)），进而由 \(\cos\theta=1-2p\) 反解出成功率的估计值

\[p=\frac{1-\cos\theta}{2}=\sin^2\frac{\theta}{2}.\]

思考题：

这个算法的精度和 \(\sqrt{p}\) 之间的关系是什么？（提示：计数寄存器对 \(\theta\) 的分辨率为 \(O(2\pi/N)\)，而 \(p\approx\theta^2/4\) 在 \(p\) 较小时会把角度误差放大。）
这个算法的访问复杂度（query complexity）是多少？请分“实现 \(G^t\) 与实现 \(G\) 复杂度无关”与“实现 \(G^t\) 等于重复 \(t\) 次 \(G\)”两种情形讨论。

HHL算法，对矩阵进行本征分解实现求逆¶

作为相位估计的最后一个应用预告，我们考虑线性方程组求解：给定线性方程组 \(Ax=b\)，即找到 \(x=A^{-1}b\)。其量子版本描述如下：

给出厄密矩阵（Hermitian matrix）\(A\)，假设我们能实现幺正演化 \(U=e^{iAt}\)，其中 \(t\) 是某实数；假设拥有输入态 \(|b\rangle\)，目标是制备

\[|x\rangle=\frac{A^{-1}|b\rangle}{\|A^{-1}|b\rangle\|_2}\]

其中 \(\|\cdot\|_2\) 是向量的 \(2\)-范数（Euclidean norm），\(1/\|A^{-1}|b\rangle\|_2\) 是归一化常数：量子态必须归一化，因此算法只能以“比例”的形式给出解 \(A^{-1}b\) 的方向。以下假设 \(A\) 可逆，即所有本征值非零。

对\(U=e^{iAt}\)的本征分解¶

\(U=e^{iAt}\) 和 \(A\) 具有相同的本征态。

不妨设 \(A|u_i\rangle=\lambda_i|u_i\rangle\)（\(A\) 厄密保证本征值 \(\lambda_i\) 为实数，且存在正交归一的本征基）。由归纳法可得 \(A^m|u_i\rangle=\lambda_i^m|u_i\rangle\) 对一切非负整数 \(m\) 成立。把这一事实代入矩阵指数的幂级数定义 \(e^{iAt}=\sum_{m=0}^{\infty}\frac{(iAt)^m}{m!}\)，逐项作用即得

\[e^{iAt}|u_i\rangle=\sum_{m=0}^{\infty}\frac{(i\lambda_i t)^m}{m!}|u_i\rangle=e^{i\lambda_i t}|u_i\rangle\]

于是我们根据 \(A\) 的本征态和本征值，直接得到了 \(U=e^{iAt}\) 的本征态（与 \(A\) 相同）和本征值（\(e^{i\lambda_i t}\)）。相位估计从 \(U\) 中读出的相位正是 \(\lambda_i t \bmod 2\pi\)。
计算 \(x=A^{-1}b\)。

有了上面的本征分解，求逆的路线就清晰了：在 \(A\) 的本征基下，\(A^{-1}\) 的作用就是把每个本征分量乘上 \(1/\lambda_i\)，而相位估计恰好能把本征值“暴露”到寄存器上，供我们实施这个乘法。具体步骤为：
- 展开：把 \(|b\rangle\) 写成 \(|b\rangle=\sum_i\beta_i|u_i\rangle\)，其中 \(\beta_i=\langle u_i|b\rangle\)；于是 \(A^{-1}|b\rangle=\sum_i\frac{\beta_i}{\lambda_i}|u_i\rangle\)。
- 相位估计：以 \(e^{iAt}\) 为受控算子对 \(|0\rangle|b\rangle\) 做相位估计。由第 1 点，每个分量 \(|u_i\rangle\) 都是其本征态，相位 \(\lambda_i t\bmod 2\pi\) 被转移到计数寄存器，得到 \(\sum_i\beta_i|\widetilde{\lambda_i t}\rangle|u_i\rangle\)。
- 受控旋转（controlled rotation）：根据计数寄存器中的读数，对辅助比特做受控旋转，把振幅乘上一个正比于 \(1/\lambda_i\) 的因子。
- 逆相位估计与测量：做逆相位估计“清空”计数寄存器，再对辅助比特进行测量（或用振幅放大）筛选成功分支，最终得到正比于 \(\sum_i\frac{\beta_i}{\lambda_i}|u_i\rangle=A^{-1}|b\rangle\) 的归一化态，即 \(|x\rangle\)。
具体的线路、成功率（与条件数 condition number \(\kappa\) 的关系）、精度与复杂度分析将在第 6 章完整展开，参见 HHL 算法详解。