量子假币问题

假币称量问题是最古老的算法谜题之一：有 $N$ 枚外观完全相同的硬币，其中混有若干枚假币——所有真币重量相同，所有假币重量也相同，但假币比真币轻。我们手里只有一架天平，每次称量可以把任意两堆数量相同的硬币分别放上左右盘，天平只回答一个比特：平衡或倾斜（它不告诉我们哪一边更轻）。目标是用尽可能少的称量次数，把所有假币的位置全部找出来。

本词条讨论该问题的”多假币”版本：已知假币恰好有 $k$ 枚，并且承诺 $k<N/2$。我们将看到：

• 经典算法（包括任何自适应策略）需要 $\Omega (k\log (N/k))$ 次称量，而且这一信息论下界在量级上是紧的；
• 量子算法只需要 $O(k^{1/4})$ 次称量——不仅把对 $k$ 的依赖压到了四次根，而且完全消去了对 $N$ 的依赖。

这个问题的研究历史本身就很有启发性。早在 1997 年，Terhal 与 Smolin 就解决了 $k=1$ 的特例：他们证明单次量子查询即可在 $N$ 枚硬币中找出唯一一枚假币，而经典算法需要 $\Theta (\log N)$ 次称量（见文末 Zoo 编号 137）。十几年后，Iwama、Nishimura、Raymond 与 Teruyama 把结果推广到一般的 $k$，给出 $O(k^{1/4})$ 的量子算法（Zoo 编号 136），本词条讲解的正是后者的构造。

为什么这个问题值得放进查询复杂度一章？因为它是”用弱 oracle 模拟强 oracle”这一范式的教科书式例子。天平 oracle 只告诉我们”两边假币数是否相等”，信息量少得可怜；而我们真正想要的是能直接回答”某个子集里假币数的奇偶性”的 inner-product parity oracle——有了它，Bernstein–Vazirani 算法一次查询就能读出整串 $x$。Iwama 等人的核心想法是：用量子叠加同时尝试所有随机分盘方案，用振幅放大把”存在平衡分盘”这一事件放大成可测的信号，从而近似地模拟出 parity oracle。整个算法因此是三个我们已经学过的工具的嵌套：

1. 随机分盘 + 天平称量：把”假币数为偶数”转化为”存在平衡分盘方案”；
2. 振幅放大（见 Grover 与振幅放大）：把 $\Theta (m^{-1/2})$ 的平衡概率放大到常数，代价是 $O(m^{1/4})$ 次称量；
3. Bernstein–Vazirani 算法（见 Bernstein–Vazirani 算法）：用模拟出的 parity oracle 一次恢复假币串。

标题中的”四次方加速”（quartic speedup）指的是量子查询数 $k^{1/4}$ 是 $k$ 的四次根；后文会看到这个 $1/4$ 恰好是”两次开平方”各贡献一半的产物。

1. 问题的精确表述与 Balance Oracle

1.1 物理设定

用长度为 $N$ 的比特串

$$x\in \{0,1{\}}^N,|x|=k$$

标记假币的位置：$x_i=1$ 当且仅当第 $i$ 枚是假币。这里 $|x|={\sum }_i{x}_i$ 是 Hamming 权重，即假币总数。承诺条件 $k<N/2$ 的作用要到本节末才能看清：它用来消除一类oracle 本身永远无法消除的二义性。

设真币重量为 $w_0$，假币重量为 $w_1<w_0$。一次称量用一个查询串

$$q\in \{-1,0,1{\}}^N,\sum _{i=1}^N{q}_i=0$$

来描述：$q_i=1$ 表示把第 $i$ 枚放左盘，$q_i=-1$ 表示放右盘，$q_i=0$ 表示本次不称。约束 ${\sum }_i{q}_i=0$ 保证左盘的硬币数 $\#\{i:q_i=1\}$ 与右盘的硬币数 $\#\{i:q_i=-1\}$ 相等——这是天平称量的物理前提：只有两盘数量相同，重量的差异才能归因于假币。

1.2 天平答案的代数形式

天平的回答是

$${\chi }_x(q)=1[q\cdot x\ne 0],q\cdot x:=\sum _{i=1}^N{q}_i{x}_i\in \mathbb{Z}.$$

为什么”倾斜”恰好对应 $q\cdot x\ne 0$？直接计算左右两盘的重量差。注意 $q_i{x}_i$ 只对”被称量的假币”非零：它在左盘假币上取 $+1$，在右盘假币上取 $-1$。因此

$$q\cdot x=\#\{\text{左盘假币}\}-\#\{\text{右盘假币}\}.$$

两盘的总重量分别为（$L$、$R$ 为左右盘硬币集合，$|L|=|R|$）

$$W_L=w_0|L|-(w_0-w_1)\#\{\text{左盘假币}\},W_R=w_0|R|-(w_0-w_1)\#\{\text{右盘假币}\}.$$

由 $|L|=|R|$（即 ${\sum }_i{q}_i=0$），真币的贡献 $w_0|L|$ 与 $w_0|R|$ 恰好抵消，于是

