量子计数算法 | Codeboy's Blog

形式陈述

设 $N$ 个位置中有 $t$ 个标记， $a=t/N$ 。均匀状态制备与 good 反射定义振幅放大算子 $Q$ ；在 good/bad 二维子空间中，若

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

则 $Q$ 的两个特征值为 $e^{2i\theta}$ 与 $e^{-2i\theta}$ 。初态是对应特征向量的叠加。量子计数用 $m$ 个 evaluation qubits 对 $Q$ 做 phase estimation，令 $K=2^m$ ，把测得相位 $\widetilde\theta$ 转为

\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 保证，以至少 $8/\pi^2$ 的概率，

|\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$ 或 $-\theta$ 分支，但 $\sin^2\theta$ 相同，所以二者给同一 $a$ 。

这是一种 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$ 不在有限二进制网格上，同样的 $m=2$ 不会确定输出 $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$ 的端点虽使第一项消失，oracle convention 和 phase 分支仍要单独处理。

推论与应用

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

增加 $m$ 一位会把 $K$ 加倍，也使最大受控幂和总查询近似加倍；“多一位精度”不是常数代价。误差概率若需从 $8/\pi^2$ 提高，还要重复估计并取稳健统计量，成本随目标置信度增长。

参考资料

Gilles Brassard, Peter Høyer, and Alain Tapp, “Quantum Counting,” Proceedings of ICALP 1998, LNCS 1443, pp. 820–831.
Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp, “Quantum Amplitude Amplification and Estimation,” Contemporary Mathematics 305, 2002, pp. 53–74.
Michael A. Nielsen and Isaac L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, 2010, §5.2.

形式陈述 ​

反向链接

形式陈述