量子相位估计 | Codeboy's Blog

形式陈述

给定有限维酉算子 $U$ 的归一化特征向量 $|u\rangle$ ，满足

U|u\rangle=e^{2\pi i\varphi}|u\rangle,\qquad 0\le\varphi<1.

算法假设已制备目标寄存器 $T$ 的 $|u\rangle$ ，并可实现相干受控幂 $U^{2^j}$ ， $0\le j<m$ 。令 $K=2^m$ ，寄存器顺序固定为 $C_{m-1}\otimes\cdots\otimes C_0\otimes T$ ，控制寄存器的整数编码是 $x=\sum_j2^jx_j$ 。目标是测出近似相位 $y/K$ ，而非直接读出目标态的振幅。

从受控操作到 Fourier 信号

一般受控门定义为 $|0\rangle\langle0|\otimes I+|1\rangle\langle1|\otimes U$ 。在特征态上，它把 $(|0\rangle+|1\rangle)|u\rangle/\sqrt2$ 变成 $(|0\rangle+e^{2\pi i\varphi}|1\rangle)|u\rangle/\sqrt2$ ：目标态未变，控制线的相对相位改变。这是相位 kickback从布尔符号到一般单位圆特征值的推广。

将控制线初始化为 $|0^m\rangle$ ，逐线做 $H$ ；以 $C_j$ 控制 $U^{2^j}$ 。由于这些幂作用在同一特征态上，得到

\frac1{\sqrt K}\sum_{x=0}^{K-1}|x\rangle U^x|u\rangle =\frac1{\sqrt K}\sum_{x=0}^{K-1}e^{2\pi ix\varphi}|x\rangle|u\rangle.

随后只在控制寄存器施加逆 Fourier 变换 $F_K^\dagger$ ，最后按计算基测量并输出 $y/K$ 。这里 $F_K$ 的定义采用正指数，故解码必须采用负指数。

完整的有限输出分布

结果 $y\in\{0,\ldots,K-1\}$ 的振幅及概率为

A_y=\frac1K\sum_{x=0}^{K-1}e^{2\pi ix(\varphi-y/K)},\qquad P_\varphi(y)=|A_y|^2.

若 $\varphi=a/K$ ，单位根求和给出 $P_\varphi(a)=1$ 。否则令 $\delta=\varphi-y/K$ ，由有限几何级数及 $|1-e^{2\pi it}|=2|\sin\pi t|$ 得

P_\varphi(y)=\frac{\sin^2(\pi K\delta)}{K^2\sin^2(\pi\delta)}.

分母为零时用前面的有限和解释，不能把 $0/0$ 当作零概率。相位按模一比较；定义 $d_{\mathbb T}(s,t)=\min_{n\in\mathbb Z}|s-t-n|$ 。对最近的网格点 $y_*/K$ ，有 $d_{\mathbb T}(\varphi,y_*/K)\le1/(2K)$ ，且

P_\varphi(y_*)\ge\frac4{\pi^2}.

直觉

直接对 $U|u\rangle$ 测量看不见整体相位。控制寄存器增加了“未施加 $U$ ”的参考分支，使这个相位成为分支之间可干涉的相对相位。不同控制位让它累积 $1,2,4,\ldots$ 倍，逆 Fourier 变换再把转速转成整数标签。

上到下控制位 C2、C1、C0 分别控制 U 的四次、二次、一次幂；逆 F8 后在计算基测量，将相位 5/8 确定读成 101 — 控制位权、酉幂与相位输出

控制位在逆变换前各自呈现不同相位，却不能逐位独立测量后再拼接成答案。逆变换负责处理这些相位之间的进位关系；当真实相位没有有限二进制展开时，残余干涉表现为一整个概率分布。

例子与边界

三位精确读取 $5/8$

取 $U=\operatorname{diag}(1,e^{5\pi i/4})$ ，目标态为 $|1\rangle$ ，所以 $\varphi=5/8$ 。在顺序 $C_2,C_1,C_0$ 下， $U^4,U^2,U$ 分别产生模一相位 $1/2,1/4,5/8$ 。控制寄存器成为