$$W_L-W_R=-(w_0-w_1)q\cdot x.$$

因为 $w_0-w_1>0$，天平平衡（$W_L=W_R$）当且仅当 $q\cdot x=0$，即左右两盘的假币数相等。这里用到了一个关键假设：所有假币等重。如果假币轻重不一，重量差就不再是假币数之差的简单函数，整个构造都会失效。

天平的回答只有一个比特，量子化采用标准的相位 oracle 约定（与 Grover 算法中的相位翻转约定一致）：

$$O_{B,x}|q⟩=(-1{)}^{{\chi }_x(q)}|q⟩.$$

也就是说，倾斜的查询串相位翻转，平衡的查询串不变。注意这个 oracle 比”直接回答 $q\cdot x$“弱得多：它连 $q\cdot x$ 的符号都不给（天平不告诉我们哪边轻），更不用说具体数值了。

1.3 互补二义性与 $k<N/2$ 承诺

Balance oracle 有一个与生俱来的盲区：

Lemma 1. 对任何合法查询串 $q$（满足 ${\sum }_i{q}_i=0$），都有 ${\chi }_x(q)={\chi }_{\bar{x}}(q)$，其中 $\bar{x}=1-x$ 是 $x$ 的补串。因此，任何只使用 balance oracle 的算法——无论经典还是量子——都不可能区分 $x$ 与 $\bar{x}$。

证明。由 $\bar{x}=1-x$ 与 ${\sum }_i{q}_i=0$：

$$q\cdot \bar{x}=q\cdot (1-x)=\sum _{i=1}^N{q}_i-q\cdot x=0-q\cdot x=-q\cdot x.$$

所以 $q\cdot \bar{x}=0⟺q\cdot x=0$，即 ${\chi }_{\bar{x}}(q)=1[q\cdot \bar{x}\ne 0]=1[q\cdot x\ne 0]={\chi }_x(q)$。Q.E.D.

这个结论的物理含义很直白：把”假币”与”真币”的身份整体互换，每次称量的平衡/倾斜结果完全不变（变的是倾斜的方向，而天平恰恰不报告方向）。换句话说，balance oracle 的世界里，$x$ 和 $\bar{x}$ 是同一个问题的两个名字。

承诺条件 $k<N/2$ 正是用来在最后打破这个二义性的。两个候选串的 Hamming 权重满足

$$|x|+|\bar{x}|=N,|x|=k<\frac{N}{2}⟹|\bar{x}|=N-k>\frac{N}{2},$$

因此 $\{|x|,|\bar{x}|\}$ 中恰好有一个小于 $N/2$。算法无论输出 $x$ 还是 $\bar{x}$，只要取其中 Hamming 权重小于 $N/2$（也就是权重为 $k$）的那一个，就唯一确定了假币串。后文会看到，模拟出的 parity oracle 同样只能把 $x$ 确定到”互补对” $\{x,\bar{x}\}$，届时同样用这条承诺收尾。

2. 经典算法的瓶颈

在进入量子构造之前，先把经典极限讲清楚，这样才能看清量子加速到底加速了什么。

2.1 信息论下界

经典识别所有假币需要

$$\Omega \left(k\log \frac{N}{k}\right)$$

次称量。推导分两步，每步都只用一个简单事实。

第一步，数候选。假币串 $x$ 可以是 $\{0,1{\}}^N$ 中任意一个权重为 $k$ 的串，候选总数为 $\left(\genfrac{}{}{0ex}{}{N}{k}\right)$。天平每次只回答一个比特（平衡/倾斜），所以任何决策树式算法的称量次数 $T$ 必须满足 $2^T\ge \left(\genfrac{}{}{0ex}{}{N}{k}\right)$，即

$$T\ge {\log }_2\left(\genfrac{}{}{0ex}{}{N}{k}\right).$$

第二步，估计 ${\log }_2\left(\genfrac{}{}{0ex}{}{N}{k}\right)$。我们用标准的组合不等式

$${\left(\frac{N}{k}\right)}^k\le \left(\genfrac{}{}{0ex}{}{N}{k}\right)\le {\left(\frac{eN}{k}\right)}^k.$$

下界的证明是逐项比较：

$$\left(\genfrac{}{}{0ex}{}{N}{k}\right)=\prod _{j=0}^{k-1}\frac{N-j}{k-j}\ge \prod _{j=0}^{k-1}\frac{N}{k}={\left(\frac{N}{k}\right)}^k,$$

其中 $\frac{N-j}{k-j}\ge \frac{N}{k}$ 对 $0\le j\le k-1$ 成立，因为交叉相乘后等价于 $k(N-j)\ge N(k-j)$，即 $Nj\ge kj$，即 $N\ge k$。上界的证明：$\left(\genfrac{}{}{0ex}{}{N}{k}\right)\le \frac{N^k}{k!}$，而由 $e^k={\sum }_{j\ge 0}\frac{k^j}{j!}\ge \frac{k^k}{k!}$ 得 $k!\ge (k/e{)}^k$，代入即得 $\left(\genfrac{}{}{0ex}{}{N}{k}\right)\le \frac{N^k}{(k/e{)}^k}={\left(\frac{eN}{k}\right)}^k$。

