量子计算复杂度理论：BQP、量子图灵机与复杂性类

工程视角：造出更多、更好的量子比特
理论视角：这些量子比特在「可计算性地图」上能推到哪一格
→ 复杂度理论决定「量子优势」的边界与方向

没有复杂度理论：
  无法判断某个声称的加速是真加速，还是隐藏了指数量级的资源开销
  无法区分「算法没写好」与「问题本身做不到」

1. 上界：某个问题能否用多项式资源的量子算法解决？（BQP 成员资格）
2. 下界：某类问题至少需要多少资源？（查询复杂度、线路下界）
3. 关系：量子类比经典类大多少？（P vs BQP、BQP vs PH）
→ 上界决定「能做到什么」，下界决定「不可能做到什么」

- 判断加速真伪：忽略输入/输出开销的「量子加速」常是伪加速
- 判断问题选择：BQP 内的问题才可能有通用量子加速
- 判断路线：容错量子计算与 NISQ 的复杂度承诺完全不同
→ 复杂度理论是「量子算法选型」的第一道过滤器

经典图灵机（TM）：
  一条无限纸带 + 读写头 + 有限状态控制
  一步 = 读一格、写一格、左右移动
  资源 = 时间（步数）+ 空间（用到的格数）

概率图灵机（PTM）：
  允许抛硬币（随机转移）
  资源相同，但接受判据改为「概率 ≥ 2/3」
→ 随机性是经典计算的一等公民

量子线路模型：
  初始态 |0...0⟩
  施加一系列酉门（单比特 + 双比特 + 测量）
  资源 = 门数（时间）+ 比特数（空间）
  → 工程上最常用，直接对应硬件

量子图灵机（QTM）：
  纸带状态改为量子态，转移函数为酉矩阵
  读写头位置也处于叠加
  资源 = 步数 + 格数
  → 理论上最自然，便于定义复杂度类

Church-Turing 式的信念（量子版）：
  任何「合理」的量子计算模型之间只差多项式因子
  线路 ↔ QTM ↔ 绝热 ↔ 拓扑 ↔ 量子行走
→ 复杂度类不依赖模型选择，BQP 是「模型无关」的

线路 → QTM：
  用纸带的一段编码每个比特的振幅
  每个门 = 一段固定的酉操作序列（有限状态控制）
  开销：多项式倍（门的通用门集合有限，需编译）

QTM → 线路：
  把 T 步演化展开成 T 个受控酉算符
  每个算符用通用门集合近似到精度 ε
  开销：多项式 × polylog(1/ε)
→ 双向多项式等价

单比特 + CNOT 已经「通用」：可近似任意酉
常用集合：
  {H, T, CNOT}         —— 容错友好（Clifford + T）
  {H, S, CNOT, T}      —— 工业实现常用
  {Rz(θ), Ry(θ), CNOT} —— 变分算法常用（连续参数）

Solovay-Kitaev 定理：
  任意单比特酉可用 O(log^c(1/ε)) 个门近似
→ 通用性是「多项式开销」的保证

P     ：确定性多项式时间可解
NP    ：解可在多项式时间内被验证
BPP   ：随机多项式时间可解（错误概率 ≤ 1/3）
PSPACE：多项式空间可解（时间不限）
→ 已知包含链：P ⊆ NP ⊆ PSPACE，P ⊆ BPP ⊆ PSPACE

BQP  ：有界错误量子多项式时间（本文主角）
QMA  ：量子版的 NP（量子见证 + 量子验证者）
QIP  ：量子交互证明（= PSPACE，已被证明）
→ 量子类与经典类的交叠关系是核心研究课题

1. BQP 是否严格大于 BPP？（量子是否真的更强）
2. NP 是否包含在 BQP 内？（普遍相信不包含）
3. BQP 是否包含在 PH 内？（是否「不在多项式谱系之外」）
→ 三个问题全都未解，这正是复杂度理论的前沿

语言 L ∈ BQP，若存在多项式规模的量子线路族 {Q_n}，使得：
  1. x ∈ L  → Pr[Q_{|x|} 接受 x] ≥ 2/3
  2. x ∉ L  → Pr[Q_{|x|} 接受 x] ≤ 1/3
  3. 线路规模 poly(|x|)，深度 poly(|x|)
→ 「有界错误」+「多项式资源」，与 BPP 的定义完全平行

重复运行 k 次 + 多数表决：
  错误概率从 1/3 降到 2^(-Ω(k))
