量子假币问题：随机分盘、奇偶 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。

参考文献