对不等式取对数：

$$k{\log }_2\frac{N}{k}\le {\log }_2\left(\genfrac{}{}{0ex}{}{N}{k}\right)\le k{\log }_2\frac{N}{k}+k{\log }_{2}e,$$

所以在 $k\le N/2$ 的范围内（${\log }_2(N/k)\ge 1$，常数项 $k{\log }_{2}e$ 被吸收），

$${\log }_2\left(\genfrac{}{}{0ex}{}{N}{k}\right)=\Theta \left(k\log \frac{N}{k}\right).$$

2.2 下界是紧的，瓶颈在哪里

这个下界在量级上是紧的：经典的自适应策略（大致思想是反复把”尚未排除的候选集合”对半分盘称量，逐步缩小每枚假币的搜索范围）可以用 $O(k\log (N/k))$ 次称量找出全部假币。因此经典查询复杂度就是 $\Theta (k\log (N/k))$。

注意这个表达式的两个因子各自的来源：$\log (N/k)$ 是”定位一枚假币”所需的二分信息量，$k$ 是假币的枚数——经典算法本质上是一枚一枚（或一批一批）地找，总数随 $k$ 线性增长。量子算法要做的，正是把这个关于 $k$ 的线性依赖压成 $k^{1/4}$，并且彻底消去 $\log N$ 因子。

3. 如果有 Inner-Product Oracle，一次查询就够

现在暂时忘掉天平，设想我们手里有一个强得多的理想 oracle：对任意 $\tilde{q}\in \{0,1{\}}^N$（注意定义域是普通比特串，不再是 $\{-1,0,1{\}}^N$），它施加

$$O_{IP,x}|\tilde{q}⟩=(-1{)}^{\tilde{q}\cdot x}|\tilde{q}⟩,$$

其中 $\tilde{q}\cdot x={\sum }_i{\tilde{q}}_i{x}_i(\mathrm{mod}2)$ 是模 2 内积。这是标准的 Bernstein–Vazirani oracle：在均匀叠加 $\frac{1}{\sqrt{2^N}}{\sum }_{\tilde{q}}|\tilde{q}⟩$ 上调用一次，相位反冲（phase kickback）把 $x$ 写进相位，再做 $H^{\otimes N}$ 就直接测得 $|x⟩$——一次查询恢复全部 $N$ 个比特。

3.1 为什么必须限制在偶权查询

回到天平的世界，有一个物理约束立刻跳出来：能上天平的查询必须满足”两盘数量相等”。给定 $\tilde{q}\in \{0,1{\}}^N$，最自然的分盘方式是把指标集 $I(\tilde{q})=\{i:{\tilde{q}}_i=1\}$ 分成等大的两半，一半放左盘、一半放右盘。这要求 $|I(\tilde{q})|=|\tilde{q}|$ 是偶数。奇权查询根本无法上天平，所以我们只能退而求其次：把 Bernstein–Vazirani 限制在偶权查询的子空间上。问题是，只用偶权查询还能不能恢复 $x$？答案是”能，但只能恢复到互补对”。

3.2 偶权 Fourier 引理

权重为偶数的串恰好占 $\{0,1{\}}^N$ 的一半，共 $2^{N-1}$ 个（配对 $\tilde{q}\leftrightarrow \tilde{q}\oplus e_1$ 给出一一对应，每对恰有一个偶权串）。考虑在偶权均匀叠加上调用理想 parity oracle：

$$|{\varphi }_x⟩=\frac{1}{\sqrt{2^{N-1}}}\sum _{|\tilde{q}|\mathrm{even}}(-1{)}^{\tilde{q}\cdot x}|\tilde{q}⟩.$$

Lemma 2. 对任意 $x\in \{0,1{\}}^N$，

$$H^{\otimes N}|{\varphi }_x⟩=\frac{|x⟩+|\bar{x}⟩}{\sqrt{2}}.$$

证明。逐步计算 $H^{\otimes N}|{\varphi }_x⟩$ 在计算基矢 $|z⟩$ 上的振幅。第一步，展开 Hadamard 变换的定义 $H^{\otimes N}|\tilde{q}⟩=\frac{1}{\sqrt{2^N}}{\sum }_z(-1{)}^{\tilde{q}\cdot z}|z⟩$，代入得振幅

$$A(z)=\frac{1}{\sqrt{2^{N-1}}}\cdot \frac{1}{\sqrt{2^N}}\sum _{|\tilde{q}|\mathrm{even}}(-1{)}^{\tilde{q}\cdot x}(-1{)}^{\tilde{q}\cdot z}=2^{-(2N-1)/2}S(w),w:=x\oplus z,$$

第二步用了 $(-1{)}^a(-1{)}^b=(-1{)}^{a\oplus b}$ 把两个相位合并成 $\tilde{q}\cdot (x\oplus z)$。问题归结为求和式

$$S(w):=\sum _{|\tilde{q}|\mathrm{even}}(-1{)}^{\tilde{q}\cdot w}.$$

