复杂度类 BQP

BQP（bounded-error quantum polynomial time）指存在多项式规模量子电路族以至少 $2/3$ 正确率求解的判定问题类，是量子版的 BPP。定义对通用门集的具体选择不敏感（Solovay–Kitaev 使不同通用集之间只有对数级转换代价）。

要点

• 已知包含关系：$\mathrm{P}\subseteq \mathrm{BPP}\subseteq \mathrm{BQP}\subseteq \mathrm{PP}$；$\mathrm{NP}$ 与 BQP 互不包含已知。因数分解与离散对数（Shor）属于 BQP，且 BQP 含 P 之外的问题（相对预言机意义上，如 Simon）。
• “BQP 完备”问题刻画该类的表达力：稀疏哈密顿量模拟的某些任务、矩阵幂对角元 与字符串重写 的路径计数等被证明 BQP 完备——这些结果常被用来论证”某问题的量子难度是本质的”。
• 输出模型敏感：对函数值输出（如 主特征向量）而非采样的问题，BQP 式优势要重新核算经典读出成本。
• 与 QMA（量子版的 NP 带证明）相区分：QMA 是验证类，BQP 是求解类；量子半定规划 等问题处于这些类的交界。

关联词条

• 概念：量子电路、通用量子门集、量子查询复杂度
• 算法：稀疏矩阵幂对角元、字符串重写量子算法

取材：量子计算概述、各 BQP 完备性词条。

参考文献

• E. Bernstein, U. Vazirani. Quantum Complexity Theory. SIAM J. Comput. 26, 1411 (1997). —— BQP 的定义文献.
• J. Watrous. Quantum Computational Complexity. arXiv:0804.3401 (2008). —— 综述.
• Nielsen & Chuang.《量子计算与量子信息》第 3 章（计算复杂度）.