量子复杂性理论

量子复杂性理论（Quantum complexity theory）是理论计算机科学中计算复杂性理论的一部分。该理论使用量子计算机和量子信息来研究分析复杂性类定义，量子信息是基于量子力学的计算模型。量子复杂性理论用来研究这些复杂性类的问题的困难度，和量子复杂性类与经典（非量子的）复杂性类的关系。

复杂性类是指的是一群复杂度类似的问题的集合，可以用满足特定资源限制下的算法求解。例如复杂性类P就是可以用图灵机在多项式时间内求解的问题。也可以用量子算法（如量子计算机或量子图灵机）定义量子复杂性，例如复杂度BQP就是可以用量子计算机在多项式时间内解决，其错误的几率小于一定比例的问题。

量子复杂性中二个比较重要的复杂性类分别是BQP及QMA（英语：QMA），分别对应复杂度P及NP (复杂度)。量子复杂性理论的一个主要目的是要找到对应传统复杂性类（如P、NP、PSPACE、PP等）的量子复杂性。