BQP

計算けいさん複雑ふくざつ性せい理論りろんにおいて、BQPとは、量子りょうしコンピュータによって誤あやまり確かく率りつが高々たかだか1/3で多項式たこうしき時間じかんで解とける決定けってい問題もんだいの複雑ふくざつ性せいクラスである。Bounded-error Quantum Polynomial time の頭文字かしらもじをとったものである。ある問題もんだいがBQPに属ぞくすなら、高たかい確かく率りつで正答せいとうを返かえし、多項式たこうしき時間じかんで実行じっこう可能かのうな、量子りょうしコンピュータのためのアルゴリズムが存在そんざいする。そのアルゴリズムは解かいがYESのときもNOのときも最大さいだいで1/3の確かく率りつで間違まちがった答こたえを返かえす。

BPPと同おなじように、定義ていぎの1/3というのは0以上いじょう1/2未満みまんの任意にんいの定数ていすうである。その定数ていすうが変化へんかしてもBQPは変化へんかしない。

他たの計算けいさん量りょうクラスとの関係かんけい

このクラスは量子りょうしコンピュータのために定義ていぎされたもので、古典こてんコンピュータ（または、ランダムな挙動きょどうを許ゆるしたチューリングマシン）に自然しぜんな対応たいおうをするクラスはBPPである。

BQPはPとBPPを含ふくみ、PPとPSPACEに含ふくまれる。 まとめると以下いかのような関係かんけいがある。

${\mbox{P}}\subseteq {\mbox{BPP}}\subseteq {\mbox{BQP}}\subseteq {\mbox{PP}}\subseteq {\mbox{PSPACE}}$

BQPとNPの関係かんけいについては、2010年代ねんだいころより、NPを含ふくむPHにBQPが含ふくまれない、ということを示唆しさする結果けっかがいくつか示しめされてきている。