BQP
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2026/02/15 03:32 UTC 版)
計算複雑性理論において、BQP（Bounded-error Quantum Polynomial time）とは、問題の計算の難しさを分類する枠組みの一つであり、量子コンピュータによって多項式時間で解くことができ、かつ誤り確率を一定以下に抑えられる決定問題（答えが「はい」または「いいえ」で与えられる問題）のクラスを指す。
ある問題がBQPに属するとは、その問題に対して量子コンピュータ上で多項式時間に実行でき、正解を高い確率で出力するアルゴリズムが存在することを意味する。
このとき誤り確率は最大で1/3と定められるが、計算を繰り返して多数決をとることで誤り確率は任意に小さくできるため、この値自体に特別な意味はない。そのため、定義に用いる誤り確率は0以上1/2未満の任意の定数に変更しても、複雑性クラスBQPの範囲は変わらない。
他の計算量クラスとの関係
このクラスは量子コンピュータのために定義されたもので、古典コンピュータ（または、ランダムな挙動を許したチューリングマシン）に自然な対応をするクラスはBPPである。
BQPはPとBPPを含み、PPとPSPACEに含まれる。 まとめると以下のような関係がある。
-
一覧・
カテゴリ
|
|
|||||||||
|---|---|---|---|---|---|---|---|---|---|
| 全般 | |||||||||
| 定理 | |||||||||
| 量子通信 |
|
||||||||
| 量子アルゴリズム |
|
||||||||
| 量子複雑性理論 | |||||||||
| 量子プロセッサベンチマーク | |||||||||
| 量子計算モデル |
|
||||||||
| 量子誤り訂正 | |||||||||
| 物理的実装 |
|
||||||||
| 量子プログラミング言語 | |||||||||
- BQPのページへのリンク