Skip to main content
1 of 2
Mark Spinelli
  • 14.4k
  • 3
  • 24
  • 78

Indeed I think it follows from (1) showing that evaluating the Jones polynomial is (Promise) BQP-complete, and (2) the existence of an oracle separation between BQP and the polynomial hierarchy PH, that (3) evaluating the Jones polynomial is not likely to be in PH. That is, evaluating the Jones polynomial is precisely in BQP\PH as you had proposed.

In detail, Raz and Tal had shown that the forrelation problem of deciding whether two Boolean functions $f$ and $g$ given by black-boxes are "forrelated" (e.g., the Fourier transform of $f$ is correlated with $g$ or vice-versa) is, as an oracle problem, outside not just P, not just NP, not just AM, but even outside the entirety of the polynomial hierarchy PH. But, previously Aharanov, Jones, and Landau had provided an algorithm showing that evaluating the Jones polynomial is itself BQP-complete.

Thus, if evaluating the Jones polynomial was in the polynomial hierarchy PH, then there is a reduction from the forrelation problem to evaluating the Jones polynomial that was also in the polynomial hierarchy PH, which is what was ruled out by Raz and Tal.


This is all rough intuition and relative to oracle separations and also with respect to promises about the gap between the forrelations of $f$ and $g$ and the accuracy of the Jones polynomial evaluation, both of which take some effort to be particularly correct about, and I often get tripped up into the precise way to make the statements.

Mark Spinelli
  • 14.4k
  • 3
  • 24
  • 78