# 量子假币问题：随机分盘、奇偶 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 与振幅放大](../ch03-algo-basics/amplitude-amplification.md)）：把 $\Theta(m^{-1/2})$ 的平衡概率放大到常数，代价是 $O(m^{1/4})$ 次称量；
3. Bernstein–Vazirani 算法（见 [Bernstein–Vazirani 算法](../ch04-classic-algorithms/bernstein-vazirani-algorithm-tutorial.md)）：用模拟出的 parity oracle 一次恢复假币串。

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

:::{admonition} 本课知识点
:class: tip

1. **[问题设定与 Balance Oracle](#problem-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. **[互补二义性与承诺条件](#complement-ambiguity-promise)**——能证明 $\chi_x(q)=\chi_{\bar x}(q)$ 对一切合法查询成立，并解释 $k<N/2$ 承诺如何用 Hamming 权重在最后唯一确定假币串。
3. **[经典信息论下界](#classical-lower-bound-counterfeit-coins)**——能用决策树计数推出 $T\ge\log_2\binom{N}{k}$，并用组合不等式夹逼证明 $\log_2\binom{N}{k}=\Theta\!\left(k\log\frac{N}{k}\right)$。
4. **[偶权 Fourier 引理](#even-weight-fourier-lemma)**——能用奇偶投影技巧证明 $H^{\otimes N}|\phi_x\rangle=\frac{|x\rangle+|\bar x\rangle}{\sqrt{2}}$，并解释限制偶权查询的代价恰好是同一个互补二义性。
5. **[奇偶—平衡对应](#parity-balance-correspondence)**——能解释"存在平衡分盘当且仅当子集内假币数 $m$ 为偶数"的论证，并说明它如何给出奇偶相位 $(-1)^{\widetilde q\cdot x}$。
6. **[随机分盘的平衡概率](#balance-probability-estimate)**——能写出平衡概率的超几何精确表达式，并用 Stirling 公式完成 $p_m=\Theta(m^{-1/2})$ 的渐近估计。
7. **[振幅放大与四次方加速](#amplification-quartic-speedup)**——能计算 $\sqrt{p_m}=\Theta(m^{-1/4})$ 与放大次数 $O(1/\sqrt{p_m})=O(m^{1/4})$，比较经典与量子两条路线，并清点总查询数为何为 $O(k^{1/4})$ 且与 $N$、分支数无关。
8. **[单枚假币特例与手算](#single-coin-special-case)**——能说明 $k=1$ 时 balance oracle 精确等于 parity oracle，并在 $N=4$ 上完成"偶权叠加—相位—$H^{\otimes N}$—权重判据"的完整手算。

:::

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

(problem-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 算法](../ch03-algo-basics/grover.md)中的相位翻转约定一致）：

$$
O_{B,x}|q\rangle = (-1)^{\chi_x(q)}|q\rangle.
$$

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

(complement-ambiguity-promise)=
### 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. 经典算法的瓶颈

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

(classical-lower-bound-counterfeit-coins)=
### 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$？答案是"能，但只能恢复到互补对"。

(even-weight-fourier-lemma)=
### 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. 随机分盘：把"假币数为偶"变成"可能平衡"

(parity-balance-correspondence)=
### 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$。

(balance-probability-estimate)=
### 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$ 的复杂度表述都应在这一启发式框架下理解。

(amplification-quartic-speedup)=
## 5. 振幅放大与四次根的来源

### 5.1 把分盘方案放进叠加

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

$$
|\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.
$$

这一步**不消耗任何 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 与振幅放大](../ch03-algo-basics/amplitude-amplification.md)）的标准输入：一个以振幅 $\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$ 的特例能建立直觉：此时连振幅放大都不需要。

(single-coin-special-case)=
### 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 节](#problem-balance-oracle)）

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 节](#complement-ambiguity-promise)）

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 节](#classical-lower-bound-counterfeit-coins)）

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 节](#even-weight-fourier-lemma)）

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 节](#parity-balance-correspondence)）

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 节](#balance-probability-estimate)）

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 节](#amplification-quartic-speedup)）

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 节](#single-coin-special-case)）

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}}$。

## 参考文献

- Zoo 编号 136：Kazuo Iwama、Harumichi Nishimura、Rudy Raymond 与 Junichi Teruyama, [Quantum Counterfeit Coin Problems](https://arxiv.org/abs/1009.0416).
- Zoo 编号 137：Barbara Terhal 与 John Smolin, [Single Quantum Querying of a Database](https://arxiv.org/abs/quant-ph/9705041).