量子算法进阶：Deutsch-Jozsa、Bernstein-Vazirani 与量子相位估计

引言

理解了 Shor 与 Grover 两大算法之后，真正的挑战是建立量子算法的思维直觉：为什么叠加态能让某些问题指数加速？答案藏在几个「教学算法」里——它们规模小、却精确展示了量子的核心招式：并行评估、相位编码、干涉放大。

本文沿一条渐进曲线展开：从 Deutsch-Jozsa（判断函数是常量还是平衡，量子只问一次）到 Bernstein-Vazirani（从一次查询中提取全部比特秘密），再到量子计算的「瑞士军刀」——量子傅里叶变换（QFT）与量子相位估计（QPE）（Shor 分解的核心引擎）。每一步都用 Qiskit 跑通，让你从「看懂公式」升级为「看懂为什么」。

前置：量子门与电路（https://plumephp.com/quantum-qubit-gates-basics/）、Qiskit（https://plumephp.com/quantum-qiskit-programming/）。Shor/Grover 见 https://plumephp.com/quantum-algorithms-shor-grover/。

目录

• 1. 量子算法的通用套路
• 2. Deutsch 问题与 Deutsch-Jozsa 算法
• 3. Bernstein-Vazirani：一次提取全部秘密
• 4. 量子傅里叶变换：从比特到相位
• 5. 量子相位估计：QFT 的杀手级应用
• 6. 实战：Qiskit 实现 Deutsch-Jozsa 与 QPE
• 7. 直觉整合：干涉如何带来加速
• 8. 通往 Shor：QPE 如何分解因数
• 9. 总结：量子算法的思维模型
• 延伸阅读

1. 量子算法的通用套路

1.1 三步曲

几乎所有量子算法都遵循：

1. 叠加：把所有可能输入放进叠加态（并行）
2. 演化：用一个量子电路同时评估所有输入
3. 干涉：用变换让「正确答案」的概率被放大、错误答案被抵消

1.2 关键区别

• 经典一次算一个输入。
• 量子一次算所有输入，但结果藏在相位/振幅里。
• 算法设计的核心 = 如何把「答案」从概率云里提取出来。

1.3 为什么不是免费午餐

叠加态包含所有输入，但测量只会坍缩到其中一个。量子算法靠干涉把想要的答案放大——这才是加速的真正来源。

2. Deutsch 问题与 Deutsch-Jozsa 算法

2.1 问题

判断一个函数 f: {0,1} → {0,1} 是常量（全 0 或全 1）还是平衡（一半 0 一半 1）：

f(0), f(1) 可能：
常量: (0,0) 或 (1,1)
平衡: (0,1) 或 (1,0)

2.2 经典 vs 量子

2.3 直觉

把两个输入放进叠加 |+⟩，一次「评估」同时知道 f(0) 与 f(1)；通过干涉，常量函数与平衡函数给出相反的测量结果。

3. Bernstein-Vazirani：一次提取全部秘密

3.1 问题

未知秘密 s（n 位），查询函数 f(x) = s·x (mod 2)（点积）。经典需要 n 次查询逐个猜比特；量子只需 1 次。

3.2 直觉

把秘密编码进相位：每个比特的贡献叠加在相位上，一次 QFT 把相位变成可读的比特串。

秘密 s = 101
经典: 查 f(001), f(010), f(100) → 3 次
量子: 一次查询 → 干涉 → 测量得到 101

3.3 教学意义

它是「相位编码 + 干涉提取」最干净的演示，是理解 QPE 的跳板。

4. 量子傅里叶变换：从比特到相位

4.1 QFT 是什么

经典 DFT 把「时间域」变到「频率域」；QFT 把量子态从计算基变到相位基：

QFT |j⟩ = (1/√N) Σₖ ω^(jk) |k⟩   (ω = e^{2πi/N})

4.2 电路实现

from qiskit.circuit.library import QFT

qft = QFT(num_qubits=3)
qft.draw()
# H 门 + 受控相位门 + 交换门

4.3 直觉

• QFT 把「哪个比特是 1」的信息分散到所有比特的相位上。
• 逆 QFT 再把相位信息「聚焦」回可读的比特。
• 它是 Shor 与 QPE 的核心引擎。

