1. 量子计算模型与复杂度基础

要理解量子算法为什么可能比经典算法更快，必须先建立一套统一的“计算模型”语言。经典计算中，我们用比特、逻辑门和电路来描述计算；量子计算中，对应的基本对象是量子比特、量子门和量子电路，而更抽象的理论边界则由量子图灵机与复杂度类 BQP 刻画。本节从这些基本对象出发，逐步搭建起量子算法复杂度分析的概念框架。

量子比特：从确定状态到叠加态

经典比特只能取 0 或 1。量子比特（qubit）的状态则用一个二维复向量表示：

|ψ⟩ = α|0⟩ + β|1⟩,   α, β ∈ ℂ,   |α|² + |β|² = 1

其中 |0⟩ 和 |1⟩ 是计算基态，α、β 称为概率幅。测量时得到 0 的概率为 |α|²，得到 1 的概率为 |β|²。与经典概率分布的关键区别在于：概率幅是复数，可以相互干涉——同号相加增强，反号相消减弱。这正是量子算法获得加速的根本来源之一。

多个量子比特通过张量积组合。例如两个量子比特的一般态为

|ψ⟩ = α₀₀|00⟩ + α₀₁|01⟩ + α₁₀|10⟩ + α₁₁|11⟩

n 个量子比特的联合态需要 2ⁿ 个概率幅描述，这一指数级的状态空间既是量子计算能力的来源，也是经典模拟量子系统困难的原因。需要注意的是，n 个量子比特并不等于“同时并行计算 2ⁿ 个经典结果”，测量只能得到一个基态结果，量子算法的技巧在于通过干涉让正确答案的概率幅增强、错误答案的概率幅抵消。

量子门与量子电路模型

量子门是对量子态施加的酉变换（unitary transformation），即满足 U†U = I 的线性算子。常见单比特门包括：

• Pauli-X 门：类似经典非门，交换 |0⟩ 与 |1⟩。
• Hadamard 门（H）：把 |0⟩ 变为 (|0⟩+|1⟩)/√2，是制造叠加态的基本工具。
• 相位门 S、T：只改变 |1⟩ 的相位，是构造通用量子门集的重要成分。

两比特门中最重要的是受控非门（CNOT）：当控制比特为 1 时翻转目标比特，用于产生纠缠态。例如 H 门作用于第一个比特后再接 CNOT，可得到贝尔态 (|00⟩+|11⟩)/√2。单比特门与 CNOT 组合构成通用门集，可以近似任意酉变换。

量子电路模型把计算表示为：初始化若干 |0⟩ 比特，按时间顺序施加一系列量子门，最后在计算基下测量部分或全部比特。电路深度（并行门层数）和门数量是衡量量子算法资源开销的两个核心指标。与经典电路不同，量子电路中的门必须可逆（除测量外），因为酉变换本身可逆。

量子图灵机与 BQP 类

量子电路模型适合描述具体算法，而量子图灵机（Quantum Turing Machine, QTM）提供了更一般的理论模型。QTM 的纸带内容、读写头位置和内部状态构成一个量子态，每一步转移由酉变换描述。可以证明，量子图灵机与量子电路模型在多项式时间内可以互相模拟，因此二者在复杂度分析中等价。

在此基础上定义复杂度类 BQP（Bounded-error Quantum Polynomial time）：一个语言 L 属于 BQP，当且仅当存在一个多项式时间的量子算法，对任意输入 x，判定 x∈L 的正确概率至少为 2/3，且对 x∉L 的错误概率也至多 1/3。这里的 2/3 是约定阈值，通过重复运行可以指数级压低错误率。

BQP 与经典复杂度类的关系可以概括为：

目前已知 P ⊆ BPP ⊆ BQP ⊆ PSPACE，且普遍相信 BQP 严格包含 BPP（如大数分解、离散对数问题属于 BQP 但未知是否属于 BPP）。但 BQP 与 NP 的关系仍悬而未决：量子计算并不能在多项式时间内解决所有 NP 完全问题，这一点常被误解，需要特别注意。

从模型到算法设计

综合来看，量子算法设计通常遵循这样的思路：先把问题编码到 n 个量子比特的初态上；用 Hadamard 门等构造均匀叠加；再通过一系列受控酉操作引入问题结构，使不同计算路径产生相位差；最后用干涉（如量子傅里叶变换、振幅放大）把目标结果的概率幅集中起来，测量得到答案。复杂度分析则关注门数量、电路深度以及所需量子比特数是否随输入规模多项式增长。

本节建立的这套语言——量子比特、量子门、量子电路、量子图灵机、BQP——是后续所有量子算法（Deutsch-Jozsa、Grover、Shor 等）分析与比较的共同基础。掌握这些对象的数学定义和相互关系，才能在看到具体算法时准确判断它“快在哪里、为什么快、代价是什么”。