Deutsch-Jozsa 算法

课程目标：

1. 理解 D-J 算法要解决的问题，并分析其经典解法的复杂度。
2. 掌握量子预言机 (Quantum Oracle) 的概念及其核心技术——相位回踢 (Phase Kickback)。
3. 通过数学推导，一步步走通 D-J 算法的量子线路。
4. 从量子干涉的角度，理解 D-J 算法“为何”有效。
5. 将 D-J 算法置于计算复杂性理论的宏大背景中，理解 P, BPP 和 BQP 的区别。

1. 问题设定：一个关于“承诺”的问题

想象一下，你有一个“黑盒”函数 $f$，它接收一个 n-bit 的二进制串 $x \in \{0, 1\}^n$作为输入，并输出一个 1-bit 的结果 $f(x) \in \{0, 1\}$。

这个函数被承诺 (promised) 只有两种可能性之一：

1. 常数函数 (Constant)：对于所有的输入 x，输出都是相同的值（要么全是0，要么全是1）。
2. 平衡函数 (Balanced)：对于所有的输入 x，输出结果中恰好有一半是0，另一半是1。

任务：用最少的查询次数，判断这个函数 f 是常数函数还是平衡函数。

经典解法分析

• 确定性算法 (Deterministic):

  • 运气好的情况: 你查询了 $f(00...0)$ 得到 0，然后查询 $f(11...1)$ 得到 1。仅两次查询，你就知道函数不可能是常数，因此它一定是平衡的。
  • 运气最差的情况: 你查询了 $2^{n-1}$ 个不同的输入，发现它们的输出全是0。此时你仍然无法100%确定！因为函数可能是一个全0的常数函数，也可能是一个平衡函数，只是你恰好查询了所有输出为0的那一半输入。你必须再做一次查询，即第 $2^{n-1} + 1$ 次，才能做出最终判断。
  • 结论: 在最坏情况下，经典确定性算法需要 $2^{n-1} + 1$ 次查询。这是一个指数级的复杂度。

• 概率性算法 (Probabilistic):

  • 如果我们不要求100%确定呢？我们随机查询 k 个不同的输入。如果结果都一样，我们就有很高的把握猜测它是常数函数。例如，查询两次，如果 $f(x_1)=f(x_2)$，函数是常数的概率是 $1/2$，是平衡的概率是 $\approx 1/2$。查询三次都相同，函数是常数的可能性就更高。
  • 结论: 我们可以用一个很小的常数次查询，就以极高的概率做出正确判断。这属于 BPP 复杂度类，我们稍后会详细讨论。

而 D-J 算法的目标是：仅用一次查询，100%确定地解决这个问题。

2. 量子预言机 (Quantum Oracle)

为了在量子计算机上“查询”函数 f，我们需要一个量子门来代表这个黑盒。这个特殊的门就是预言机 (Oracle)，记作 $U_f$。

定义

预言机 $U_f$ 是一个酉变换，它作用于 $n+1$ 个量子比特上。前 n 个是数据寄存器 $|x\rangle$，最后1个是辅助寄存器 (ancilla) $|y\rangle$。其作用是：
$$ U_f |x\rangle_n |y\rangle_1 = |x\rangle_n |y \oplus f(x)\rangle_1 $$
其中 $\oplus$ 是异或运算（模2加法）。

• 它保持数据寄存器 $|x\rangle$ 不变。
• 它将函数值 $f(x)$ “异或”到辅助比特 $|y\rangle$ 上。

现实世界的类比：密码验证

想象一个密码验证系统，它就是一个黑盒。

• 输入 x: 你尝试的密码（一个比特串）。
• 函数 f(x): 内部的验证逻辑，例如 HASH(x) == STORED_HASH。如果密码正确，f(x)=1，否则 f(x)=0。
• 预言机 $U_f$: 就是这个完整的、封装好的验证硬件/软件。你不知道它的内部实现，你只能给它一个输入 x，然后看它对辅助比特 y 做了什么。我们的目标是在不“反编译”这个预言机的情况下，判断 f 的全局属性。

关键技巧：相位回踢 (Phase Kickback)

