📚 课程目录第2章量子计算模型与复杂度类基础

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

要讨论量子计算的复杂度，首先必须明确“量子计算机”在理论上的两种等价刻画：量子电路模型与量子图灵机。它们分别从“并行门阵列”和“逐步读写带子”两个角度描述同一类可计算过程，并共同支撑起 BQP、QMA、QCMA 等复杂度类的定义。

量子电路模型：把算法写成门序列

量子电路模型是最常用的描述方式。它由三部分组成：若干量子比特（qubit）的寄存器、一系列量子门、以及末尾的测量。一个规模为 n 的输入被编码到初始态 |x⟩ 上，通常再补上若干辅助比特 |0…0⟩，然后依次作用酉门 U₁, U₂, …, U_m，最后对指定输出比特做计算基测量。

电路模型的关键约束是：门集合必须有限且通用，例如 {H, T, CNOT} 就是通用集合；电路规模用门数 m 与比特数 n 的多项式来度量。若存在一个经典多项式时间算法能根据输入长度 n 输出电路的描述，则称该电路族是一致（uniform）的。复杂度类通常要求一致性，否则会混入不可计算的信息。

一个直观的示例是 Deutsch–Jozsa 电路：输入 n 比特，先施加 Hadamard 层，再查询一次黑箱 U_f，最后再施加 Hadamard 层并测量。若函数为常函数，测量结果全为 0；若为平衡函数，则结果非全 0。这个例子说明量子电路可以用一次查询区分两类函数，而经典确定性算法最坏需要 2^n-1+1 次查询。

量子图灵机：更贴近“计算”的定义

量子图灵机（QTM）把经典图灵机的读写头、无限带子和状态转移推广到量子情形。带子上的内容、读写头位置和内部状态共同构成一个基态，整个机器处于这些基态的叠加中。每一步转移是一个酉变换，要求局部性：读写头只能读取当前格，并只能把当前格改写为有限种符号之一。

QTM 与量子电路模型在多项式时间内是等价的：给定一个一致量子电路族，可以构造一个多项式时间的 QTM 模拟它；反之，QTM 的每一步也可展开为有限个局部量子门。因此，在定义复杂度类时，两者可以互换使用。实际研究中，电路模型更便于描述算法和资源，QTM 更便于讨论可计算性与停机问题。

BQP：有界错误量子多项式时间

BQP（Bounded-error Quantum Polynomial time）是量子计算最核心的复杂度类。语言 L 属于 BQP，当且仅当存在一个一致量子电路族 {C_n}，其规模为 n 的多项式，使得：

若 x ∈ L，则测量接受概率 ≥ 2/3；
若 x ∉ L，则测量接受概率 ≤ 1/3。

这里的 2/3 与 1/3 是约定阈值，通过重复运行并取多数结果，可把错误概率压到任意小。BQP 包含 P，也包含整数分解、离散对数、量子模拟等问题。它与 NP 的关系尚未确定：普遍认为 BQP 不包含 NP-完全问题，否则多项式层级会坍塌。

QMA 与 QCMA：量子见证与经典见证

把 NP 的“证书”概念量子化，就得到 QMA（Quantum Merlin–Arthur）。语言 L 属于 QMA，当存在多项式规模量子电路 V（验证者）和多项式规模量子态 |ψ⟩（见证）时：

若 x ∈ L，存在 |ψ⟩ 使 V 接受概率 ≥ 2/3；
若 x ∉ L，对任意 |ψ⟩，V 接受概率 ≤ 1/3。

若把见证限制为经典比特串，则得到 QCMA（Quantum Classical Merlin–Arthur）。显然 QCMA ⊆ QMA。一个经典例子是局部哈密顿量问题（k-LOCAL HAMILTONIAN）：给定多个作用在常数个量子比特上的哈密顿量项，问基态能量是否低于某阈值。该问题是 QMA-完全的，其见证就是基态本身。

QMA 与 QCMA 的差异在于见证是否必须为量子态。若某个问题的最优见证本质上是量子的、无法用多项式长度的经典串替代，则它很可能在 QMA 而不在 QCMA 中。目前已知 QCMA ≠ QMA 尚未被证明，但多数研究者相信二者不同。

类之间的关系与包含结构

把这些类放在一起，可以得到如下包含链：P ⊆ BQP ⊆ QMA，NP ⊆ QMA，QCMA ⊆ QMA，且 BQP 与 NP 的关系未知。BQP 与 QCMA 之间没有已知的包含关系：QCMA 的验证者可以接收经典见证，但验证过程本身是量子的；BQP 则不允许外部见证。若把 BQP 的验证者改为可接收量子见证，就得到 QMA。

图中用嵌套椭圆表示包含关系：P 最小，被 BQP 包含；BQP 又被 QCMA 包含；QCMA 与 NP 都包含于 QMA。BQP 与 NP 之间用虚线箭头加问号表示关系未知。需要强调，这些包含关系是定义层面的直接推论，而“是否严格包含”大多仍是开放问题。

如何判断一个问题属于哪个类

面对一个新问题，可以按以下顺序判断：第一，若存在经典多项式时间算法，则属于 P，自然属于 BQP。第二，若存在量子多项式时间算法且无需外部见证，则属于 BQP。第三，若问题形如“是否存在一个对象使某量子验证者接受”，且对象可以是量子态，则属于 QMA；若对象必须是经典串，则属于 QCMA。第四，若问题形如“是否存在经典串使经典验证者接受”，则属于 NP。

判断时注意：BQP 的验证过程是量子的，但没有外部见证；QCMA 有经典见证但验证过程是量子的；QMA 的见证和验证都是量子的。三者的区别不在“是否量子”，而在“谁提供见证、见证是什么形态”。

以整数分解为例：输入为合数 N，问是否存在因子 p ∈ (1, N)。经典上属于 NP ∩ co-NP，但不知是否属于 P。Shor 算法给出多项式时间量子算法，因此该问题属于 BQP。这里没有外部见证，验证者自己完成全部计算。再以局部哈密顿量问题为例：输入为哈密顿量 H 和阈值 a，问基态能量是否 ≤ a。验证者收到一个量子态 |ψ⟩，测量其能量，若 ≤ a 则接受。由于最优见证是量子态，该问题属于 QMA，且是 QMA-完全的。

理解这些类的定义与相互关系，是后续讨论量子优势、资源估算和误差纠正的前提。电路模型与 QTM 提供计算模型，BQP、QMA、QCMA 提供复杂度刻度，二者结合才能回答“量子计算机到底能多快解决什么问题”。