Quantum Algorithm Banner

摘要： 量子计算的强大能力源于其独特的物理原理，但这些原理如何一步步组合起来，最终形成能够解决实际问题的算法呢？本文将扮演一位向导，带您从量子世界最微小的积木——量子比特和量子门开始，通过一个简单而经典的“Deutsch 问题”，亲手构建一个完整的量子算法。您将看到，叠加、纠缠和干涉这些抽象概念是如何在实践中协同工作，并最终展现出超越经典计算的“量子优势”的。（在本文的 Deutsch 算法示例中，核心驱动力是叠加与干涉；纠缠则作为量子计算的重要资源，在更复杂的算法中发挥关键作用。）

第一步：奠定基石 - 量子比特与基本状态

一切计算都需要一个起点。经典计算的起点是比特 0 和 1，而量子计算的起点是量子比特 (Qubit) 的基态：\(|0\rangle\) 和 \(|1\rangle\)。

  • \(|0\rangle\)：可以想象成一个指向“北极”的箭头。
  • \(|1\rangle\)：可以想象成一个指向“南极”的箭头。

在没有进行任何操作时，一个量子比特就处于这两个明确的状态之一，通常我们从 \(|0\rangle\) 开始。

Qubit States 图1：量子比特的两个基本状态 |0⟩ 和 |1⟩，对应布洛赫球面的北极和南极。

第二步：引入魔力 - 单量子比特门

要让计算发生，我们需要改变量子比特的状态。这就是量子门 (Quantum Gate) 的作用。它们就像是施加在量子比特上的“旋转指令”。

在数学上，量子门是酉矩阵——它们对量子态向量进行线性变换，同时保证概率的总和始终为 1。

常用量子门的矩阵表示 图1.5：常用量子门的矩阵表示。量子门的本质是对量子态向量的可逆线性变换。

2.1 X 门：量子世界的“非”门

X 门 是最简单的量子门之一，它的作用等同于经典计算中的 NOT（非）门。它能将量子比特的状态翻转： - 如果是 \(|0\rangle\)，就变成 \(|1\rangle\)。 - 如果是 \(|1\rangle\)，就变成 \(|0\rangle\)。

在布洛赫球面上，这相当于将状态向量绕 X 轴旋转 180 度。

2.2 H 门：创造“叠加”的钥匙

H 门（哈达玛门, Hadamard Gate） 是量子计算中最重要的门之一。它是一把能开启“量子并行性”的钥匙，因为它能创造出均匀叠加态。

  • 对 \(|0\rangle\) 施加 H 门，会得到一个“一半是 \(|0\rangle\)，一半是 \(|1\rangle\)”的状态，记作 \(|+\rangle\)。 \[ H|0\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) = |+\rangle \]
  • 对 \(|1\rangle\) 施加 H 门，会得到一个相位不同的叠加态，记作 \(|-\rangle\)。 \[ H|1\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle) = |-\rangle \]

经过 H 门之后，量子比特不再是一个确定的 0 或 1，而是同时拥有了两种可能性。这是量子算法能够并行处理大量信息的基础。

Hadamard Gate 图2：H 门将基态 |0⟩ 旋转到 X 轴上，创造出均匀叠加态 |+⟩。

2.3 叠加的“概率幅” vs 经典概率

这里有一个容易混淆的点：\(H|0\rangle\) 之后，我们说“测量时有 50% 概率得到 0，50% 概率得到 1”，这听起来很像经典的“掷硬币”。但量子叠加和经典概率混合有一个本质区别：

  • 经典情形下（比如一枚硬币盖在桌子上），它要么已经是正面，要么已经是反面，只是我们不知道；我们的“50%”是一种无知。
  • 量子叠加中，状态 \(|+\rangle = (|0\rangle + |1\rangle)/\sqrt{2}\) 本身就是一个物理上存在的“既非纯 0 也非纯 1”的向量状态，在测量之前“0/1”这个问题其实还没有被决定。