第三步，用奇偶投影技巧把”只枚举偶权串”改写为代数运算。”$|\tilde{q}|$ 为偶数”的指示函数可以写成 $\frac{1+(-1{)}^{|\tilde{q}|}}{2}$（偶权时为 $1$，奇权时为 $0$），于是

$$S(w)=\sum _{\tilde{q}\in \{0,1{\}}^N}(-1{)}^{\tilde{q}\cdot w}\frac{1+(-1{)}^{|\tilde{q}|}}{2}=\frac{1}{2}\underset{S_1}{\underbrace{\sum _{\tilde{q}}(-1{)}^{\tilde{q}\cdot w}}}+\frac{1}{2}\underset{S_2}{\underbrace{\sum _{\tilde{q}}(-1{)}^{\tilde{q}\cdot w+|\tilde{q}|}}}.$$

第四步，分别计算两个和。$S_1$ 就是标准 Fourier 正交性：${\sum }_{\tilde{q}}(-1{)}^{\tilde{q}\cdot w}=2^N{\delta }_{w,0}$（$w=0$ 时每项为 $1$；否则按坐标分解为 ${\prod }_i(1+(-1{)}^{w_i})=0$）。对 $S_2$，注意 $|\tilde{q}|={\sum }_i{\tilde{q}}_i$，所以指数可以按坐标分配：

$$S_2=\sum _{\tilde{q}}\prod _{i=1}^N(-1{)}^{{\tilde{q}}_i(w_i+1)}=\prod _{i=1}^N\left(1+(-1{)}^{w_i+1}\right)=2^N{\delta }_{w,1},$$

其中最后一个等号是因为：因子 $1+(-1{)}^{w_i+1}$ 在 $w_i=1$ 时等于 $2$，在 $w_i=0$ 时等于 $0$，所以整个乘积非零当且仅当每一位 $w_i=1$，即 $w=1$（全 1 串）。合并得

$$S(w)=2^{N-1}\left({\delta }_{w,0}+{\delta }_{w,1}\right).$$

第五步，代回振幅。$A(z)$ 非零当且仅当 $w=x\oplus z\in \{0,1\}$，即 $z=x$ 或 $z=x\oplus 1=\bar{x}$；此时

$$A(z)=2^{-(2N-1)/2}\cdot 2^{N-1}=2^{-(2N-1)/2+(N-1)}=2^{-1/2}=\frac{1}{\sqrt{2}}.$$

所以 $H^{\otimes N}|{\varphi }_x⟩=\frac{1}{\sqrt{2}}|x⟩+\frac{1}{\sqrt{2}}|\bar{x}⟩$。Q.E.D.

证明的第三步到第四步值得停下来体会：限制在偶权查询上，代价是把 Fourier 变换的输出从”单点 $x$“变成了”两点 $\{x,\bar{x}\}$“。这不是分析不够精细，而是信息真的丢失了——奇权查询恰好携带区分 $x$ 与 $\bar{x}$ 的那部分信息，而我们用不了它们。好在这与 Lemma 1 的互补二义性是同一个二义性，并不造成额外损失：测量得到 $x$ 或 $\bar{x}$ 各以概率 $1/2$，然后用 $k<N/2$ 承诺取权重较小的那个即可。

至此，整个算法的”顶层设计”完成了：只要我们能用 balance oracle 模拟出（近似）parity oracle $(-1{)}^{\tilde{q}\cdot x}$，剩下的就是一次偶权 Bernstein–Vazirani。 接下来两节解决唯一剩下的问题：奇偶相位从哪里来。

4. 随机分盘：把”假币数为偶”变成”可能平衡”

4.1 分盘方案与奇偶性的联系

固定一个偶权查询 $\tilde{q}$，记其支持集

$$I(\tilde{q})=\{i:{\tilde{q}}_i=1\},|I|=2s\text{为偶数}.$$

一次天平查询对应一个分盘方案：把 $I$ 平分为左右两盘 $(Y,I\setminus Y)$，其中 $Y\subseteq I$、$|Y|=s$；左盘对应 $q_i=+1$，右盘对应 $q_i=-1$。设这个子集中恰好有

$$m:=\tilde{q}\cdot x\in \{0,1,\dots ,k\}$$

枚假币（注意 $m\le k$，且 $\tilde{q}\cdot x\mathrm{mod}2$ 正是我们想模拟的奇偶相位）。天平平衡当且仅当两盘假币数相等（第 1.2 节的结论），即

$$\text{平衡}⟺\#\{Y\text{ 中的假币}\}=\frac{m}{2}.$$

由此立刻得到奇偶性的关键观察：

• $m$ 为奇数：$m/2$ 不是整数，任何分盘方案都不可能平衡——所有 $\left(\genfrac{}{}{0ex}{}{2s}{s}\right)$ 种分盘全部倾斜；
• $m=2r$ 为偶数：平衡当且仅当左盘恰好分到 $r$ 枚假币，这样的分盘方案确实存在。

