跳到正文
EN

9.7

Deutsch-Jozsa 算法

第一个量子加速的干净范例：相位反冲把函数值写进相位，干涉一次性读出「常数还是平衡」——经典最坏要问 2ⁿ⁻¹ + 1 次，量子问 1 次。

建议先掌握

学完本节你应该能

  • 陈述 Deutsch–Jozsa 问题，并说明经典算法最坏情况需要 2ⁿ⁻¹ + 1 次查询
  • 手算单比特 Deutsch 算法的完整态演化，指出干涉在哪一步发生
  • 解释相位反冲：为什么函数值会跑到相位上
  • 说清「量子并行」为什么单独不够、必须配上干涉才能兑现加速

前几节的纠缠协议解决的是通信问题。本节换战场：计算。 我们要看到量子力学第一次在算力上干净利落地赢过经典—— 赢的方式不是「算得更快」，而是「问得更少」。

问题开门：一次提问能鉴定一枚硬币的两面吗

有人给你一个黑盒子（oracle，谕示机），里面装着函数 f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\}——输入 nn 位串，吐出一位。他承诺 ff 只可能是两种之一：

  • 常数：所有输入都给同一个输出（全 0 或全 1）；
  • 平衡：恰好一半输入给 0，另一半给 1。

任务：判断是哪种。你唯一能做的就是查询——喂一个输入，看一个输出。 问：最少查几次？

经典的账。 运气好时查 2 次（两个输出不同 ⇒ 平衡）。 但要确定无疑地判「常数」，最坏情况必须查

2n2+1=2n−1+1 次(9.7.1)\frac{2^n}{2}+1=2^{n-1}+1\ \text{次}\tag{9.7.1}

——查了一半还全相同时，第 2n−1+12^{n-1}+1 次才能一锤定音。n=100n=100 时这是约 6.3×10296.3\times10^{29} 次，宇宙年龄都不够。而量子算法查 1 次。

朴素的「量子并行」为什么不够

量子版的黑盒必须可逆（9.2 节），标准做法是带一条辅助线：

Uf∣x⟩∣y⟩=∣x⟩∣y⊕f(x)⟩(9.7.2)U_f\ket{x}\ket{y}=\ket{x}\ket{y\oplus f(x)}\tag{9.7.2}

（⊕\oplus 是模 2 加；作用两次还原，确实幺正。）第一招人人都想得到： 用一排 HH 造出所有输入的叠加，再查询一次：

Uf(12n∑x∣x⟩)∣0⟩=12n∑x∣x⟩∣f(x)⟩(9.7.3)U_f\left(\frac{1}{\sqrt{2^n}}\sum_x\ket{x}\right)\ket{0} =\frac{1}{\sqrt{2^n}}\sum_x\ket{x}\ket{f(x)}\tag{9.7.3}

一次调用，2n2^n 个函数值全算出来了——这就是量子并行。 但先别庆祝：这个态测一下，只随机塌出一个 (x,f(x))(x, f(x)) 对， 跟经典查一次毫无区别。9.1 节的老教训：装进态里的信息 ≠ 取得出的信息。 量子并行是必要的燃料，点火的是干涉——要让所有 f(x)f(x) 的信息 汇聚到测量结果的概率分布上。实现汇聚的扳手叫相位反冲。

相位反冲：把函数值搬到相位上基础~5 min

把辅助位预先制成 ∣−⟩=∣0⟩−∣1⟩2\ket{-}=\frac{\ket{0}-\ket{1}}{\sqrt2}，再喂给 UfU_f：

Uf∣x⟩∣−⟩=∣x⟩⊗∣0⊕f(x)⟩−∣1⊕f(x)⟩2(9.7.4)U_f\ket{x}\ket{-} =\ket{x}\otimes\frac{\ket{0\oplus f(x)}-\ket{1\oplus f(x)}}{\sqrt2}\tag{9.7.4}

分两种情况：

  • f(x)=0f(x)=0：辅助位是 ∣0⟩−∣1⟩2=∣−⟩\frac{\ket{0}-\ket{1}}{\sqrt2}=\ket{-}，原样不动；
  • f(x)=1f(x)=1：辅助位是 ∣1⟩−∣0⟩2=−∣−⟩\frac{\ket{1}-\ket{0}}{\sqrt2}=-\ket{-}，多出一个负号。

两种情况合成一句：

