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

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

现在把前面所有零件——叠加、干涉、预言机与相位反冲——拼成第一个真正的量子算法。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」三明治：

跑通它

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))

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

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

为什么一次就够：干涉

魔法还是干涉。经过 H 和预言机后，测量到全 0 态 $\ket{0\cdots0}$ 的振幅是：

分两种情况看这个和：

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

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

小结与下一章

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

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

参考文献

• [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 算法分析。