量子计数算法 | Codeboy's Blog

形式陈述

取整数 $N\ge1$ 、 $0\le t\le N$ 与 $m\ge1$ 。设 $N$ 个位置中有 $t$ 个标记， $a=t/N$ 。均匀状态制备与 good 反射定义振幅放大算子 $Q=-A S_0 A^\dagger S_G$ 。当 $0<t<N$ 时，初态的 good/bad 两个归一化投影张成二维不变子空间；若

\sin^2\theta=a,\qquad 0\le\theta\le\frac\pi2,

则 $Q$ 在此子空间的两个特征值为 $e^{2i\theta}$ 与 $e^{-2i\theta}$ ，初态是对应特征向量的叠加。当 $t=0$ 或 $t=N$ 时，其中一个投影为零，这个不变空间退化为一维；按上述 $Q$ 的约定，初态的特征值分别为 $+1$ 、 $-1$ ，归一化相位分别为 $0$ 、 $1/2$ 。量子计数用 $m$ 个 evaluation qubits 对 $Q$ 做量子相位估计，令 $K=2^m$ 。若测得整数 $y$ ，先定义折回角 $\widetilde\theta=\pi\min(y/K,1-y/K)$ ，再转为

\widetilde a=\sin^2\widetilde\theta,\qquad \widetilde t=N\widetilde a.

受控幂 $Q,Q^2,\ldots,Q^{2^{m-1}}$ 总共使用 $K-1$ 次基本 iterate，故查询成本为 $O(K)$ 乘每个 $Q$ 内的状态制备、逆制备和 good reflection 成本。它不是把一个 controlled- $Q^{2^j}$ 当成一次免费 oracle。

Phase estimation 还要求 coherent controlled- $Q$ 。若模型只直接提供标准 bit oracle，就不能把“给未知黑盒加控制”视为免费门；可先用一次查询把 $x_i$ 写入 ancilla，以 Toffoli 按外部控制位和该 ancilla 翻转 target，再用第二次查询清理 ancilla。这个归约只改变常数，却必须计入每个受控 iterate 的查询账。

引用 BHMT amplitude estimation 的 Theorem 12，以至少 $8/\pi^2$ 的概率有[1]

|\widetilde a-a| \le \frac{2\pi\sqrt{a(1-a)}}K+\frac{\pi^2}{K^2}.

等价的计数误差为

|\widetilde t-t| \le \frac{2\pi\sqrt{t(N-t)}}K+\frac{\pi^2N}{K^2}.

选择 $K$ 前必须先声明所需绝对或相对误差；只写“phase estimation 有 $m$ 位精度”不足以推出整数计数正确。

直觉

搜索把未知角 $\theta$ 旋转到接近 good 轴，计数则把同一角当作待测信号。Grover iterate 的转角由标记比例唯一决定，phase estimation 通过不同幂次累积相位，再以 Fourier 变换读出频率。测得的归一化相位可能落在 $\theta/\pi$ 或 $1-\theta/\pi$ 两个分支；折回后的角相同，所以二者给同一 $\sin^2\theta=a$ 。

左侧 Grover 迭代以 2θ 等长旋转，右侧相位估计的归一化结果 1/4 与 3/4 折回 θ̃=π/4 并换算出 t̃=8 — 量子计数从 Grover 相位到标记数

这是一种 approximate counting，不会列出标记位置。获得很准的比例可能远便宜于输出全部见证；反过来，知道数量也不告诉标记在哪里。

例子与边界

取 $N=16,t=8$ ，则 $a=1/2$ 、 $\theta=\pi/4$ 。 $Q$ 的特征相位占整圆的比例为

\frac{2\theta}{2\pi}=\frac14 \quad\text{或}\quad 1-\frac14=\frac34.

用 $m=2$ 个 evaluation qubits， $K=4$ 的相位网格恰含 $1/4$ 与 $3/4$ ；理想 phase estimation 必测得二者之一。无论取哪个，折回的角都是 $\pi/4$ ，于是

