Note: Cross-posted on Theoretical Computer Science SE.

This question is inspired by thinking about quantum computing power with respect to games, such as chess/checkers/other toy games. Games fit naturally into the polynomial hierarchy $\mathrm{PH}$; I'm curious about follow-up questions.

Every Venn diagram or Hasse diagram I see illustrating the "standard model" of computational complexity describes a universe of $\mathrm{PSPACE}$ problems, and puts $\mathrm{BQP}$ into a position containing all of $\mathrm{P}$, and not containing all of $\mathrm{NP}$, but cutting through to outside of the polynomial hierarchy $\mathrm{PH}$. That is, such Venn diagrams posit that there are likely problems efficiently solvable with a quantum computer that are outside of $\mathrm{PH}$.

But how does this "cut through?"

That is, does this imply that there must be a $\mathrm{BQP}$ problem in the first level of the hierarchy, one in the second level of the hierarchy, one in the third level $\cdots$, and one such as "forrelation" (correlation of Fourier series) completely outside of the hierarchy?

Or could it be that there are some $\mathrm{BQP}$ problems in the first level of the hierarchy, some outside of the hierarchy, and an infinite number of levels of the hierarchy that are voided of any $\mathrm{BQP}$ problems?

Quanta Magazine Article

See, e.g., the above picture from the Quanta Magazine article "Finally, a Problem that Only Quantum Computers Will Ever Be Able to Solve" link. Could $\mathrm{BQP}$ be disconnected between $\mathrm{NP}$ and the island outside of $\mathrm{PH}$? Or must there be a bridge over $\mathrm{PH}$ connecting the two?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.