量子假币问题：随机分盘、奇偶 oracle 与四次方加速

假币称量问题是最古老的算法谜题之一：有 \(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——能写出假币串 \(x\)（\(|x|=k<N/2\)）与查询串 \(q\in\{-1,0,1\}^N\)（\(\sum_i q_i=0\)）的定义，推导重量差 \(W_L-W_R=-(w_0-w_1)\,q\cdot x\)，并说明"平衡当且仅当两盘假币数相等"。

  2. 互补二义性与承诺条件——能证明 \(\chi_x(q)=\chi_{\bar x}(q)\) 对一切合法查询成立，并解释 \(k<N/2\) 承诺如何用 Hamming 权重在最后唯一确定假币串。

  3. 经典信息论下界——能用决策树计数推出 \(T\ge\log_2\binom{N}{k}\)，并用组合不等式夹逼证明 \(\log_2\binom{N}{k}=\Theta\!\left(k\log\frac{N}{k}\right)\)。

  4. 偶权 Fourier 引理——能用奇偶投影技巧证明 \(H^{\otimes N}|\phi_x\rangle=\frac{|x\rangle+|\bar x\rangle}{\sqrt{2}}\)，并解释限制偶权查询的代价恰好是同一个互补二义性。

  5. 奇偶—平衡对应——能解释"存在平衡分盘当且仅当子集内假币数 \(m\) 为偶数"的论证，并说明它如何给出奇偶相位 \((-1)^{\widetilde q\cdot x}\)。

  6. 随机分盘的平衡概率——能写出平衡概率的超几何精确表达式，并用 Stirling 公式完成 \(p_m=\Theta(m^{-1/2})\) 的渐近估计。

  7. 振幅放大与四次方加速——能计算 \(\sqrt{p_m}=\Theta(m^{-1/4})\) 与放大次数 \(O(1/\sqrt{p_m})=O(m^{1/4})\)，比较经典与量子两条路线，并清点总查询数为何为 \(O(k^{1/4})\) 且与 \(N\)、分支数无关。

  8. 单枚假币特例与手算——能说明 \(k=1\) 时 balance oracle 精确等于 parity oracle，并在 \(N=4\) 上完成"偶权叠加—相位—\(H^{\otimes N}\)—权重判据"的完整手算。

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

1.1 物理设定

用长度为 \(N\) 的比特串

\[ x\in\{0,1\}^N,\qquad |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,\qquad \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)=\mathbf{1}[\,q\cdot x\neq 0\,],\qquad q\cdot x := \sum_{i=1}^N q_i x_i \in\mathbb{Z}. \]

为什么"倾斜"恰好对应 \(q\cdot x \neq 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{左盘假币}\},\qquad 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\rangle = (-1)^{\chi_x(q)}|q\rangle. \]

也就是说，倾斜的查询串相位翻转，平衡的查询串不变。注意这个 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 = \mathbf{1} - x\) 是 \(x\) 的补串。因此，任何只使用 balance oracle 的算法——无论经典还是量子——都不可能区分 \(x\) 与 \(\bar x\)。

证明。由 \(\bar x = \mathbf{1} - x\) 与 \(\sum_i q_i = 0\)：

\[ q\cdot\bar x = q\cdot(\mathbf{1}-x) = \sum_{i=1}^N q_i - q\cdot x = 0 - q\cdot x = -q\cdot x. \]

所以 \(q\cdot\bar x = 0 \iff q\cdot x = 0\)，即 \(\chi_{\bar x}(q) = \mathbf{1}[q\cdot\bar x \neq 0] = \mathbf{1}[q\cdot x \neq 0] = \chi_x(q)\)。Q.E.D.

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

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

