# Lower bound on alternations needed in $BQP$ versus $PH$ result?

1. 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)?

2. 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?

• 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. – Joshua Grochow May 19 '19 at 2:17
• @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)]}$? – T.... May 19 '19 at 2:24

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.