\widetilde a=\sin^2(\pi/4)=\frac12,\qquad \widetilde t=16\cdot\frac12=8.

该例精确只是因为相位恰落在二进制网格。若 $t=4$ ，则 $\theta=\pi/6$ ，两支相位为 $1/6,5/6$ 。取同样的 $m=2$ ，由相位估计的有限分布

P_\varphi(y)=\frac1{16}\left|\sum_{x=0}^3e^{2\pi ix(\varphi-y/4)}\right|^2

可直接计算全部结果。对于 $\varphi=1/6$ ，例如 $y=0$ 时四项之和为 $i\sqrt3$ ，概率是 $3/16$ ； $y=1$ 时用几何级数求模平方得到 $(6+3\sqrt3)/16$ 。另一支满足 $P_{5/6}(y)=P_{1/6}((-y)\bmod4)$ ，所以交换 $y=1,3$ 的概率：

$y$	$P_{1/6}(y)$	$P_{5/6}(y)$	$\widetilde t=16\sin^2(\pi y/4)$
$0$	$3/16$	$3/16$	$0$
$1$	$(6+3\sqrt3)/16$	$(6-3\sqrt3)/16$	$8$
$2$	$1/16$	$1/16$	$16$
$3$	$(6-3\sqrt3)/16$	$(6+3\sqrt3)/16$	$8$

每列概率之和为一。两支相位各自折回后，都给出 $\Pr(\widetilde t=0)=3/16$ 、 $\Pr(\widetilde t=8)=3/4$ 、 $\Pr(\widetilde t=16)=1/16$ ；因此无论初态在两支上的权重如何，计数分布都相同。这次运行根本没有输出 $4$ 的可能，平均输出还等于 $7$ 而非 $4$ ，所以有限精度版本也不能被默认为无偏估计。提高精度的依据是概率误差界，而不是将相位截断误认为真实相位。

若想四舍五入得到精确整数，充分条件是

\frac{2\pi\sqrt{t(N-t)}}K+\frac{\pi^2N}{K^2}<\frac12.

这个条件在 $t$ 接近 $N/2$ 时迫使 $K=\Omega(N)$ ，所以算法没有对所有输入都用次线性查询精确计数的承诺。在 $t=0$ 或 $t=N$ 的一维端点，初态相位分别是 $0$ 或 $1/2$ ；当 $m\ge1$ 时，两者都恰在相位网格上，理想相位估计精确返回相应计数。

推论与应用

量子计数可估计解空间大小、Monte Carlo 成功概率或组合结构密度，但每个应用都必须提供可逆状态制备、good 反射及其查询成本。若 good 判定本身要访问输入，不能只统计受控 $Q$ 的次数而漏掉内部 oracle。

增加 $m$ 一位会把 $K$ 加倍，也使最大受控幂和总查询近似加倍；“多一位精度”不是常数代价。若需更高置信度，可独立重复制备与估计奇数 $r$ 次，再取实数估计值的中位数。一次结果落在上述以真实 $t$ 为中心的误差区间内的概率至少为 $p_0=8/\pi^2>1/2$ ；只要过半结果在区间内，中位数也在其中。Hoeffding 界给失败概率至多 $e^{-2r(p_0-1/2)^2}$ 。因此对 $0<\delta<1$ ，取不小于 $\ln(1/\delta)/(2(p_0-1/2)^2)$ 的奇数 $r$ 足够，总调用预算相应乘以 $r$ 。

参考资料

Gilles Brassard, Peter Høyer, and Alain Tapp, “Quantum Counting,” Proceedings of ICALP 1998, LNCS 1443, pp. 820–831.
[1] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp, “Quantum Amplitude Amplification and Estimation,” Contemporary Mathematics 305, 2002, pp. 53–74；Theorem 12 的成功概率与加法误差，以及整数计数的精度讨论。
Michael A. Nielsen and Isaac L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, 2010, §5.2.

形式陈述 ​

反向链接

形式陈述