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に含まれる。 まとめると以下のような関係がある。

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

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

表 話 編 歴 主な複雑性クラス
実用的な時間で解けるクラス	DLOGTIME AC0 ACC0 TC0 L SL RL NL NC SC CC P P完全 ZPP RP BPP BQP APX
実用的な時間で解けないと疑われているクラス	UP NP NP完全 NP困難 co-NP co-NP完全 AM QMA PH ⊕P PP #P #P完全 IP PSPACE
実用的な時間では解けないクラス	EXPTIME NEXPTIME EXPSPACE ELEMENTARY PR R RE ALL
クラス階層	多項式階層 指数階層 グジェゴルチク階層 算術的階層 ブーリアン階層
クラスの族	DTIME NTIME DSPACE NSPACE PCP 対話型証明系
一覧・ カテゴリ