Uf∣x⟩∣−⟩=(−1)f(x)∣x⟩∣−⟩(9.7.5)U_f\ket{x}\ket{-}=(-1)^{f(x)}\ket{x}\ket{-}\tag{9.7.5}

辅助位全程是 ∣−⟩\ket{-} 没变，函数值变成了 ∣x⟩\ket{x} 分支上的相位 (−1)f(x)(-1)^{f(x)}。 单看一个 xx，整体相位毫无意义；但对叠加态,每个分支各领各的符号—— 它们成了相对相位，而相对相位正是干涉的操纵杆（9.2 节 Z∣+⟩=∣−⟩Z\ket{+}=\ket{-} 的教训）。

先手算最小案例：Deutsch 算法（n = 1）

n=1n=1 时四种可能的 ff：常数（f≡0f\equiv0、f≡1f\equiv1）， 平衡（f(x)=xf(x)=x、f(x)=1−xf(x)=1-x）。判定问题等价于问一个比特：f(0)⊕f(1)=?f(0)\oplus f(1)=? （0 ⇒ 常数，1 ⇒ 平衡）。线路：

|0⟩ ──[H]──┬──────[H]──[测量] → 0：常数 / 1：平衡
           │Uf
|−⟩ ───────┴────────────────── （辅助位始终是 |−⟩）

逐步演化（辅助位恒为 ∣−⟩\ket{-}，只写第一位）：

∣0⟩ →H ∣0⟩+∣1⟩2 →Uf (−1)f(0)∣0⟩+(−1)f(1)∣1⟩2(9.7.6)\ket{0} \ \xrightarrow{H}\ \frac{\ket{0}+\ket{1}}{\sqrt2} \ \xrightarrow{U_f}\ \frac{(-1)^{f(0)}\ket{0}+(-1)^{f(1)}\ket{1}}{\sqrt2}\tag{9.7.6}

提出整体相位 (−1)f(0)(-1)^{f(0)}（不可观测，扔掉）：

