Deutsch–Jozsa 与相位回踢：第一个加速算法

一句话定义

Deutsch–Jozsa（DJ）问题承诺一个 n 位布尔函数 f 要么常值（恒 0 或恒 1）要么平衡（一半输入给 1），量子算法只需一次查询 f 即可判定，而确定性经典算法最坏需要 2ⁿ⁻¹+1 次。

为什么重要

历史上第一个有严格分离证明的量子算法，它把两件工具传给了整个领域：黑箱查询模型（把函数封装成可调用的"预言机"门）与相位回踢——把函数值写进相位而不破坏叠加的技巧。此后几乎所有知名算法（QFT、Shor、Grover、相位估计）都建立在这两块基石上。同时 DJ 也是一堂诚实的课：它的"加速"只在承诺问题与确定性经典基线下成立，随机经典算法期望两次查询即可——如何解读这类加速，本节末尾直面。

前置知识

kp-010（H 门与矩阵效果）、kp-011（CNOT 真值表）。推导只用到向量乘法与 H 的两次作用，全程可手算。

核心概念

• 预言机（oracle）：把 f 装进酉门 U_f|x⟩|y⟩ = |x⟩|y⊕f(x)⟩，把它当"可调用但不可拆开"的黑箱。
• 相位回踢：把目标位制备成 |−⟩ 后，U_f 等价于给 |x⟩ 乘 (−1)^f(x)——函数值从"结果位"转移到了"相位"。
• 干涉读出：回踢后的 n 位叠加再过一遍 H^⊗n，常值函数的振幅全部同相叠加到 |0…0⟩，平衡函数在 |0…0⟩ 的振幅恰好相消为零。
• 判定规则：测得全 0 → 常值；否则 → 平衡。一次查询，确定性输出。

直观类比

经典的你在图书馆查一本书"每页是否都盖了章"，只能一页页翻（最坏翻半本）；DJ 的量子读者则把所有页同时放进一个"相位复印机"——盖章与否只改变每页的墨迹深浅符号，然后一次显影就让"全盖/半盖"直接显形成一句话。关键在两步：信息进入相位（不是读出来的数字），再由干涉把相位差翻译成可读的概率分布。

原理与机制

完整推导（单比特版即 Deutsch 问题）。制备：|0⟩|−⟩，对查询位加 H 得 |0⟩+|1⟩√2|−⟩。回踢：U_f 作用于叠加，展开按 kp-011 的真值表逐项计算——U_f(|x⟩|−⟩) = |x⟩(|f(x)⟩−|1⊕f(x)⟩√2) = (−1)^f(x)|x⟩|−⟩：目标位不变（仍是 |−⟩），查询位获得相位 (−1)^f(x)。干涉：查询位已是 α₀=±1/√2、α₁=±1/√2 的叠加，再过 H：测 0 的振幅 = (α₀+α₁)/√2。常值函数两振幅同号，测 0 概率 1；平衡函数异号，测 0 概率 0。n 位推广完全平行：n 位 H 制造全部 2ⁿ 个输入的均匀叠加，回踢写入全部 (−1)^f(x)，末端的 H^⊗n 让 |0…0⟩ 振幅等于 12ⁿΣ_x(−1)^f(x)——常值时求和为 ±1，平衡时（承诺下）严格为零。一次查询，确定性判别。

公式或模型

相位回踢恒等式：U_f |x⟩|−⟩ = (−1)^f(x)|x⟩|−⟩。
末态 |0…0⟩ 振幅：a = 12ⁿ Σ_x (−1)^f(x)；P(全0) = |a|² ∈ {1, 0}（承诺下）。
经典下界：确定性算法最坏 2ⁿ⁻¹+1 次查询；随机算法期望约 2 次——量子优势是相对确定性基线的"1 次 vs 指数次"。

图示

实例或案例

用 n=2 手算一个平衡函数 f(x)=x₀⊕x₁：回踢后振幅按 00→+、01→+、10→−、11→− 分布；末端 H^⊗2 后 |00⟩ 振幅 = ¼(1+1−1−1)=0，测得全 0 的概率为 0 → 判定"平衡"。把 f 换成常值 1：振幅全为 −1，|00⟩ 振幅 = −1，P=1。kp-030 的平台上有一个现成的 DJ 教程，两行代码改 f 即可复现。

与其他知识点的关系

kp-003 的干涉总纲在此第一次落地；kp-016 的 QFT 与 kp-017 的 Shor 复用"叠加→黑箱写相位→傅里叶/干涉读出"的三段式；kp-018 的 Grover 是相位回踢的迭代版；kp-033 会重新评估 DJ 的"实际意义"。

常见误区

• "DJ 证明量子计算机全面碾压经典"：只针对带承诺的特定问题、且相对确定性经典算法；去掉承诺或允许随机化，经典只需常数次查询。
• "一次查询=更少的计算"：黑箱模型计数的是"打开黑箱的次数"；把 U_f 完整实现的门成本（与 f 的电路规模相关）不计入该模型——解读加速时要先对齐计数口径。
• "相位回踢是 DJ 独有的技巧"：它是整个量子算法领域的通用引擎，DJ 只是第一个使用者。

自测题

1. 写出 f 为常值 0 时 DJ 线路的完整态演化。

答案要点：回踢后仍为均匀叠加（全部 +1），末端 H^⊗n 把全部振幅聚到 |0…0⟩，P=1。

2. 为什么目标位必须制备成 |−⟩ 而不是 |0⟩ 或 |+⟩？

答案要点：|0⟩ 会被 U_f 改写为 |f(x)⟩（复制函数值到基态，破坏查询位叠加）；|+⟩ 无确定相位回踢关系；|−⟩ 恰好使异或输出等价于 (−1)^{f(x)} 相位。

3. 若去掉"常值或平衡"承诺，DJ 算法还能给出确定性判定吗？

答案要点：不能；一般函数下 P(全0) 取中间值，只能给出统计信息——承诺是算法成立的前提。

延伸阅读

Deutsch & Jozsa (1992) 原始论文；N. D. Mermin《Quantum Computer Science》第 2 章（对黑箱模型与下界的谨慎讨论）。