\[ |x| + |\bar x| = N,\qquad |x| = k < \tfrac{N}{2} \implies |\bar x| = N - k > \tfrac{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\) 的串，候选总数为 \(\binom{N}{k}\)。天平每次只回答一个比特（平衡/倾斜），所以任何决策树式算法的称量次数 \(T\) 必须满足 \(2^T \ge \binom{N}{k}\)，即

\[ T \ge \log_2\binom{N}{k}. \]

第二步，估计 \(\log_2\binom{N}{k}\)。我们用标准的组合不等式

\[ \left(\frac{N}{k}\right)^k \le \binom{N}{k} \le \left(\frac{eN}{k}\right)^k. \]

下界的证明是逐项比较：

\[ \binom{N}{k} = \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\)。上界的证明：\(\binom{N}{k} \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\)，代入即得 \(\binom{N}{k} \le \frac{N^k}{(k/e)^k} = \left(\frac{eN}{k}\right)^k\)。

对不等式取对数：

\[ k\log_2\frac{N}{k} \;\le\; \log_2\binom{N}{k} \;\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\binom{N}{k} = \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：对任意 \(\widetilde q \in \{0,1\}^N\)（注意定义域是普通比特串，不再是 \(\{-1,0,1\}^N\)），它施加

\[ O_{IP,x}|\widetilde q\rangle = (-1)^{\widetilde q\cdot x}|\widetilde q\rangle, \]

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

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

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

3.2 偶权 Fourier 引理

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

\[ |\phi_x\rangle = \frac{1}{\sqrt{2^{N-1}}}\sum_{|\widetilde q|\ \mathrm{even}} (-1)^{\widetilde q\cdot x}|\widetilde q\rangle. \]

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

\[ H^{\otimes N}|\phi_x\rangle = \frac{|x\rangle + |\bar x\rangle}{\sqrt{2}}. \]

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

\[ A(z) = \frac{1}{\sqrt{2^{N-1}}}\cdot\frac{1}{\sqrt{2^{N}}}\sum_{|\widetilde q|\ \mathrm{even}} (-1)^{\widetilde q\cdot x}\,(-1)^{\widetilde q\cdot z} = 2^{-(2N-1)/2}\, S(w),\qquad w := x \oplus z, \]

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

\[ S(w) := \sum_{|\widetilde q|\ \mathrm{even}} (-1)^{\widetilde q\cdot w}. \]

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

\[ S(w) = \sum_{\widetilde q \in \{0,1\}^N} (-1)^{\widetilde q\cdot w}\,\frac{1 + (-1)^{|\widetilde q|}}{2} = \frac{1}{2}\underbrace{\sum_{\widetilde q} (-1)^{\widetilde q\cdot w}}_{S_1} + \frac{1}{2}\underbrace{\sum_{\widetilde q} (-1)^{\widetilde q\cdot w + |\widetilde q|}}_{S_2}. \]

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

\[ S_2 = \sum_{\widetilde q} \prod_{i=1}^N (-1)^{\widetilde q_i (w_i + 1)} = \prod_{i=1}^N \left(1 + (-1)^{w_i + 1}\right) = 2^N\,\delta_{w,\mathbf{1}}, \]

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

\[ S(w) = 2^{N-1}\left(\delta_{w,0} + \delta_{w,\mathbf{1}}\right). \]

第五步，代回振幅。\(A(z)\) 非零当且仅当 \(w = x \oplus z \in \{0, \mathbf{1}\}\)，即 \(z = x\) 或 \(z = x \oplus \mathbf{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}|\phi_x\rangle = \frac{1}{\sqrt{2}}|x\rangle + \frac{1}{\sqrt{2}}|\bar x\rangle\)。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)^{\widetilde q\cdot x}\)，剩下的就是一次偶权 Bernstein–Vazirani。 接下来两节解决唯一剩下的问题：奇偶相位从哪里来。

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

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

固定一个偶权查询 \(\widetilde q\)，记其支持集

\[ I(\widetilde q) = \{i : \widetilde q_i = 1\},\qquad |I| = 2s \ \text{为偶数}. \]

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

\[ m := \widetilde q\cdot x \in \{0, 1, \dots, k\} \]

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

