Question

The approximation of Jones polynomials is “this complexity class complete.” This complexity class’s subroutine theorem proves that algorithms for promise problems in it can be queried as oracles. Scott Aaronson’s concept of (10[1])“forrelation” (“for-eh-LAY-shun”) was used to show that there is an oracle relative to which this complexity class is [emphasize] not a subset of PH. Upper bounds on this class can be established by tracing out computation trees as a sum over histories. The canonical problem used to show the oracle separation of this class and BPP (10[1])is Simon’s problem. The discrete logarithm problem and the integer factorization problem (10[1])belong (10[1])to this class (10[1])because they are solved by Shor’s algorithm. (10[1]-5[1])For 10 points, (10[2])name this class of problems decidable in polynomial (-5[1])time (10[1]-5[1])by a quantum computer (-5[1])with bounded error (-5[1])probability. (10[2])■END■ (10[2]0[11])

Back to tossups

Buzzes

Summary