也就是说，“是否存在平衡分盘”这一性质恰好等于”$m$ 为偶数”。如果我们能可靠地探测前者，就实现了后者，也就实现了 parity oracle 的相位 $(-1{)}^m=(-1{)}^{\tilde{q}\cdot x}$。边界情形 $m=0$ 也自动正确：子集中没有假币，任何分盘都平衡，相位为 $+1=(-1{)}^0$。

4.2 随机分盘的平衡概率

怎样探测”存在性”？朴素的经典思路是随机试：均匀随机地选一个等分方案 $Y$（共 $\left(\genfrac{}{}{0ex}{}{2s}{s}\right)$ 种），称一次；如果运气好碰到平衡分盘就知道了。这引出核心量——随机分盘的平衡概率。当 $m=2r$ 时，超几何分布给出精确值

$$p_m=\mathrm{Pr}[\text{平衡}]=\frac{\left(\genfrac{}{}{0ex}{}{m}{r}\right)\left(\genfrac{}{}{0ex}{}{2s-m}{s-r}\right)}{\left(\genfrac{}{}{0ex}{}{2s}{s}\right)},$$

分子是从 $m$ 枚假币中选 $r$ 枚、从 $2s-m$ 枚真币中补足剩下 $s-r$ 个位置的方式数，分母是所有等分方案数。

这个精确表达式不方便直接使用，我们采用如下启发式处理（这是本算法分析中模型依赖的一步，稍后会说明其地位）：当子集远大于假币数（$s\gg m$）时，每枚假币近似独立地以概率 $1/2$ 落入左盘，于是”恰好 $r$ 枚落左盘”的概率趋近于二项分布的中项

$$p_m\asymp \frac{\left(\genfrac{}{}{0ex}{}{2r}{r}\right)}{2^{2r}}.$$

用 Stirling 公式 $n!\sim \sqrt{2\pi n}(n/e{)}^n$ 估计中心二项式系数：

$$\left(\genfrac{}{}{0ex}{}{2r}{r}\right)=\frac{(2r)!}{(r!{)}^2}\approx \frac{\sqrt{4\pi r}(2r/e{)}^{2r}}{2\pi r(r/e{)}^{2r}}=\frac{4^r}{\sqrt{\pi r}},$$

因此

$$p_m\asymp \frac{\left(\genfrac{}{}{0ex}{}{2r}{r}\right)}{2^{2r}}=\frac{1}{\sqrt{\pi r}}=\Theta (r^{-1/2})=\Theta (m^{-1/2}),$$

最后一步用了 $m=2r$。数值小例子：$m=2$（即 $r=1$）时 $\left(\genfrac{}{}{0ex}{}{2}{1}\right)/2^2=1/2$；$m=4$（$r=2$）时 $\left(\genfrac{}{}{0ex}{}{4}{2}\right)/2^4=6/16=3/8=0.375$，与渐近值 $1/\sqrt{2\pi }\approx 0.399$ 已经很接近。

小结这一节的逻辑链：

$$m\text{ 为奇数}⟹p_m=0;m\text{ 为偶数}⟹p_m=\Theta (m^{-1/2})>0.$$

“奇偶之分”被翻译成了”平衡概率是零还是 $\Theta (m^{-1/2})$“。但 $\Theta (m^{-1/2})$ 太小，直接随机尝试需要 $1/p_m=\Theta (m^{1/2})$ 次称量——下一节用振幅放大把这个开销再开一次平方。

4.3 一处必须交代的保留条款

上面的 $p_m=\Theta (m^{-1/2})$ 是在”子集远大于假币数、各假币近似独立落盘”的启发式极限下得到的；对一般的 $s$ 与 $m$，精确的超几何概率需要更细致的分析。这个启发式步骤在原论文（Zoo 编号 136）中对应 big-pan（大盘）一类的结构性假设；同样地，第 5 节将要使用的”均匀随机分盘”对应论文中的 random-partition 结构。正如第 6 节会强调的：论文只在满足这些结构的算法框架内给出了匹配的查询下界证据，不能据此宣称 $O(k^{1/4})$ 是无条件最优的。本词条保留这一限定，后文所有涉及 $p_m$ 的复杂度表述都应在这一启发式框架下理解。

5. 振幅放大与四次根的来源

5.1 把分盘方案放进叠加

经典随机尝试的量子化是彻底的：不要”随机选一个分盘”，而是对所有分盘方案取均匀叠加。具体地，对每个处于叠加态中的偶权查询 $|\tilde{q}⟩$，附加一个辅助寄存器，相干地制备

$$|\tilde{q}⟩⟼|\tilde{q}⟩\otimes \frac{1}{\sqrt{\left(\genfrac{}{}{0ex}{}{2s}{s}\right)}}\sum _{\begin{array}{c}Y\subseteq I(\tilde{q})\\ |Y|=s\end{array}}|Y⟩.$$

这一步不消耗任何 oracle 查询：给定 $\tilde{q}$，枚举其支持集的所有等分方案是一个已知的、可逆的经典计算，可以做成不含 oracle 的酉电路。接着调用一次 balance oracle，把所有平衡分盘标记出来（相位翻转）。此时辅助寄存器的态可以分解为

