Deutsch-Jozsa 算法

Deutsch-Jozsa 算法

本词条要点：

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

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

想象我们有一个”黑盒”函数 $f$：它接收一个 $n$ 比特的二进制串 $x\in \{0,1{\}}^n$ 作为输入，并输出一个比特 $f(x)\in \{0,1\}$。

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

1. 常数函数 (Constant)：对于所有输入 $x$，输出都是同一个值（要么全是 0，要么全是 1）。
2. 平衡函数 (Balanced)：在全部 $2^n$ 个输入上，输出恰好一半是 0，另一半是 1。

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

经典解法分析

• 确定性算法 (Deterministic)：

  • 运气好的情况：我们查询 $f(00\cdots 0)$ 得到 0，再查询 $f(11\cdots 1)$ 得到 1。仅两次查询，我们就能断定函数不可能是常数，因此它一定是平衡的。
  • 运气最差的情况：我们查询了 $2^{n-1}$ 个不同的输入，发现输出全是 0。此时我们仍然无法做出最终判断：函数可能是全 0 的常数函数，也可能是一个平衡函数，而我们恰好查询完了所有输出为 0 的那一半输入。我们必须再做一次查询，即第 $2^{n-1}+1$ 次；这一次的输出决定了答案——若仍为 0，则函数是常数函数，否则是平衡函数。
  • 结论：在最坏情况下，经典确定性算法需要 $2^{n-1}+1$ 次查询。这是一个指数级的复杂度。

• 概率性算法 (Probabilistic)：

  • 如果我们不要求 100% 确定，就可以随机地查询 $k$ 个不同的输入；当所有查询结果一致时，我们猜测函数是常数函数。这个策略可能出错，而且出错只发生在 $f$ 实际上是平衡函数、而我们恰好”抽中了”取值相同的那一半输入的时候。若 $f$ 是平衡函数，$k$ 次随机查询结果全部一致的概率至多为 $2^{1-k}$（例如 $k=2$ 时，该概率的精确值为 $\frac{2^{n-1}-1}{2^n-1}\approx \frac{1}{2}$）。因此，采用”k 次全同则判为常数”的规则，错误概率不超过 $2^{-k}$（假设两种函数的先验概率各为 $\frac{1}{2}$）。
  • 结论：我们只需常数次查询，就能以任意接近 1 的概率做出正确判断。要达到错误率 $\epsilon$，取 $k=O(\log \frac{1}{\epsilon })$ 即可。这类算法属于 BPP 复杂度类，我们在第 5 节详细讨论。

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

---

2. 量子预言机 (Quantum Oracle)

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

定义

预言机 $U_f$ 是一个酉变换，它作用于 $n+1$ 个量子比特上：前 $n$ 个是数据寄存器 $|x⟩$，最后 1 个是辅助寄存器 (ancilla) $|y⟩$。其作用是

$U_f|x{⟩}_n|y{⟩}_1=|x{⟩}_n|y\oplus f(x){⟩}_1,$

其中 $\oplus$ 是异或运算（模 2 加法）。

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

由于模 2 加法可逆（两次异或同一个 $f(x)$ 相互抵消），我们有 $U_f{U}_f=I$，因此 $U_f$ 是酉算子，可以合法地出现在量子线路中。

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

我们可以把预言机想象成一个密码验证系统，它就是一个黑盒。

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

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

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

我们将辅助比特 $|y⟩$ 初始化为特殊状态 $|-⟩=\frac{1}{\sqrt{2}}(|0⟩-|1⟩)$。现在来追踪预言机的作用。由线性性，我们可以让 $U_f$ 分别作用在两个分支上：

$U_f|x⟩|-⟩=\frac{1}{\sqrt{2}}\left(U_f|x⟩|0⟩-U_f|x⟩|1⟩\right).$

根据定义，$U_f|x⟩|0⟩=|x⟩|0\oplus f(x)⟩$，$U_f|x⟩|1⟩=|x⟩|1\oplus f(x)⟩$。我们分两种情况讨论。

• Case 1: $f(x)=0$。此时 $0\oplus f(x)=0$、$1\oplus f(x)=1$，两个分支都不变：

$\frac{1}{\sqrt{2}}(|x⟩|0⟩-|x⟩|1⟩)=|x⟩\frac{1}{\sqrt{2}}(|0⟩-|1⟩)=|x⟩|-⟩.$

