Skip to main content
added 341 characters in body
Source Link
Mark Spinelli
  • 14.4k
  • 3
  • 24
  • 78

Indeed I think it follows from (1) showing that evaluating the Jones polynomial is (Promise) BQPBQP-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., whether 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 BQPPromiseBQP-completeComplete.

Thus, if evaluatingbecause the Jones polynomial was in the polynomial hierarchy PHis BQP-Complete, then there is a reduction from the forrelationany problem in BQP (such as forrelation) to evaluating the evaluation of some Jones polynomial that was also in. Hence, we can relate forrelation to this evaluation, and use AJL's BQP algorithm to evaluate the Jones polynomial hierarchy PHas a vehicle to evaluate the forrelation, which is whatbut we can't evaluate the forrelation in PH because that was ruled out by Raz and Tal. Thus the particular Jones polynomial related to forrelation cannot be evaluated in PH, and therefore evaluating the Jones polynomial is in BQP but not in PH.


This is all rough intuition and imprecise intuition about reductions 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. For me at least these require some effort to be particularly correct about, and I often get tripped up into the precise way to make the statements.!

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.

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., whether the Fourier transform of $f$ is correlated with $g$) 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 PromiseBQP-Complete.

Thus, because the Jones polynomial is BQP-Complete, there is a reduction from any problem in BQP (such as forrelation) to the evaluation of some Jones polynomial. Hence, we can relate forrelation to this evaluation, and use AJL's BQP algorithm to evaluate the Jones polynomial as a vehicle to evaluate the forrelation, but we can't evaluate the forrelation in PH because that was ruled out by Raz and Tal. Thus the particular Jones polynomial related to forrelation cannot be evaluated in PH, and therefore evaluating the Jones polynomial is in BQP but not in PH.


This is all rough and imprecise intuition about reductions 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. For me at least these require some effort to be particularly correct about, and I often get tripped up into the precise way to make the statements!

Source Link
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.