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?

  • $\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 Grochow May 19 '19 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$ – 1.. 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.

  • $\begingroup$ Would you know 2. as well? $\endgroup$ – 1.. May 18 '19 at 7:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.