5. 量子相位估计：QFT 的杀手级应用

5.1 问题

给定酉算子 U 与特征向量 |u⟩，估计特征相位：

U |u⟩ = e^{2πiθ} |u⟩   →  求出 θ

5.2 算法流程

1. 辅助寄存器全叠加
2. 受控 U 门（相位编码进辅助比特）
3. 逆 QFT 把相位转成比特读数
4. 测量 → 得到 θ 的二进制近似

5.3 应用价值

QPE 是 Shor 分解、量子化学能量估计、HHL 线性求解的共同底层。

6. 实战：Qiskit 实现 Deutsch-Jozsa 与 QPE

6.1 Deutsch-Jozsa（平衡函数示例）

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator
from qiskit import transpile

# 1 数据比特 + 1 辅助比特，判定 f 是常量还是平衡
qc = QuantumCircuit(2, 1)
qc.x(1)                    # 辅助比特置 |1⟩
qc.h([0, 1])               # 叠加
qc.cx(0, 1)                # 平衡函数：f(x)=x → CNOT
qc.h(0)                    # 干涉
qc.measure(0, 0)

sim = AerSimulator()
counts = sim.run(transpile(qc, sim), shots=1024).result().get_counts()
print(counts)              # 平衡 → 测量到 |0⟩ 概率≈0；常量 → ≈1

6.2 QPE 最小实现（3 比特）

from qiskit.circuit.library import QFT, PhaseGate
import numpy as np

theta = 1/4   # 待估计相位
n = 3

qc = QuantumCircuit(n+1, n)
qc.h(range(n))            # 辅助寄存器叠加
qc.x(n)                   # 特征向量 |1⟩
for k in range(n):        # 受控相位门编码 θ
    qc.append(PhaseGate(2*np.pi * theta * 2**k).control(1), [k, n])
qc.append(QFT(n).inverse(), range(n))   # 逆 QFT
qc.measure(range(n), range(n))

counts = sim.run(transpile(qc, sim), shots=1024).result().get_counts()
print(counts)              # 二进制 100... → θ=1/4 (0.01₂)

6.3 结果解读

• QPE 测量得到 θ 的二进制表示（如 100 → 0.5, 010 → 0.25）。
• 精度随辅助比特数增加——这就是「相位测量的可编程精度」。

7. 直觉整合：干涉如何带来加速

7.1 三个阶段对齐

7.2 加速的本质

经典: 穷举 → 指数
量子: 并行评估 + 干涉聚焦 → 多项式

7.3 局限提醒

• 不是所有函数都能这样加速。
• 提取相位需要「相位集中在少数值」。
• 干涉对噪声敏感（容错的重要性）。

8. 通往 Shor：QPE 如何分解因数

8.1 桥接

Shor 分解 = 把因数分解转化为求某个酉算子的相位：

选 a，定义 U: |x⟩ → |ax mod N⟩
求 U 的特征相位 → 得到 a 的阶 r
r 为偶数 → gcd(a^{r/2}±1, N) 给出因数

8.2 为什么要学这些教学算法

Deutsch-Jozsa（1 次 vs 2 次）看似玩具，但它的叠加+干涉模板正是 Shor、Grover、QPE 共用的骨架。理解了最简形式，大算法只是「往骨架上加规模」。

8.3 递归学习地图

Deutsch-Jozsa → Bernstein-Vazirani → QFT → QPE → Shor/Grover

9. 总结：量子算法的思维模型

9.1 四句话心法

1. 叠加是并行，不是免费加速。
2. 干涉是提取答案的关键。
3. QFT 是连接比特与相位的桥梁。
4. 教学算法是理解大算法的钥匙。

9.2 自检清单

延伸阅读

• https://plumephp.com/quantum-qubit-gates-basics/ — 门与叠加的基础
• https://plumephp.com/quantum-algorithms-shor-grover/ — 量子优势的旗舰算法
• https://plumephp.com/quantum-qiskit-programming/ — Qiskit 电路实战
• Qiskit 算法教程 与 Nielsen & Chuang 教材