BQP Not in the Polynomial-Time Hierarchy in Relativized Worlds

https://blog.computationalcomplexity.org/2018/06/bqp-not-in-polynomial-time-hierarchy-in.html

by EvgeniyZh • 8 years ago

45 5 8 years ago

blog.computationalcomplexity.org

So 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• 8 years ago

Unfortunately, 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_clas...

zitterbewegung2• 8 years ago

Yea, Its been awhile since I studied quantum computation. Thanks!

selimthegrim• 8 years ago

This thread by Henry Yuen puts this in context well: https://twitter.com/henrytcs/status/1002233325514194944

tonymillion• 8 years ago

That title looks like it was written by a markov chain

BQP Not in the Polynomial-Time Hierarchy in Relativized Worlds

Related Stories