$$\sqrt{p_m}|\mathrm{bal}⟩+\sqrt{1-p_m}|\mathrm{tilt}⟩,$$

其中 $|\mathrm{bal}⟩$ 是所有平衡分盘的（归一化）均匀叠加，$|\mathrm{tilt}⟩$ 是倾斜分盘的叠加，$p_m$ 就是第 4 节的平衡概率。

5.2 第一次开平方：概率变成振幅

注意这里已经发生了一次开平方：平衡事件的概率是 $p_m=\Theta (m^{-1/2})$，但它在量子态中以振幅 $\sqrt{p_m}$ 出现。由 $\sqrt{\Theta (m^{-1/2})}=\Theta (m^{-1/4})$，平衡分支的振幅只有

$$\sqrt{p_m}=\Theta (m^{-1/4}).$$

这正是振幅放大框架（见 Grover 与振幅放大）的标准输入：一个以振幅 $\sqrt{p_m}$ 落在”好状态”上的制备过程。

5.3 第二次开平方：振幅放大的 Grover 加速

振幅放大定理说：若一个酉过程以概率 $p$ 制备出好状态，则只需调用该过程 $O(1/\sqrt{p})$ 次，就能把好状态的概率放大到常数。套用到这里（$p=p_m$，“好状态”= 平衡分盘）：

$$O\left(\frac{1}{\sqrt{p_m}}\right)=O\left(\frac{1}{m^{-1/4}}\right)=O(m^{1/4})$$

次调用。每次调用包含一次 balance oracle 查询（用来标记平衡分盘），其余都是无 oracle 的可逆计算。所以探测”是否存在平衡分盘”的查询成本是 $O(m^{1/4})$ 次称量。

对比两条路线，可以清楚地看到两次开平方各在哪里：

• 经典随机尝试：重复 $1/p_m=\Theta (m^{1/2})$ 次称量；
• 量子路线：概率先开平方变成振幅 $\sqrt{p_m}=\Theta (m^{-1/4})$（第一次开平方），振幅放大再开平方，迭代数 $1/\sqrt{p_m}=O(m^{1/4})$（第二次开平方）。

总查询数关于 $m$ 的指数是 $\frac{1}{2}\times \frac{1}{2}=\frac{1}{4}$。由于 $m\le k$，最坏情况取 $m=k$，得到 $O(k^{1/4})$ 次称量——这就是”四次方加速”的全部来历。

5.4 施加相位与清除辅助寄存器

完成”寻找平衡分盘”的放大之后，按结果给 $\tilde{q}$ 分支打上奇偶相位：

1. 若放大成功（找到了平衡分盘）：由第 4 节，这意味着 $m$ 为偶数，施加相位 $+1$；
2. 若不存在平衡分盘（$m$ 为奇数，所有分盘恒倾斜，放大必然失败）：施加相位 $-1$；
3. 反向运行分盘制备与振幅放大的全部电路（uncompute），把辅助寄存器恢复到 $|0⟩$，只留下相位。

净效果就是在 $\tilde{q}$ 上实现了

$$|\tilde{q}⟩⟼(-1{)}^m|\tilde{q}⟩=(-1{)}^{\tilde{q}\cdot x}|\tilde{q}⟩,$$

即 parity oracle。相位取值的正确性直接来自第 4.1 节的对应关系：平衡存在 $⟺$ $m$ 偶 $⟺$ $(-1{)}^{\tilde{q}\cdot x}=+1$。

5.5 为什么是”近似”实现，以及总账目

上面的描述隐含了一个简化：振幅放大把成功概率放大到接近 $1$，但对不同的 $\tilde{q}$ 分支，$m$ 不同、所需的精确迭代次数也不同，而我们并不知道各分支的 $m$。统一运行固定的 $O(k^{1/4})$ 次迭代后，各分支会残留小的错误振幅，所以第 5.4 节实现的是 parity oracle 的近似版本。好在 Bernstein–Vazirani 的读出对小的常数级相干误差是稳健的——最终算法是一个有界错误算法；当 $k$ 已知时还可以进一步做成零错误（见第 6 节）。

最后清点总查询数，这也是整个算法最漂亮的一笔账：

• 对 $\tilde{q}$ 的均匀叠加，第 5.1–5.4 节的模拟过程是相干地、一次性地作用在所有分支上的——每个分支的放大并行进行，总查询数由最坏分支决定，即 $O(k^{1/4})$，不需要乘上分支数 $2^{N-1}$；
• 模拟完成后，执行一次偶权 Bernstein–Vazirani（第 3 节），它不引入新的 oracle 类型，parity 查询已经包含在上一步中；
• 测量得到 $x$ 或 $\bar{x}$，用 $k<N/2$ 承诺取权重较小者。

总查询复杂度：

$$O(k^{1/4})\text{次称量，与 }N\text{ 无关}.$$

对比经典的 $\Theta (k\log (N/k))$：量子算法把关于 $k$ 的依赖从线性压到四次根，并把 $\log N$ 因子整体消去。

6. 精确性、已知 $k$ 与下界边界

本节交代算法的若干精细性质与已知结果的边界，其中包含若干保留条款，阅读复杂度结论时应一并记住。