直接使用预言机似乎没什么特别。但如果我们巧妙地设置辅助比特的状态，就能产生惊人的效果。

我们将辅助比特 $|y\rangle$ 初始化为特殊状态 $|-\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$。
现在来看预言机的作用：
$ U_f |x\rangle |-\rangle = U_f |x\rangle \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle) = \frac{1}{\sqrt{2}} (U_f|x\rangle|0\rangle - U_f|x\rangle|1\rangle) $
根据定义，$U_f|x\rangle|0\rangle = |x\rangle|0 \oplus f(x)\rangle$ 和 $U_f|x\rangle|1\rangle = |x\rangle|1 \oplus f(x)\rangle$。

• Case 1: 如果 $f(x)=0$
  $ \frac{1}{\sqrt{2}} (|x\rangle|0\rangle - |x\rangle|1\rangle) = |x\rangle \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle) = |x\rangle|-\rangle $
• Case 2: 如果 $f(x)=1$
  $ \frac{1}{\sqrt{2}} (|x\rangle|1\rangle - |x\rangle|0\rangle) = -|x\rangle \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle) = -|x\rangle|-\rangle $

将两种情况合并，我们得到了一个极其优美的结果：
$$ U_f |x\rangle |-\rangle = (-1)^{f(x)} |x\rangle |-\rangle $$
这就是相位回踢：函数 $f(x)$ 的输出值（0或1）没有改变辅助比特的状态，而是作为一个相位因子（$(-1)^0=1$ 或 $(-1)^1=-1$）被“踢回”到了数据寄存器 $|x\rangle$ 上！我们成功地将函数信息编码成了量子态的相位。

3. D-J 算法线路与数学推导

D-J 算法的线路非常简洁和优雅：

让我们一步步跟踪量子态的演化：

1. Step 0: 初始化
   系统从 $n+1$ 个量子比特的基态开始：
   $ |\psi_0\rangle = |0\rangle^{\otimes n} |1\rangle $
2. Step 1: 创建叠加态
   对所有 $n+1$ 个量子比特应用 Hadamard 门：
   $ |\psi_1\rangle = (H^{\otimes n}|0\rangle^{\otimes n}) \otimes (H|1\rangle) $
   我们知道 $H|0\rangle = |+\rangle$ 和 $H|1\rangle = |-\rangle$。并且 $H^{\otimes n}|0\rangle^{\otimes n} = \frac{1}{\sqrt{2^n}}\sum_{x \in \{0,1\}^n} |x\rangle$。
   所以，
   $ |\psi_1\rangle = \left(\frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1} |x\rangle\right) \otimes |-\rangle $
   这就是量子并行性的体现：我们一次性创建了所有可能输入 x 的叠加。
3. Step 2: 查询预言机 (一次！)
   将 $|\psi_1\rangle$ 输入预言机 $U_f$。利用我们刚刚推导的相位回踢技巧：
   $ |\psi_2\rangle = U_f |\psi_1\rangle = \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1} U_f(|x\rangle |-\rangle) = \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1} (-1)^{f(x)}|x\rangle \otimes |-\rangle $
   所有函数 $f(x)$ 的值，现在都以相位的形式并行地加载到了叠加态上。
4. Step 3: 干涉
   我们再次对前 n 个数据比特应用 Hadamard 变换 $H^{\otimes n}$。辅助比特我们不再关心。
   $ |\psi_3\rangle = (H^{\otimes n} \otimes I) |\psi_2\rangle = \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1} (-1)^{f(x)} (H^{\otimes n}|x\rangle) \otimes |-\rangle $
   这里需要一个重要的恒等式：$H^{\otimes n}|x\rangle = \frac{1}{\sqrt{2^n}}\sum_{z \in \{0,1\}^n} (-1)^{x \cdot z} |z\rangle$，其中 $x \cdot z$ 是比特串的点积（按位相乘再模2加）。
   代入上式，我们得到一个双重求和：
   $ |\psi_3\rangle = \frac{1}{2^n} \sum_{x=0}^{2^n-1} \sum_{z=0}^{2^n-1} (-1)^{f(x) + x \cdot z} |z\rangle \otimes |-\rangle $
   这个表达式看起来很复杂，但我们只关心最终测量到 $|0\rangle^{\otimes n}$ 状态的概率，即 z=00...0 时的振幅。

