[cross-posted on QCSE a couple of weeks ago]

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

But how does this "cut through?"

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

Or could it be that there are some $\mathsf{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 $\mathsf{BQP}$ problems, even in the "relativized" world?

Quanta Magazine Venn Diagram

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, which describes Raz and Tal's results on the forrelation problem of Aaronson and Aaronson/Ambainis. Could $\mathsf{BQP}$ be disconnected between $\mathsf{NP}$ and the island outside of $\mathsf{PH}$? Or must there be a bridge over PH connecting the two?

If the first case, could that imply that there is a game, that is played out on a $\mathsf{BQP}$ machine but not on a classical machine? Like a game based on forrelation, where the territory/points won by one player ("black") following one line is correlated with the Fourier transform of the counter-moves of the other player ("white")?

  • 3
    $\begingroup$ That's not the main point of your question, but... The Raz-Tal paper does not establish $\textsf{BQP} \not\subseteq \mathsf{PH}$, it gives an oracle separation. There exists $O$ such that $\textsf{BQP}^O \not\subseteq \mathsf{PH}^O$. $\endgroup$ – Clement C. Apr 14 at 5:03

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.