一次提问分辨公平与作弊：Deutsch-Jozsa

先备导航：你需要 016（干涉与交叉项）、017（换轴）、019（相位写信息）、021/022（H、CNOT）、024（电路图）。

下一篇预告：032《听出隐藏的比特串：Bernstein-Vazirani》。

一次提问分辨公平与作弊：Deutsch-Jozsa

桌上两台铸币机，外观一模一样。一台公平：投进去一枚空白坯，吐出来的硬币正反各半；另一台作弊：吐出来的永远是同一面（要么全是正、要么全是反）。你从中任取一台装进盲盒，允许你投坯问机器。问：最少问几次，才能保证分辨出它是公平还是作弊？

经典世界的答案：两次。只抛一次，落下一枚正面——公平机会也会给正面，你不敢断言；抛两次，全同面才敢下"作弊"的结论（严格论证：想"保证"分辨，两次是底线）。

1992 年，两个问题被并在一起提出来：如果把"抛坯问机器"换成量子版——坯是量子比特、机器是量子黑箱——一次就够，而且不是运气好，是保证一次。这就是 Deutsch-Jozsa 算法（下称 DJ 算法），量子算法家族的第一件成品。它小到两三个比特就能演示，却装着之后所有大算法（Grover、Simon、Shor）的完整套路。批四就从它开始。

把问题写规范

先把铸币机翻译成数学。黑箱函数 f，输入一个比特、输出一个比特，且事先承诺二选一：

• 常数：f(0) = f(1)（两问同答——作弊机）；
• 平衡：f(0) ≠ f(1)（两问一正一反——公平机）。

任务：判断 f 属于哪一类。经典确定算法必须调用黑箱两次（各问 f(0)、f(1)，比较答案）。量子算法的宣言：一次调用，确定分辨。

先拦一个必然会冒出来的念头：*"一次调用把 f(0) 和 f(1) 同时读了"？*——不是。005 篇拆过的"指数并行"误会在这里再次现形：黑箱只被调用一次，但它的输入被铺成了叠加（0 和 1 同时在场）；测量结束时，你读不到 f(0) 或 f(1) 中的任何一个——你读到的是一个全局性质（"f 是否恒等"）。经典问两次、读两个值；量子问一次、读一个性质。这一句就是全部量子算法的宪法，值得抄在门框上。

主角登场：相位回踢

量子黑箱怎么"调用"？它是一个合法的量子门（018 篇资格线）：把输入线 x 和一根辅助线做联合变换——U_f 作用在 |x⟩|y⟩ 上，输出 |x⟩|y 加 f(x)⟩：x 原样通过，f(x) 的值加到辅助线上（异或）。

妙处在选辅助线的初态：不喂 |0⟩ 或 |1⟩，喂 |−⟩（017 篇的赤道反相点）。看 U_f 作用上去会发生什么——

• f(x)=0：辅助线加 0，还是 |−⟩；
• f(x)=1：辅助线加 1，|−⟩ 翻成 |+⟩，整体相当于输入线那一支被乘了 −1。

辅助线在两种情形下自己纹丝不动（|−⟩ 加 0 变 |+⟩？——细看：|−⟩=(|0⟩−|1⟩)/√2，加 1 得 |1−0⟩=(|1⟩−|0⟩)/√2=−|−⟩，整体一个负号），效果全部落在输入线上：f(x) 的值变成了输入线那支箭头的符号。

这步棋有个学名"相位回踢"，但叫法不重要，画面要拿住：黑箱的答案没有变成任何可测的值，它变成了箭头的朝向——019 篇的"隐形墨水"第一次正式上岗：信息被写进了相位。

电路全景与干涉收网

完整电路（024 篇的语法）：

q0(输入): ──H──■──H──M
              │
q1(辅助): ──H──X─────

三步读谱：一，输入线过 H，铺成 (|0⟩+|1⟩)/√2——两个问题"同时在场"；辅助线过 H，调成 |−⟩（伏笔用）。二，黑箱 U_f 调用一次——f(0)、f(1) 的值经回踢写进两支箭头的符号：常数机，两支同号；平衡机，两支异号。三，输入线再过一次 H，干涉收网：

• 两支同号（常数）：它们本来是 0 与 1 各占一半的对称叠加，H 是自己的逆（021 篇），对称叠加被原路收回——|0⟩ 振幅相加、|1⟩ 振幅相消，测得 0，概率 100%；
• 两支异号（平衡）：同款的对称叠加，但其中一支被翻了符号——相消与相加的位置互换，|1⟩ 振幅合流，测得 1，概率 100%。

一次调用，一次测量，答案非 0 即 1，没有概率成分——这是 DJ 最反直觉的地方：不是"量子方法成功率更高"，是干涉把两种情形逼成了两个完全确定的结局。016 篇的交叉项（同向相长、反向相消）在这里不是解释工具，是算法的发动机本身。

它凭什么入史册

DJ 实用价值很小——谁家真有"承诺公平或作弊"的铸币机？它入史册靠两件事：

一，它是第一个严格证明"量子调用次数严格少于经典"的问题（一次对两次）。一次与两次听起来寒酸，但这是第一次有数学证明：某些任务上，量子黑箱调用次数必然更省——不是工程改进，是模型本身的差距。

二，套路即模板。回头看三步：H 铺开叠加（021 篇"一切算法的第一步"兑现）→ 黑箱信息写进相位（回踢）→ 干涉收网读全局性质。把"铺开"从 2 个输入换成上亿个、把"全局性质"从恒等换成周期、把一次 H 收网换成傅里叶变换收网——就是 Grover（033）、Simon（035）、Shor（037）。DJ 是量子算法的果蝇：构造简单到能解剖清楚，结构却与整个家族同源。030 篇的两条跑道现在就用得上：这个电路在免费模拟器上几秒跑完，值得亲手跑一遍。

把类比拆掉

铸币机类比借了哪里：

• 不像之一：抛硬币的"一次"可能撞运气，量子的"一次"是确定的——干涉把随机性完全挤干了；类比里"问"是记录观测，量子里"调用黑箱"本身已经在改写箭头（017 篇：换轴改变对象）。
• 不像之二："同时投两枚坯"的直觉不存在——黑箱只吃一个叠加输入，f(0) 与 f(1) 各自的值自始至终没有分别出炉；出炉的只有它们"同与不同"这一件事。类比负责"一次定公平"，别负责"一次读两值"。

带走的行李

1. 量子算法宪法：经典问 N 次、读 N 个值；量子一次调用、读一个全局性质——叠加让输入同场，干涉让性质显形。 2. 相位回踢：辅助线备 |−⟩，黑箱的答案变成输入箭头的符号——信息写进相位（019 隐形墨水上岗），测不到但干涉读得出。 3. DJ 模板：H 铺开 → 回踢 → 干涉收网；常数收向 |0⟩、平衡收向 |1⟩，概率 100%——Grover/Simon/Shor 全是这个模板的升级版。

下一站的钩子：DJ 读的是"1 比特的性质"（恒等与否）。要是黑箱里藏着一整串比特——比如 1011——量子一次能听出来吗？能，而且电路只比 DJ 多一步。032《听出隐藏的比特串：Bernstein-Vazirani》。

#量子计算 #从硬币到纠错 #DeutschJozsa #相位回踢