更新时间：2022-08-25 16:31
在计算复杂性理论中，BQP（bounded-error quantum polynomial time）是量子计算机在多项式时间内可以解决的一类决策问题，所有实例的错误概率至多为1/3。它是复杂类BPP的量子类比。
也可以被看作与某些有界误差统一的量子电路系列相关的语言。 当且仅当存在多项式时间统一的量子电路族{ ： }时，语言L在中，使得
对于全部 ， 取 个比特作为输入并输出1比特;
对于L中的所有x， ;
对于L中的所有x， .
计算机中的量子比特数允许为实例大小的多项式函数。 例如，已知用仅超过2n个量子位（Shor算法）来分解n位整数的算法。
通常，量子计算机上的计算以测量结束。 这导致量子态向基态的崩溃。 可以说量子态被测量的概率很高，处于正确的状态。
量子计算机已经引起了广泛的兴趣，因为已知一些实际感兴趣的问题在中，但被怀疑在之外。一些突出的例子是：
a.整数因子分解（参见Shor算法）;
b.离散对数;
c.量子系统的模拟（见通用量子模拟器）;
d.在统一的某个根逼近琼斯多项式;
该类是为量子计算机定义的，其普通计算机(或图灵机加随机源)的自然对应类是 。就像 和 一样, 本身就很低，这意味着 = 。非正式地说，这是因为多项式时间算法在组合下是闭合的。如果一个多项式时间算法作为子程序调用多项式多项式时间算法，则所得到的算法仍然是多项式时间。
包含 和 ，并包含在 ， 和 中。事实上， 对于 来说是低的，这意味着PP机器不能立即解决 问题，这表明这些相似类别之间可能存在差异。
由于 的问题还没有解决， 和上述类别之间不平等的证明应该是困难的。 和 之间的关系尚不清楚。
将后期选择添加到 会导致复杂性类Post 于 。