5
$\begingroup$

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?

$\endgroup$

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.