BQP
出典: フリー百科事典『ウィキペディア（Wikipedia）』
計算複雑性理論において、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に含まれる。 まとめると以下のような関係がある。
BQPとNPの関係は解っていない。
 |
この項目「BQP」は、数学に関連した書きかけの項目です。加筆・訂正などをして下さる協力者を求めています。（ポータル 数学／ウィキプロジェクト 数学） |