=∣0⟩+(−1)f(0)⊕f(1)∣1⟩2={∣+⟩,常数∣−⟩,平衡=\frac{\ket{0}+(-1)^{f(0)\oplus f(1)}\ket{1}}{\sqrt2} =\begin{cases}\ket{+},&\text{常数}\\[2pt]\ket{-},&\text{平衡}\end{cases}

最后一步 HH 把 ∣±⟩\ket{\pm} 转回计算基：

∣+⟩→H∣0⟩ (常数),∣−⟩→H∣1⟩ (平衡)(9.7.7)\ket{+}\xrightarrow{H}\ket{0}\ (\text{常数}),\qquad \ket{-}\xrightarrow{H}\ket{1}\ (\text{平衡})\tag{9.7.7}

测量第一位，确定性读出答案。一次查询，问出了经典要问两次的 f(0)⊕f(1)f(0)\oplus f(1)——注意我们没有得到 f(0)f(0) 和 f(1)f(1) 各自的值， 只得到了它们的一个全局性质。量子加速从来都是这个套路： 放弃逐点信息，换取全局信息。

一般情形：n 比特的 Deutsch–Jozsa

|0⟩ ──[H]──┬─────[H]──[测量]┐
|0⟩ ──[H]──┤Uf   [H]──[测量]├─ 全 0：常数 / 否则：平衡
 ⋮    ⋮    │      ⋮     ⋮   │
|−⟩ ───────┴────────────────┘（辅助位不测）
干涉如何把答案集中到全零串上进阶~8 min

第 1 步：制备与查询。 nn 个 ∣0⟩\ket{0} 过一排 HH，再经相位反冲：

12n∑x∣x⟩ →Uf 12n∑x(−1)f(x)∣x⟩(9.7.8)\frac{1}{\sqrt{2^n}}\sum_{x}\ket{x} \ \xrightarrow{U_f}\ \frac{1}{\sqrt{2^n}}\sum_{x}(-1)^{f(x)}\ket{x}\tag{9.7.8}

第 2 步：再过一排 HH。 需要 H⊗nH^{\otimes n} 对基矢的作用公式。 单比特时 H∣x⟩=12∑y(−1)xy∣y⟩H\ket{x}=\frac{1}{\sqrt2}\sum_{y}(-1)^{xy}\ket{y}（代 x=0,1x=0,1 可验证）， nn 位逐位相乘：

H⊗n∣x⟩=12n∑y(−1)x⋅y∣y⟩,x⋅y≡x1y1⊕⋯⊕xnyn(9.7.9)H^{\otimes n}\ket{x}=\frac{1}{\sqrt{2^n}}\sum_{y}(-1)^{x\cdot y}\ket{y}, \qquad x\cdot y\equiv x_1y_1\oplus\cdots\oplus x_ny_n\tag{9.7.9}

代入得末态：

∣Ψ末⟩=∑y[12n∑x(−1)f(x)+x⋅y]∣y⟩(9.7.10)\ket{\Psi_{\text{末}}}=\sum_{y}\left[\frac{1}{2^n}\sum_{x}(-1)^{f(x)+x\cdot y}\right]\ket{y}\tag{9.7.10}

第 3 步：只看全零串 y=0⋯0y=0\cdots0 的振幅。 此时 x⋅y=0x\cdot y=0：

c0=12n∑x(−1)f(x)(9.7.11)c_{0}=\frac{1}{2^n}\sum_{x}(-1)^{f(x)}\tag{9.7.11}
  • 常数：2n2^n 项同号，c0=±1c_0=\pm1。概率 ∣c0∣2=1|c_0|^2=1—— 所有分支相长干涉涌进全零串，测量必得 0⋯00\cdots0。
  • 平衡：+1+1 与 −1-1 各半，逐对抵消，c0=0c_0=0—— 全零串被相消干涉清空，测量必得非零串。

判据：读数全零 ⇒ 常数；有任何一位非零 ⇒ 平衡。一次查询，零错误率。

物理图像

加速的三步曲。 回看全程，量子优势来自三件事的接力： （1）叠加让一次查询触及所有输入； （2）相位反冲把每个函数值转写成分支相位； （3）干涉（末排 HH）让相位以「全体投票」的方式 决定测量分布——常数函数全票通过流向全零串，平衡函数票数对半抵消。 缺任何一环都退回经典：没有干涉是抽签， 没有相位反冲则各分支毫无差别，没有叠加则无票可投。

数学形式

查询复杂度对比（判定确定无误）：

经典（确定性）: 2n−1+1(9.7.12)\text{经典（确定性）}:\ 2^{n-1}+1\tag{9.7.12}量子: 1(9.7.13)\text{量子}:\ 1\tag{9.7.13}

指数对常数。但要诚实标注：若允许经典算法随机抽查 kk 次并容忍 出错概率 2−k2^{-k}，经典也只需常数次。所以 DJ 的指数优势严格说是 「精确判定」意义下的——它是原理演示，而非实用算法。

本节关键公式

  • 量子 oracle

    Uf∣x⟩∣y⟩=∣x⟩∣y⊕f(x)⟩U_f\ket{x}\ket{y}=\ket{x}\ket{y\oplus f(x)}

    可逆化的函数查询；作用两次复原

  • 相位反冲

    Uf∣x⟩∣−⟩=(−1)f(x)∣x⟩∣−⟩U_f\ket{x}\ket{-}=(-1)^{f(x)}\ket{x}\ket{-}

    辅助位设为 ∣−⟩，函数值搬到相位

  • Hadamard 变换

    H⊗n∣x⟩=12n∑y(−1)x⋅y∣y⟩H^{\otimes n}\ket{x}=\frac{1}{\sqrt{2^n}}\sum_y(-1)^{x\cdot y}\ket{y}

    x·y 为逐位乘积的模 2 和

  • 判定振幅

    c0=12n∑x(−1)f(x)=±1 或 0c_0=\frac{1}{2^n}\sum_x(-1)^{f(x)}=\pm1\ \text{或}\ 0

    常数 ⇒ 必测得全零串；平衡 ⇒ 必测得非零串

自测共 4 题

  1. 1.

    n = 3（8 个输入）。经典算法要确定无疑地判定常数/平衡，最坏情况需要查询多少次？

    允许 0% 相对误差
  2. 2.

    相位反冲要求辅助位处于什么态？

  3. 3.

    算法结束时测得全零串 00…0，说明什么？

  4. 4.

    关于「量子并行」，正确的说法是？（多选）

    多选题

接下来

Deutsch–Jozsa 是为量子力学量身定做的表演赛：问题人工、经典随机算法也不难。 真刀真枪的问题长这样：NN 个抽屉里有一个藏着钥匙，翻一个看一次， 经典平均要翻 N/2N/2 个。量子能不能少翻几个？ 下一节的 Grover 算法给出 N\sqrt N——而且我们会用一张纯几何的图 （两面镜子夹出一个旋转）把它看得明明白白。

全站第 71 / 106 节 · 用 ← → 翻页