4. 结果分析：量子干涉的力量

让我们来计算最终状态中，基态 $|0\rangle^{\otimes n}$ (即 $z=0$) 的振幅 A：
当 $z = |0...0\rangle$ 时，$x \cdot z = 0$。所以振幅为：
$$ A_{|0...0\rangle} = \frac{1}{2^n} \sum_{x=0}^{2^n-1} (-1)^{f(x)} $$

现在，分析我们关心的两种情况：

• Case 1: f 是常数函数

  • 如果 $f(x)=c$ 对所有 x 成立，那么求和项 $(-1)^{f(x)}$ 也是一个常数 $(-1)^c$。
  • $A_{|0...0\rangle} = \frac{1}{2^n} \sum_{x=0}^{2^n-1} (-1)^c = \frac{1}{2^n} \cdot 2^n \cdot (-1)^c = \pm 1$
  • 测量到 $|0\rangle^{\otimes n}$ 的概率是 $|A|^2 = 1$。
  • 物理意义: 所有 $2^n$ 条计算路径都以相同的相位（+1或-1）到达终点，发生了完全的相长干涉 (constructive interference)。

• Case 2: f 是平衡函数

  • 求和项 $\sum (-1)^{f(x)}$ 中，恰好有一半的项是 $(-1)^0=1$，另一半是 $(-1)^1=-1$。
  • $A_{|0...0\rangle} = \frac{1}{2^n} (2^{n-1} \cdot 1 + 2^{n-1} \cdot (-1)) = \frac{1}{2^n} (0) = 0$
  • 测量到 $|0\rangle^{\otimes n}$ 的概率是 $|A|^2 = 0$。
  • 物理意义: 来自不同计算路径的相位正好两两抵消，发生了完全的相消干涉 (destructive interference)。

算法结论：
在 Step 3 之后，我们对前 n 个量子比特进行测量：

• 如果测量结果是 00...0，我们 100% 确定函数是常数函数。
• 如果测量结果是任何其他值，我们 100% 确定函数是平衡函数。

我们只用了一次对预言机的调用，就确定性地解决了问题！

5. 宏大视角：P, BPP, 和 BQP

D-J 算法不仅是一个巧妙的技巧，它首次在理论上清晰地将量子计算与经典计算的疆界划分开。

• P (Polynomial time): 所有能被一个确定性经典计算机在多项式时间内解决的判定问题。
• BPP (Bounded-error Probabilistic Polynomial time): 所有能被一个概率性经典计算机在多项式时间内以有界错误率（例如，<1/3）解决的判定问题。BPP 被认为是经典计算机“实际能高效解决”问题的范围。
• BQP (Bounded-error Quantum Polynomial time): 所有能被一台量子计算机在多项式时间内以有界错误率解决的判定问题。

D-J 算法的启示：

1. D-J vs 确定性经典算法: D-J算法是指数级加速（1次 vs $O(2^n)$次）。这表明 P $\subsetneq$ BQP，即量子计算机可以高效解决一些经典确定性计算机无法高效解决的问题。
2. D-J vs 概率性经典算法: 正如我们之前分析的，经典概率算法只需要常数次查询就能以高概率解决D-J问题。这意味着D-J问题本身在BPP中。因此，D-J算法并没有证明 BQP 比 BPP 更强大。它展示的是量子计算机在保证100%正确率的前提下，相对于经典方法的巨大优势。

真正的分水岭（如Shor算法）会解决那些我们相信甚至不在BPP中的问题。

本课总结

• D-J 算法展示了量子计算机如何利用量子并行性一次性评估所有输入。
• 核心技巧相位回踢将函数信息编码到量子态的相位中，这是许多量子算法的通用工具。
• 算法的威力源于量子干涉：通过巧妙设计的 H-Uf-H 结构，使得对于不同类型的函数，计算路径会发生相长或相消干涉，将答案汇聚到一个可测量的确定性结果上。
• D-J 算法为 BQP 这一复杂度类的研究打开了大门，是探索量子计算能力边界的理论基石。