- For a time t QTM M, we have a GapP f such that prob that M accepts is f/52t.
- If L is in BQP via QTM M then for all x,
- If x is in L then Pr(M(x) accepts) > 2/3 so f/52t > 2/3.
- If x is not in L then Pr(M(x) accepts) < 1/3 so f/52t < 1/3.

- Let g = 52t.

Previous slide | Next slide | Back to the first slide | View Graphic Version |