• Case 2: $f(x)=1$。此时 $0\oplus f(x)=1$、$1\oplus f(x)=0$，两个分支互换：

$\frac{1}{\sqrt{2}}(|x⟩|1⟩-|x⟩|0⟩)=-|x⟩\frac{1}{\sqrt{2}}(|0⟩-|1⟩)=-|x⟩|-⟩.$

把两种情况合并，我们得到一个优美的结果：

$U_f|x⟩|-⟩=(-1{)}^{f(x)}|x⟩|-⟩.$

这就是相位回踢：函数值 $f(x)$ 没有改变辅助比特的状态，而是作为一个相位因子（$(-1{)}^0=1$ 或 $(-1{)}^1=-1$）被”踢回”到了数据寄存器的分量 $|x⟩$ 上。我们成功地把函数信息编码成了量子态的相位。

---

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

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

下面我们把每一步的量子态显式地写出来。为了帮助读者核对推导，我们在本节末尾还会用一个 $n=2$ 的具体例子，把每一步的振幅逐一算出。

1. Step 0: 初始化

   系统从 $n+1$ 个量子比特的基态开始：

   $|{\psi }_0⟩=|0{⟩}^{\otimes n}|1⟩.$

2. Step 1: 创建叠加态

   我们对所有 $n+1$ 个量子比特应用 Hadamard 门。利用 $H|0⟩=|+⟩=\frac{1}{\sqrt{2}}(|0⟩+|1⟩)$、$H|1⟩=|-⟩$，并且逐比特张量起来得到 $H^{\otimes n}|0{⟩}^{\otimes n}=\frac{1}{\sqrt{2^n}}{\sum }_{x\in \{0,1{\}}^n}|x⟩$，于是

   $|{\psi }_1⟩=\left(H^{\otimes n}|0{⟩}^{\otimes n}\right)\otimes \left(H|1⟩\right)=\left(\frac{1}{\sqrt{2^n}}{\sum }_{x\in \{0,1{\}}^n}|x⟩\right)\otimes |-⟩.$

   这就是**量子并行性 (quantum parallelism)** 的体现：我们一次性创建了所有可能输入 $x$ 的叠加。

3. Step 2: 查询预言机（一次！）

   我们将 $|{\psi }_1⟩$ 输入预言机 $U_f$，并利用刚刚推导的相位回踢：

   $|{\psi }_2⟩=U_f|{\psi }_1⟩=\frac{1}{\sqrt{2^n}}{\sum }_{x\in \{0,1{\}}^n}(-1{)}^{f(x)}|x⟩\otimes |-⟩.$

   所有输入上的函数值 $f(x)$，现在都以相位的形式并行地加载到了叠加态上。