\frac{|0\rangle-|1\rangle}{\sqrt2} \otimes\frac{|0\rangle+i|1\rangle}{\sqrt2} \otimes\frac{|0\rangle+e^{5\pi i/4}|1\rangle}{\sqrt2} =F_8|101\rangle.

因此 $F_8^\dagger$ 后以概率一测得 $101$ ，输出 $5/8$ 。这同时检验了幂次、正负号和位序；若用正向 $F_8$ 解码，将得到负标签 $-5\bmod8=3$ ，而不是 $5$ 。

两位估计 $1/3$ 的全部结果

令 $m=2$ 、 $\varphi=1/3$ 。例如 $y=1$ 时 $\delta=1/12$ ，于是

P(1)=\frac{\sin^2(\pi/3)}{16\sin^2(\pi/12)} =\frac{6+3\sqrt3}{16}.

其余三项同理由有限和得到：

测得位串	输出 $y/4$	概率
$00$	$0$	$1/16$
$01$	$1/4$	$(6+3\sqrt3)/16$
$10$	$1/2$	$3/16$
$11$	$3/4$	$(6-3\sqrt3)/16$

四项之和恰为一。最近点 $1/4$ 的成功概率约为 $0.699760$ ，相位误差为 $1/12$ ；算法既不确定输出二进制截断，也不可能用这四个输出值精确表示 $1/3$ 。接近相位 $1$ 时，最近输出可能是 $0$ ，所以误差必须按圆周距离解释。

特征态和受控接口不是自动获得的

若输入为 $|\psi\rangle=\sum_\ell c_\ell|u_\ell\rangle$ ，在有限维谱定理给出的正交特征基中演算并忽略目标寄存器，得到 $P(y)=\sum_\ell|c_\ell|^2P_{\varphi_\ell}(y)$ 。这是按权重抽取特征相位的混合分布，不是对相位期望值做估计。应用必须另行解释特征态制备或所需特征空间的重叠概率。

只有未知 $U$ 黑盒时，不能一般地免费给它加控制： $U$ 与 $e^{i\gamma}U$ 作为孤立黑盒相差不可观测的整体相位，而它们的受控版本在控制线留下不同的相对相位。本算法的受控访问假设必须在应用的 oracle 或已知门电路中落实。

推论与应用

资源账要区分两种接口。若外部直接提供各个受控幂，主算法调用它们 $m$ 次；若每个幂靠重复受控 $U$ 实现，总调用数为 $1+2+\cdots+2^{m-1}=K-1$ 。控制寄存器的 Fourier 电路另需 $O(m^2)$ 个门。因此分辨率随 $2^{-m}$ 缩小，并不代表基本查询成本也只随 $m$ 增长。

若已知 $U$ 的电路有 $g$ 个门，且各门可按常数开销受控，直接实现的成本为 $O(g(K-1)+m^2)$ ；固定门集的近似合成还需额外精度分析。量子查询模型将输入无关门视为免费，只是一种计费约定，不能据此把一般受控幂或特征态制备记成免费。

量子计数把 Grover 迭代的两支特征相位折回同一个标记比例，因而不必先选出其中一支特征态。它仍须把上述有限分布转为计数误差，不能把一个 $m$ 位相位输出直接等同于正确整数答案。

参考资料

Andrew M. Childs, Lecture Notes on Quantum Algorithms，2025-04-17 版，§4.3，印刷页 18–19，式 (4.11)–(4.17)：受控幂与有限输出分布。
Richard Cleve, Artur Ekert, Chiara Macchiavello, Michele Mosca, “Quantum Algorithms Revisited”，arXiv v1，1997-08-08，§5，式 (5.1)–(5.4)：相位估计构造及最近网格点的 $4/\pi^2$ 成功率。此处引用已核验的预印本编号，而非 1998 年期刊版页码。

形式陈述 ​

从受控操作到 Fourier 信号 ​

完整的有限输出分布 ​

三位精确读取 5/8 ​

两位估计 1/3 的全部结果 ​

特征态和受控接口不是自动获得的 ​