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 “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 is Simon’s problem. The discrete logarithm problem and the integer factorization problem belong to this class because they are solved by Shor’s algorithm. For 10 points, name this class of problems decidable in polynomial time by a quantum computer with bounded error probability. ■END■
ANSWER: BQP [accept BQP-complete; accept bounded-error quantum polynomial time until “time” is read] (PH is the polynomial hierarchy.)
<Other Science>
= Average correct buzz position