4. Step 3: 干涉

   我们再次对前 $n$ 个数据比特应用 Hadamard 变换 $H^{\otimes n}$；辅助比特此后不再关心。这一步需要一个重要的恒等式：

   $H^{\otimes n}|x⟩=\frac{1}{\sqrt{2^n}}{\sum }_{z\in \{0,1{\}}^n}(-1{)}^{x\cdot z}|z⟩,$

   其中 $x\cdot z=(x_1{z}_1+x_2{z}_2+\cdots +x_n{z}_n)\mathrm{mod}2$ 是比特串的按位点积（模 2）。

   恒等式的推导。先看单比特。把 Hadamard 门在两个基矢上的作用统一写成

   $H|x⟩=\frac{1}{\sqrt{2}}{\sum }_{z\in \{0,1\}}(-1{)}^{x\cdot z}|z⟩,x\in \{0,1\}.$

   这一项公式覆盖了两种情形：当 $x=0$ 时 $x\cdot z=0$ 对所有 $z$ 成立，两个相位都是 $+1$，给出 $H|0⟩=\frac{1}{\sqrt{2}}(|0⟩+|1⟩)$；当 $x=1$ 时 $x\cdot z=z$，$z=1$ 的分支带负号，给出 $H|1⟩=\frac{1}{\sqrt{2}}(|0⟩-|1⟩)$。对 $n$ 比特，Hadamard 变换逐位作用：

   $H^{\otimes n}|x⟩=H|x_1⟩\otimes H|x_2⟩\otimes \cdots \otimes H|x_n⟩={⨂}_{i=1}^n\left[\frac{1}{\sqrt{2}}{\sum }_{z_i\in \{0,1\}}(-1{)}^{x_i{z}_i}|z_i⟩\right].$

   展开右端的张量积时，每个比特独立地选定一个 $z_i\in \{0,1\}$；$n$ 个比特的选法组合起来恰好遍历所有 $z=z_1{z}_2\cdots z_n\in \{0,1{\}}^n$，而相位因子与系数分别相乘：

   $H^{\otimes n}|x⟩=\frac{1}{\sqrt{2^n}}{\sum }_{z\in \{0,1{\}}^n}(-1{)}^{x_1{z}_1}(-1{)}^{x_2{z}_2}\cdots (-1{)}^{x_n{z}_n}|z⟩=\frac{1}{\sqrt{2^n}}{\sum }_{z\in \{0,1{\}}^n}(-1{)}^{x\cdot z}|z⟩,$

   其中把 $n$ 个相位因子合并成 $(-1{)}^{x\cdot z}$ 时用了指数按模 2 相加。推导完毕。

   把恒等式代入 Step 2 的态，我们得到一个双重求和：

   $|{\psi }_3⟩=(H^{\otimes n}\otimes I)|{\psi }_2⟩=\frac{1}{2^n}{\sum }_{x\in \{0,1{\}}^n}{\sum }_{z\in \{0,1{\}}^n}(-1{)}^{f(x)\oplus x\cdot z}|z⟩\otimes |-⟩.$

   这个表达式看起来很复杂，但我们只关心最终测量到 $|0{⟩}^{\otimes n}$ 的概率，也就是 $z=00\cdots 0$ 那一项的振幅。

例子：n = 2 的完整数值走查

取 $n=2$，数据寄存器有 4 个基矢 $|00⟩,|01⟩,|10⟩,|11⟩$（下面把比特串与它表示的整数混用）。我们对一个常数 Oracle 和一个平衡 Oracle 分别把每一步的振幅都算出来。

例 1：常数函数 $f\equiv 0$。

• Step 0：$|{\psi }_0⟩=|00⟩\otimes |1⟩$。
• Step 1：三个 Hadamard 之后，数据寄存器的四个振幅都是 $\frac{1}{2}$：

$|{\psi }_1⟩=\frac{1}{2}\left(|00⟩+|01⟩+|10⟩+|11⟩\right)\otimes \frac{|0⟩-|1⟩}{\sqrt{2}}.$

• Step 2：相位回踢给每一项乘上 $(-1{)}^{f(x)}=(-1{)}^0=+1$，量子态保持不变。
• Step 3：注意到 $\frac{1}{2}{\sum }_x|x⟩$ 恰好就是 $H^{\otimes 2}|00⟩$，而 $H^{\otimes 2}\cdot H^{\otimes 2}=I$，所以数据寄存器精确地回到 $|00⟩$：

$|{\psi }_3⟩=|00⟩\otimes |-⟩.$

我们以概率 1 测得 $00$，判定：常数函数。（若 $f\equiv 1$，Step 2 会给整个态乘上 $-1$；这是一个全局相位，测量结果与 $f\equiv 0$ 完全相同。）

例 2：平衡函数 $f(x_1{x}_2)=x_1$，即 $f(00)=f(01)=0$、$f(10)=f(11)=1$。

• Step 1 与例 1 相同。
• Step 2：相位回踢使后两项变号：

$|{\psi }_2⟩=\frac{1}{2}\left(|00⟩+|01⟩-|10⟩-|11⟩\right)\otimes |-⟩.$

• Step 3：对四个基矢分别应用恒等式 $H^{\otimes 2}|x⟩=\frac{1}{2}{\sum }_z(-1{)}^{x\cdot z}|z⟩$（$z$ 从左到右按 $00,01,10,11$ 排列）：

$$\begin{array}{rl}{H}^{\otimes 2}|00⟩& =\frac{1}{2}\left(|00⟩+|01⟩+|10⟩+|11⟩\right),\\ H^{\otimes 2}|01⟩& =\frac{1}{2}\left(|00⟩-|01⟩+|10⟩-|11⟩\right),\\ H^{\otimes 2}|10⟩& =\frac{1}{2}\left(|00⟩+|01⟩-|10⟩-|11⟩\right),\\ H^{\otimes 2}|11⟩& =\frac{1}{2}\left(|00⟩-|01⟩-|10⟩+|11⟩\right).\end{array}$$

