Relation between BQP-Complete and BQP \ PH

Question

Recently, the oracle separation between BQP and PH has been proven. Does this result tell us something about the relation between BQP-complete problems (e.g. approximation Jones polynomial solved by AJL algorithm) and BQP\PH? In particular, is the latter included in the former?

Answer 1

Let me abstract the question a bit. We have two complexity classes: $\mathrm{C}=\mathrm{BQP}$ and $\mathrm{D} = \mathrm{PH}$, as well as a promise problem $A$ that's complete for $\mathrm{C}$. We also have an oracle relative to which $\mathrm{C}$ is not contained in $\mathrm{D}$. If I'm understanding the question correctly, it's asking if we can conclude that $A$ is not contained in $\mathrm{D}$. Certainly we cannot, which shouldn't come as a surprise given that even proving that computing the Jones polynomial is outside of $\mathrm{P}$ would separate $\mathrm{P}$ from $\mathrm{BQP}$.

So, nothing that we currently know definitively rules out the possibility that approximating the Jones polynomial is in $\mathrm{PH}$. What we can say is that if computing the Jones polynomial is in $\mathrm{PH}$, then $\mathrm{BQP} \subseteq \mathrm{PH}$, so if this containment is not true then obviously computing the Jones polynomial is not in $\mathrm{PH}$ — but this conclusion is independent of any oracle separations. We can also say that if it were to be proved that $\mathrm{BQP} \subseteq \mathrm{PH}$, by this or any other method, then it would necessarily be a so-called non-relativizing proof, meaning one that fails to work when the underlying machines are able to make oracle queries.

However, this is not so far fetched. For an actual counter-example, take $\mathrm{C}=\mathrm{PSPACE}$, $\mathrm{D} = \mathrm{IP}$ (problems with interactive proof systems), and $A = \mathrm{QBF}$ (the quantified Boolean formula problem). There is an oracle (due to Fortnow and Sipser) relative to which $\mathrm{PSPACE}$ is not contained in $\mathrm{IP}$ (and in fact even $\mathrm{co}$-$\mathrm{NP}$ is not contained in $\mathrm{IP}$), but nevertheless $\mathrm{QBF}$ is contained in $\mathrm{IP}$ (as proved by Shamir). What exactly is the non-relativizing technique here? In essence it comes from the Cook-Levin theorem, which leads to the completeness of $\mathrm{QBF}$ for $\mathrm{PSPACE}$. In short, Boolean formulas don't make oracle queries.

But the same basic ideas (with a lot of added detail) are at play when showing that approximating the Jones polynomial is complete for $\mathrm{BQP}$. In particular, as far as I know there's no known reduction from an oracle problem like forrelation to approximating the Jones polynomial. We can go gate by gate in a quantum circuit and construct braid diagrams and so on to prove that approximating the Jones polynomial is complete for $\mathrm{BQP}$ — but how do you get queries to an oracle to be properly reflected in this process?

Answer 2

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!}