9

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?

Mark Spinelli
  • 11,947
  • 2
  • 19
  • 65
  • I find it quite a natural and interesting problem. Is it possible to make this post accessible to cs.theory.se? We can hope for an answer/pointer from them. – Manish Kumar Mar 27 '24 at 10:26
  • You're free to generalize the question and ask over there - you can point to this question here but otherwise it's generally bad form to forum shop and cross-post. If you do post a related question over on cstheory then I recommend changing the wording of the question to say something like "how does the Fourier hierarchy in BQP relate to the polynomial hierarchy PH" or something... – Mark Spinelli Mar 27 '24 at 16:33
  • I will try the tips. Thanks! – Manish Kumar Mar 27 '24 at 19:43

0 Answers0