AWPP contains BQP
AWPP contains BQP
- 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.