Quote

All of you readers should be familiar with the P v NP question. P is the set of problems efficiently solvable by a deterministic computer. NP are the problems for which there exists a witness that we can verify quickly. The polynomial-time hierarchy (PH) is the constant alternation generalization of NP that has played a major role in computational complexity So why don't we talk about the P vs PH question? That's just equivalent to P vs NP.

BQP is the the class of problem efficiently solved by a quantum computer. Since P sits in BQP which sits in PSPACE we can't prove outright any separations for BQP without separating P from PSPACE. We can though get an understanding of complexity by allowing the machines access to the same oracle and seeing what we can separate. We already knew BQP doesn't sit in NP relative to an oracle. Same was true for BPP (efficient probabilistic computation) but BPP is in PH for all oracles as are constant round interactive proofs. So we might expect we can have BQP in PH, BQP solvable with constant alternations, relative to all oracles. Raz and Tal refute that hypothesis.

BQP is the the class of problem efficiently solved by a quantum computer. Since P sits in BQP which sits in PSPACE we can't prove outright any separations for BQP without separating P from PSPACE. We can though get an understanding of complexity by allowing the machines access to the same oracle and seeing what we can separate. We already knew BQP doesn't sit in NP relative to an oracle. Same was true for BPP (efficient probabilistic computation) but BPP is in PH for all oracles as are constant round interactive proofs. So we might expect we can have BQP in PH, BQP solvable with constant alternations, relative to all oracles. Raz and Tal refute that hypothesis.

Link: https://blog.computa...erarchy-in.html

Scott Aaronson's take on the problem is also a worthwhile read: https://www.scottaar...om/blog/?p=3827