已知 $k$ 时的零错误版本。 如果 $k$ 事先已知，那么每个分支上可能的 $m\le k$ 取值范围也是已知的。此时可以用精确振幅放大（exact amplitude amplification，即通过调整反射算子中的相位，把成功概率精确放大到 $1$ 的变体）或分阶段搜索：按 $m$ 的可能取值分阶段运行放大，每个阶段用恰好匹配的迭代次数。这样每个分支的奇偶相位都是精确的，最终算法零错误。

未知 $k$ 时。 如果 $k$ 未知，可以用变长的量子搜索（QSearch 型策略：指数增长地试探迭代次数）得到有界错误的 $O(k^{1/4})$ 型算法，代价是停止时机与精确相位校正的处理更复杂。本词条不展开细节。

经典下界回顾。 第 2 节已经证明经典算法需要 $\Omega (k\log (N/k))$ 次称量，它来自”答案只有一比特、候选串有 $\left(\genfrac{}{}{0ex}{}{N}{k}\right)$ 个”的纯信息论论证。

量子下界的现状（保留条款）。 量子算法把对 $N$ 的依赖完全消去了，但一个匹配的、无条件的 $\Omega (k^{1/4})$ 量子查询下界尚未被证明。原论文（Zoo 编号 136）只对满足 big-pan 与 random-partition 等结构性假设的一类算法给出了该下界的证据——也就是说，“在这个框架内 $k^{1/4}$ 是最优的”，而不是”任何量子算法都不可能做得更好”。因此 $O(k^{1/4})$ 不能写成无条件最优；这是本问题仍然开放的一面。

7. $k=1$ 的直观特例（含完整手算）

一般的构造比较间接，先看 $k=1$ 的特例能建立直觉：此时连振幅放大都不需要。

7.1 一枚假币时，balance oracle 就是 parity oracle

$k=1$ 时，任何查询子集内至多有一枚假币。取偶权查询 $\tilde{q}$，把子集 $I(\tilde{q})$ 任意等分到两盘，逐情形分析：

• 假币不在 $I$ 中（$\tilde{q}\cdot x=0$）：两盘全是真币且数量相等，天平必平衡，${\chi }_x=0$；
• 假币在 $I$ 中（$\tilde{q}\cdot x=1$）：唯一的假币落在某一盘，该盘更轻，天平必倾斜，${\chi }_x=1$。

两种情形合并就是

$${\chi }_x(\tilde{q})=\tilde{q}\cdot x(k=1,|\tilde{q}|\text{ 为偶数}),$$

即 balance oracle 精确等于 parity oracle，无须随机分盘、无须振幅放大——因为”存在平衡分盘”这个随机事件退化成了确定事件。于是对所有偶权 $\tilde{q}$ 取均匀叠加、调用一次 balance oracle、再做 $H^{\otimes N}$，由 Lemma 2 直接得到

$$\frac{|x⟩+|\bar{x}⟩}{\sqrt{2}},$$

测量后用权重判据（$|x|=1<N/2$，而 $|\bar{x}|=N-1>N/2$）挑出 $x$。单次量子称量就找到了唯一假币的位置，而经典算法需要 $\Theta (\log N)$ 次（信息论下界 ${\log }_{2}N$ 次，二分称量可以达到）。这正是 Terhal–Smolin 的”单量子查询检索数据库”思想（Zoo 编号 137），也是整个 $O(k^{1/4})$ 算法的灵感起点。

7.2 $N=4$ 的完整手算

把第 7.1 节的论证在最小非平凡例子 $N=4$、$k=1$ 上完整算一遍。设第 2 枚是假币，即 $x=0100$（假币位置就是我们要找的答案）。

第一步，列出全部 $2^{4-1}=8$ 个偶权查询串，并计算相位 $(-1{)}^{\tilde{q}\cdot x}=(-1{)}^{{\tilde{q}}_2}$（$x$ 只有第 2 位为 1，内积就是 $\tilde{q}$ 的第 2 位）：

$\tilde{q}$	${\tilde{q}}_2$	相位
0000	0	$+1$
0011	0	$+1$
0101	1	$-1$
0110	1	$-1$
1001	0	$+1$
1010	0	$+1$
1100	1	$-1$
1111	1	$-1$

查询后的态为

$$|{\varphi }_x⟩=\frac{1}{\sqrt{8}}\left(|0000⟩+|0011⟩-|0101⟩-|0110⟩+|1001⟩+|1010⟩-|1100⟩-|1111⟩\right).$$

第二步，施加 $H^{\otimes 4}$。按 Lemma 2 的证明，输出态在 $|z⟩$ 上的振幅是 $A(z)=2^{-7/2}S(x\oplus z)$，其中 $S(w)=2^3({\delta }_{w,0}+{\delta }_{w,1111})$。逐个检验：

• $z=x=0100$：$w=0000$，$S=8$，$A=8/2^{7/2}=2^3/2^{7/2}=2^{-1/2}=\frac{1}{\sqrt{2}}$；
• $z=\bar{x}=1011$：$w=1111$，$S=8$，同样 $A=\frac{1}{\sqrt{2}}$；
• 其余 $z$（例如 $z=1100$，$w=1000$）：$w\notin \{0000,1111\}$，$S=0$，振幅为 $0$。