\[ \text{平衡} \iff \#\{Y \text{ 中的假币}\} = \frac{m}{2}. \]

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

  • \(m\) 为奇数：\(m/2\) 不是整数，任何分盘方案都不可能平衡——所有 \(\binom{2s}{s}\) 种分盘全部倾斜；

  • \(m = 2r\) 为偶数：平衡当且仅当左盘恰好分到 \(r\) 枚假币，这样的分盘方案确实存在。

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

4.2 随机分盘的平衡概率

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

\[ p_m = \Pr[\text{平衡}] = \frac{\dbinom{m}{r}\dbinom{2s-m}{s-r}}{\dbinom{2s}{s}}, \]

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

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

\[ p_m \asymp \frac{\binom{2r}{r}}{2^{2r}}. \]

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

\[ \binom{2r}{r} = \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{\binom{2r}{r}}{2^{2r}} = \frac{1}{\sqrt{\pi r}} = \Theta(r^{-1/2}) = \Theta(m^{-1/2}), \]

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

小结这一节的逻辑链：

\[ m \text{ 为奇数} \implies p_m = 0;\qquad m \text{ 为偶数} \implies 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 把分盘方案放进叠加

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

\[\begin{split} |\widetilde q\rangle \;\longmapsto\; |\widetilde q\rangle \otimes \frac{1}{\sqrt{\binom{2s}{s}}}\sum_{\substack{Y \subseteq I(\widetilde q)\\ |Y| = s}} |Y\rangle. \end{split}\]

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

\[ \sqrt{p_m}\,|\mathrm{bal}\rangle + \sqrt{1 - p_m}\,|\mathrm{tilt}\rangle, \]

其中 \(|\mathrm{bal}\rangle\) 是所有平衡分盘的（归一化）均匀叠加，\(|\mathrm{tilt}\rangle\) 是倾斜分盘的叠加，\(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 施加相位与清除辅助寄存器

完成"寻找平衡分盘"的放大之后，按结果给 \(\widetilde q\) 分支打上奇偶相位：

  1. 若放大成功（找到了平衡分盘）：由第 4 节，这意味着 \(m\) 为偶数，施加相位 \(+1\)；

  2. 若不存在平衡分盘（\(m\) 为奇数，所有分盘恒倾斜，放大必然失败）：施加相位 \(-1\)；

  3. 反向运行分盘制备与振幅放大的全部电路（uncompute），把辅助寄存器恢复到 \(|0\rangle\)，只留下相位。

净效果就是在 \(\widetilde q\) 上实现了

\[ |\widetilde q\rangle \longmapsto (-1)^{m}|\widetilde q\rangle = (-1)^{\widetilde q\cdot x}|\widetilde q\rangle, \]

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

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

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

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

  • 对 \(\widetilde 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}) \quad\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))\) 次称量，它来自"答案只有一比特、候选串有 \(\binom{N}{k}\) 个"的纯信息论论证。

量子下界的现状（保留条款）。 量子算法把对 \(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\) 时，任何查询子集内至多有一枚假币。取偶权查询 \(\widetilde q\)，把子集 \(I(\widetilde q)\) 任意等分到两盘，逐情形分析：

  • 假币不在 \(I\) 中（\(\widetilde q \cdot x = 0\)）：两盘全是真币且数量相等，天平必平衡，\(\chi_x = 0\)；

  • 假币在 \(I\) 中（\(\widetilde q \cdot x = 1\)）：唯一的假币落在某一盘，该盘更轻，天平必倾斜，\(\chi_x = 1\)。

两种情形合并就是

\[ \chi_x(\widetilde q) = \widetilde q\cdot x \qquad (k = 1,\ |\widetilde q| \text{ 为偶数}), \]

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

\[ \frac{|x\rangle + |\bar x\rangle}{\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)^{\widetilde q\cdot x} = (-1)^{\widetilde q_2}\)（\(x\) 只有第 2 位为 1，内积就是 \(\widetilde q\) 的第 2 位）：

\(\widetilde q\)

\(\widetilde 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\)

查询后的态为

