<p>If you just want oracle separations with <span class="math-container">$\#P$</span>, you don't need to use the new result of Raz and Tal. You can use the classic Parity/Majority not in <span class="math-container">$AC^0$</span> results from the 1980s. </p>

<p>For example, the strongest quantitative version of Parity not in <span class="math-container">$AC^0$</span> says that the <span class="math-container">$n$</span>-bit Parity function cannot be computed by a quasi-polynomial size <span class="math-container">$AC^0$</span> circuit of depth <span class="math-container">$o(\log n/ \log\log n)$</span>. So scaling this up, we get an oracle separation between <span class="math-container">$\oplus P$</span>, which is in <span class="math-container">$\# P$</span>, and <span class="math-container">$PH$</span> with <span class="math-container">$o(n/\log n)$</span> quantifiers.</p>

CC BY-SA 4.0
2019-05-18T07:06:10.487Z
Would you know 2. as well?
Turbo
CC BY-SA 4.0
2019-05-17T16:01:11.517Z
2019-05-17T16:01:11.517Z
Robin Kothari
<ol>
<li><p>What is the fastest <span class="math-container">$f(n)$</span> the relatively new result of oracle <a href="https://eccc.weizmann.ac.il/report/2018/107/" rel="nofollow noreferrer">separation of <span class="math-container">$\mathsf{BQP}$</span> from <span class="math-container">$\mathsf{PH}$</span></a> provides such that <span class="math-container">${\#\mathsf{SAT}}\not\subseteq\mathsf{FP}^{\mathsf{PH}[O(f(n))]}$</span> holds where <span class="math-container">$n$</span> is number of inputs to <span class="math-container">$\mathsf{SAT}$</span> formula (note <span class="math-container">$\mathsf{BQP}\subseteq\mathsf{PP}$</span>) (here <span class="math-container">$\mathsf{FP}^{\mathsf{PH}[O(f(n))]}$</span> refers to <span class="math-container">$\mathsf{FP}$</span> with oracle access to <span class="math-container">${\mathsf{PH}[O(f(n))]}$</span>)? Is <span class="math-container">$f(n)=O\Big(\frac{n}{\log n}\Big)$</span> (comments in <a href="https://blog.computationalcomplexity.org/2018/06/bqp-not-in-polynomial-time-hierarchy-in.html" rel="nofollow noreferrer">https://blog.computationalcomplexity.org/2018/06/bqp-not-in-polynomial-time-hierarchy-in.html</a> seems to indicate such a bound on <span class="math-container">$f(n)$</span> however was not sure)?</p></li>
<li><p>What would be the consequence if indeed <span class="math-container">$\mathsf{PP}$</span> and/or <span class="math-container">$\#\mathsf{SAT}$</span> are/is in <span class="math-container">$\mathsf{PH}[O(\log n)]$</span> and <span class="math-container">$\mathsf{FP}^{\mathsf{PH[O(\log n)]}}$</span> respectively? Would it nullify the <span class="math-container">$\mathsf{BQP}$</span> versus <span class="math-container">$\mathsf{PH}$</span> result of Raz and Tal (it could still be <span class="math-container">$\mathsf{BQP}\not\subseteq\mathsf{PH}$</span> is true but the evidence achieved will be falsified) and the result Robin Kothari is quoting? Would it have other consequences? </p></li>
</ol>

CC BY-SA 4.0
2019-05-19T02:17:25.443Z
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
CC BY-SA 4.0
2019-05-19T02:24:10.750Z
@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)]}$?
Turbo
<cc.complexity-theory><quantum-computing><big-picture><oracles><polynomial-hierarchy>
Lower bound on alternations needed in $BQP$ versus $PH$ result?
Turbo
# Lower bound on alternations needed in $BQP$ versus $PH$ result?

(Asked by: username_0 on 2019-05-17)

1. What is the fastest $f(n)$ the relatively new result of oracle [separation of $\mathsf{BQP}$ from $\mathsf{PH}$](https://eccc.weizmann.ac.il/report/2018/107/) 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 username_2 is quoting? Would it have other consequences?

**Tags:** cc.complexity-theory, quantum-computing, big-picture, oracles, polynomial-hierarchy

> **Comments:**
> **username_1**: 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.  
> **username_0**: @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)]}$?  

---

## 1 answers

### Answer by username_2 on 2019-05-17. Score: 5

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.

> **Comments:**
> **username_0**: Would you know 2. as well?  

---

