Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals

To warm-up, we first consider the idealized setting where there are $r$ “non-connected” output bits, by which we mean no two such output bits depend on a common input bit. In particular, the $r$ marginal distributions of $f(\mathrm{\Pi })$ projected onto the individual coordinates are independent. Here, one should view $r$ as large, say ${\mathrm{\Omega }}_d(n)$. We proceed via a concentration vs. anticoncentration dichotomy, present in various forms in the works [31, 14, 35, 21, 22]. Specifically, we classify each of the $r$ output bits according to how their corresponding marginal distribution compares to the marginal distribution of the target distribution.

At a high level, we would like to argue that either many of these output bits have marginal distributions which are far from those of the target distribution, in which case we can combine the marginal errors, or many of these output bits are close to the “correct” marginal distribution, in which case a more complicated anticoncentration argument shows that a specific potential function highlights a noticeable discrepancy between the two distributions. To this end, we call an output bit $b$ Type-1 if the marginal distribution ${f(\mathrm{\Pi })|}_b$ is $\delta$-far in total variation distance from the marginal distribution ${{𝒟}_{\mathrm{𝗁𝖺𝗋𝖽}}(n,m)|}_b$, and call it Type-2 otherwise. Here, $\delta =O_d(1)$ is some small threshold parameter.

Suppose at least $r/2$ of the non-connected output bits are Type-1. Note that since total variation distance is closed under projection, a single Type-1 neighborhood already gives distance $\delta$. To strengthen the bound, one can take advantage of independence and apply standard concentration inequalities, as in the proof of [21, Lemma 4.2], to conclude $f(\mathrm{\Pi })$ has distance roughly $1-e^{-{\delta }^2\cdot r}$ from ${𝒟}_{\mathrm{𝗁𝖺𝗋𝖽}}(n,m)$.³³3There is a small subtlety here, in that if the set of Type-1 output bits fully contains the last $m$ output bits, then those output bits are not a product distribution in ${𝒟}_{\mathrm{𝗁𝖺𝗋𝖽}}(n,m)$. For simplicity, we will assume that this does not occur, although the full statement of [21, Lemma 4.2] is robust enough to still apply in that scenario. For $r\gg 1/{\delta }^2$, this is at least 0.24, as desired.

The more involved case is when at least $r/2$ output bits are Type-2. Here, rather than directly comparing $f(\mathrm{\Pi })$ to ${𝒟}_{\mathrm{𝗁𝖺𝗋𝖽}}(n,m)$, we compare the expectation of a complex-valued potential function $h(x,y)={𝗂}^{|x|+2|y|}$ over samples $(x,y)$ drawn from the two distributions. Direct calculations show that ${𝔼}_{x,y}\left[h(x,y)\right]\approx 1/2$ for $(x,y)\sim {𝒟}_{\mathrm{𝗁𝖺𝗋𝖽}}(n,m)$ (see [17, Claim 5.3]) and that $|𝔼[{𝗂}^A]|$ is bounded away from 1 for any integral random variable $A$ suitably far from constant modulo 4 (see [17, Claim 5.5]). It is tempting to argue that by the independence of the non-connected output bits, we can fix the value of the input bits not affecting any Type-2 output bits to view ${𝔼}_{x,y}\left[h(x,y)\right]$ as a product of many independent random variables with magnitudes bounded away from 1. Then we could conclude that for each of these input conditionings, $|{𝔼}_{x,y}\left[h(x,y)\right]|\ll 0.01$ for $(x,y)\sim f(\mathrm{\Pi })$, which would give the desired distance of $0.24$ (using [17, Lemma 3.4]).

The problem, however, is that the contributions of the remaining output bits can compensate for those of the non-connected output bits. For example, consider the string $z_1,1-z_1,z_2,1-z_2,\mathrm{\dots },z_k,1-z_k$, where the $z_k$’s are independent random bits. There are $k$ independent bits, yet the string’s Hamming weight is fixed at $k$. Thus, we cannot reason about ${𝔼}_{x,y}\left[h(x,y)\right]$ solely from the non-connected output bits. Instead, we need to consider the neighborhood of each output bit $b$, i.e., the set of output bits that are also influenced by the input bits determining $b$.

To fix our analysis, let us change our assumption from there being $r$ non-connected output bits to there being $r$ non-connected neighborhoods. Here, we refer to two neighborhoods $N_1,N_2$ as non-connected if for every pair of output bits $b_1\in N_1$ and $b_2\in N_2$, the input bits that determine $b_1$ are disjoint from those that determine $b_2$. We can similarly classify each neighborhood as Type-1 or Type-2 depending on the distance of its marginal distribution to that of the target distribution. The analysis in the case of many Type-1 neighborhoods is performed almost identically to the previous scenario, but now we are able to reason more carefully when there are many Type-2 neighborhoods.