→ 2/3 与 1/3 之间的间隙可任意拉大
  （这是「有界错误」定义的稳健性来源）

- 补集封闭：L ∈ BQP ⟺ ¬L ∈ BQP（因为接受/拒绝判据对称）
- 多项式时间归约封闭
- 允许辅助比特（辅助比特不增加算力）
- 允许中间测量（延迟测量原理）
→ BQP 是一个「行为良好」的复杂度类

P ⊆ BPP ⊆ BQP ⊆ PSPACE
         ↑
    量子在这里

BQP ⊆ PP（概率多项式时间，允许无界错误）
BQP ⊆ AWPP（一个更精细的类）
→ 上界收得很紧，但都不是「严格」的

证明 P ≠ BQP 需要：
  找到一个在 BQP 内但不在 BPP 内的问题
  → 但连 P ≠ PSPACE 都还没证明
  → 分离问题被「卡」在同一个障碍上

相对化障碍（Relativization）：
  存在神谕 A 使 BQP^A ⊄ BPP^A，也存在神谕使二者相等
  → 任何「相对化」的证明技术都不可能分离它们
→ 必须用非相对化技术，这是核心难点

1. 查询复杂度分离：已有严格的量子-经典分离（见第 8 章）
2. 采样问题分离：玻色采样、IQP 线路的「采样优势」
3. 结构性问题：某些代数问题疑似在 BQP 之外
→ 「采样问题」是目前最接近严格分离的前沿

定义：语言 L ∈ QMA，若存在多项式规模量子线路 V（验证者），使得
  x ∈ L  → ∃ 量子见证 |w⟩，Pr[V 接受] ≥ 2/3
  x ∉ L  → ∀ 量子见证 |w⟩，Pr[V 接受] ≤ 1/3
→ 「存在一个量子态能说服验证者」，对应经典 NP 的「存在一个证书」

Local Hamiltonian Problem（局部哈密顿量问题）：
  给定 k-局部哈密顿量 H 与阈值 a < b，
  判断基态能量 E0 ≤ a 还是 E0 ≥ b
  → QMA 完全（Kitaev 定理）
→ 这是量子化学模拟「困难性」的理论根源

QIP：验证者与证明者之间允许量子通信的多轮交互
里程碑结果：QIP = PSPACE
  → 量子交互不增加超过经典交互（PSPACE）的能力
  → 但证明技术本身极其深刻（用到了量子纠缠的性质）

奇偶性下界 Θ(N)：
  说明「量子并非对一切函数都快」——结构决定加速
  → 量子算法只能利用「全局的、干涉友好的」结构

查询下界 ⇒ 时间下界（在查询模型内）：
  时间 ≥ 查询次数，因此查询下界是时间下界的最强工具
→ 但查询模型的下界不直接等于线路模型的下界（需额外论证）

核心思想：
  量子算法查询 t 次后，接受概率是各输入比特的「多项式」
  多项式的次数 ≤ 2t
  → 若目标函数不能用低次多项式近似，则查询下界成立

经典应用：
  OR 函数的 Ω(√N) 下界
  对称函数的量子查询下界
→ 最成功、最通用的量子下界工具

核心思想：
  构造两组「难区分」的输入（好实例 + 坏实例）
  量子算法每次查询只能「区分一点点」
  累加后得到下界

两个版本：
  一般对抗法：给下界，但需解一个半正定规划
  负权对抗法：更紧，是 Grover 下界的最优证明
→ 与多项式方法互补，覆盖不同函数

1. 渐近优势：某个问题族上 BQP 严格快于 BPP（理论上）
2. 采样优势：在特定采样任务上「经典难以模拟」（实验上）
3. 实用优势：在真实业务上更快更省（工程上）
→ 三者完全不同，媒体常把它们混为一谈

判断一个「量子加速」声称是否可信：
  □ 输入制备（态准备）的代价算进去了吗？
  □ 输出读出（层析/采样）的代价算进去了吗？
  □ 对比的经典基线是最优的吗？
  □ 问题在 BQP 内，还是只借用了「模拟困难」？
→ 忽略输入/输出的加速大多是「量子优势幻觉」

容错量子计算（FTQC）：
  承诺 BQP 的完整能力（Shor、相位估计、HHL）
  代价：需成千上万个物理比特编码一个逻辑比特

NISQ（含噪中等规模量子）：
  没有复杂度类级别的严格承诺
  优势来自「启发式 + 采样」，需实验逐案验证
→ 复杂度理论对 NISQ 几乎「不背书」