Improved Separation Between Quantum and Classical Computers for Sampling and Functional Tasks

As $\mathrm{\#}𝖯$-complete languages are random self-reducible and only one oracle call is needed we can use a random reduction of $\mathrm{\#}𝖯$ to give the answer to the oracle call and use the polynomial time $\varphi$ algorithm to perform the rest of the $𝖯$ algorithm. $◀$

The next lemma captures the intuition that ${\mathrm{𝖡𝖯𝖯}}_{\parallel }^{\mathrm{𝖭𝖯}}$ algorithms are “almost” rr to $\mathrm{𝖭𝖯}$, only missing the random element selection part of the definition (property (2)).

If $L\in {\mathrm{𝖡𝖯𝖯}}_{\parallel }^{\mathrm{𝖭𝖯}}$ then there exists a polynomial time algorithm, $A$, to decide $x\in L$ which calls only one set of up to $m$ non-adaptive $\mathrm{𝖭𝖯}$ queries. We assume the $\mathrm{𝖭𝖯}$ calls $\mathrm{𝖲𝖠𝖳}$ for simplicity. Let the algorithm for ${\sigma }_B(i,x,r)$ run $A$ until the step involving oracle queries and then output just the $i$’th query (assuming some arbitrary query ordering). The algorithm for ${\varphi }_B$ is now just the algorithm $A$ using the oracle calls produced asked by ${\sigma }_B(i,x,r)$ in place of directly making its own calls. Since both ${\varphi }_B$ and ${\sigma }_{𝖡}$ have access to the same random string $r$ they will both select the same oracle calls. $◀$ Lemma 8 is useful as it proves that ${\mathrm{𝖡𝖯𝖯}}_{\parallel }^{\mathrm{𝖭𝖯}}$ fulfils property (1) of the definition of random reducibility to $\mathrm{𝖭𝖯}$, but does not prove the random distribution of ${\sigma }_B(1,x,r)$. The next theorem shows that if a langauge already randomly reduces to ${\mathrm{𝖡𝖯𝖯}}_{\parallel }^{\mathrm{𝖭𝖯}}$ then this random reduction condition (condition (2)) is also fufilled, and thus the language is random reducible to $\mathrm{𝖭𝖯}$

Let $L$ be a language which is random reducible to $L_B\in {\mathrm{𝖡𝖯𝖯}}_{\parallel }^{\mathrm{𝖭𝖯}}$. We will demonstrate that $L$ is rr to $\mathrm{𝖭𝖯}$ by writing out the definition of random reducibility to $L_B$ then using lemma 8 to substitute the calls to $L_B$ with a formula using calls to $\mathrm{𝖲𝖠𝖳}$. We can then rearange this into a format which directly makes calls to $\mathrm{𝖲𝖠𝖳}$ and we show that these calls inherit the randomness property from the random reduction of $L$ to $L_B$.

Let us assume the random reduction of $L$ to $L_B$ on input $x$ uses $k$ calls, from the definition of random reducibility there exists $\varphi$ and $\sigma$ such that

Define $y_i:=\sigma (i,x,r)$.

Using lemma 8 we can substitute $L_B$ with ${\varphi }_B$, ${\sigma }_B$ and a random string $r_i$ for the i’th call to $L_B$. In the following we assume each lemma-8-reduction uses $m$ $\mathrm{𝖲𝖠𝖳}$ calls. ${\mathrm{Pr}}_{r,r_1,\mathrm{\dots }{r}_k}(L(x)=\varphi (x,r,$ ${\varphi }_B(y_1,r_1,\mathrm{𝖲𝖠𝖳}({\sigma }_B(1,y_1,r_1)),\mathrm{\dots },\mathrm{𝖲𝖠𝖳}({\sigma }_B(m,y_1,r_1))),$ (1) $\mathrm{\dots },$ ${\varphi }_B(y_k,r_k,\mathrm{𝖲𝖠𝖳}({\sigma }_B(1,y_k,r_k)),\mathrm{\dots },\mathrm{𝖲𝖠𝖳}({\sigma }_B(m,y_k,r_k))))\ge 1-(k+1)2{}^{-n}.$ (2)

The failure probability $1-(k+1)2^{-n}$ comes the failure probability of the $k$ reductions combined with the failure probability from the random reduction.

We can now begin to combine elements of the reduction from $L$ to $L_B$ with reduction from $L_B$ to $\mathrm{𝖲𝖠𝖳}$. We start with $\varphi$ which we combine with ${\varphi }_B$ to define ${\varphi }^{\prime }$, informally we can think of this as doing the two polynomial-time algorithms as a larger polynomial time algorithm.

We use “$x\mathrm{\#}y$” to denote $y$ appended to $x$. Define $𝐫:=r\mathrm{\#}{r}_1\mathrm{\#}\mathrm{\dots }\mathrm{\#}{r}_k$.

Again we define a new function, ${\sigma }^{\prime }$, as the combination of two existing function, $\sigma$ and ${\sigma }_B$:

Which gives the following simplified equation:

We will now directly check the definition of ${\sigma }^{\prime }$, ${\varphi }^{\prime }$ and the equation 3 against the definition of random-reducbile, recall the two conditions definition 3:

1. 1.

   For all $n$ and all $x\in {\{0,1\}}^n$ $f(x)$ can probably be solved by $\varphi$ with instance of $g(y)$ for $y$ selected by $\sigma$:

   $${\mathrm{Pr}}_r\left(f(x)=\varphi (x,r,g(\sigma (1,x,r)),\mathrm{\dots },g(\sigma (k,x,r)))\right)\ge 2/3$$

2. 2.

   For all $n$, all pairs $\{x_1,x_2\}\subset {\{0,1\}}^n$ and all $i$, if $r$ is chosen uniformly at random then $\sigma (i,x_1,r)$ and $\sigma (i,x_2,r)$ are identically distrubuted.

We can see that these two conditions are met:

1. 1.

   For sufficiently large $n$, $1-(k+1)2^{-n}>2/3$ therefore equation 3 is of the form:

   $${\mathrm{Pr}}_r\left(f(x)=\varphi (x,r,\mathrm{𝖲𝖠𝖳}(\sigma (1,x,r)),\mathrm{\dots },\mathrm{𝖲𝖠𝖳}(\sigma (k,x,r)))\right)\ge 2/3.$$

2. 2.

   For all $n$, all pairs $\{x_1,x_2\}\subset {\{0,1\}}^n$, all $i$ and $j$, if $r$ is chosen uniformly at random then $\sigma (j,x_1,r)$ and $\sigma (j,x_2,r)$ are identically distributed (as per their definition), therefore ${\sigma }^{\prime }(i\mathrm{\#}j,x_{1/2},𝐫)$ is identically distributed too. This is because the only dependence on $x$ is through the identically distributed $\sigma$: ${\sigma }^{\prime }(i\mathrm{\#}j,x,𝐫)={\sigma }_{𝖡}(i,\sigma (j,x,r),r_j)$. This holds for all $r_i$, $r_j$.

Thus fufilling the conditions for $L$ to be random reducible to $\mathrm{𝖭𝖯}$ $◀$

Finally, we can proceed with the proof of theorem 6

Toda [15] showed that $\mathrm{𝖯𝖧}\subseteq {𝖯}^{\mathrm{\#}𝖯[\mathrm{𝟣}]}$. Therefore, by the assumption of the theorem if ${𝖯}^{\mathrm{\#}𝖯}={\mathrm{𝖡𝖯𝖯}}_{\parallel }^{\mathrm{𝖭𝖯}}=\mathrm{𝖯𝖧}$ then ${𝖯}^{\mathrm{\#}𝖯}={𝖯}^{\mathrm{\#}𝖯[\mathrm{𝟣}]}$.

By lemma 7 we know ${𝖯}^{\mathrm{\#}𝖯}$ is rr to $\mathrm{\#}𝖯$. Under the assumption of this theorem, $\mathrm{\#}𝖯\subseteq {\mathrm{𝖡𝖯𝖯}}_{\parallel }^{\mathrm{𝖭𝖯}}$, ${𝖯}^{\mathrm{\#}𝖯}$ is rr to ${\mathrm{𝖡𝖯𝖯}}_{\parallel }^{\mathrm{𝖭𝖯}}$. By lemma 9 this means ${𝖯}^{\mathrm{\#}𝖯}$ is rr to $\mathrm{𝖭𝖯}$. $◀$

The next result is heavily based on the work of Feigenbaum and Fortnow [9]. They show that if $\mathrm{𝖭𝖯}$ is random self reducible then $\mathrm{𝖼𝗈𝖭𝖯}$ is in $\mathrm{𝖭𝖯}/\mathrm{𝗉𝗈𝗅𝗒}$, while the result we are trying to show is slightly different than this, the method is very similar.

Let ${\mathrm{𝖠𝖬}}^{\mathrm{𝗉𝗈𝗅𝗒}}$ be $\mathrm{𝖠𝖬}$ with polynomial advice given to Arthur²²2 This is not the same as $\mathrm{𝖠𝖬}/\mathrm{𝗉𝗈𝗅𝗒}$, as the latter must be an $\mathrm{𝖠𝖬}$ language for all advice, whereas the former only needs to be defined for the correct advice.. It turns out that ${\mathrm{𝖠𝖬}}^{\mathrm{𝗉𝗈𝗅𝗒}}=\mathrm{𝖭𝖯}/\mathrm{𝗉𝗈𝗅𝗒}$ and ${\mathrm{𝖼𝗈𝖠𝖬}}^{\mathrm{𝗉𝗈𝗅𝗒}}=\mathrm{𝖼𝗈𝖭𝖯}/\mathrm{𝗉𝗈𝗅𝗒}$ [9]. We will prove $L$ is in ${\mathrm{𝖠𝖬}}^{\mathrm{𝗉𝗈𝗅𝗒}}\cap {\mathrm{𝖼𝗈𝖠𝖬}}^{\mathrm{𝗉𝗈𝗅𝗒}}$, beginning with $L\in {\mathrm{𝖠𝖬}}^{\mathrm{𝗉𝗈𝗅𝗒}}$.

Suppose $L(x)$ is non-adaptively $k(n)$ random-reducible to $\mathrm{𝖲𝖠𝖳}(x)$ with error probability $2^{-n}$. We will adopt the notation $y_i=\sigma (i,x,r)$. For instance size $n$ we will give Arthur the advice $(p_1,\mathrm{\dots },p_k)$ where $p_i$ is the probability that $y_i=1$,

As $\sigma (i,x,r)$ is distributed identically (given uniform random $r$) for all $x$ this advice does not depend on the input $x$.

The proof system will consist of Arthur selecting $m=9k^3$ random strings, ${\{r_j\}}_{j\in [m]}$, and passing this to Merlin, these random strings defines which $\mathrm{𝖲𝖠𝖳}$ queries, $y_{0,j},\mathrm{\dots },y_{k,j}$, will be made. Merlin will hand back $m$ “transcripts”. These transcripts consist of a list $w_{i,j}$ which is either a witness for $y_{i,j}$ or is the string “NIL” (which is interpreted as the claim that $y_{i,j}\notin \mathrm{𝖲𝖠𝖳}$). For each of the $m$ random strings we get the transcript:

Arthur performs three checks:

1. 1.

   For all $i,j$ either the witness $w_{i,j}$ is “NIL” or he checks the witness is valid for $y_{i,j}\in \mathrm{𝖲𝖠𝖳}$

2. 2.

   Let $b_{i,j}$ be 0 if $w_{i,j}$ is “NIL” and one otherwise. For all $j\in [m]$ Arthur checks that $\varphi (x,r_j,b_{0,j},\mathrm{\dots },b_{k,j})=1$, i.e. If Merlin has told the truth then $\varphi$ will accept.

3. 3.

   For each $i\in [k]$ Arthur checks that more than $p_{i}m-2\sqrt{km}$ of the $y_{i,j}$ have been proved to be in $\mathrm{𝖲𝖠𝖳}$, if this condition does not hold he rejects.

If these checks all pass, then Arthur accepts. The trick in this proof is this final condition. Over the random strings, each $y_i$ has some probability of being in $\mathrm{𝖲𝖠𝖳}$ with a given variance, by picking $m$ to be large we force this variance to be small. With high probability, a correct answer lies in this range. Since Merlin cannot lie about yes instances (since he must prove them), he can only lie about no instances. However, if he lied too much it would be clear that not enough of $y_i$ are in $\mathrm{𝖲𝖠𝖳}$, thus we could probabilistically guess he was cheating. To exploit this, $m$ is picked precisely so Merlin cannot cheat on all $j$ without exceeding his “lying budget”. We will now formally show soundness and completeness.

Completness. If $x\in L$ and Merlin is honest, providing witnesses for all $y_{i,j}$ in $\mathrm{𝖲𝖠𝖳}$, condition (1) will always hold. Condition (2) holds with probability at least $1-2^{-n}$ (by the definition of rr). Therefore we just need to show condition (3) holds with high probability.

Let $Z_{i,j}:=(y_{i,j}=1)$ and $Z_i={\sum }_{j=1}^m{Z}_{i,j}$. We defined our advice so $p_i=𝔼[Z_i]/m$, we can derive that . We can use these properties and Chebyshev’s inequality to bound our probability of failing check (2).

The probability of failing any check given $x\in L$ is less than $\frac{1}{4}+2^{-n}$ which is less than $1/3$ for large enough $n$. This proves completeness

Soundness. Suppose $x\notin L$, if Arthur accepts then all 3 checks must have passed for all $j\in [m]$. If some $y_{i,j}$ is in $\mathrm{𝖲𝖠𝖳}$ but Merlin has provided $w_{i,j}=\mathrm{‘}\mathrm{‘}NI{L}^{\prime \prime }$ then we say Merlin has lied about $y_{i,j}$, if check (1) passes Merlin has not lied about any “yes” instances, so we disregard this case. The probability of the random reduction failing is $2^{-n}$ without any lies, so for all $m$ reductions to fail Merlin must lie $m$ times with probability ${(1-2^{-n})}^m>1-m{2}^{-n}$.

If Merlin lies $m$ times there must be an $i$ that he claims at least $m/k$ of the $y_{i,j}$ are not in $\mathrm{𝖲𝖠𝖳}$ when they are. To satisfy condition (3) at least $p_{i}m-2\sqrt{km}+𝐦/𝐤$ of the $y_{i,j}$ must be in $\mathrm{𝖲𝖠𝖳}$ to leave “room” for Merlin to lie $m/k$ times without violating (3). The probability of this is given by a Chernoff bound on the random variable $Z_i$, as defined above.

Combining this with the normal probability that the random reduction fails even with correct oracle answers (which had a $2^{-n}$ probability) gives an acceptance probability given $x\notin L$ of less than for large enough $n$. This proves soundness.

The previous analysis can just as easily be repeated for ${\mathrm{𝖼𝗈𝖠𝖬}}^{\mathrm{𝗉𝗈𝗅𝗒}}$ with Merlin proving no instances, giving $L\in {\mathrm{𝖠𝖬}}^{\mathrm{𝗉𝗈𝗅𝗒}}\cap {\mathrm{𝖼𝗈𝖠𝖬}}^{\mathrm{𝗉𝗈𝗅𝗒}}$. By Feigenbaum and Fortnow we know this equals $\mathrm{𝖭𝖯}/\mathrm{𝗉𝗈𝗅𝗒}\cap \mathrm{𝖼𝗈𝖭𝖯}/\mathrm{𝗉𝗈𝗅𝗒}$. $◀$

To prove the next Theorem we must recall a crucial result by Arvind and Köbler, which checkability [6, 4]. The notion of checkability is somewhat involved but intuitively has to do with whether efficent programs that decide the set can themselves be efficently checked. Since we will just need the checkability of $\mathrm{𝖯𝖯}$ and $\mathrm{\#}𝖯$ to deploy the following theorem we will not formally define it, instead we refer the reader to [6, 7].

This result is imperative to proceed, as while it is true that $\mathrm{𝖭𝖯}\subset (\mathrm{𝖭𝖯}\cap \mathrm{𝖼𝗈𝖭𝖯})/\mathrm{𝗉𝗈𝗅𝗒}$ implies $\mathrm{𝖯𝖧}={\mathrm{𝖹𝖯𝖯}}^{\mathrm{𝖭𝖯}}$, the same is not true for $\mathrm{𝖭𝖯}\subset (\mathrm{𝖭𝖯}/\mathrm{𝗉𝗈𝗅𝗒})\cap (\mathrm{𝖼𝗈𝖭𝖯}/\mathrm{𝗉𝗈𝗅𝗒})$.

By Toda ${𝖯}^{\mathrm{\#}𝖯}={𝖯}^{\mathrm{𝖯𝖯}}$ [15]. If ${𝖯}^{\mathrm{𝖯𝖯}}$ is in $\mathrm{𝖼𝗈𝖭𝖯}/\mathrm{𝗉𝗈𝗅𝗒}\cap \mathrm{𝖭𝖯}/\mathrm{𝗉𝗈𝗅𝗒}$ then clearly so is $\mathrm{𝖯𝖯}$, combining this with the existence of $\mathrm{𝖯𝖯}$-complete checkable sets [6] we know that $\mathrm{𝖯𝖯}$ is low for ${\mathsf{\Sigma }}_{\mathrm{𝟤}}^{𝖯}$.

This lowness implies we can put ${𝖯}^{\mathrm{\#}𝖯}$ in ${\mathsf{\Sigma }}_{\mathrm{𝟤}}^{𝖯}$ by the following series of inclusions

As ${\mathsf{\Sigma }}_{\mathrm{𝟤}}^{𝖯}\subseteq {𝖯}^{\mathrm{\#}𝖯}$ by Toda [15] we can fix the previous inclusion into an equality: ${\mathsf{\Sigma }}_{\mathrm{𝟤}}^{𝖯}={𝖯}^{\mathrm{\#}𝖯}$.

As ${\mathsf{\Pi }}_{\mathrm{𝟤}}^{𝖯}\subseteq {𝖯}^{\mathrm{\#}𝖯}$ (Toda [15]) we get ${\mathsf{\Pi }}_{\mathrm{𝟤}}^{𝖯}\subseteq {\mathsf{\Sigma }}_{\mathrm{𝟤}}^{𝖯}$. Which gives us the final equality:

$◀$

The previous lemma has achieved a collapse to the second level but we can collapse to ${\mathrm{𝖹𝖯𝖯}}^{\mathrm{𝖭𝖯}}$ by using the proveability of languages in ${\mathsf{\Sigma }}_{\mathrm{𝟤}}^{𝖯}\cap {\mathsf{\Pi }}_{\mathrm{𝟤}}^{𝖯}$ to make the ${\mathrm{𝖡𝖯𝖯}}_{\parallel }^{\mathrm{𝖭𝖯}}$ algorithm zero-error.

Fix some $L\in {\mathrm{𝖡𝖯𝖯}}^{\mathrm{𝖭𝖯}}\cap {\mathsf{\Sigma }}_{\mathrm{𝟤}}^{𝖯}\cap {\mathsf{\Pi }}_{\mathrm{𝟤}}^{𝖯}$. We can check if $x\in L$ using the ${\mathrm{𝖡𝖯𝖯}}^{\mathrm{𝖭𝖯}}$ algorithm. Use the ${\mathrm{𝖡𝖯𝖯}}^{\mathrm{𝖭𝖯}}$ program to determine a proof of this fact for either the ${\mathsf{\Sigma }}_{\mathrm{𝟤}}^{𝖯}$ verifier or the ${\mathsf{\Pi }}_{\mathrm{𝟤}}^{𝖯}$ verifier. We can test either proof in ${𝖯}^{\mathrm{𝖭𝖯}}$ using the verifiers from either ${\mathsf{\Sigma }}_{\mathrm{𝟤}}^{𝖯}$ or ${\mathsf{\Pi }}_{\mathrm{𝟤}}^{𝖯}$. With probability $1-2^{-n}$ the ${\mathrm{𝖡𝖯𝖯}}^{\mathrm{𝖭𝖯}}$ algorithm succeeds in producing a valid proof in polynomial time, any valid proof proves or disproves $x\in L$. Therefore in polynomial time the algorithm has successfully determined if $x\in L$ with probability $1-2^{-n}$ and never incorrectly answers, placing $L\in {\mathrm{𝖹𝖯𝖯}}^{\mathrm{𝖭𝖯}}$. $◀$

This completes the proof of our main theorem which is given below.

If ${𝖯}^{\mathrm{\#}𝖯}={\mathrm{𝖡𝖯𝖯}}_{\parallel }^{\mathrm{𝖭𝖯}}$ then ${𝖯}^{\mathrm{\#}𝖯}$ is random reducible to $\mathrm{𝖭𝖯}$ (Theorem 5).

If ${𝖯}^{\mathrm{\#}𝖯}$ is random reducible to $\mathrm{𝖭𝖯}$ then ${𝖯}^{\mathrm{\#}𝖯}$ is in $\mathrm{𝖼𝗈𝖭𝖯}/\mathrm{𝗉𝗈𝗅𝗒}\cap \mathrm{𝖭𝖯}/\mathrm{𝗉𝗈𝗅𝗒}$ (Theorem 10).

If ${𝖯}^{\mathrm{\#}𝖯}\subseteq \mathrm{𝖼𝗈𝖭𝖯}/\mathrm{𝗉𝗈𝗅𝗒}\cap \mathrm{𝖭𝖯}/\mathrm{𝗉𝗈𝗅𝗒}$ then ${𝖯}^{\mathrm{\#}𝖯}={\mathsf{\Sigma }}_{\mathrm{𝟤}}^{𝖯}\cap {\mathsf{\Pi }}_{\mathrm{𝟤}}^{𝖯}$ (Lemma 12).

If ${𝖯}^{\mathrm{\#}𝖯}={\mathsf{\Sigma }}_{\mathrm{𝟤}}^{𝖯}\cap {\mathsf{\Pi }}_{\mathrm{𝟤}}^{𝖯}$ and ${𝖯}^{\mathrm{\#}𝖯}={\mathrm{𝖡𝖯𝖯}}^{\mathrm{𝖭𝖯}}$ then ${𝖯}^{\mathrm{\#}𝖯}={\mathrm{𝖹𝖯𝖯}}^{\mathrm{𝖭𝖯}}$ (Lemma 13). $◀$

The following theorem formalises the “natural interpretation” of our result given in the intro.

This result becomes easy to show after Theorem 18, so we will prove it at the end of the next section.

Assume $\mathrm{𝖯𝗈𝗌𝗍𝖡𝖰𝖯}=\mathrm{𝖯𝗈𝗌𝗍𝖡𝖯𝖯}$. By Toda $\mathrm{𝖯𝖧}\subseteq {𝖯}^{\mathrm{\#}𝖯}$, by Aaronson [1] $\mathrm{𝖯𝗈𝗌𝗍𝖡𝖰𝖯}=\mathrm{𝖯𝖯}$ and by $\mathrm{𝖯𝗈𝗌𝗍𝖡𝖯𝖯}\subseteq {\mathrm{𝖡𝖯𝖯}}_{\parallel }^{\mathrm{𝖭𝖯}}$ [13, 11]. This gives:

Therefore ${𝖯}^{\mathrm{\#}𝖯}=\mathrm{𝖯𝖧}$.

At this point we recall an interesting lemma from Toda [15] to continue.

Clearly $\mathrm{𝖯𝖧}\subseteq {\mathrm{𝖯𝖯}}^{\mathrm{𝖯𝖧}}$ and it can be shown that if $\mathrm{𝖯𝖯}\subseteq {\mathrm{𝖡𝖯𝖯}}_{\parallel }^{\mathrm{𝖭𝖯}}$ then $\mathrm{𝖡𝖯}\cdot \mathrm{𝖯𝖯}\subseteq {\mathrm{𝖡𝖯𝖯}}_{\parallel }^{\mathrm{𝖭𝖯}}$ (a full proof follows in lemma 19), therefore

Since $\mathrm{𝖯𝖧}={𝖯}^{\mathrm{\#}𝖯}$ and ${\mathrm{𝖡𝖯𝖯}}_{\parallel }^{\mathrm{𝖭𝖯}}\subseteq \mathrm{𝖯𝖧}$ we can conclude ${𝖯}^{\mathrm{\#}𝖯}={\mathrm{𝖡𝖯𝖯}}_{\parallel }^{\mathrm{𝖭𝖯}}$. We now have the condition ${𝖯}^{\mathrm{\#}𝖯}={\mathrm{𝖡𝖯𝖯}}_{\parallel }^{\mathrm{𝖭𝖯}}$ so by theorem 2 we get ${𝖯}^{\mathrm{\#}𝖯}={\mathrm{𝖹𝖯𝖯}}^{\mathrm{𝖭𝖯}}$, the final result. $◀$

Fix some $L\in \mathrm{𝖡𝖯}\cdot \mathrm{𝖯𝖯}$. By the definition, there exists $A\in \mathrm{𝖯𝖯}$ which defines $L$. Assume $\mathrm{𝖯𝖯}$ is in ${\mathrm{𝖡𝖯𝖯}}_{\parallel }^{\mathrm{𝖭𝖯}}$, therefore $A$ is in ${\mathrm{𝖡𝖯𝖯}}_{\parallel }^{\mathrm{𝖭𝖯}}$. Therefore $L$ is in $\mathrm{𝖡𝖯}\cdot {\mathrm{𝖡𝖯𝖯}}_{\parallel }^{\mathrm{𝖭𝖯}}$.

Note that majority-vote amplification can be used on $\mathrm{𝖡𝖯}\cdot \mathrm{𝖯𝖯}$ and ${\mathrm{𝖡𝖯𝖯}}_{\parallel }^{\mathrm{𝖭𝖯}}$ to decrease the probability of failure to less than $1/6$.

If we combine the random coin flips of both the $\mathrm{𝖡𝖯}\cdot \mathrm{𝖯𝖯}$ and $\mathrm{𝖡𝖯𝖯}$ parts of the algorithm we get a single failure probability below 1/3, which fits the definition of ${\mathrm{𝖡𝖯𝖯}}_{\parallel }^{\mathrm{𝖭𝖯}}$. $◀$

Theorem 18 provides a quick a simple proof of Theorem 15 (the natural interpretation of our result).

By definition $\mathrm{\#}𝖯=\mathrm{𝖤𝗑𝖺𝖼𝗍𝖢𝗈𝗎𝗇𝗍}$. O’Donnell and Say show ${𝖯}_{\parallel }^{\mathrm{𝖠𝗉𝗉𝗋𝗈𝗑𝖢𝗈𝗎𝗇𝗍}}=\mathrm{𝖯𝗈𝗌𝗍𝖡𝖯𝖯}$ [13]. Therefore we can rewrite the antecedent of the Theorem as ${𝖯}_{\parallel }^{\mathrm{\#}𝖯}=\mathrm{𝖯𝗈𝗌𝗍𝖡𝖯𝖯}$.

Any problem in $\mathrm{𝖯𝖯}$ can be solved with one $\mathrm{\#}𝖯$ query, which can obviously be done in one parallel round of oracle calls, so $\mathrm{𝖯𝖯}\subseteq {𝖯}_{\parallel }^{\mathrm{\#}𝖯}$. This gives $\mathrm{𝖯𝖯}=\mathrm{𝖯𝗈𝗌𝗍𝖡𝖯𝖯}$ (as we already know $\mathrm{𝖯𝗈𝗌𝗍𝖡𝖯𝖯}\subseteq \mathrm{𝖯𝖯}$ and by Theorem 18 ${𝖯}^{\mathrm{\#}𝖯}={\mathrm{𝖹𝖯𝖯}}^{\mathrm{𝖭𝖯}}$. $◀$

Fix a target error, $g$, from the assumption of the theorem there exists $d$ such that $g>1+\frac{1}{n^d}$. By lemma 21 we can approximate ${\sum }_{x\in {\{0,1\}}^n}f(x)h(x)$ to a multiplicative factor of $g^{\prime }=1+\frac{1}{3n^d}$ with high probability. Similarly we can approximate ${\sum }_{x\in {\{0,1\}}^n}h(x)$ to $g^{\prime }$ as well. Dividing the first sum by the second gives us $p$ within a multiplicative factor of

with sufficiently high probability. Since each of these sums can be done in parallel and then divided for the final answer we can perform them in parallel. Given we only need to decrease the failure probability by a factor of 2 the final algorithm is in $\mathrm{𝖥𝖡𝖯𝖯}_{\parallel }^{\mathrm{𝖭𝖯}}{}_{}{}^f$. $◀$

We will first apply the above logic for $\mathrm{𝖡𝗈𝗌𝗈𝗇𝖲𝖺𝗆𝗉𝗅𝗂𝗇𝗀}$ results. Aaronson and Arkhipov use one post-selection step in lemma 42 in [3], they then perform one approximate counting step on a quantity derived from this post-selection step to prove their main theorem. The structure of this proof fits the format of lemma 20, therefore we can state a parallelised version of their main theorem.

The ${|GPE|}_{\pm }^2$ problem (defined in [3]) becomes $\mathrm{\#}𝖯$ complete given two conjectures: The permanent-of-Gaussians Conjecture (PGC) and the Permanent Anti-Concentration Conjecture (PACC). These conjectures capture the belief that the permanent of Gaussian matrices does not concentrate close to zero and is hard to estimate, further justification of these conjectures is available in the original paper [3]. These are the additional assumptions we referred to earlier.

Next, we discuss how the same strategy applies to the $\mathrm{𝖨𝖰𝖯}$ case. The proof provided by Bremner, Montanaro and Shepherd uses just Stockmeyer counting to prove their collapse to ${\mathrm{𝖡𝖯𝖯}}^{\mathrm{𝖭𝖯}}$ in their theorem 1. By lemma 21 all $\mathrm{𝖭𝖯}$ calls in their algorithm can be done in parallel and we can convert their theorem 1 to a ${\mathrm{𝖡𝖯𝖯}}_{\parallel }^{\mathrm{𝖭𝖯}}$ result. For $\mathrm{𝖨𝖰𝖯}$ we do not need to conjecture the concentration of some hard-problem. The result only rest on the conjectured average case hardness of approximately computing either the partition function of the Ising model or on a property of low-degree polynomials over finite fields (Conjectures 2 and 3 in [8]).

Finally, the same strategy can be applied to improve Morimae’s result [12] on the hardness of the $\mathrm{𝖣𝖰𝖢𝟣}$ model for sampling [10] as it again depends on Stockmeyer counting. The necessary conjecture for Morimae’s is an assumption directly about the average case hardness of the one clean qubit model.

It seems likely that other results will fit the structure we give here, although we provide only these three results.

We finish this section by noting that the above results are in $\mathrm{𝖲𝖺𝗆𝗉𝖡𝖰𝖯}$, so classical impossibility on any of these tasks would imply $\mathrm{𝖲𝖺𝗆𝗉𝖡𝖰𝖯}\ne \mathrm{𝖲𝖺𝗆𝗉𝖯}$, which would also imply a separation in the functional classes $\mathrm{𝖥𝖡𝖰𝖯}\ne \mathrm{𝖥𝖡𝖯𝖯}$[2].