4. 经典复杂度理论回顾与对比

在讨论量子计算能带来什么之前，必须先有一把“经典标尺”。复杂度类就是这把标尺：它按资源约束（时间、空间、随机性）把判定问题分门别类。本节回顾 P、NP、PSPACE、BPP 这几个最常用的经典类，再把 BQP、QMA 等量子类放进来，看它们之间的包含关系与分离证据。

一、四个经典类：定义与直觉

所有讨论都基于判定问题：输入为长度 n 的比特串，输出为“是/否”。资源以 n 的函数计量。

• P（多项式时间）：存在确定性图灵机，在 O(n^k) 步内判定。直觉是“能高效精确求解”。典型代表：排序、最短路、线性规划、素性判定（AKS）。
• NP（非确定性多项式时间）：若答案为“是”，存在一个多项式长度的证书，且能在多项式时间内验证该证书。注意 NP 不要求“求解容易”，只要求“验证容易”。典型代表：SAT、哈密顿回路、子集和。
• PSPACE（多项式空间）：存在图灵机在 O(n^k) 空间内判定，时间不限。空间可复用，因此 PSPACE 通常比 P 大得多。典型代表：QBF（量化布尔公式）、博弈胜负判定。
• BPP（有界错误概率多项式时间）：存在随机化多项式时间算法，对所有输入，错误概率 ≤ 1/3（可通过重复降到任意小）。直觉是“抛硬币也能高效求解”。典型代表：Miller–Rabin 素性测试、多项式恒等测试。

它们的基本包含链是：P ⊆ NP ⊆ PSPACE，且 P ⊆ BPP ⊆ PSPACE。NP 与 BPP 之间没有已知包含关系——随机性看起来既不能解决 NP 完全问题，也不被 NP 完全覆盖。

二、量子类：BQP 与 QMA

把“确定性图灵机”换成“量子电路”，就得到量子版本：

• BQP（有界错误量子多项式时间）：量子电路在多项式时间内以 ≤1/3 错误概率判定。对应经典 BPP 的量子类比。典型代表：整数分解（Shor）、非结构化搜索（Grover，平方加速）。
• QMA（量子 Merlin–Arthur）：量子版 NP，证书本身可以是量子态，验证者是量子电路。典型代表：局部哈密顿量问题（k-LOCAL HAMILTONIAN）是 QMA 完全的。

已知包含关系为：BPP ⊆ BQP ⊆ PSPACE，且 NP ⊆ QMA ⊆ PSPACE。BQP 与 NP 的关系同样未知：既不知道 NP ⊆ BQP，也不知道 BQP ⊆ NP。

三、包含关系与分离证据

“包含”是已证明的，“分离”几乎全是猜想。目前唯一被严格证明的分离是 P ≠ EXP（时间层级定理），而 P vs NP、BPP vs P、BQP vs BPP 都未解决。我们拥有的只是相对化证据与结构性证据：

• 相对化世界：存在使 P=NP 的谕示，也存在使 P≠NP 的谕示，说明对角化方法不足以解决 P vs NP。
• 电路下界：已证明某些函数需要指数级电路（如 PARITY 对 AC⁰），但这类下界尚未触及 NP。
• BQP 的边界：BQP ⊆ PP ⊆ PSPACE；若 BQP 能解决 NP 完全问题，则多项式层级会坍塌，这被广泛认为不太可能。
• BPP 与 P：若存在足够强的伪随机生成器，则 BPP = P；这是主流猜想，但未证明。

下面这张图把经典类与量子类的包含关系、已知边界和代表性完全问题放在同一张“复杂度地图”上，便于对照记忆。

四、对比要点与常见误区

把四类经典与两类量子放在一起，可以提炼出几条关键对比：

两个常见误区值得强调。第一，“量子一定比经典快”是错的：BQP 并不包含 NP，Shor 算法解决的是有特殊代数结构的分解问题，而非一般 NP 完全问题。第二，“BPP 就是 P”尚未证明：虽然去随机化猜想很流行，但严格证明仍缺失。理解这些边界，才能在后续资源估算中判断“量子优势”到底发生在哪一层。