\[ |\phi_x\rangle = \frac{1}{\sqrt{8}}\left(|0000\rangle + |0011\rangle - |0101\rangle - |0110\rangle + |1001\rangle + |1010\rangle - |1100\rangle - |1111\rangle\right). \]

第二步，施加 \(H^{\otimes 4}\)。按 Lemma 2 的证明，输出态在 \(|z\rangle\) 上的振幅是 \(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\rangle + |1011\rangle}{\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) = \mathbf{1}[q\cdot x \neq 0]\)），不报告哪边更轻，也不返回内积奇偶。

  • 互补二义性：balance oracle 永远区分不了 \(x\) 与 \(\bar x\)（\(q\cdot\bar x = -q\cdot x\)）；承诺 \(k < N/2\) 用 Hamming 权重在最后消除这一二义性。

  • 经典瓶颈：信息论下界 \(\log_2\binom{N}{k} = \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【问题设定与 Balance Oracle】（→ 1.1 节）

  1. 写出假币串 \(x\in\{0,1\}^N\)（\(|x|=k<N/2\)）与查询串 \(q\in\{-1,0,1\}^N\) 的定义，并解释约束 \(\sum_i q_i = 0\) 为什么恰好保证左右两盘硬币数相等。

  2. 设左、右盘硬币集合为 \(L\)、\(R\)（\(|L|=|R|\)）：推导 \(W_L - W_R = -(w_0 - w_1)\,q\cdot x\)，说明"平衡 \(\iff\) 两盘假币数相等"，并指出推导中哪一步用到了"所有假币等重"的假设。

提示：把每盘重量写成 \(w_0\times(\text{硬币数})-(w_0-w_1)\times(\text{假币数})\)。

练习 2【互补二义性与承诺条件】（→ 1.3 节）

  1. 取 \(N=6\)、\(k=2\)、\(x=\texttt{110000}\)：写出补串 \(\bar x\)，计算 \(|x|\) 与 \(|\bar x|\)，说明权重判据如何从互补对 \(\{x,\bar x\}\) 中唯一选出答案；再问：若 \(k = N/2\)，判据是否仍然可用？

  2. （概念）说明承诺 \(k < N/2\) 怎样消除互补二义性：如果 \(k > N/2\) 或 \(k = N/2\) 会发生什么？结合 Lemma 1 说明为什么这个二义性不可能靠改进 oracle 查询来消除。

提示：\(|x|+|\bar x|=N\)，两个权重中至多一个小于 \(N/2\)；而 Lemma 1 对任何合法查询都成立，与算法设计无关。

练习 3【经典信息论下界】（→ 2.1 节）

  1. 解释为什么任何经典决策树算法的称量次数 \(T\) 必须满足 \(2^T\ge\binom{N}{k}\)；取 \(N=100\)、\(k=10\)，用 \(\binom{N}{k}\ge(N/k)^k\) 估计次数下界，并与 \(k\log_2(N/k)\approx 33.2\) 比较。

  2. 补全上界 \(\binom{N}{k}\le\left(\frac{eN}{k}\right)^k\) 的证明：先证 \(\binom{N}{k}\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\)，合并两步。

提示：\(\binom{N}{k}\) 是"有序选出 \(k\) 个位置"方式数的 \(1/k!\) 倍。

练习 4【偶权 Fourier 引理】（→ 3.2 节）

  1. 证明 \(\{0,1\}^N\) 中偶权串恰有 \(2^{N-1}\) 个，并解释 3.1 节的物理约束为什么迫使 Bernstein–Vazirani 只能使用偶权查询。

  2. （证明）验证求和式 \(\sum_{|\widetilde q|\,\mathrm{even}}(-1)^{\widetilde q\cdot w} = 2^{N-1}(\delta_{w,0} + \delta_{w,\mathbf{1}})\)，从而偶权 Fourier 态只支持在 \(x\) 与 \(\bar x\) 上。

提示：用指示函数 \(\frac{1+(-1)^{|\widetilde q|}}{2}\) 把"只枚举偶权串"拆成两个可按坐标分解的求和。

练习 5【奇偶—平衡对应】（→ 4.1 节）

  1. 设子集 \(I\)（\(|I|=2s\)）中恰有 \(m\) 枚假币：说明 \(m\) 为奇数时为什么任何等分方案都不可能平衡；\(m=2r\) 为偶数时，平衡要求左盘恰好分到几枚假币？

  2. 说明"存在平衡分盘 \(\iff m\) 为偶数"这一对应如何与第 5.4 节的相位施加规则配合，实现 \(|\widetilde q\rangle\mapsto(-1)^{\widetilde q\cdot x}|\widetilde q\rangle\)，并检验 \(m=0\) 的边界情形。

提示：\(m=0\) 时任何分盘都平衡，相位为 \(+1=(-1)^0\)，与奇偶对应一致。

练习 6【随机分盘的平衡概率】（→ 4.2 节）

  1. 计算 \(m=2\) 与 \(m=4\) 时启发式概率 \(\binom{2r}{r}/2^{2r}\) 的精确值，并与渐近值 \(1/\sqrt{\pi r}\) 比较，验证正文"已经很接近"的说法。

  2. （计算）用 Stirling 公式 \(n! \sim \sqrt{2\pi n}\,(n/e)^n\) 推导 \(\binom{2r}{r}/2^{2r} = \Theta(r^{-1/2})\)，并给出渐近常数（即证明它 \(\sim 1/\sqrt{\pi r}\)）。

  3. （计算）设子集大小 \(|I| = 2s\)，其中恰有 \(m = 2r\) 枚假币。写出随机等分时平衡概率的精确超几何表达式，并证明当 \(s \to \infty\)、\(m\) 固定时它趋于 \(\binom{2r}{r}/2^{2r}\)。

提示：第 3 题比较 \(\binom{2s-m}{s-r}\) 与 \(\binom{2s}{s}\) 的渐近比值。

练习 7【振幅放大与四次方加速】（→ 5 节）

  1. 取 \(m=4\)（\(p_m \asymp 3/8\)）：计算平衡分支的振幅 \(\sqrt{p_m}\) 与振幅放大所需调用次数 \(1/\sqrt{p_m}\) 的数值，并与 \(m^{1/4}\) 比较。

  2. （概念）解释算法中两次"开平方"分别出现在何处：第一次把什么量变成什么量，第二次把什么量变成什么量？由此说明为什么总查询是 \(k\) 的四次根，以及"quartic speedup"一词的含义。

  3. 说明对全部 \(2^{N-1}\) 个偶权分支的模拟为什么不需要把 \(O(k^{1/4})\) 乘上分支数，总查询数由什么决定；并解释第 5.4 节的反向运行（uncompute）若被省略，后续 Bernstein–Vazirani 读出会发生什么。

提示：放大相干地作用在整个叠加上，查询数按最坏分支计；未清除的辅助寄存器会与 \(\widetilde q\) 纠缠，使 \(H^{\otimes N}\) 后得不到干净的 \(\frac{|x\rangle+|\bar x\rangle}{\sqrt{2}}\)。

练习 8【单枚假币特例与手算】（→ 7.1 节）

  1. \(k=1\) 时，对偶权查询 \(\widetilde q\) 分"假币不在 \(I\) 中"与"假币在 \(I\) 中"两种情形说明 \(\chi_x(\widetilde q) = \widetilde q\cdot x\)，并解释为什么此时不再需要随机分盘与振幅放大、单次量子称量即可定位假币。

  2. （手算）在 \(N = 4\)、\(k = 1\)、\(x = 0010\)（第 3 枚为假币）的设定下，仿照第 7.2 节列出全部偶权查询串及其相位，计算 \(H^{\otimes 4}\) 后的态，并验证最终测量结果经权重判据后唯一确定 \(x\)。

提示：内积满足 \((-1)^{\widetilde q\cdot x}=(-1)^{\widetilde q_3}\)，输出态应为 \(\frac{|\texttt{0010}\rangle+|\texttt{1101}\rangle}{\sqrt{2}}\)。

参考文献