可以直接验证归一化：$|\frac{1}{\sqrt{2}}{|}^2+|\frac{1}{\sqrt{2}}{|}^2=1$。最终态为

$$\frac{|0100⟩+|1011⟩}{\sqrt{2}}.$$

第三步，测量以各 $1/2$ 的概率得到 $0100$ 或 $1011$。由承诺 $k=1<2$，取 Hamming 权重为 $1$ 的那个：$|0100|=1$ 保留，$|1011|=3$ 排除。答案：第 2 枚是假币。全程只用了一次称量（以量子叠加的形式）。

8. 小结与习题

小结

• 问题与 oracle：$N$ 枚硬币中恰有 $k<N/2$ 枚等重的轻假币；balance oracle 只判断左右两盘假币数是否相等（${\chi }_x(q)=1[q\cdot x\ne 0]$），不报告哪边更轻，也不返回内积奇偶。
• 互补二义性：balance oracle 永远区分不了 $x$ 与 $\bar{x}$（$q\cdot \bar{x}=-q\cdot x$）；承诺 $k<N/2$ 用 Hamming 权重在最后消除这一二义性。
• 经典瓶颈：信息论下界 ${\log }_2\left(\genfrac{}{}{0ex}{}{N}{k}\right)=\Omega (k\log (N/k))$，且在量级上紧。
• 算法骨架：理想 parity oracle + 偶权 Bernstein–Vazirani 一次恢复 $\{x,\bar{x}\}$；限制偶权查询的代价恰好是同一个互补二义性，无额外损失。
• 随机分盘：子集中假币数 $m$ 为奇数时永不平衡；$m$ 为偶数时随机分盘以 $p_m=\Theta (m^{-1/2})$ 的概率平衡（启发式/模型依赖的一步，见第 4.3 节）。
• 四次根的来源：概率 $\to$ 振幅开一次平方（$\sqrt{p_m}=\Theta (m^{-1/4})$），振幅放大再开一次平方（$O(1/\sqrt{p_m})=O(m^{1/4})$）；取最坏 $m=k$ 得总查询 $O(k^{1/4})$，与 $N$ 无关。
• 边界：$k$ 已知时可做成零错误；匹配的 $\Omega (k^{1/4})$ 无条件量子下界尚未证明，现有证据限于 big-pan、random-partition 等结构化框架。

习题

1. （计算）用 Stirling 公式 $n!\sim \sqrt{2\pi n}(n/e{)}^n$ 推导 $\left(\genfrac{}{}{0ex}{}{2r}{r}\right)/2^{2r}=\Theta (r^{-1/2})$，并给出渐近常数（即证明它 $\sim 1/\sqrt{\pi r}$）。
2. （证明）补全 Lemma 2 的细节：证明 $\{0,1{\}}^N$ 中偶权串恰有 $2^{N-1}$ 个，并验证求和式 ${\sum }_{|\tilde{q}|\mathrm{even}}(-1{)}^{\tilde{q}\cdot w}=2^{N-1}({\delta }_{w,0}+{\delta }_{w,1})$，从而偶权 Fourier 态只支持在 $x$ 与 $\bar{x}$ 上。
3. （概念）解释算法中两次”开平方”分别出现在何处：第一次把什么量变成什么量，第二次把什么量变成什么量？由此说明为什么总查询是 $k$ 的四次根，以及”quartic speedup”一词的含义。
4. （概念）说明承诺 $k<N/2$ 怎样消除互补二义性：如果 $k>N/2$ 或 $k=N/2$ 会发生什么？结合 Lemma 1 说明为什么这个二义性不可能靠改进 oracle 查询来消除。
5. （计算）设子集大小 $|I|=2s$，其中恰有 $m=2r$ 枚假币。写出随机等分时平衡概率的精确超几何表达式，并证明当 $s\to \infty$、$m$ 固定时它趋于 $\left(\genfrac{}{}{0ex}{}{2r}{r}\right)/2^{2r}$。（提示：比较 $\left(\genfrac{}{}{0ex}{}{2s-m}{s-r}\right)$ 与 $\left(\genfrac{}{}{0ex}{}{2s}{s}\right)$ 的渐近比值。）
6. （手算）在 $N=4$、$k=1$、$x=0010$（第 3 枚为假币）的设定下，仿照第 7.2 节列出全部偶权查询串及其相位，计算 $H^{\otimes 4}$ 后的态，并验证最终测量结果经权重判据后唯一确定 $x$。

参考文献

• Zoo 编号 136：Kazuo Iwama、Harumichi Nishimura、Rudy Raymond 与 Junichi Teruyama, Quantum Counterfeit Coin Problems.
• Zoo 编号 137：Barbara Terhal 与 John Smolin, Single Quantum Querying of a Database.

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch11-query-complexity/counterfeit-coins
• 内容遵循 CC BY-NC-SA 4.0 许可协议