如果用布洛赫球来可视化：

  • \(|0\rangle\) 是指向北极的箭头。
  • \(|1\rangle\) 是指向南极的箭头。
  • \(|+\rangle\) 则是指向赤道上的某个点（例如 X 轴正方向）。

H 门的作用就是一个“旋转”：

  1. 起点：\(|0\rangle\) 对应北极。
  2. 施加一次 H：箭头被转到赤道上，得到 \(|+\rangle\)，测量时 0/1 各半。
  3. 再施加一次 H：\(H|+\rangle = |0\rangle\)，箭头又转回北极。

这说明 H 门并不是“增加随机性”的操作，而是一个完全可逆的线性变换。所谓“50%/50%”来自向量系数的平方（概率幅的平方），而不是因为“我们什么都不知道”。

Hadamard 门的可逆性 图2.5：H 门是可逆的旋转操作——连续两次 H 门会回到原点。

第三步：构建联系 - 多量子比特门

如果只有单个量子比特，我们能做的事情非常有限。量子计算的真正威力来自于多个量子比特之间的相互作用。

CNOT 门：创造“纠缠”的工具

CNOT 门（受控非门, Controlled-NOT Gate） 是一个双量子比特门，它是创造量子纠缠的关键工具。它有两个输入： - 控制比特 (Control Qubit) - 目标比特 (Target Qubit)

它的工作逻辑是： - 如果控制比特是 \(|0\rangle\)，那么目标比特保持不变。 - 如果控制比特是 \(|1\rangle\)，那么对目标比特执行一个 X 门（翻转）。

现在，看看当控制比特处于叠加态时会发生什么。假设我们将一个 H 门作用于第一个量子比特（控制比特），然后再将它们一起送入 CNOT 门：

  1. 初始状态：\(|00\rangle\) (两个量子比特都是 \(|0\rangle\))
  2. 施加 H 门：第一个量子比特变成叠加态，整体状态为 \(\frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)|0\rangle = \frac{1}{\sqrt{2}}(|00\rangle + |10\rangle)\)。
  3. 施加 CNOT 门：
  • 对于 \(|00\rangle\) 部分，控制比特处于 \(|0\rangle\)，目标比特保持 \(|0\rangle\) 不变，结果仍是 \(|00\rangle\)。
  • 对于 \(|10\rangle\) 部分，控制比特处于 \(|1\rangle\)，目标比特从 \(|0\rangle\) 翻转为 \(|1\rangle\)，结果变为 \(|11\rangle\)。

最终，我们得到的状态是 \(\frac{1}{\sqrt{2}}(|00\rangle + |11\rangle)\)。这就是著名的贝尔态 (Bell State)，一个完美的纠缠态。在这个状态下，两个量子比特不再独立。如果你测量第一个是 0，那么第二个必然是 0；如果你测量第一个是 1，那么第二个必然是 1。它们被“纠缠”在了一起。

CNOT Gate 图3：CNOT 门创造纠缠的过程。

3.1 纠缠的“局部随机”与“整体确定”

贝尔态 \(\frac{1}{\sqrt{2}}(|00\rangle + |11\rangle)\) 的微妙之处在于，它同时具备：

  • 局部看：完全随机。
  • 整体看：完全相关。

具体来说，如果我们做很多次实验，并记录两个比特的测量结果，会得到这样的统计：

  • 单独看第一个比特：
    • \(P(第一个是 0) = 0.5\)
    • \(P(第一个是 1) = 0.5\)
  • 单独看第二个比特：
    • \(P(第二个是 0) = 0.5\)
    • \(P(第二个是 1) = 0.5\)

但如果我们看“成对”的结果（联合分布）：

  • \(P(00) = 0.5\)
  • \(P(11) = 0.5\)
  • \(P(01) = 0\)
  • \(P(10) = 0\)

也就是说，每个比特单独看都像是抛硬币一样随机，但两者永远一致，要么一起是 0，要么一起是 1。这就是“局部随机但整体高度相关”的纠缠特性。

