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

## Phase Estimation

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

$$\langle u|U^\dagger U|u\rangle=|\lambda|^2\langle u|u\rangle=\langle u|u\rangle,$$

两边约去 $\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$ 为整数的情形处理，非整数情形的结论我们在测量一节补充说明。

[![](http://chenzhaoyun.com/usr/uploads/2025/11/2121858598.png "量子算法基础3：相位估计")](http://chenzhaoyun.com/usr/uploads/2025/11/2121858598.png "点击放大图片")

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

### 到Controlled-U为止做了什么

[![](http://chenzhaoyun.com/usr/uploads/2025/11/1745640627.png "量子算法基础3：相位估计")](http://chenzhaoyun.com/usr/uploads/2025/11/1745640627.png "点击放大图片")

线路中从上到下的计数比特依次记为第 $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{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}  
$$

第 $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{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}  
$$

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

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

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

这一求和是后文反复出现的几何级数，我们先在这里把它算清楚。设整数 $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{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}  
$$

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

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

1. 先明确符号的定义。$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$ 的振幅。

2. 再看振幅的结构。每个振幅都是 $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$ 的整数倍，各项互相抵消（下面严格计算）。

3. 把输出态按基矢顺序写成矢量形式（求和指标 $x$ 取遍 $0$ 到 $N-1$）：

   $$  
   \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}  
   $$

   前置系数 $\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$。下面的概率计算会从另一个角度再次验证这一点。

4. 测量这个量子态，得到每个基矢 $|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{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}  
$$

- 当 $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{pmatrix}  
0\\ 0\\ 0\\ \vdots\\ 1\\ \vdots\\ 0  
\end{pmatrix}=|\phi\rangle .
$$

非整数情形的补充说明：当 $\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$ 个受控幂，存在两种可能性：

1.  实现 $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)$。

2.  实现 $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{aligned}  
U_S&=U(2|0,0\rangle\langle 0,0|-I)U^\dagger \\  
&=2|\psi\rangle\langle \psi|-I
\end{aligned}  
$$

其中第二个等号用到了 $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{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}  
$$

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

$$  
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},
$$

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

$$  
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},  
$$

其中我们定义了角度 $\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$ 旋转矩阵做本征分解。列出本征方程：

$$  
\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 .
$$

展开得 $\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$；归一化后得到

$$  
|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 .
$$

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

$$  
|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 .
$$

我们可以用矩阵直接乘一次来验证：$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$

![qpe.png](http://chenzhaoyun.com/usr/uploads/2025/11/2121858598.png "qpe.png")

上图是相位估计的完整线路。与标准用法稍有不同，我们把下方输入的本征态 $|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{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}  
$$

其中

$$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{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}  
$$

其中 $|\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}.$$

思考题：

1.  这个算法的精度和 $\sqrt{p}$ 之间的关系是什么？（提示：计数寄存器对 $\theta$ 的分辨率为 $O(2\pi/N)$，而 $p\approx\theta^2/4$ 在 $p$ 较小时会把角度误差放大。）
2.  这个算法的访问复杂度（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}$的本征分解

1.  $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$。

2.  计算 $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 算法详解](../ch06-scientific-computing/hhl-algorithm-tutorial.md)。