BQP

也可以被看作與某些有界誤差統一的量子電路系列相關的語言。 當且僅當存在多項式時間統一的量子電路族{

：

}時，語言L在

中，使得

對於全部

，

取

個比特作為輸入並輸出1比特;

對於L中的所有x，

;

對於L中的所有x，

.

計算機中的量子比特數允許為實例大小的多項式函數。 例如，已知用僅超過2n個量子位（Shor算法）來分解n位整數的算法。

通常，量子計算機上的計算以測量結束。 這導致量子態向基態的崩潰。 可以説量子態被測量的概率很高，處於正確的狀態。

量子計算機已經引起了廣泛的興趣，因為已知一些實際感興趣的問題在

中，但被懷疑在

之外。一些突出的例子是：

a.整數因子分解（參見Shor算法）;

b.離散對數;

c.量子系統的模擬（見通用量子模擬器）;

d.在統一的某個根逼近瓊斯多項式;

該類是為量子計算機定義的，其普通計算機(或圖靈機加隨機源)的自然對應類是

。就像

和

一樣,

本身就很低，這意味着

=

。非正式地説，這是因為多項式時間算法在組合下是閉合的。如果一個多項式時間算法作為子程序調用多項式多項式時間算法，則所得到的算法仍然是多項式時間。

包含

和

，幷包含在

，

和

中。事實上，

對於

來説是低的，這意味着PP機器不能立即解決

問題，這表明這些相似類別之間可能存在差異。

由於

的問題還沒有解決，

和上述類別之間不平等的證明應該是困難的。

和

之間的關係尚不清楚。

將後期選擇添加到

會導致複雜性類Post

於

^[1]  。