Indeed, consider a Type-2 neighborhood $N=(x^{\prime },y^{\prime })$, where $x^{\prime }$ is the output bits contained in the first $n$ indices (corresponding to $x$) and $y^{\prime }$ is the output bits contained in the latter $m$ indices (corresponding to $y$). If we can show that $|x^{\prime }|+2|y^{\prime }|(\mathrm{mod}4)$ is not too close to being a constant, then the potential function argument sketched above can actually be carried out. To this end, let $b$ be the output bit that defines the neighborhood $N=N(b)$, and consider the effect of conditioning on $b=0$ vs. on $b=1$.

First suppose $b$ is in the $x$ part. In this case, we can write $x^{\prime }=(b,x^{\prime \prime })$ and express $|x^{\prime }|+2|y^{\prime }|(\mathrm{mod}4)$ as $b+|x^{\prime \prime }|+2|y^{\prime }|(\mathrm{mod}4)$. Recall that $N$ is a Type-2 neighborhood, so it should resemble a product distribution. In particular, the distribution of $|x^{\prime \prime }|+2|y^{\prime }|(\mathrm{mod}4)$ conditioned on $b=0$ should be roughly the same as when conditioned on $b=1$. Observe then, that $1+|x^{\prime \prime }|+2|y^{\prime }|(\mathrm{mod}4)$ and $|x^{\prime \prime }|+2|y^{\prime }|(\mathrm{mod}4)$ should have noticeably different distributions, as we are essentially comparing a binomial distribution with its shift. Since $b$ should be close to $(1/4)$-biased, it takes both values with constant probability, so $|x^{\prime }|+2|y^{\prime }|(\mathrm{mod}4)$ cannot be too close to any fixed value. A similar analysis shows that if $b$ is in the $y$ part, then we are comparing the density of $|x^{\prime }|+2|y^{\prime }|(\mathrm{mod}4)$ and $|x^{\prime }|+2(|y^{\prime }|+1)(\mathrm{mod}4)$.

Unfortunately, there is a problem with this latter case. Suppose the neighborhood $N$ does not contain any bits in the $x$ part. Then we are comparing the density of $2|y^{\prime }|(\mathrm{mod}4)$ and $2(|y^{\prime }|+1)(\mathrm{mod}4)$, or equivalently, $|y^{\prime }|(\mathrm{mod}2)$ and $|y^{\prime }|+1(\mathrm{mod}2)$. The $y$ part is $(1/2)$-biased, so $|y^{\prime }|(\mathrm{mod}2)$ can have the same distribution as $|y^{\prime }|+1(\mathrm{mod}2)$! Note that it is this fact which allows for the previously described sampling algorithm for $(X,\text{PARITY})$. Hence, we must make one further refinement to our assumption.

Now instead of simply assuming there are $r$ non-connected neighborhoods, we insist that all $r$ neighborhoods are generated by output bits in the $x$ part. Moreover, we will only require the non-connectedness property on bits in the $x$ part of the neighborhoods. This second condition actually makes the analysis more challenging, but we will later see it is necessary for this model case to be obtainable. We once more redefine Type-1 and Type-2 neighborhoods; this time we classify neighborhoods based only on their marginals on the first $n$ output bits. The case of many Type-1 neighborhoods essentially works as before (see [17, Lemma 5.2]), so it remains to address the case where at least $r/2$ of the neighborhoods are Type-2.

To obtain some structure in the $y$ part, we exploit our assumption on the size of $m$. Since we have $m\le n^2/\mathrm{tow}(30d)$, most pairs of neighborhoods do not intersect in the last $m$ output bits. Quantitatively, we can find $C\approx r^2/(m{d}^2)\gg 1$ non-connected Type-2 neighborhoods that do not intersect in the $y$ part. Without loss of generality, assume they are $N(1),N(2),\mathrm{\dots },N(C)$. By fixing the value of all the input bits that do not affect $1,2,\mathrm{\dots },C$, the contributions to $h$ from these neighborhoods are now independent. In particular, the expectation of $h$ becomes a product of expectations over the output of the neighborhood. As noted above, we can conclude the expectation over the neighborhood $N=(x^{\prime },y^{\prime })$ is bounded away from 1 if $|x^{\prime }|+2|y^{\prime }|(\mathrm{mod}4)$ is not too close to any fixed value.

