3. Deutsch-Jozsa与Bernstein-Vazirani算法
Deutsch-Jozsa（DJ）与 Bernstein-Vazirani（BV）是量子查询复杂度的两个奠基性算法。它们并不解决实际工程问题，却精确展示了量子并行性如何把“需要多次查询”变成“一次查询即可判定”。理解这两个算法，关键不是记住电路符号，而是看清它们各自的问题定义、判定目标，以及为什么经典算法必须付出指数或线性代价。
问题定义：两种不同的“黑箱”
两个算法都围绕一个未知布尔函数 f: {0,1}^n → {0,1} 展开，但承诺条件不同。
Deutsch-Jozsa 问题：给定 f，并承诺它要么是常函数（对所有输入都返回 0，或都返回 1），要么是平衡函数（恰好一半输入返回 0，一半返回 1）。目标是判定 f 属于哪一类。经典确定性算法最坏情况下需要查询 2^(n-1)+1 次才能确定；量子算法只需 1 次查询。
Bernstein-Vazirani 问题：给定 f(x) = a·x mod 2，其中 a 是未知的 n 位串，a·x 表示按位与后模 2 求和（即内积的奇偶性）。目标是求出隐藏串 a。经典算法需要 n 次查询（每次取 x = e_i 得到第 i 位），量子算法同样只需 1 次查询。
两者的共同点是都使用“相位回踢”（phase kickback）机制：把函数值写入辅助位，再通过 Hadamard 变换把函数值转化为相位信息，最后在输入寄存器上读出结果。
量子电路构造
两个算法共享同一套电路骨架，区别只在最后的测量与解释方式。
电路包含两个寄存器：n 位输入寄存器（初始为 |0⟩^⊗n）和 1 位辅助寄存器（初始为 |1⟩）。步骤如下：
- 对输入寄存器的每一位施加 H 门，得到均匀叠加态
(1/√2^n) Σ_x |x⟩。 - 对辅助位施加 H 门，得到
|−⟩ = (|0⟩−|1⟩)/√2。 - 施加查询门
U_f: |x,y⟩ → |x, y ⊕ f(x)⟩。由于辅助位处于|−⟩，函数值被“回踢”为相位：|x⟩ → (−1)^{f(x)} |x⟩。 - 再次对输入寄存器施加 H 门。
- 测量输入寄存器。
第 4 步是核心。对 DJ 问题，若 f 为常函数，所有相位相同，H 变换后输入寄存器回到 |0⟩^⊗n；若 f 为平衡函数，正负相位相消，测量结果一定不是全零。因此“测量结果是否全为 0”就是判定依据。
对 BV 问题，第 4 步后输入寄存器的状态恰好是 |a⟩。也就是说，一次查询后直接测量就能读出隐藏串 a，无需任何后处理。
确定性判定与概率性判定
DJ 算法的量子版本是确定性的：测量结果全为 0 当且仅当 f 是常函数，不存在错误概率。这一点常被误解——量子算法并非天然概率性，DJ 的判定是精确的。
但若把 DJ 问题放宽为“允许小概率错误”，经典随机算法只需常数次查询：随机取几个 x，若发现 f(x) 既有 0 又有 1，即可判定为平衡函数；若连续 k 次都得到相同值，则以 2^(1−k) 的概率误判为常函数。这说明 DJ 的量子优势是相对于确定性经典算法的指数加速，而非相对于随机算法。
BV 算法同样是确定性的：测量结果就是 a，无需重复运行。它的优势是查询次数的线性加速（n → 1），在 n 较大时意义显著。
U_f 不改变辅助位，却把 f(x) 以 (−1)^f(x) 的形式“踢”回输入寄存器的相位上。这是所有基于查询的量子算法的共同技巧。复杂度对比与实验模拟
下表汇总两个算法在查询复杂度上的差异。注意“查询次数”指调用黑箱 U_f 的次数，不包含 H 门等基本门开销。
| 算法 | 经典确定性 | 经典随机 | 量子 | 加速类型 |
|---|---|---|---|---|
| Deutsch-Jozsa | 2^(n−1)+1 | O(1)（有误差） | 1 | 指数（对确定性） |
| Bernstein-Vazirani | n | n | 1 | 线性 |
在实验模拟中，可以用 Qiskit 构造这两个电路。以 BV 为例，n=3、隐藏串 a = 101 时，查询门可用 CNOT 实现：对 a 中为 1 的每一位，将该输入位作为控制、辅助位作为目标施加 CNOT。运行 1024 次后，测量结果应全部为 101，直方图只有一根柱。
from qiskit import QuantumCircuit, Aer, execute
n = 3
a = '101'
qc = QuantumCircuit(n + 1, n)
qc.x(n) # 辅助位置 |1⟩
qc.h(range(n + 1)) # 全部 H
for i, bit in enumerate(reversed(a)):
if bit == '1':
qc.cx(i, n) # 实现 a·x mod 2
qc.h(range(n)) # 输入寄存器再 H
qc.measure(range(n), range(n))
backend = Aer.get_backend('qasm_simulator')
result = execute(qc, backend, shots=1024).result()
print(result.get_counts()) # 预期 {'101': 1024}
对 DJ 问题，查询门需要根据 f 的真值表构造。以 n=2 的平衡函数 f(00)=0, f(01)=1, f(10)=1, f(11)=0 为例，可用 CNOT 与 X 门组合实现。运行后测量结果只会是 01、10、11 之一，绝不会出现 00，从而判定为平衡函数。
这两个算法的教学价值在于：它们把“量子并行性 + 相位回踢 + Hadamard 干涉”这条主线压缩到最小可运行规模。掌握 DJ 与 BV 的电路后，再理解 Simon 算法、Grover 搜索和 Shor 算法时，就能识别出相同的结构复用。