5 ms·
BQP Not in the Polynomial-Time Hierarchy in Relativized Worlds
- zitterbewegung 8y agoSo from my casual reading of the Blog post and Paper BQP is now proven to have sets of problems that aren't efficiently solvable from classical computers?
- thebzax 8y agoUnfortunately, not quite. Note from the blog post that "Since P sits in BQP which sits in PSPACE we can't prove outright any separations for BQP without separating P from PSPACE". We still haven't proven P isn't equal to PSPACE. What BQP does efficiently solve, which classical computers do not, is a particular "Promise Problem" of the form "Input X is either of type A, B, or C, please classify it as either A or B". The promise is that I won't give you any inputs of type C, but you don't know how to tell if I break the promise. Note also that >> "In particular, it has been shown there exist languages A and B such that P^A=NP^A and P^B≠NP^B (Baker, Gill, and Solovay 1975). The fact the P = NP question relativizes both ways is taken as evidence that answering this question is difficult, because a proof technique that relativizes (i.e., unaffected by the addition of an oracle) will not answer the P = NP question. Most proof techniques relativize." from https://en.wikipedia.org/wiki/Oracle_machine#Complexity_classes_of_oracle_machines https://en.wikipedia.org/wiki/Oracle_machine#Complexity_clas...
- zitterbewegung 8y agoYea, Its been awhile since I studied quantum computation. Thanks!
- selimthegrim 8y agoThis thread by Henry Yuen puts this in context well: https://twitter.com/henrytcs/status/1002233325514194944 https://twitter.com/henrytcs/status/1002233325514194944
- tonymillion 8y agoThat title looks like it was written by a markov chain