如果配一幅图，可以画两组柱状图：

  • 左边两幅：分别是“第一个比特”的 0/1 概率条、“第二个比特”的 0/1 概率条——两幅图看起来都是 0/1 高度相同。
  • 右边一幅：联合结果的四根柱子里，只有 00 和 11 的柱子有高度，01 和 10 的柱子高度为 0。

这类纠缠态是许多量子协议（如量子密钥分发、超密编码等）的资源基础，也是量子算法中让“比特不再独立计数，而是成指数级增长的整体”的关键原因之一。

第四步：组装算法 - Deutsch 问题实例

现在我们拥有了创造叠加和纠缠的工具，接下来用它们来解决一个简单但极具启发性的问题：Deutsch 问题。

问题描述： 假设你有一个“黑盒”函数 \(f(x)\)，它的输入和输出都只能是 0 或 1。这个函数只有两种可能： 1. 常数函数 (Constant)：无论输入是什么，输出都相同（即 \(f(0) = f(1)\)）。 2. 平衡函数 (Balanced)：输入 0 和 1，输出的结果刚好相反（即 \(f(0) \neq f(1)\)）。

任务：判断这个函数是“常数”还是“平衡”，要求调用函数（黑盒）的次数尽可能少。

  • 经典方法：你必须调用函数两次。先用 0 调用一次得到 \(f(0)\)，再用 1 调用一次得到 \(f(1)\)，然后比较两个结果。两次调用是必须的。

  • 量子方法：利用量子算法，我们只需要调用函数一次就能解决问题！

Deutsch 算法的构建步骤：

我们将使用两个量子比特：第一个是输入比特 \(x\)，第二个是辅助比特 \(y\)。

  1. 初始化 (Initialization)： 准备两个量子比特，状态为 \(|01\rangle\)。

  2. 创建叠加态 (Superposition)： 对两个量子比特都施加 H 门。

  • 第一个比特变为：\(H|0\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)\)
  • 第二个比特变为：\(H|1\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)\) 此时，输入状态已经包含了所有可能的输入值 (0 和 1)。
  1. 调用函数（量子黑盒） (Oracle)： 这是最关键的一步。我们将这个叠加态输入到代表函数 \(f(x)\) 的量子黑盒（称为 Oracle, \(U_f\)）中。这个黑盒的作用是将输入 \(|x, y\rangle\) 变为 \(|x, y \oplus f(x)\rangle\)（\(\oplus\) 是异或操作）。 由于我们的输入是叠加态，函数 \(f(x)\) 被同时作用在了所有可能的输入上。更妙的是，我们事先把第二个量子比特准备在 \(\frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)\) 这种带有负号的叠加态中，使得 \(f(x)\) 的输出不直接体现在“可见的比特值”上，而是被编码进了第一个比特所携带的相位信息中。

这个技巧被称为相位踢回（Phase Kickback）：当 Oracle 作用于辅助比特的 \(|-\rangle\) 态时，\(f(x)\) 的值会以 \((-1)^{f(x)}\) 的形式“踢回”到控制端（第一个比特）的相位上。于是，第一个比特的状态变为 \(\frac{1}{\sqrt{2}}\big((-1)^{f(0)}|0\rangle + (-1)^{f(1)}|1\rangle\big)\)，函数信息完全被编码在了相位差里。

