[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
  • $\begingroup$ @ClementC. If we assume that problems in the OP are asked in the relativized oracle world, then seemingly they make sense. $\endgroup$ – Lwins Apr 28 at 5:05
  • 1
    $\begingroup$ I suppose you are talking about the relativized world. Note that the Raz-Tal result is converted from that “there is a problem in QLOGTIME but not in AC0” via a “standard argument” (If you are not familiar with this, it will be helpful to read the beginning of Aaronson’s paper scottaaronson.com/papers/bqpph.pdf). One of your problems would likely to be “Is there a problem in QLOGTIME and depth-k AC0 but not in depth-(k+1) AC0?”. As for as I know it is not a direct corollary of the Raz-Tal result. $\endgroup$ – Lwins Apr 28 at 5:17
  • $\begingroup$ @Lwins I envision levels of the hierarchy as if there is a $2$ player game between $\exists$ and $\forall$, with the $2n^{th}$ level being a "mate-in-$n$" sort of statement. So I think of the question as "is there a game such that a quantum computer find a 'mate-in-$n$' faster than a classical computer?" If so, what would the game look like? The territory controlled by $\exists$ is correlated with the Fourier transform of the territory controlled by $\forall$? $\endgroup$ – Mark S Apr 28 at 21:59

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.