BQP
From Wikipedia, the free encyclopedia
計算複雑性理論において、BQP（Bounded-error Quantum Polynomial time）とは、問題の計算の難しさを分類する枠組みの一つであり、量子コンピュータによって多項式時間で解くことができ、かつ誤り確率を一定以下に抑えられる決定問題（答えが「はい」または「いいえ」で与えられる問題）のクラスを指す。
ある問題がBQPに属するとは、その問題に対して量子コンピュータ上で多項式時間に実行でき、正解を高い確率で出力するアルゴリズムが存在することを意味する。
このとき誤り確率は最大で1/3と定められるが、計算を繰り返して多数決をとることで誤り確率は任意に小さくできるため、この値自体に特別な意味はない。そのため、定義に用いる誤り確率は0以上1/2未満の任意の定数に変更しても、複雑性クラスBQPの範囲は変わらない。