把它们按系数 $\frac{1}{2}(+1,+1,-1,-1)$（对应 $x=00,01,10,11$）加权求和，逐个基矢归并同类项，得到四个振幅：

• $|00⟩$：$\frac{1}{4}(1+1-1-1)=0$；
• $|01⟩$：$\frac{1}{4}(1-1-1+1)=0$；
• $|10⟩$：$\frac{1}{4}(1+1+1+1)=1$；
• $|11⟩$：$\frac{1}{4}(1-1+1-1)=0$。

因此 $|{\psi }_3⟩=|10⟩\otimes |-⟩$：我们以概率 1 测得 $10$。由于 $10\ne 00$，我们判定：平衡函数。

注意振幅的消长与干涉的对应：$|00⟩$ 的四条计算路径两两正负抵消（相消干涉），而 $|10⟩$ 的四条路径贡献全为正（相长干涉）。这正是下一节分析的一般现象在 $n=2$ 下的具体体现。

---

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

我们来计算最终态中基矢 $|0{⟩}^{\otimes n}$（即 $z=00\cdots 0$）的振幅 $A$。当 $z=0$ 时，$x\cdot z=0$ 对所有 $x$ 成立，相位因子化为 $(-1{)}^{f(x)}$，于是双重求和中只剩下对 $x$ 的一重求和：

$A_{|0\cdots 0⟩}=\frac{1}{2^n}{\sum }_{x\in \{0,1{\}}^n}(-1{)}^{f(x)}.$

现在我们分析承诺的两种情况。

• Case 1: $f$ 是常数函数

  • 如果 $f(x)=c$ 对所有 $x$ 成立（$c$ 为 0 或 1），那么每一项 $(-1{)}^{f(x)}$ 都等于同一个常数 $(-1{)}^c$，求和就是 $2^n$ 个相同数的和：

$A_{|0\cdots 0⟩}=\frac{1}{2^n}\cdot 2^n\cdot (-1{)}^c=(-1{)}^c=\pm 1.$

• 测量到 $|0{⟩}^{\otimes n}$ 的概率是 $|A{|}^2=1$。

• 物理意义：所有 $2^n$ 条计算路径都以相同的相位（$+1$ 或 $-1$）到达终点，发生了完全的相长干涉 (constructive interference)。

• Case 2: $f$ 是平衡函数

  • 求和 ${\sum }_x(-1{)}^{f(x)}$ 中，恰好一半的项来自 $f(x)=0$、取值 $+1$，另一半来自 $f(x)=1$、取值 $-1$：

$A_{|0\cdots 0⟩}=\frac{1}{2^n}\left(2^{n-1}\cdot 1+2^{n-1}\cdot (-1)\right)=\frac{1}{2^n}\cdot 0=0.$

• 测量到 $|0{⟩}^{\otimes n}$ 的概率是 $|A{|}^2=0$。
• 物理意义：来自不同计算路径的相位正好两两抵消，发生了完全的相消干涉 (destructive interference)。

算法结论：

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

• 如果测量结果是 $00\cdots 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 次查询解决了确定性经典算法最坏情况下需要 $2^{n-1}+1$ 次查询的问题，这是查询次数上的指数级分离。需要强调的是，这是**查询复杂度模型**下的分离；就复杂度类而言，我们知道 $P\subseteq BPP\subseteq BQP$，但这些包含关系是否严格仍是开放问题，所以 D-J 算法本身并不能证明 $P⊊BQP$。它真正展示的是：在保证 100% 正确率的前提下，量子方法相对于确定性经典方法的巨大优势。
2. D-J vs 概率性经典算法：正如我们之前分析的，经典概率算法只需常数次查询就能以高概率解决 D-J 问题。这意味着 D-J 问题本身在 BPP 中。因此，D-J 算法并没有证明 BQP 比 BPP 更强大。

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

本词条总结

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

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch03-algo-basics/deutsch-jozsa
• 内容遵循 CC BY-NC-SA 4.0 许可协议