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

有 $N$ 枚外观相同的硬币，其中恰有 $k<N/2$ 枚等重的轻假币。天平每次只能回答“平衡/倾斜”，不告诉哪边更轻。经典识别所有假币需要 $\Omega(k\log(N/k))$ 次称量；量子算法把大量分盘方案置于叠加，用振幅放大近似模拟 inner-product parity oracle，再由 Bernstein--Vazirani 一次恢复假币串，总查询为 $O(k^{1/4})$。

## 1. Balance oracle 的精确定义

用

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

表示假币位置。查询串

$$
q\in\{-1,0,1\}^N,\qquad
\sum_iq_i=0
$$

把 $q_i=1$ 的币放左盘、$-1$ 放右盘、0 不称；两盘硬币总数相同。答案

$$
\chi_x(q)=1[q\cdot x\ne0]
$$

表示倾斜。量子相位 oracle 为

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

该 oracle 无法区分 $x$ 与补串 $\bar x$，因为

$$
q\cdot\bar x=q\cdot(\mathbf1-x)=-q\cdot x.
$$

$k<N/2$ 的承诺用 Hamming weight 在最终消除这二义性。

## 2. 如果有 inner-product oracle，一次就够

理想 oracle 对任意 $\widetilde q\in\{0,1\}^N$ 施加

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

在均匀叠加上调用一次，再做 $H^{\otimes N}$，Bernstein--Vazirani 直接输出 $|x\rangle$。

为满足两盘等大，先把查询限制为偶 Hamming weight。偶权查询态的 Fourier 变换只区分 $x$ 与 $\bar x$：

$$
\frac1{\sqrt{2^{N-1}}}
\sum_{|\widetilde q|\ \mathrm{even}}
(-1)^{\widetilde q\cdot x}|\widetilde q\rangle
\xrightarrow{H^{\otimes N}}
\frac{|x\rangle+|\bar x\rangle}{\sqrt2}.
$$

测量后选择权重小于 $N/2$ 的结果，就恢复 $x$。问题只剩：怎样用 balance oracle 实现奇偶相位？

## 3. 随机分盘把偶数假币变成“可能平衡”

固定偶权子集

$$
I(\widetilde q)=\{i:\widetilde q_i=1\}.
$$

将它均匀随机分为等大的左右盘 $(Y,I\setminus Y)$。设该子集中恰有 $m$ 枚假币。

- 若 $m$ 为奇数，不可能左右各有 $m/2$ 枚假币，所有分盘都倾斜。
- 若 $m=2r$ 为偶数，天平平衡当且仅当左右各有 $r$ 枚假币。

忽略真币如何补足两盘后，随机分盘把假币均分的概率含中心二项式因子

$$
p_m\asymp
\frac{\binom{2r}{r}}{2^{2r}}
=\Theta(m^{-1/2}).
$$

所以“是否存在平衡分盘”正好区分 $m$ 的偶奇：奇数时成功概率 0，偶数时至少 $\Theta(1/\sqrt m)$。

## 4. 振幅放大为何产生四次根

对每个处于叠加的 $\widetilde q$，再相干制备其所有等分盘的均匀叠加，调用 balance oracle 标记平衡分盘。若 $m$ 偶，初始成功概率

$$
p_m=\Theta(m^{-1/2});
$$

振幅本身只有 $\sqrt{p_m}=\Theta(m^{-1/4})$。振幅放大把平衡分支放大到常数需要

$$
O(1/\sqrt{p_m})=O(m^{1/4})
$$

次称量查询。因 $m\le k$，最坏为 $O(k^{1/4})$。

完成“寻找平衡分盘”后：

1. 若找到平衡，给 $\widetilde q$ 分支施加偶 parity 相位 $+1$；
2. 若不存在（所有分盘倾斜），施加奇 parity 相位 $-1$；
3. 反向运行分盘制备与放大，清除辅助寄存器。

这就在整个 $\widetilde q$ 叠加上近似实现 $(-1)^{\widetilde q\cdot x}$。最后执行 parity-restricted Bernstein--Vazirani，测得 $x$ 或 $\bar x$。

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

若 $k$ 已知，可以根据可能的 $m\le k$ 设计 exact amplitude amplification/分阶段搜索，使最终算法零错误；若 $k$ 未知，变长 QSearch 仍给有界错误 $O(k^{1/4})$ 型算法，但停止与精确相位校正更复杂。

经典 lower bound 来自答案只有一比特、候选串数为 $\binom Nk$：

$$
\log_2\binom Nk
=\Omega(k\log(N/k)).
$$

量子算法消除了 $N$ 依赖，但一般匹配的 $\Omega(k^{1/4})$ 下界尚未证明。论文只对满足 big-pan 与 random-partition 等结构的算法给出该下界证据，不能写成无条件最优。

## 6. $k=1$ 的直观特例

任意查询子集内至多一枚假币。把子集等分到两盘：

- 没有假币时平衡；
- 有一枚时必倾斜。

所以一次 balance query 已精确给出该子集的 parity，不需振幅放大。对所有偶权子集叠加查询并做 Hadamard，单次量子称量就把假币位置编码为 $|x\rangle+|\bar x\rangle$。这与 Terhal--Smolin 的单查询数据库思想一致。

## 7. 小结与习题

- Balance oracle 判断左右假币数是否相等，而不是直接返回奇偶。
- 奇数枚假币永不平衡；偶数枚在随机分盘下以 $\Theta(m^{-1/2})$ 概率平衡。
- 振幅放大对概率开平方，产生 $m^{1/4}$ 查询成本。
- 模拟出的 parity oracle 再由 Bernstein--Vazirani 一次恢复整串。

1. 用 Stirling 公式推导 $\binom{2r}{r}/2^{2r}=\Theta(r^{-1/2})$。
2. 证明偶权 Fourier 态只支持 $x$ 与 $\bar x$。
3. 解释两次“开平方”分别出现在何处，为什么称为 quartic speedup。
4. 说明 $k<N/2$ 承诺怎样消除 complement ambiguity。

## 参考文献

- 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).