粗略地说： - 如果 \(f(x)\) 是常数函数，那么两条路径（\(x=0\) 和 \(x=1\)）经历相同的相位变化，整体状态的相对相位不变，第一个量子比特的“方向”不被翻转。 - 如果 \(f(x)\) 是平衡函数，那么两条路径中的一条会额外获得一个负号（相位反转），使得第一个量子比特的叠加态从“偏向 0 的方向”翻转成“偏向 1 的方向”。

  1. 干涉与测量 (Interference & Measurement)： 在函数调用后，我们再次对第一个量子比特施加一个 H 门。这个 H 门此时扮演的是“干涉仪”的角色：
  • 如果函数是常数的（两条路径同相），干涉结果是“向 \(|0\rangle\) 方向完全构建、向 \(|1\rangle\) 方向完全抵消”，于是经过 H 门后，第一个比特变回 \(|0\rangle\)。
  • 如果函数是平衡的（一条路径多了一个负号，两条路径相差一个“π 相位”），干涉结果变为“向 \(|1\rangle\) 方向构建、向 \(|0\rangle\) 方向抵消”，于是经过 H 门后，第一个比特变成 \(|1\rangle\)。

最后，我们只需要测量第一个量子比特： - 如果测得 0，我们就知道函数是常数的。 - 如果测得 1，我们就知道函数是平衡的。

Deutsch Algorithm Circuit 图4：Deutsch 算法的量子线路图。整个过程只需调用一次函数 Uf。

状态演化汇总（以第一个量子比特为重点）：

阶段 第一比特状态 第二比特状态 说明
初始化 \(|0\rangle\) \(|1\rangle\) 基态准备
H 门后 \(\frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)\) \(\frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)\) 创建叠加态
Oracle 后 \(\frac{1}{\sqrt{2}}\big((-1)^{f(0)}|0\rangle + (-1)^{f(1)}|1\rangle\big)\) \(\frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)\) 相位踢回
末 H 门后 常数 → \(|0\rangle\)；平衡 → \(|1\rangle\) （不再关注） 干涉揭示答案

结论：量子优势的体现

通过 Deutsch 算法，我们清楚地看到： 1. H 门 创造了叠加态，使所有输入能”一次性”提供给函数。 2. 量子黑盒 \(U_f\) 利用了量子并行性，同时计算了 \(f(0)\) 和 \(f(1)\)。 3. 相位反转 和第二个 H 门 巧妙地构成了量子干涉，将目标全局属性（“常数”还是”平衡”）编码到了第一个量子比特的最终状态上。

最终，我们用一次函数调用就完成了经典计算需要两次才能完成的任务。虽然这只是一个简单的例子，但它完美地展示了量子算法是如何从最基本的原理出发，一步步构建起来，并最终实现超越经典计算的“量子优势”的。

如果你希望从更宏观的视角理解量子计算的物理背景、三大核心原理（叠加、纠缠和干涉）以及 Grover 等经典算法的直观图像，可以搭配阅读配套文章《量子计算的核心原理》。这两篇文章一内一外：本文侧重“从量子门到量子线路再到具体算法”的构建过程，而那篇文章则帮助你建立对整个量子计算图景的直觉。如果你对“所有路径一起算，然后用相位控制它们在终点处如何相遇”这一视角感兴趣，则可以进一步参考进阶篇《量子计算的多路径视角：从干涉到算法》。

而如果你想见识量子计算真正的“核武器”，了解它如何利用这些原理破解现代密码学，请阅读《量子计算如何分解质因子：Shor 算法详解》。

同主题继续阅读

把当前热点继续串成多页阅读，而不是停在单篇消费。

2026-04-03 · computer-science

量子计算的核心原理

深入浅出介绍量子计算的三大核心支柱：量子比特、叠加态和纠缠态，探讨量子计算机如何利用这些奇特性质解决特定问题，以及 Grover 算法如何实现量子搜索加速。

2025-11-16 · computer-science / physics

量子计算的多路径视角：从干涉到算法

从费曼路径积分的视角理解量子计算，探讨如何将所有可能路径的振幅叠加，通过相位控制实现干涉，最终在算法层面放大正确答案的概率。

2025-11-30 · computer-science

量子计算如何分解质因子：Shor 算法详解

深入解析 Shor 算法：如何利用量子傅里叶变换 (QFT) 和周期查找将大整数分解的时间复杂度从指数级降低到多项式级，从而破解 RSA 加密。