相位估计（QPE）

Phase Estimation

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

$⟨u|U^{†}U|u⟩=|\lambda {|}^2⟨u|u⟩=⟨u|u⟩,$

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

$U|u⟩=e^{i\theta }|u⟩,0\le \theta <2\pi .$

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

$\varphi =\frac{N\theta }{2\pi }.$

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

$U|u⟩=e^{2\pi i\varphi /N}|u⟩.$

这里需要注意两点：

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

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

到Controlled-U为止做了什么

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

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

$$c\text{-}U\cdot \frac{|0⟩|u⟩+|1⟩|u⟩}{\sqrt{2}}=\frac{1}{\sqrt{2}}\left(|0⟩|u⟩+e^{2\pi i\varphi /N}|1⟩|u⟩\right)=\frac{1}{\sqrt{2}}\sum _{z=0}^1{e}^{2\pi i\varphi z/N}|z⟩|u⟩.$$

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

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

$$\begin{array}{rl}& \frac{1}{\sqrt{8}}\sum _{z_2,z_1,z_0}|z_2{z}_1{z}_0⟩\otimes |u⟩\\ \to & \frac{1}{\sqrt{8}}\sum _{z_2,z_1,z_0}|z_2{z}_1{z}_0⟩e^{(2\pi i\varphi /N)z_0}|u⟩\\ \to & \frac{1}{\sqrt{8}}\sum _{z_2,z_1,z_0}|z_2{z}_1{z}_0⟩e^{(2\pi i\varphi /N)z_0}{e}^{(2\pi i\varphi /N)2z_1}|u⟩\\ \to & \frac{1}{\sqrt{8}}\sum _{z_2,z_1,z_0}|z_2{z}_1{z}_0⟩e^{(2\pi i\varphi /N)z_0}{e}^{(2\pi i\varphi /N)2z_1}{e}^{(2\pi i\varphi /N)4z_2}|u⟩\\ \to & \cdots \end{array}$$

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

$2^0{z}_0+2^1{z}_1+\cdots +2^{n-1}{z}_{n-1}=z,z=\overline{z_{n-1}\dots z_2{z}_1{z}_0},$

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

$$\frac{1}{\sqrt{N}}\sum _{z=0}^{N-1}{e}^{(2\pi i\varphi /N)z}|z⟩\otimes |u⟩.$$

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

QFT和iQFT

QFT

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

$$F_N:|x⟩\mapsto \frac{1}{\sqrt{N}}\sum _{y=0}^{N-1}{e}^{2\pi ixy/N}|y⟩$$

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

$$F_N:|x⟩\mapsto \frac{1}{\sqrt{N}}\sum _{y=0}^{N-1}{\omega }^{xy}|y⟩.$$

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

$$\begin{array}{rl}{U}_{\mathrm{QFT}}=F_N& =\sum _{x=0}^{N-1}\left(\frac{1}{\sqrt{N}}\sum _{y=0}^{N-1}{\omega }^{xy}|y⟩\right)⟨x|\\ & =\frac{1}{\sqrt{N}}\sum _{x=0}^{N-1}\sum _{y=0}^{N-1}{\omega }^{xy}|y⟩⟨x|.\end{array}$$

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

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

