BPP

クラスBPP

$ϵ$: PPTで判定した時に間違えてしまう確率
Poly乱択アルゴリズムで $ϵ\le \frac{1}{3}$
判定を $n$ 回もやることで $ϵ\le (\frac{1}{3}{)}^n$ に下げる事ができる

参考文献

• 決定性チューリング機械から量子チューリング機械へ
• www.math.cm.is.nagoya-u.ac.jp/~hnishimura/kyudai_qclass.pdf