What is the fastest $f(n)$ the relatively new result of oracle separation of $\mathsf{BQP}$ from $\mathsf{PH}$ provides such that ${\#\mathsf{SAT}}\not\subseteq\mathsf{FP}^{\mathsf{PH}[O(f(n))]}$ holds where $n$ is number of inputs to $\mathsf{SAT}$ formula (note $\mathsf{BQP}\subseteq\mathsf{PP}$) (here $\mathsf{FP}^{\mathsf{PH}[O(f(n))]}$ refers to $\mathsf{FP}$ with oracle access to ${\mathsf{PH}[O(f(n))]}$)? Is $f(n)=O\Big(\frac{n}{\log n}\Big)$ (comments in https://blog.computationalcomplexity.org/2018/06/bqp-not-in-polynomial-time-hierarchy-in.html seems to indicate such a bound on $f(n)$ however was not sure)?
What would be the consequence if indeed $\mathsf{PP}$ and/or $\#\mathsf{SAT}$ are/is in $\mathsf{PH}[O(\log n)]$ and $\mathsf{FP}^{\mathsf{PH[O(\log n)]}}$ respectively? Would it nullify the $\mathsf{BQP}$ versus $\mathsf{PH}$ result of Raz and Tal (it could still be $\mathsf{BQP}\not\subseteq\mathsf{PH}$ is true but the evidence achieved will be falsified) and the result Robin Kothari is quoting? Would it have other consequences?
-
$\begingroup$ The oracle notation is conflicting with the PH notation here. Typically $A^{B[f(n)]}$ means A with a B oracle, making at most f(n) queries. But I think you still want it to be number of alternation of quantifiers (right?). Not sure of a better notation, but it'd help to clarify it in the text. $\endgroup$– Joshua GrochowMay 19, 2019 at 2:17
-
$\begingroup$ @JoshuaGrochow Yes number of quantifiers. Perhaps $[[]]$ or leave it that way since if we are calling $\mathsf{PH}$ generically is meaningless and if we call $f(n)$ queries we may say $\mathsf{FP}^{\mathsf{PH}[O(\log n)][f(n)]}$? $\endgroup$– TurboMay 19, 2019 at 2:24
1 Answer
If you just want oracle separations with $\#P$, you don't need to use the new result of Raz and Tal. You can use the classic Parity/Majority not in $AC^0$ results from the 1980s.
For example, the strongest quantitative version of Parity not in $AC^0$ says that the $n$-bit Parity function cannot be computed by a quasi-polynomial size $AC^0$ circuit of depth $o(\log n/ \log\log n)$. So scaling this up, we get an oracle separation between $\oplus P$, which is in $\# P$, and $PH$ with $o(n/\log n)$ quantifiers.