This ends up being a bit difficult to show directly, since while the $C$ neighborhoods are disjoint in the $y$ part, they may be connected. Fortunately, the variance of $|x^{\prime }|+2|y^{\prime }|(\mathrm{mod}4)$ over a random such fixing of the input bits follows from that of $|x^{\prime }|(\mathrm{mod}2)$, where we do have non-connectedness in the $x$ part. By the previous argument of considering $|x^{\prime }|$ conditioned on the output bit $b$ being 0 vs. being 1, we are able to prove $|x^{\prime }|(\mathrm{mod}2)$ is typically not too close to constant (see [17, Claim 5.7]). This concludes the analysis of many Type-2 neighborhoods (see [17, Lemma 5.6]), as well as the proof of Theorem 2 under certain ideal assumptions.

Previously, we assumed a rather strong structure: $r={\mathrm{\Omega }}_d(n)$ many output bits generating neighborhoods that are non-connected in $[n]$. This, of course, is not a structure readily present in an arbitrary $d$-local function $f$. To reduce to this case, a standard approach (appearing in, e.g., [31, 8, 34, 14, 35, 21, 22]) is to strategically condition on bits to express an arbitrary $d$-local function as a convex combination of functions with the desired structure. In other words, if we can find some set $S$ of input bits whose removal induces many non-connected neighborhoods of the form we want, then we can express $f(\mathrm{\Pi })$ as

where $f_{\rho }:{\{0,1\}}^{\ast }\to {\{0,1\}}^{n+m}$ is defined as $f$ with the input bits in $S$ fixed to their values in $\rho$. Observe that each $f_{\rho }$ has the structured form we already know how to analyze, regardless of the actual values the bits in $S$ are set to. More formally, we have:

1. 1.

   If most of the non-connected neighborhoods are Type-1, then $f_{\rho }(\mathrm{\Pi })$ is $\approx (1-e^{-{\mathrm{\Omega }}_d(r)})$-far from ${𝒟}_{\mathrm{𝗁𝖺𝗋𝖽}}(n,m)$, and

2. 2.

   Otherwise, ${𝔼}_{(x,y)\sim {𝒟}_{\mathrm{𝗁𝖺𝗋𝖽}}(n,m)}[h(x,y)]-{𝔼}_{(x,y)\sim f_{\rho }(\mathrm{\Pi })}[h(x,y)]\ge 0.49$.

By a union bound argument (see [17, Lemma 3.4]), these results on the conditioned functions can be combined to obtain ${\Vert f(\mathrm{\Pi })-{𝒟}_{\mathrm{𝗁𝖺𝗋𝖽}}(n,m)\Vert }_{\mathrm{𝖳𝖵}}\gtrsim 0.245-2^{|S|}\cdot e^{-{\mathrm{\Omega }}_d(r)}$. Then as long as $r\gg |S|$, we obtain the desired distance bound of 0.24.

At this point, the remaining task is combinatorial. We construct a bipartite graph whose left side is the first $n$ output bits, and whose right side is the input bits. Note that each left vertex has maximum degree $d$. We want to remove $s$ right vertices to obtain $r$ non-connected neighborhoods of the prescribed form, where $r\gg s$. Ideally, we would like $r$ to be as large as possible to maximize the total variation distance. Fortunately, this task has already been done for us. By [21, Corollary 4.11], we can take $s\ll r$ and $r={\mathrm{\Omega }}_d(n)$, as desired.

For the sake of completeness, we briefly highlight the main idea behind the proof of [21, Corollary 4.11]. The key observation is that locality, while only explicitly constraining the left vertices, also constrains the right ones, since it upper bounds the number of edges by $dn$. Thus while we cannot forbid high-degree right vertices, there cannot be many of them. This implies that we can “affordably” remove all right vertices above a particular degree threshold, and greedily find non-connected vertices on the left side. A more involved analysis (see [21, Corollary 4.8]) provides better parameters than one could obtain via this naive approach, and an even more involved analysis guarantees non-connected left neighborhoods, rather than just vertices. Still, the proofs morally operate in a similar way to the strategy described. This completes the sketch of the proof of Theorem 2; the full details can be found in [17, Section 5].

We conclude by remarking that the above analysis is fairly robust, and it allows one to rule out the sampleability of a number of simple distributions by shallow circuits. Thus, the specific distributions we have chosen to consider are primarily a function of what can be produced by shallow quantum circuits, rather than what can be forbidden for shallow classical ones.