$$\frac{1}{N}\sum _{y=0}^{N-1}{\omega }^{(x-x^{\prime })y}=\{\begin{array}{ll}1,& x=x^{\prime }\\ 0,& x\ne x^{\prime }\end{array}$$

这一求和是后文反复出现的几何级数，我们先在这里把它算清楚。设整数 $k\not\equiv 0(\mathrm{mod}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(k\not\equiv 0(\mathrm{mod}N)).$$

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

iQFT

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

$$U_{\mathrm{iQFT}}=F_N^{†}=(F_N^T{)}^{\ast }=F_N^{\ast }=\frac{1}{\sqrt{N}}\sum _{x=0}^{N-1}\sum _{y=0}^{N-1}{\omega }^{-xy}|y⟩⟨x|.$$

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

相位估计 Phase estimation

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

$$\begin{array}{rl}& U_{\mathrm{iQFT}}\cdot \frac{1}{\sqrt{N}}\sum _{z=0}^{N-1}{\omega }^{\varphi z}|z⟩\\ =& \frac{1}{\sqrt{N}}\sum _{x=0}^{N-1}\sum _{y=0}^{N-1}{\omega }^{-xy}|y⟩⟨x|\cdot \frac{1}{\sqrt{N}}\sum _{z=0}^{N-1}{\omega }^{\varphi z}|z⟩\\ =& \frac{1}{N}\sum _{x=0}^{N-1}\sum _{y=0}^{N-1}\sum _{z=0}^{N-1}{\omega }^{\varphi z-xy}|y⟩⟨x|z⟩\\ =& \frac{1}{N}\sum _{x=0}^{N-1}\sum _{y=0}^{N-1}{\omega }^{\varphi x-xy}|y⟩\\ =& \sum _{y=0}^{N-1}\left(\frac{1}{N}\sum _{x=0}^{N-1}{\omega }^{x(\varphi -y)}\right)|y⟩\end{array}$$

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

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

1. 先明确符号的定义。$x,y,z$ 都是取遍 $\{0,1,\dots ,N-1\}$ 的整数；$|y⟩$ 是整数 $y$ 对应的计算基矢；而 $\frac{1}{N}{\sum }_{x=0}^{N-1}{\omega }^{x(\varphi -y)}$ 是分量 $|y⟩$ 的振幅。

2. 再看振幅的结构。每个振幅都是 $N$ 个模为 $1$ 的复数之和，其中第 $x$ 项的相位为 $2\pi x(\varphi -y)/N$，即 $\omega$ 的相位的 $x(\varphi -y)$ 倍。当 $y=\varphi$ 时所有项相位相同，发生相长叠加；当 $y\ne \varphi$ 时相邻两项的相位差 $2\pi (\varphi -y)/N$ 不是 $2\pi$ 的整数倍，各项互相抵消（下面严格计算）。

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

   $$\frac{1}{N}\left(\begin{array}{c}{\sum }_x{\omega }^{x(\varphi -0)}\\ {\sum }_x{\omega }^{x(\varphi -1)}\\ {\sum }_x{\omega }^{x(\varphi -2)}\\ ⋮\\ {\sum }_x{\omega }^{x(\varphi -(N-2))}\\ {\sum }_x{\omega }^{x(\varphi -(N-1))}\end{array}\right)$$

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

4. 测量这个量子态，得到每个基矢 $|y⟩$ 的概率为

   $p_y=\frac{1}{N^2}{\left|{\sum }_{x=0}^{N-1}{\omega }^{x(\varphi -y)}\right|}^2$

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

• 当 $y=\varphi$ 时，每一项都是 ${\omega }^0=1$：

$$\begin{array}{rl}{p}_{y=\varphi }& =\frac{1}{N^2}{\left|\sum _{x=0}^{N-1}{\omega }^0\right|}^2\\ & =\frac{1}{N^2}{N}^2=1.\end{array}$$

• 当 $y\ne \varphi$ 时，由等比数列求和公式

$$\sum _{x=0}^{N-1}{\omega }^{x(\varphi -y)}=\frac{({\omega }^N{)}^{\varphi -y}-1}{{\omega }^{\varphi -y}-1}=\frac{1-1}{{\omega }^{\varphi -y}-1}=0,$$

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

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

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

$$\left(\begin{array}{c}0\\ 0\\ 0\\ ⋮\\ 1\\ ⋮\\ 0\end{array}\right)=|\varphi ⟩.$$

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

$p_y=\frac{1}{N^2}\cdot \frac{{\sin }^2(\pi (\varphi -y))}{{\sin }^2(\pi (\varphi -y)/N)},$

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

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

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

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

小结

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

$|0⟩|u⟩\mapsto |\varphi ⟩|u⟩,$

其中 $|u⟩$ 是 $U$ 的本征态，$\varphi$ 由本征值决定，具体来说有 $U|u⟩=e^{2\pi i\varphi /N}|u⟩$。计数寄存器共有 $n$ 位，$N=2^n$，$\varphi$ 是一个 $n$ 位整数；当 $\varphi$ 不是整数时，输出为最接近 $\varphi$ 的整数（成功概率不低于 $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$。若把这个分辨率记为精度 $ϵ=\frac{1}{N}$，那么访问复杂度为 $O(\log 1/ϵ)$。

2. 实现 $c\text{-}{U}^t$ 等于重复 $t$ 次 $c\text{-}U$

   • 此时受控调用的总次数为 ${\sum }_{j=0}^{n-1}{2}^j=N-1$，访问复杂度为 $O(N)$；用精度 $ϵ$ 表示的话，写为 $O(1/ϵ)$。

Amplitude estimation (Quantum counting)

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

$U|0,0⟩=\sqrt{p_{\mathrm{succ}}}|\mathrm{good}⟩|0⟩+\sqrt{1-p_{\mathrm{succ}}}|\mathrm{bad}⟩|1⟩,$

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

回顾Amplitude amplification

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

$$U_O=I-2|\mathrm{good}⟩⟨\mathrm{good}|\otimes I$$

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

$$\begin{array}{rl}{U}_S& =U(2|0,0⟩⟨0,0|-I)U^{†}\\ & =2|\psi ⟩⟨\psi |-I\end{array}$$

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

$$\begin{array}{rl}{U}_S|g⟩& =2|\psi ⟩⟨\psi |g⟩-|g⟩=2\sqrt{p}|\psi ⟩-|g⟩=(2p-1)|g⟩+2\sqrt{p(1-p)}|b⟩,\\ U_S|b⟩& =2|\psi ⟩⟨\psi |b⟩-|b⟩=2\sqrt{1-p}|\psi ⟩-|b⟩=2\sqrt{p(1-p)}|g⟩+(1-2p)|b⟩.\end{array}$$

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

$$U_S=\left(\begin{array}{cc}2p-1& 2\sqrt{p(1-p)}\\ 2\sqrt{p(1-p)}& 1-2p\end{array}\right),U_O=\left(\begin{array}{cc}-1& 0\\ 0& 1\end{array}\right),$$

相乘便得到振幅放大的迭代算符 $G:=U_S{U}_O$：

$$G=U_S{U}_O=\left(\begin{array}{cc}1-2p& 2\sqrt{p(1-p)}\\ -2\sqrt{p(1-p)}& 1-2p\end{array}\right)=\left(\begin{array}{cc}\cos \theta & \sin \theta \\ -\sin \theta & \cos \theta \end{array}\right),$$

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

$\cos \theta =1-2p,\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\le \alpha \le \pi /2$，即 $\sin \alpha =\sqrt{p}$），则由倍角公式

$\cos \theta =1-2{\sin }^2\alpha =\cos 2\alpha ,\sin \theta =2\sin \alpha \cos \alpha =\sin 2\alpha ,$

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

$G^n|\psi ⟩=\sin (\alpha +n\theta )|g⟩+\cos (\alpha +n\theta )|b⟩.$

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

$n\approx \frac{\pi /2-\alpha }{2\alpha }\le \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_S{U}_O$ 是两个幺正算符的乘积，因此它本身仍然是一个幺正算符。于是本词条开头对一般幺正算符的讨论对它同样适用：存在一组本征态 $|u⟩$ 满足

$G|u⟩=e^{2\pi i\varphi /N}|u⟩$

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

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

$$\det (\lambda I-G)=\left|\begin{array}{cc}\lambda -\cos \theta & -\sin \theta \\ \sin \theta & \lambda -\cos \theta \end{array}\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 },{\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=i{v}_1$；归一化后得到

$$|u_1⟩=\frac{1}{\sqrt{2}}\left(\begin{array}{c}1\\ i\end{array}\right)=\frac{1}{\sqrt{2}}\left(|g⟩+i|b⟩\right),G|u_1⟩=e^{i\theta }|u_1⟩.$$

同理，把 ${\lambda }_2=e^{-i\theta }$ 代入可得 $v_2=-i{v}_1$，即

$$|u_2⟩=\frac{1}{\sqrt{2}}\left(\begin{array}{c}1\\ -i\end{array}\right)=\frac{1}{\sqrt{2}}\left(|g⟩-i|b⟩\right),G|u_2⟩=e^{-i\theta }|u_2⟩.$$

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

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

振幅估计 = 将振幅放大算符$U_S{U}_O$作为相位估计的算子$U$

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

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

$$|g⟩=\frac{1}{\sqrt{2}}\left(|u_1⟩+|u_2⟩\right),|b⟩=\frac{-i}{\sqrt{2}}\left(|u_1⟩-|u_2⟩\right).$$

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

$$\begin{array}{rl}|\psi ⟩& =\frac{\sqrt{p}}{\sqrt{2}}\left(|u_1⟩+|u_2⟩\right)+\frac{-i\sqrt{1-p}}{\sqrt{2}}\left(|u_1⟩-|u_2⟩\right)\\ & =\frac{\sqrt{p}-i\sqrt{1-p}}{\sqrt{2}}|u_1⟩+\frac{\sqrt{p}+i\sqrt{1-p}}{\sqrt{2}}|u_2⟩\\ & =C_1|u_1⟩+C_2|u_2⟩,\end{array}$$

其中

$C_1=\frac{\sqrt{p}-i\sqrt{1-p}}{\sqrt{2}},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 ⟩$ 与 $\{|u_1⟩,|u_2⟩\}$ 都是归一化的正交态。（作为交叉验证，也可以直接用内积计算：$C_1=⟨u_1|\psi ⟩=\frac{1}{\sqrt{2}}(⟨g|-i⟨b|)(\sqrt{p}|g⟩+\sqrt{1-p}|b⟩)=\frac{\sqrt{p}-i\sqrt{1-p}}{\sqrt{2}}$，与上式一致。）

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

$$\begin{array}{rl}& |0⟩\otimes (C_1|u_1⟩+C_2|u_2⟩)\\ =& C_1|0⟩|u_1⟩+C_2|0⟩|u_2⟩\\ \to & C_1|{\tilde{\varphi }}_1⟩|u_1⟩+C_2|{\tilde{\varphi }}_2⟩|u_2⟩,\end{array}$$

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

当我们测量第一个寄存器时，读数以概率 $|C_1{|}^2=\frac{1}{2}$ 落在 ${\varphi }_1$ 附近，以概率 $|C_2{|}^2=\frac{1}{2}$ 落在 ${\varphi }_2$ 附近。把读数 $\tilde{\varphi }$ 换算回角度 $\hat{\phi }=2\pi \tilde{\varphi }/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{\phi }>\pi$，则取 $\theta =2\pi -\hat{\phi }$），进而由 $\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⟩$，目标是制备

  $|x⟩=\frac{A^{-1}|b⟩}{\Vert A^{-1}|b⟩{\Vert }_2}$

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

对$U=e^{iAt}$的本征分解

1. $U=e^{iAt}$ 和 $A$ 具有相同的本征态。

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

   $e^{iAt}|u_i⟩={\sum }_{m=0}^{\infty }\frac{(i{\lambda }_{i}t{)}^m}{m!}|u_i⟩=e^{i{\lambda }_{i}t}|u_i⟩$

   于是我们根据 $A$ 的本征态和本征值，直接得到了 $U=e^{iAt}$ 的本征态（与 $A$ 相同）和本征值（$e^{i{\lambda }_{i}t}$）。相位估计从 $U$ 中读出的相位正是 ${\lambda }_{i}t\mathrm{mod}2\pi$。

2. 计算 $x=A^{-1}b$。

   有了上面的本征分解，求逆的路线就清晰了：在 $A$ 的本征基下，$A^{-1}$ 的作用就是把每个本征分量乘上 $1/{\lambda }_i$，而相位估计恰好能把本征值“暴露”到寄存器上，供我们实施这个乘法。具体步骤为：

   • 展开：把 $|b⟩$ 写成 $|b⟩={\sum }_i{\beta }_i|u_i⟩$，其中 ${\beta }_i=⟨u_i|b⟩$；于是 $A^{-1}|b⟩={\sum }_i\frac{{\beta }_i}{{\lambda }_i}|u_i⟩$。

   • 相位估计：以 $e^{iAt}$ 为受控算子对 $|0⟩|b⟩$ 做相位估计。由第 1 点，每个分量 $|u_i⟩$ 都是其本征态，相位 ${\lambda }_{i}t\mathrm{mod}2\pi$ 被转移到计数寄存器，得到 ${\sum }_i{\beta }_i|\widetilde{{\lambda }_{i}t}⟩|u_i⟩$。

   • 受控旋转（controlled rotation）：根据计数寄存器中的读数，对辅助比特做受控旋转，把振幅乘上一个正比于 $1/{\lambda }_i$ 的因子。

   • 逆相位估计与测量：做逆相位估计“清空”计数寄存器，再对辅助比特进行测量（或用振幅放大）筛选成功分支，最终得到正比于 ${\sum }_i\frac{{\beta }_i}{{\lambda }_i}|u_i⟩=A^{-1}|b⟩$ 的归一化态，即 $|x⟩$。

   具体的线路、成功率（与条件数 condition number $\kappa$ 的关系）、精度与复杂度分析将在完整展开，参见 HHL 算法详解。

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch03-algo-basics/phase-estimation
• 内容遵循 CC BY-NC-SA 4.0 许可协议