BQP
このクラスは量子コンピュータのために定義されたもので、古典コンピュータ(または、ランダムな挙動を許したチューリングマシン)に自然な対応をするクラスはBPPである。
BQPはPとBPPを含み、PPとPSPACEに含まれる。 まとめると以下のような関係がある。
P ⊆ BPP ⊆ BQP ⊆ PP ⊆ PSPACE {\displaystyle {\mbox{P}}\subseteq {\mbox{BPP}}\subseteq {\mbox{BQP}}\subseteq {\mbox{PP}}\subseteq {\mbox{PSPACE}}}
BQPとNPの関係については、2010年代ころより、NPを含むPHにBQPが含まれない、ということを示唆する結果がいくつか示されてきている。