# 量子算法基础1：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\cdots0)$ 得到 0，再查询 $f(11\cdots1)$ 得到 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}$（假设两种函数的先验概率各为 $\frac12$）。
  - **结论**：我们只需常数次查询，就能以任意接近 1 的概率做出正确判断。要达到错误率 $\varepsilon$，取 $k = O(\log\frac{1}{\varepsilon})$ 即可。这类算法属于 **BPP** 复杂度类，我们在第 5 节详细讨论。

而 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$ 上。

由于模 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\rangle$ 初始化为特殊状态 $|-\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$。现在来追踪预言机的作用。由线性性，我们可以让 $U_f$ 分别作用在两个分支上：

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

根据定义，$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$**。此时 $0 \oplus f(x) = 0$、$1 \oplus f(x) = 1$，两个分支都不变：

$$ \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$**。此时 $0 \oplus f(x) = 1$、$1 \oplus f(x) = 0$，两个分支互换：

$$ \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)$ 没有改变辅助比特的状态，而是作为一个**相位因子**（$(-1)^0=1$ 或 $(-1)^1=-1$）被"踢回"到了数据寄存器的分量 $|x\rangle$ 上。我们成功地把函数信息编码成了量子态的相位。

------------------------------------------------------------------------

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

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

[![](https://upload.wikimedia.org/wikipedia/commons/thumb/1/18/Deutsch-Jozsa_algorithm.svg/500px-Deutsch-Jozsa_algorithm.svg.png "量子算法基础1：Deutsch-Jozsa算法")](https://upload.wikimedia.org/wikipedia/commons/thumb/1/18/Deutsch-Jozsa_algorithm.svg/500px-Deutsch-Jozsa_algorithm.svg.png "点击放大图片")

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

1.  **Step 0: 初始化**

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

    $$ |\psi_0\rangle = |0\rangle^{\otimes n} |1\rangle. $$

2.  **Step 1: 创建叠加态**

    我们对所有 $n+1$ 个量子比特应用 Hadamard 门。利用 $H|0\rangle = |+\rangle = \frac{1}{\sqrt{2}}(|0\rangle+|1\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(H^{\otimes n}|0\rangle^{\otimes n}\right) \otimes \left(H|1\rangle\right) = \left(\frac{1}{\sqrt{2^n}}\sum_{x \in \{0,1\}^n} |x\rangle\right) \otimes |-\rangle. $$

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

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

    我们将 $|\psi_1\rangle$ 输入预言机 $U_f$，并利用刚刚推导的相位回踢：

    $$ |\psi_2\rangle = U_f |\psi_1\rangle = \frac{1}{\sqrt{2^n}}\sum_{x \in \{0,1\}^n} (-1)^{f(x)}|x\rangle \otimes |-\rangle. $$

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

4.  **Step 3: 干涉**

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

    $$ 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 = (x_1 z_1 + x_2 z_2 + \cdots + x_n z_n) \bmod 2$ 是比特串的按位点积（模 2）。

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

    $$ H|x\rangle = \frac{1}{\sqrt{2}}\sum_{z \in \{0,1\}} (-1)^{x\cdot z}|z\rangle, \qquad x \in \{0,1\}. $$

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

    $$ H^{\otimes n}|x\rangle = H|x_1\rangle \otimes H|x_2\rangle \otimes \cdots \otimes H|x_n\rangle = \bigotimes_{i=1}^n \left[\frac{1}{\sqrt{2}}\sum_{z_i \in \{0,1\}} (-1)^{x_i z_i}|z_i\rangle\right]. $$

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

    $$ H^{\otimes n}|x\rangle = \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\rangle = \frac{1}{\sqrt{2^n}} \sum_{z \in \{0,1\}^n} (-1)^{x \cdot z} |z\rangle, $$

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

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

    $$ |\psi_3\rangle = (H^{\otimes n} \otimes I) |\psi_2\rangle = \frac{1}{2^n} \sum_{x \in \{0,1\}^n} \sum_{z \in \{0,1\}^n} (-1)^{f(x) \oplus x \cdot z} |z\rangle \otimes |-\rangle. $$

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

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

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

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

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

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

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

$$ |\psi_3\rangle = |00\rangle \otimes |-\rangle. $$

  我们以概率 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\rangle = \frac{1}{2}\left(|00\rangle + |01\rangle - |10\rangle - |11\rangle\right) \otimes |-\rangle. $$

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

$$
\begin{aligned}
H^{\otimes 2}|00\rangle &= \tfrac{1}{2}\left(|00\rangle + |01\rangle + |10\rangle + |11\rangle\right),\\
H^{\otimes 2}|01\rangle &= \tfrac{1}{2}\left(|00\rangle - |01\rangle + |10\rangle - |11\rangle\right),\\
H^{\otimes 2}|10\rangle &= \tfrac{1}{2}\left(|00\rangle + |01\rangle - |10\rangle - |11\rangle\right),\\
H^{\otimes 2}|11\rangle &= \tfrac{1}{2}\left(|00\rangle - |01\rangle - |10\rangle + |11\rangle\right).
\end{aligned}
$$

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

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

  因此 $|\psi_3\rangle = |10\rangle \otimes |-\rangle$：我们以概率 1 测得 $10$。由于 $10 \neq 00$，我们判定：平衡函数。

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

------------------------------------------------------------------------

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

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

$$ A_{|0\cdots0\rangle} = \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\cdots0\rangle} = \frac{1}{2^n} \cdot 2^n \cdot (-1)^c = (-1)^c = \pm 1. $$

  - 测量到 $|0\rangle^{\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\cdots0\rangle} = \frac{1}{2^n} \left(2^{n-1} \cdot 1 + 2^{n-1} \cdot (-1)\right) = \frac{1}{2^n} \cdot 0 = 0. $$

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

**算法结论：**

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

- 如果测量结果是 $00\cdots0$，我们 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 \subsetneq 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** 这一复杂度类的研究打开了大门，是探索量子计算能力边界的理论基石。