BQPのソースを表示

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

[[BPP (計算複雑性理論)|'''BPP''']]と同じように、定義の1/3というのは0以上1/2未満の任意の定数である。その定数が変化しても'''BQP'''は変化しない。

== 他の計算量クラスとの関係 ==
このクラスは量子コンピュータのために定義されたもので、古典コンピュータ（または、[[ランダム]]な挙動を許した[[チューリングマシン]]）に自然な対応をするクラスは'''BPP'''である。

'''BQP'''は[[P (計算複雑性理論)|'''P''']]と'''BPP'''を含み、[[PP (計算複雑性理論)|'''PP''']]と'''[[PSPACE]]'''に含まれる。
まとめると以下のような関係がある。
:<math>\mbox{P} \subseteq \mbox{BPP} \subseteq \mbox{BQP}\subseteq \mbox{PP} \subseteq \mbox{PSPACE}</math>

'''BQP'''と'''[[NP]]'''の関係については、2010年代ころより、NPを含む[[PH (計算複雑性理論)|PH]]にBQPが含まれない、ということを示唆する結果がいくつか示されてきている。

{{複雑性クラス}}
{{量子情報}}

{{DEFAULTSORT:ひいきゆうひい}}
[[カテゴリ:複雑性クラス]]
[[カテゴリ:確率的複雑性クラス|BQP]]
[[カテゴリ:量子コンピューティング|BQP]]
[[カテゴリ:量子複雑性理論|BQP]]
[[カテゴリ:数学に関する記事|BQP]]