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])

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

Back to tossups

Summary

2024 ACF Nationals2024-04-21Y2162%0%24%106.77

Buzzes

PlayerTeamOpponentBuzz PositionValue
Simon GorbatyDukeClaremont Colleges3110
Mattias EhatammWaterlooIndiana8610
John MarvinChicago BColumbia A9810
Skand ParvatikarArizona StateFlorida9910
Matt JacksonChicago AWUSTL A10210
Andrew SalijNorthwesternBerkeley A109-5
Vincent DuNorth Carolina ATexas10910
Asha BasuMcGillMinnesota B11210
Rasheeq AzadNorth Carolina BVanderbilt11210
William HoustonChicago DBerkeley B120-5
Michal GerasimiukStanfordCornell A12110
Eylon CaplanPurdueMinnesota A121-5
Liam StarnesChicago CTruman State125-5
Sky LiToronto AMichigan128-5
Isaac MammelMarylandBrown12910
Jack ObermanSouth CarolinaKentucky12910
Swapnil GargBerkeley ANorthwestern13010
Fred GarveyTruman StateChicago C1300
Jacob Hardin-BernhardtNYUIllinois1300
Andrew WangIllinoisNYU1300
Joel MilesMinnesota APurdue1300
Jeremy CummingsWUSTL BRutgers1300
Aum MundheRutgersWUSTL B1300
Yashwanth BajjiMichiganToronto A1300
Jason ZhangToronto BVirginia1300
Kenny ZhangVirginiaToronto B1300
Seth EbnerJohns HopkinsYale A13010
Lydia TarekegnYale BOttawa1300
Adrian WongOttawaYale B1300