量子回路
そのため
Tr  ( S U ∗ E F ( x )  U ) ≥ 1 − ε − δ . {\displaystyle \operatorname {Tr} (SU^{*}\operatorname {E} _{F(x)}U)\geq 1-\epsilon -\delta .}
定理 もしε+δ<1/2であるならば、Y上の確率分布
Pr  { y } = Tr  ( S U ∗ E y  U ) {\displaystyle \operatorname {Pr} \{y\}=\operatorname {Tr} (SU^{*}\operatorname {E} _{y}U)}
は、十分に大きなサンプルサイズに対して、多数決サンプリングによって誤差の確率が任意に小さいF(x)を決定できる。 具体的には、 Y上の確率分布からk個の独立したサンプルを取得し、サンプルの半分以上が一致する値を選択する。 値F (x)がk / 2回以上サンプリングされる確率は少なくとも次式で表される。
1 − e − 2 γ 2 k , {\displaystyle 1-e^{-2\gamma ^{2}k},}
ただし、γ= 1/2-ε-δである。これはチェルノフ限界を適用することで得られる。