# Deutsch-Jozsa · 一次查询判定性质

> 历史上第一个证明「量子能指数级超越经典」的算法。给定一个函数，只承诺它「要么恒定、要么对半」，判断是哪种——经典最坏要查指数次，量子只要一次。这一章用代码跑通它，并讲清干涉如何让答案确定地浮现。

- 作者：David（道雾轩）
- 专栏：写给程序员的量子计算（https://daiw.org/manual/quantum-computing.md）
- 最后更新：2026-07-14
- 原文：https://daiw.org/manual/quantum-computing/deutsch-jozsa
- 转载与引用：请注明出处并附原文链接（https://daiw.org/about/copyright）

# Deutsch-Jozsa · 一次查询判定性质

现在把前面所有零件——[叠加](https://daiw.org/manual/quantum-computing/superposition)、[干涉](https://daiw.org/manual/quantum-computing/superposition)、[预言机与相位反冲](https://daiw.org/manual/quantum-computing/oracle)——拼成第一个真正的量子算法。**Deutsch-Jozsa** 是历史上第一个证明「量子能指数级超越经典」的例子，虽然问题有点人造，但它把量子算法的套路展示得淋漓尽致。

## 问题

给你一个函数 $f:\{0,1\}^n \to \{0,1\}$，并**承诺**它必是以下两种之一：

- **恒定(constant)**：对所有输入都输出同一个值（全 0，或全 1）。
- **对半(balanced)**：恰好一半输入输出 0，另一半输出 1。

**任务：判断 $f$ 是恒定还是对半。**（承诺它只可能是这两种，不会是别的。）

**经典要查几次？** 最坏情况下，你得查到 $2^{n-1}+1$ 次——查了一半的输入都还一样，才敢断定它是恒定（万一第 $2^{n-1}+1$ 个不一样呢）。随 $n$ **指数增长**。

**量子要查几次？** ——**一次。**

## 线路

Deutsch-Jozsa 的线路是那个熟悉的「H → 预言机 → H」三明治：

```mermaid
flowchart LR
  A["输入 n 个 qubit: |0…0⟩<br/>辅助 qubit: |1⟩"] --> B["全部过 H<br/>输入→均匀叠加, 辅助→|−⟩"]
  B --> C["预言机 U_f<br/>(相位反冲盖 (-1)^f(x))"]
  C --> D["输入再过 H"]
  D --> E["测量输入<br/>全 0 → 恒定; 否则 → 对半"]
```

## 跑通它

```python
from qiskit import QuantumCircuit, transpile
from qiskit_aer import AerSimulator

def deutsch_jozsa(oracle, n):
    qc = QuantumCircuit(n + 1, n)
    qc.x(n)                       # 辅助 qubit → |1⟩
    qc.h(range(n + 1))            # 全部 H:输入→叠加,辅助→|−⟩
    qc.compose(oracle, inplace=True)   # 预言机
    qc.h(range(n))               # 输入再过 H
    qc.measure(range(n), range(n))
    sim = AerSimulator()
    return sim.run(transpile(qc, sim), shots=1000).result().get_counts()

n = 3
# 恒定预言机 f(x)=0:什么都不做
const_oracle = QuantumCircuit(n + 1)

# 对半预言机 f(x)=x0⊕x1⊕x2(奇偶):每个输入都 CX 到辅助位
bal_oracle = QuantumCircuit(n + 1)
for q in range(n):
    bal_oracle.cx(q, n)

print("恒定:", deutsch_jozsa(const_oracle, n))
print("对半:", deutsch_jozsa(bal_oracle, n))
```

```text
恒定: {'000': 1000}
对半: {'111': 1000}
```

**判据一目了然：测到全 0(`000`)就是恒定，测到任何非全 0 就是对半。** 而这个结论，量子只跑了**一次**预言机就得到了——经典最坏要 $2^{n-1}+1=5$ 次。$n$ 越大，差距越悬殊。

## 为什么一次就够：干涉

魔法还是[干涉](https://daiw.org/manual/quantum-computing/superposition)。经过 H 和预言机后，测量到全 0 态 $\ket{0\cdots0}$ 的**振幅**是：

$$
\frac{1}{2^n}\sum_{x} (-1)^{f(x)}
$$

分两种情况看这个和：

- **$f$ 恒定**：所有 $(-1)^{f(x)}$ 同号（全 $+1$ 或全 $-1$），$2^n$ 项**同向相加**，和为 $\pm 1$——全 0 态振幅是 $\pm1$，**测量必定得全 0**（相长干涉）。
- **$f$ 对半**：一半 $+1$、一半 $-1$，**正好两两抵消**，和为 $0$——全 0 态振幅是 $0$，**永远测不到全 0**（相消干涉）。

<Callout type="info">
  又是「[相消错误、相长正确](https://daiw.org/manual/quantum-computing/superposition)」那一套：算法把「是不是恒定」这个信息，通过预言机盖的相位 + 最后一层 H 的干涉，**聚焦到了「全 0 态」这一个测量结果上**——恒定则全 0 态相长（必测到）、对半则全 0 态相消（测不到）。你没有「读出所有 $f(x)$」，你只是让干涉替你把答案**一次性**逼了出来。这正是所有量子加速算法的共同灵魂，Deutsch-Jozsa 是它最干净的一个样本。
</Callout>

## 它的地位：一个「概念验证」

<Callout type="warn">
  **别高估 Deutsch-Jozsa 的实用性。** 它解决的是一个**人造问题**（现实里很少有「保证恒定或对半」的函数），而且它的指数优势是相对**确定性**经典算法而言；如果允许经典算法**随机采样几次**，出错概率也能压到极低。所以 Deutsch-Jozsa 的价值**不在实用，而在历史与教学**：它是第一个把「量子算法 = 用叠加铺开 + 用干涉聚焦」这个范式**严格证明**出来的例子。真正有实用威胁的加速——[Grover](https://daiw.org/manual/quantum-computing/grover) 的搜索、[Shor](https://daiw.org/manual/quantum-computing/qft-shor) 的分解——用的是同一套思想，但打的是真问题。
</Callout>

## 小结与下一章

Deutsch-Jozsa 用「H → 预言机 → H」的干涉，**一次查询**就判定了函数是恒定还是对半（经典最坏指数次）：恒定则全 0 态相长（必测到），对半则相消（测不到）。它是「叠加铺开 + 干涉聚焦」范式的最干净样本，价值在教学而非实用。

下一章是第一个**真有用**的量子算法——**Grover 搜索**。它解决「在 $N$ 个无序项里找一个」，把经典的 $O(N)$ 降到 $O(\sqrt N)$。你会亲手搭出「振幅放大」，看着正确答案的振幅一轮轮被抬高。👉 [Grover 搜索：振幅放大与 √N 加速](https://daiw.org/manual/quantum-computing/grover)。

## 参考文献

- [1] Deutsch & Jozsa.「Rapid solution of problems by quantum computation.」1992. —— 原始论文。
- [2] Qiskit 官方文档.「Deutsch-Jozsa algorithm.」https://learning.quantum.ibm.com —— 线路实现。
- [3] Nielsen & Chuang.《Quantum Computation and Quantum Information》， §1.4.4 —— DJ 算法分析。