# Quantum advantage from measurement-induced entanglement
in random shallow circuits

Adam Bene Watts1,2 David Gosset2,3,4 Yinchen Liu2,3,4 Mehdi Soleimanifar5 1
Department of Pure Mathematics, University of Waterloo  2 Institute for
Quantum Computing, University of Waterloo  3 Department of Combinatorics and
Optimization, University of Waterloo  4 Perimeter Institute for Theoretical
Physics, Waterloo  5 California Institute of Technology

###### Abstract

We study random constant-depth quantum circuits in a two-dimensional
architecture. While these circuits only produce entanglement between nearby
qubits on the lattice, long-range entanglement can be generated by measuring a
subset of the qubits of the output state. It is conjectured that this long-
range measurement-induced entanglement (MIE) proliferates when the circuit
depth is at least a constant critical value $d^{*}$. For circuits composed of
Haar-random two-qubit gates, it is also believed that this coincides with a
quantum advantage phase transition in the classical hardness of sampling from
the output distribution.

Here we provide evidence for a quantum advantage phase transition in the
setting of random Clifford circuits. Our work extends the scope of recent
separations between the computational power of constant-depth quantum and
classical circuits, demonstrating that this kind of advantage is present in
canonical random circuit sampling tasks. In particular, we show that in any
architecture of random shallow Clifford circuits, the presence of long-range
MIE gives rise to an unconditional quantum advantage. In contrast, any
depth-$d$ 2D quantum circuit that satisfies a short-range MIE property can be
classically simulated efficiently and with depth $O(d)$. Finally, we introduce
a two-dimensional, depth-$2$, “coarse-grained” circuit architecture, composed
of random Clifford gates acting on $O(\log(n))$ qubits, for which we prove the
existence of long-range MIE and establish an unconditional quantum advantage.

##  I Introduction

Identifying computational tasks where quantum computers yield an advantage
compared to classical ones is a central goal of quantum information science.
To make effective progress, one hopes to understand which families of quantum
circuits admit efficient classical simulation algorithms, with a focus on
quantum circuit architectures that are experimentally feasible in the near-
term.

A key task involving quantum circuits is simulating measurement of their
output state in the standard basis. In the worst case, classically sampling
from this output distribution is intractable—even for the 2D brickwork
architecture, and with circuit depth as small as $d=3$ TerhalConstantDepth2004
. However, the classical hardness of this problem for circuit architectures
composed of random local gates remains less well understood. Such random
quantum circuits have diverse applications: they underpin quantum supremacy
experiments google2019supremacy ; harrow2017supremacy ; Aaronson2017supremacy
, provide benchmarking schemes for near-term quantum devices
boixo2018characterizing ; liu2021benchmarking , and model typical quantum
states arising from the dynamics or ground states of locally-interacting
quantum systems fisher2023random . Random instances of quantum circuits can
also help identify _generic_ features that relate to the classical hardness of
simulating quantum circuits.

Perhaps surprisingly, it has been conjectured that the complexity of sampling
from the output distribution of random geometrically local quantum circuits in
a two-dimensional architecture undergoes a _quantum advantage phase
transition_ : polynomial-time classical simulation is believed to be possible
if and only if the circuit depth is below a constant critical value $d^{*}$
NappShallow2022 . Recent works have proposed an intriguing physical origin for
this computational transition, linking it to a change in the amount of
_measurement-induced entanglement_ (MIE) in random quantum circuits
NappShallow2022 ; bao2021finite ; Liu2022MeasurementInduced .

Measurement-induced entanglement, which enables quantum protocols such as
teleportation and entanglement swapping, occurs when spatially separated
subsystems of a many-body state become entangled due to measurements on other
subsystems. When combined with unitary dynamics, MIE gives rise to emergent
phases with distinctive entanglement patterns Skinner2019Monitored ;
Chan2019Monitored ; Li2018Monitored . In 2D constant-depth quantum circuits,
where only nearby qubits may be entangled prior to measurements, MIE can lead
to the formation of entanglement between more distant qubits. This in turn can
affect the cost of classically simulating measurement of all qubits in the
output state of the quantum circuit. Based on numerical simulations and
heuristic mappings to statistical models, previous works bao2021finite ;
NappShallow2022  have suggested that for circuit depth $d<d^{*}$, MIE results
in _short-range_ entanglement, making the circuit amenable to classical
simulation techniques. However, for depths $d\geq d^{*}$, MIE induces _long-
range_ entanglement, which poses an obstacle for the efficient classical
simulation of random quantum circuits. Fig. 2 illustrates the change in
behaviour of MIE at the conjectured critical circuit depth $d^{*}=6$ for two-
dimensional random Clifford circuits. A similar transition in MIE has been
recently observed in random 2D circuits composed of one- and two-qubit gates
that form a universal gate set google2023measurementInduced .

Establishing this quantum advantage of random quantum circuits—and more
broadly, a separation between efficient quantum and classical computation—has
remained elusive. A series of recent works bravyi2018quantum ;
bravyi2020quantum ; BeneWatts2019Seperation ; Coudron2021Certifiable ;
LeGall2019AverageCase ; Grier2020Interactive ; caha2022single ;
caha2023colossal  have provided unconditional results addressing a more
limited notion of quantum advantage. In these works, a computational problem
is introduced that can be solved by geometrically-local constant-depth quantum
circuits, but not by any classical probabilistic circuit whose depth grows
sub-logarithmically with the input size. These works also provide
distributions over instances such that classical shallow circuits cannot even
solve an instance in the average case (see e.g., bravyi2018quantum ;
LeGall2019AverageCase ). Existing results along these lines make use of
certain specially tailored families of shallow quantum circuits. This raises
the question of whether generic shallow quantum circuits over a fixed
architecture demonstrate a similar quantum advantage.

In this paper, we answer this question in the affirmative. We describe a
family of random quantum circuits whose measurement distributions cannot be
simulated with shallow classical circuits. The key to our findings is
establishing a connection between the emergence of long-range MIE at the
critical depth $d^{*}$ and the limitations of low-depth classical simulation
methods.

Let us now describe our results in more detail.

B$L$C Figure 1: A 2D grid of qubits, partitioned into three regions $A,B$ and
$C$. The purple region indicates the single qubit $A$. The red region
indicates the square shielding region $B$ with side length $L$ which in this
example is $L=7$. All other qubits are in $C$.

Figure 2:  Classical simulation of MIE in 2D random Clifford circuits in the
brickwork architecture (see Fig. 3). Here $A$ is the qubit at the centre of
the grid, $C$ contains all the qubits on the boundary of the grid, and $B$
contains all the other qubits. Each data point is estimated from $1040$
circuit instance samples. The simulation is performed using Stim
gidney2021stim .

##  II Overview of results

###  II.1 Measurement-induced entanglement

Consider $n$ qubits at the vertices of a 2D square lattice. These qubits are
partitioned into three sets $A$, $B$, and $C$ where $A$ is a single qubit and
$B$ is a square region that shields $A$ from $C$, see Fig. 2. All qubits are
initialized in the $|0\rangle$ state. We apply a unitary $U$ to $A\cup B\cup
C$ and then measure qubits in $B$ in the computational basis. For the moment
we consider the case where $U$ is a random depth-$d$ circuit in the brickwork
architecture, see Fig. 3. We study the setting where the side length of $B$ is
much larger than $2d$. By a lightcone argument, this ensures that qubit $A$ is
unentangled from qubits in $C$ in the output state of the quantum circuit, and
only may become entangled as a result of the measurement of qubits in $B$.

In this setting, one can ask: _What is the shallowest depth $d^{*}$ at which
there is measurement-induced entanglement between $A$ and $C$?_

For simplicity we can imagine that we have already taken the limit of an
infinite lattice $n\rightarrow\infty$. Then for depth $d<d^{*}$ it is
conjectured that the expected purity $\mathbb{E}[\text{Tr}(\rho^{2}_{A})]$ of
qubit $A$ (averaged over the random choice of circuit and measurement outcomes
on $B$) approaches $1$ exponentially fast as $|B|$ grows, while for $d\geq
d^{\star}$ this expected purity is at most $1-\gamma(d)$ where $\gamma(d)>0$
is a constant that may depend on depth $d$, but is independent of the size of
the shielding region $B$ NappShallow2022 ; bao2021finite .

This scenario motivates the following definitions of short-range and long-
range MIE for output states of 2D random quantum circuits. In the following
definitions, a 2D, $n$-qubit, random quantum circuit is described by a
probability distribution over quantum circuits that act on $n$ qubits arranged
at the vertices of a two-dimensional square grid. A family of 2D random
quantum circuits is described by a sequence of such probability distributions,
with an increasing number of qubits $n_{1},n_{2},n_{3},\ldots$. Note that here
we do not restrict the gates of the circuit to act on nearest-neighbor qubits.

######  Property 1 (Short-range MIE).

A family $\mathcal{F}$ of random 2D quantum circuits satisfies the short-range
MIE property if the following holds. Suppose $\psi$ is a random pure state on
a 2D lattice of $n$ qubits that is generated according to $\mathcal{F}$. We
measure all qubits of $\psi$ in an $L\times L$ shielding region $B$ centred at
qubit $A\in[n]$, obtaining outcome $x\in\\{0,1\\}^{|B|}$. Let
$\rho_{A}=\rho_{A}(x)$ be the postmeasurement state of qubit $A$. Then

$\mathbb{E}\left[\mathrm{Tr}{\rho_{A}^{2}}\right]\geq 1-e^{-\Omega(L)}.$ (1)

Here the expectation is taken over the randomness in generating $\psi$ as well
as the distribution of random measurement outcomes on qubits in $B$.

######  Property 2 (Long-range MIE).

A family $\mathcal{F}$ of random 2D quantum circuits satisfies the long-range
MIE property if there is a constant $c\in(0,1)$ such that the following holds.
Let $\psi$ be a random pure state on a 2D lattice of $n$ qubits that is
generated according to $\mathcal{F}$. We measure all qubits of $\psi$ in an
$L\times L$ shielding region $B$ centred at qubit $A\in[n]$, obtaining outcome
$x\in\\{0,1\\}^{|B|}$. Let $\rho_{A}=\rho_{A}(x)$ be the postmeasurement state
of qubit $A$. Here $L$ is any positive integer such that $|C|\neq 0$. Then

$\mathbb{E}\left[\mathrm{Tr}{\rho_{A}^{2}}\right]<c,$ (2)

where the expectation is taken over the randomness in generating $\psi$ as
well as the distribution of random measurement outcomes on qubits in $B$.

As noted above, we expect 2D brickwork random circuits to have the short-range
MIE property for depth $d<d^{*}$ and to satisfy the long-range MIE property
for $d\geq d^{*}$. In fact, in the latter case we expect that measurement-
induced entanglement is “everywhere”—that is, present with respect to more
general tripartitions $[n]=ABC$ of the qubits (not just the case discussed
above where $B$ is a square shielding region centred at $A$). We also expect
that this proliferation of MIE gives rise to genuine multipartite
entanglement. We shall use the following notion of long-range tripartite MIE,
which is phrased in more general terms and can be applied to random circuits
in other architectures.

######  Property 3 (Long-range tripartite MIE).

A family $\mathcal{F}$ of random quantum circuits satisfies the long-range
tripartite MIE property if there are constants $c_{1},c_{2}\in(0,1)$ such that
the following holds. Suppose $\psi$ is a random $n$-qubit pure state that is
generated according to $\mathcal{F}$. Let $\Omega=\\{h,i,j\\}\subseteq[n]$ be
a uniformly random triple of qubits. Let $\rho_{\Omega}=\rho_{\Omega}(x)$ be
the state of qubits in $\Omega$ after measuring all other qubits of $\psi$ in
the computational basis and obtaining outcome $x\in\\{0,1\\}^{n-3}$. Let
$\rho_{h},\rho_{i},\rho_{j}$ be its one-qubit reduced density matrices. Then,
with probability at least $c_{1}>0$ we have

$\mathrm{Tr}[\rho_{h}^{2}]<c_{2}\quad\text{and}\quad\mathrm{Tr}[\rho_{i}^{2}]<c_{2}\quad\text{and}\quad\mathrm{Tr}[\rho_{j}^{2}]<c_{2}.$
(3)

Here the probability is over the random choice of $\psi$, the choice of triple
$\\{h,i,j\\}$, and the random measurement outcomes on qubits in
$[n]\setminus\\{h,i,j\\}$.

Rigorously establishing the conjectures described above, and the existence of
a phase transition in measurement-induced entanglement for 2D brickwork
circuits at a constant depth $d^{*}$, is a challenging open problem. Part of
the challenge is that the shallow circuit depth does not allow the quantum
system to fully randomize in most senses of interest. On the other hand, for
larger circuit depths $d$ growing with $n$, random circuits can be easier to
analyze as they begin to inherit properties of the Haar-random unitary
ensemble, such as the unitary $t$-design property and anticoncentration.

Indeed, we show that long-range MIE exists whenever there is subsystem
anticoncentration–a feature of random quantum circuits which is expected to
hold for depth $\Omega(\log(n))$ Dalzell2022AntiConcentration . Let
$P_{AB}(0)=\langle 0^{ABC}|U^{\dagger}|0\rangle\langle
0|_{AB}U|0^{ABC}\rangle$ be the probability of measuring all-zeros on qubits
in $AB$. Define a measure of subsystem anticoncentration

$\chi\equiv 4^{|AB|}\mathbb{E}_{U}[P_{AB}(0)^{2}]-1.$ (4)

Here $\chi$ depends on the tripartition $ABC$ as well as the random circuit
ensemble. Note that if $U$ is a Haar-random $n$-qubit unitary then

$\chi_{\mathrm{Haar}}=\frac{2^{|AB|}-1}{2^{|ABC|}+1}$

which is exponentially small in $|C|$. We say that the subsystem $AB$
anticoncentrates with respect to a random circuit ensemble if $\chi\rightarrow
0$ as $|C|$ grows.

The following result shows that subsystem anticoncentration implies long-range
MIE.

######  Theorem 1 (Informal).

For any tripartition of the qubits $ABC$ where $A$ is a single qubit, we have

$\mathbb{E}\left[\mathrm{Tr}{\rho_{A}^{2}}\right]\leq\frac{1}{2}+\frac{3}{2}\sqrt{\chi}.$

We will use this bound to establish long-range MIE in a certain “coarse-
grained” circuit architecture which is introduced below; this describes
depth-$2$ circuits with gates acting on $O(\log(n))$ qubits at a time.
However, we expect long-range MIE to be present even in constant-depth 2D
random quantum circuits composed of two-local gates and with depth above the
critical value. Such circuits do not satisfy the subsystem anticoncentration
condition considered above. Indeed, for $|C|<n$, the $\chi$ value for
depth-$d$ random quantum circuits composed of two-local gates over an
arbitrary architecture admits the following lower bound

$\displaystyle\chi$
$\displaystyle=\sum_{s\in\\{0,1\\}^{|AB|}}\mathbb{E}_{U}[\langle
0^{n}|U^{\dagger}(Z(s)_{AB}\otimes I_{C})|0^{n}\rangle^{2}]-1$
$\displaystyle\geq\mathbb{E}_{U}[\langle
0^{n}|U^{\dagger}Z_{A}U|0^{n}\rangle^{2}]\geq\frac{1}{3}\left(\frac{2}{5}\right)^{d}$

where the last inequality follows from Lemma 2.12 in Ref. liu2021moments ; see
also barak2020spoofing . Thus, $\chi\geq\Omega(1)$ for $d=O(1)$, demonstrating
that a different proof technique is needed to establish long-range MIE in this
setting.

Next we describe how MIE is related to classical simulation and quantum
advantage.

###  II.2 Shallow and efficient classical simulation

We obtain a simple, efficient, and shallow classical simulation of 2D quantum
circuits under the condition that they only generate short-range MIE. We
expect that this condition is satisfied by 2D brickwork random circuits in the
low-depth regime $d<d^{*}$ where MIE is expected to be short-range.

Our classical simulation algorithm is a modified version of the recently
introduced “gate-by-gate” method bravyi2022simulate .

######  Theorem 2 (Informal).

Consider a depth-$d$ quantum circuit $U=U_{t}U_{t-1}\ldots U_{1}$ acting on
$n$ qubits arranged at the vertices of a 2D grid. Suppose that each gate in
the circuit is either a CNOT gate between nearest-neighbor qubits on the grid,
or a single-qubit gate. Suppose that the output state of any subcircuit of $U$
satisfies the short-range MIE condition Eq. 1. Then there is an efficient
algorithm which samples from the output distribution of $U$. Moreover, this
probabilistic classical algorithm can be parallelized to depth $O(d)$ using
gates that act on $O(\log^{2}(n))$ bits at a time.

The classical circuit in the above can be parallelized to depth $O(d)$ even in
a “programmable” setting where it takes as input the specification of the
individual gates $U_{1},U_{2},\ldots,U_{t}$ in the circuit and outputs a
binary string approximately sampled from the output distribution.

Our algorithm complements an existing technique from Ref. NappShallow2022  for
classically simulating low-depth 2D circuits which is efficient under a
different criterion for short-range MIE. The ‘patching algorithm’ described in
NappShallow2022  proceeds by first sampling from small disjoint subregions of
the 2D lattice and then patching them together to obtain an overall sample
from the output distribution. This algorithm succeeds when the short-range MIE
property holds for subregions $A$ of size $O(\log^{2}(n))$ and when $X=A\cup
B\cup C$ corresponds to a subregion $X\subset[n]$ obtained by tracing out
disconnected squares of side $O(\log(n))$ from the lattice. In contrast, our
simulation algorithm for the quantum circuit $U$ in Theorem 2 relies on any
subcircuit of $U$ exhibiting short-range MIE when $A$ is a single qubit and
$A\cup B\cup C=[n]$ is a tripartition of the entire lattice.

Figure 3: 2D brickwork architecture on a $6\times 6$ grid of qubits. Edges
with the same color indicate two-qubit gates that can be applied
simultaneously in a single layer. A circuit of depth $d$ applies a sequence of
$d$ layers that rotates through the four colors.

###  II.3 Quantum advantage with random shallow Clifford circuits

Next we specialize to shallow Clifford circuits. These circuits are capable of
outperforming classical constant-depth circuits at certain tasks—the kind of
quantum advantage described in Refs. bravyi2018quantum ; bravyi2020quantum ;
BeneWatts2019Seperation ; Coudron2021Certifiable ; LeGall2019AverageCase ;
Grier2020Interactive ; caha2022single ; caha2023colossal . More precisely,
these works use classically controlled (or “programmable”) Clifford circuits:
the quantum circuit takes as input a binary string $x$ and then samples from
the output distribution of a Clifford circuit $C_{x}$ that depends on the
input.

To study quantum advantage in random Clifford circuits we view them as
programmable Clifford circuits with random inputs. That is, for any depth-$d$
circuit architecture with gates acting on $k$-qubits at a time, we consider a
controlled Clifford circuit that takes as input a specification of the
individual gates in the circuit. Note that a $k$-qubit Clifford gate can be
specified by $O(k^{2})$ bits. So the programmable Clifford circuit is also
depth-$d$ but has gates that act on $O(k^{2})$ qubits at a time.

Can this programmable Clifford circuit, with random input, be simulated by a
shallow classical circuit? For a given choice of gates (input) the classical
simulator succeeds if its output distribution is close in total variation
distance to the correct output distribution. We say that a classical
probabilistic circuit simulates random Clifford circuits in this architecture
if it succeeds with high probability over the choice of random gates.

The following result shows that shallow random Clifford circuit families with
$k=O(1)$-qubit gates that generate long-range tripartite MIE cannot be
simulated by constant-depth classical circuits using gates that act on
$K=O(1)$ bits at a time.

######  Theorem 3 (Informal).

Consider a depth-$d$ circuit architecture with random Clifford gates. Suppose
that the family of random Clifford circuits in this architecture satisfies the
long-range tripartite MIE property (3). Suppose $n$ is sufficiently large.
Then a probabilistic classical circuit composed of gates with fan-in $K$ and
circuit depth $D$ which simulates $n$-qubit random Clifford circuits in this
architecture satisfies $D\geq\frac{1}{4}\frac{\log(n)}{\log(K)}$.

Since it is conjectured that shallow Clifford circuits in a 2D brickwork
architecture with depth $d\geq d^{*}$ satisfy the long-range tripartite MIE
property, this result provides evidence that such random shallow Clifford
circuits attain a quantum advantage over classical shallow circuits.

The proof of Theorem 3 extends the classical lower bound from Ref.
bravyi2018quantum  which can be viewed as exploiting the fact that tripartite
MIE in 2D grid graph states is hard for a classical shallow circuit to
simulate. While that proof made use of the structure of 2D grid graph states,
here we show that long-range tripartite MIE is all that is needed for quantum
advantage.

Note that Theorem 3 applies to more general circuit architectures beyond the
2D brickwork architecture. Can we rigorously establish long-range MIE, long-
range tripartite MIE, and quantum advantage in some architecture of random 2D
circuits?

To this end, we introduce a “coarse-grained” architecture shown in Fig. 4. The
qubits are arranged on a $\sqrt{n}\times\sqrt{n}$ two-dimensional lattice and
the circuit applies only two layers of gates. Each gate acts on a square
$\tau\times\tau$ subgrid of qubits. Note that here the depth of the quantum
circuit is $2$ and $\tau$ is a parameter that describes the locality of gates.
This parameter plays the same role as circuit depth in the 2D brickwork
architecture—it measures the linear size of the lightcone of a single qubit
111In particular, if $U$ is a coarse-grained circuit and $O_{j}$ is an
operator acting on qubit $j$, then the support of $UO_{j}U^{\dagger}$ is
contained within a square region of size $O(\tau^{2})$ centered at $j$. .

######  Theorem 4.

Random coarse-grained Clifford circuits with $\tau=O(\sqrt{\log(n)})$ and with
$n$ sufficiently large, satisfy both the long-range MIE property, and the
long-range tripartite MIE property.

To prove Theorem 4 we first show that the coarse-grained architecture with the
stated choice of $\tau$ satisfies a strong form of subsystem anticoncentration
in which the parameter $\chi$ from Eq. 4 decays exponentially with the size of
$C$. This subsystem anticoncentration is established using a (first moment)
probabilistic method. We then show that for Clifford circuits this strong form
of subsystem anticoncentration is enough to guarantee both long-range and
long-range tripartite MIE.

As a direct corollary of Theorems 3 and 4 we obtain an unconditional quantum
advantage with random Clifford circuits in the coarse-grained architecture:

######  Theorem 5.

Random coarse-grained Clifford circuits with $\tau=O(\sqrt{\log(n)})$ and with
$n$ sufficiently large, cannot be simulated by any probabilistic classical
circuit of depth $D<\frac{1}{4}\frac{\log(n)}{\log(K)}$ and fan-in $K$.

The family of random coarse-grained Clifford circuits with
$\tau=O(\sqrt{\log(n)})$ can be implemented (in a programmable sense) via a
depth-$2$ quantum circuit with gates acting on $k=O(\log(n)^{2})$ qubits. In
contrast, Theorem 5 states that any classical probabilistic circuit composed
of gates with fan-in $K=\mathrm{poly}{\log(n)}$ that simulates the random
circuit family must have depth $D>\Omega(\log(n)/\log\log(n))$.

###  II.4 Discussion

We have shown that an unconditional quantum advantage with random shallow
Clifford circuits follows from the presence of long-range tripartite MIE. We
also exhibited a random circuit architecture with this property.

Moreover, Theorems 2 and 3 provide evidence that 2D random shallow Clifford
circuits in the standard brickwork architecture undergo a quantum advantage
phase transition that coincides with the emergence of long-range (and long-
range tripartite) MIE at the critical depth $d^{*}=6$. This provides a scaled-
down Clifford counterpart to the conjectured phase transition in the classical
hardness of simulating random circuits composed of two-qubit Haar-random gates
in the same architecture.

There are several open questions related to this work. Can we prove the
existence of a phase transition in MIE at a constant critical circuit depth
$d^{*}$ for 2D brickwork random shallow circuits? Can we show that the quantum
advantage with shallow circuits follows from the long-range MIE property
(rather than the tripartite version)? Can we establish a quantum advantage in
circuit depth for random circuits composed of Haar-random gates (instead of
Clifford gates)?

In the remaining sections of the paper we prove Theorems 1-4, respectively.

##  III Subsystem anticoncentration implies long-range MIE

Here we show that random circuits that anticoncentrate also exhibit long-range
measurement-induced entanglement. In particular, we prove Theorem 1.

Suppose $U=U_{m}U_{m-1}\ldots U_{1}$ is an $n$-qubit quantum circuit where
each gate $U_{j}$ is a Haar random $k$-qubit gate acting on the qubits in its
support. Here our results apply to general quantum circuits—i.e., we do not
specify an architecture or require the circuit to act on a system of qubits in
a 2D geometry. In the following we shall relate properties of $U$ to those of
a random Clifford circuit $D=D_{m}D_{m-1}\ldots D_{1}$ where each $D_{i}$ is a
random Clifford unitary that acts on the qubits in the support of $U_{i}$.

For any $s\in\\{0,1\\}^{n}$, let $Z(s)=\prod_{j=1}^{n}Z_{j}^{s_{j}}$. Here
$Z_{j}$ is the Pauli $Z$ operator acting on the $j$th qubit. Let $[n]=ABC$ be
a tripartition of the qubits such that $|A|=1$. For the output state of the
Clifford circuit $D$, the presence or absence of post-measurement entanglement
between $A$ and $C$ after measuring $B$ is determined by a set $S$ defined as
follows (this set indexes “entanglement-killing” stabilizers of the state
$D|0^{n}\rangle$). For $P=X,Y,Z$, let

$\displaystyle S_{P}\equiv$
$\displaystyle\\{s\in\\{0,1\\}^{n}:DZ(s)D^{\dagger}=(-1)^{\alpha}P_{A}\otimes
Z(r)_{B}\otimes I_{C}$ $\displaystyle\text{ for some
}r\in\\{0,1\\}^{|B|},\alpha\in\\{0,1\\}\\}$ (5)

and let

$S=S_{X}\cup S_{Y}\cup S_{Z}.$ (6)

######  Lemma 1.

Suppose $|\phi\rangle=D|0^{n}\rangle$ where $D$ is a Clifford unitary. Let
$[n]=ABC$ be a tripartition of the qubits where $|A|=1$. There is post-
measurement entanglement between $A$ and $C$ after measuring all qubits of $B$
in the state $\phi$, if and only if $S=\emptyset$.

###### Proof.

Let $G=\\{DZ(s)D^{\dagger}:s\in\\{0,1\\}^{n}\\}$ be the stabilizer group of
$\phi$.

First suppose $S$ is nonempty. Then $(-1)^{\alpha}P_{a}\otimes Z(r)_{B}\otimes
I_{C}$ is a stabilizer of $\phi$, for some $P\in\\{X,Y,Z\\}$,
$r\in\\{0,1\\}^{n}$, $\alpha\in\\{0,1\\}$. After measuring all qubits in $B$
in the computational basis, the postmeasurement state is stabilized by $\pm
P_{A}$ for some choice of sign $\pm 1$ determined by the measurement outcomes.
In other words, the postmeasurement state is a pure 1-qubit stabilizer state.

Next suppose we measure all qubits in $B$ , obtain measurement outcome
$x\in\\{0,1\\}^{|B|}$, and the postmeasurement state $\rho_{A}$ on qubit $A$
is pure. The stabilizer group of this state is generated by

$G^{\prime}=\\{(-1)^{x_{j}}Z_{j}:j\in B\\}\cup G^{\prime\prime}$

where

$G^{\prime\prime}=\\{P\in G:P\text{ is $Z$-type on $B$}\\}.$

(We say that an $n$-qubit Pauli operator is _$Z$ -type_ if it is a tensor
product of $I$ and $Z$ Pauli operators.) Since $\rho_{A}$ is pure, it must
have a stabilizer $\pm P_{A}\otimes I_{BC}$ for some $P\in\\{X,Y,Z\\}$. This
stabilizer can be expressed as a product of elements from the set of
generators above. That is, for some $T\subseteq G^{\prime\prime}$ and
$R\subseteq B$ we have

$P_{A}=\prod_{Q\in T}Q\prod_{j\in R}(-1)^{x_{j}}Z_{j}.$

From the above we conclude that

$(-1)^{\sum_{j\in R}x_{j}}P_{A}\otimes Z(R)_{B}\otimes I_{C}=\prod_{Q\in
T}Q=DZ(s)D^{\dagger}$

for some binary string $s\in\\{0,1\\}^{n}$. Therefore $s\in S$ and
$S\neq\emptyset$.

∎

Lemma 1 shows that emptiness of $S$ determines postmeasurement entanglement
for Clifford circuits. We now show how this criterion can be extended to our
random non-Clifford circuit $U$ of interest.

Define $\Pi(x)=|x\rangle\langle x|_{B}\otimes I_{AC}$ for
$x\in\\{0,1\\}^{|B|}$. If we measure all qubits in $B$, we obtain $x$ with
probability

$q(x)\equiv\langle 0^{n}|U^{\dagger}\Pi(x)U|0^{n}\rangle.$

The postmeasurement state on $A$ is then

$\rho(x)=\frac{1}{q(x)}\mathrm{Tr}_{BC}\left(\Pi(x)U|0^{n}\rangle\langle
0^{n}|U^{\dagger}\Pi(x)\right).$

######  Theorem 6 (Formal version of Theorem 1).

The expected purity of the postmeasurement state on $A$ is upper bounded as

$\mathbb{E}_{U}\mathbb{E}_{x\sim
q}\mathrm{Tr}(\rho(x)^{2})\leq\frac{1}{2}+\frac{1}{2}\sqrt{3\mathbb{E}_{D}[|S|]}.$
(7)

Note that the LHS describes the purity of the postmeasurement state in the
universal circuit $U$, while the RHS only involves an average over the
Clifford circuit $D$. Moreover, this average is upper bounded as

$\displaystyle\frac{1}{3}\mathbb{E}_{D}[|S|]=\mathbb{E}_{D}[|S_{Z}|]$
$\displaystyle\leq\mathbb{E}_{D}\left[\sum_{s\in\\{0,1\\}^{AB},s\neq
0^{|AB|}}\langle 0^{n}|D^{\dagger}Z(s)_{AB}\otimes
I_{C}D|0^{n}\rangle^{2}\right]$
$\displaystyle=4^{|AB|}\mathbb{E}_{D}\left[|\langle
0^{n}|D^{\dagger}(|0\rangle\langle 0|_{AB}\otimes
I_{C})D|0^{n}\rangle|^{2}\right]-1$
$\displaystyle=4^{|AB|}\mathbb{E}_{U}\left[|\langle
0^{n}|U^{\dagger}(|0\rangle\langle 0|_{AB}\otimes
I_{C})U|0^{n}\rangle|^{2}\right]-1$ (8)

where in the last line we used the two-design property of the Clifford group.
Here Eq. 8 is the quantity denoted $\chi$ in the Introduction, which measures
anticoncentration of subsystem $AB$.

###### Proof of Eq. 7.

Write

$\alpha_{P}(x)\equiv\frac{1}{2}\langle
0^{n}|U^{\dagger}\Pi(x)\cdot\left(P_{A}\otimes I_{BC}\right)U|0^{n}\rangle,$

so that

$\rho(x)=\frac{1}{2\alpha_{I}(x)}\sum_{P\in\\{I,X,Y,Z\\}}\alpha_{P}(x)P.$

Using the fact that
$\sum_{x}\Pi(x)\otimes\Pi(x)=2^{-|B|}\sum_{s\in\\{0,1\\}^{|B|}}Z(s)\otimes
Z(s)$ we get

$\displaystyle\sum_{x\in\\{0,1\\}^{|B|}}|\alpha_{P}(x)|^{2}$
$\displaystyle=\frac{1}{4\cdot 2^{|B|}}\sum_{s\in\\{0,1\\}^{|B|}}|\langle
0^{n}|U^{\dagger}(P_{A}\otimes Z(s)_{B})U|0^{n}\rangle|^{2}.$

Then

$\displaystyle\mathbb{E}_{U}\mathbb{E}_{x\sim
q}\left(\frac{|\alpha_{P}(x)|}{2\alpha_{I}(x)}\right)=2^{|B|}\mathbb{E}_{U}\mathbb{E}_{x\sim\mathrm{unif}}|\alpha_{P}(x)|$
$\displaystyle\leq
2^{|B|}\left(\mathbb{E}_{U}\mathbb{E}_{x\sim\mathrm{unif}}|\alpha_{P}(x)|^{2}\right)^{1/2}$
$\displaystyle=\left(\frac{1}{4}\sum_{s\in\\{0,1\\}^{|B|}}\mathbb{E}_{U}|\langle
0^{n}|U^{\dagger}(P_{A}\otimes Z(s)_{B})U|0^{n}\rangle|^{2}\right)^{1/2}.$

Now we use the fact that every gate in $U$ is drawn from the Haar measure, and
the fact that the Clifford group is a two-design. This allows us to replace
the average over $U$ with the average over the random Clifford circuit $D$ in
the above. Then for $P\in\\{X,Y,Z\\}$ we have

$\displaystyle\mathbb{E}_{U}\mathbb{E}_{x\sim
q}\left(\frac{|\alpha_{P}(x)|}{2\alpha_{I}(x)}\right)$
$\displaystyle\leq\left(\frac{1}{4}\sum_{s\in\\{0,1\\}^{|B|}}\mathbb{E}_{D}|\langle
0^{n}|D^{\dagger}(P_{A}\otimes Z(s)_{B})D|0^{n}\rangle|^{2}\right)^{1/2}$
$\displaystyle=\frac{1}{2}\sqrt{\mathbb{E}_{D}|S_{P}|}$
$\displaystyle=\frac{1}{2\sqrt{3}}\sqrt{\mathbb{E}_{D}|S|}.$ (9)

Now the expected purity of the postmeasurement state is upper bounded as

$\displaystyle\mathbb{E}_{U}\mathbb{E}_{x\sim q}\mathrm{Tr}(\rho(x)^{2})$
$\displaystyle=\mathbb{E}_{U}\mathbb{E}_{x\sim
q}\sum_{P\in\\{I,X,Y,Z\\}}\frac{2|\alpha_{P}(x)|^{2}}{4|\alpha_{I}(x)|^{2}}$
$\displaystyle\leq\mathbb{E}_{U}\mathbb{E}_{x\sim
q}\sum_{P\in\\{I,X,Y,Z\\}}\frac{|\alpha_{P}(x)|}{2|\alpha_{I}(x)|}$
$\displaystyle=\frac{1}{2}+3\mathbb{E}_{U}\mathbb{E}_{x\sim
q}\frac{|\alpha_{Z}(x)|}{2|\alpha_{I}(x)|}$

where we used the fact that $|\alpha_{P}(x)|\leq\alpha_{I}(x)$ for all
$x\in\\{0,1\\}^{|B|}$. Plugging Eq. 9 into the above completes the proof.

∎

##  IV Efficient and shallow classical simulation of 2D circuits with short-
range MIE

In this section we prove Theorem 2. In particular, we consider the output
state $|\psi\rangle=U|0^{n}\rangle$ of a 2D, depth $d$, quantum circuit and
describe an efficient classical simulation method that approximately samples
from its output distribution, assuming that the state after each gate in the
circuit has short-range MIE. We will also show that the algorithm can be
parallelized to depth $O(d)$. The simulation algorithm is a variant of the
gate-by-gate method proposed in Ref. bravyi2022simulate .

Here we assume the circuit is expressed as $U=U_{m}U_{m-1}\ldots
U_{1}|0^{n}\rangle$ where each $U_{t}$ is either a $\mathrm{CNOT}$ gate or a
single-qubit gate.

In addition to the output state $\psi$ and its output distribution
$P(z)=|\langle z|\psi\rangle|^{2}$, it will also be convenient to consider
states and output distributions associated with subcircuits. That is, define

$|\psi_{t}\rangle=U_{t}U_{t-1}\ldots U_{1}|0^{n}\rangle\quad\text{and}\quad
P_{t}(z)=|\langle z|\psi_{t}\rangle|^{2},$

for $0\leq t\leq m$ and $z\in\\{0,1\\}^{n}$.

Now imagine that we measure all qubits in $BC$ of the state $\psi_{t}$ and
obtain outcomes $\omega\in\\{0,1\\}^{|BC|}$. The probability of this
measurement outcome is
$P_{t,BC}(\omega)\equiv\sum_{y_{BC}=\omega_{BC}}P_{t}(y)$. The postmeasurement
state on $A$ is

$\rho_{t}(\omega)=\frac{1}{P_{t,BC}(\omega)}\langle\omega|_{BC}|\psi_{t}\rangle\langle\psi_{t}|\omega\rangle_{BC}.$
(10)

If instead we only measure the qubits in $B$ of the state $\psi_{t}$,
obtaining outcome $\omega_{B}$, then the postmeasurement state of $A$ is

$\tilde{\rho}_{t}(\omega_{B})\equiv\frac{1}{P_{t,B}(\omega_{B})}\langle\omega_{B}|\mathrm{Tr}_{C}\left(|\psi_{t}\rangle\langle\psi_{t}|\right)|\omega_{B}\rangle$
(11)

where $P_{t,B}(\omega_{B})=\sum_{y:y_{B}=\omega_{B}}P_{t}(y)$. The following
claim shows that the expected fidelity between $\rho_{t}(\omega)$ and
$\tilde{\rho}_{t}(\omega_{B})$ is equal to the average purity of the latter
state.

######  Lemma 2.

$\mathbb{E}_{z\sim
P_{t,BC}}\left[F(\rho_{t}(z),\tilde{\rho}_{t}(z_{B}))\right]=\mathbb{E}_{z_{B}\sim
P_{t,B}}\left[\mathrm{Tr}(\tilde{\rho}_{t}(z_{B})^{2})\right]$

###### Proof.

Using the definitions (Eqs. 10 and 11) we have

$\displaystyle\mathbb{E}_{z\sim
P_{t,BC}}\left[F(\rho_{t}(z),\tilde{\rho}_{t}(z_{B}))\right]$
$\displaystyle=\sum_{z\in\\{0,1\\}^{|BC|}}\langle\psi_{t}|(|z_{B}\rangle\langle
z_{B}|\otimes|z_{C}\rangle\langle
z_{C}|)\tilde{\rho}_{t}(z_{B})|\psi_{t}\rangle$
$\displaystyle=\sum_{z_{B}\in\\{0,1\\}^{|B|}}\langle\psi_{t}|\left(|z_{B}\rangle\langle
z_{B}|\otimes I_{C}\right)\tilde{\rho}_{t}(z_{B})|\psi_{t}\rangle$
$\displaystyle=\sum_{z_{B}\in\\{0,1\\}^{|B|}}P_{t,B}(z_{B})\mathrm{Tr}(\tilde{\rho}_{t}(z_{B})^{2}).$

∎

Define conditional probability distributions

$q_{t}(x_{A}|z_{B}z_{C})\equiv\langle x_{A}|\rho_{t}(z_{B}z_{C})|x_{A}\rangle$
(12)

and

$\tilde{q}_{t}(x_{A}|z_{B})\equiv\langle
x_{A}|\tilde{\rho}_{t}(z_{B})|x_{A}\rangle.$ (13)

In the above discussion we fixed a partition $[n]=ABC$ but in our classical
simulation algorithm—Algorithm 1—we allow this partition to depend on $t$ in a
simple way. In particular, let $\Gamma\subseteq[m]$ be such that $U_{t}$ is a
single-qubit gate if and only if $t\in\Gamma$ (it is a $\mathrm{CNOT}$
otherwise).

Then for $t\in\Gamma$ we let $A(t)$ be the qubit on which $U_{t}$ acts, $B(t)$
be all qubits within a square subgrid centred at $A(t)$ with side length $L$,
and $C(t)=[n]\setminus(A(t)\cup B(t))$. We write $\mathrm{Square}_{L}(A)$ for
the set of all qubits that are a horizontal or vertical distance at most $L/2$
from qubit $A$, so that $B(t)=\mathrm{Square}_{L}(A(t))$.

######  Theorem 7 (Formal version of Theorem 2).

Let $\tilde{P}$ be the output distribution of Algorithm 1. Recall that
$\Gamma\subseteq[m]$ are the indices of one qubit gates in the circuit, and
$P_{t}(x)=|\langle x|U_{t}U_{t-1}\ldots U_{1}|\psi\rangle|^{2}$. Then

$\|\tilde{P}-P_{m}\|_{1}\leq
2\sum_{t\in\Gamma}\left(1-\mathop{\mathbb{E}}_{z\sim
P_{t,B(t)}}\left[\mathrm{Tr}(\tilde{\rho}_{t}(z)^{2})\right]\right)^{1/2}.$
(14)

The proof of Eq. 14 is given in the Appendix. It is obtained by combining
Lemma 2 with a robustness property of the gate-by-gate algorithm established
in Ref.bravyi2022simulate , which we adapt to our setting.

The left-hand side of Eq. 14 is the approximation error of our algorithm: the
total variation distance between the distribution sampled by our classical
simulator, and the true output distribution of the quantum circuit. We are
successful in classically simulating the quantum circuit if we can make the
right-hand-side of Eq. 14 small— at most $\epsilon=O(n^{-c})$ for a given
constant $c\geq 1$. Let us assume that MIE in the circuit is short-ranged in
the sense that, at each time $1\leq t\leq m$ in the circuit, the output state
$|\psi_{t}\rangle$ has the short-range MIE property (1). In particular, for
each $t\in\Gamma$ this gives

$\mathop{\mathbb{E}}_{z\sim
P_{t,B(t)}}\left[\mathrm{Tr}(\tilde{\rho}_{t}(z)^{2})\right]=1-e^{-\Omega(L)}.$
(15)

Plugging this into Eq. 14 we see that the RHS is $O(me^{-L})$. For polynomial-
sized circuits (i.e., $m=O(\mathrm{poly}(n))$) we can make this approximation
error at most $\epsilon=O(n^{-c})$ by choosing $L=O(\log(n))$.

Let us now show that Algorithm 1 has $O(\mathrm{poly}(n))$ runtime with this
choice of $L$. The runtime of Algorithm 1 is $O(mT(L))$ where $T(L)$ is the
cost of classically computing the conditional probability
$\tilde{q}_{t}(y|x_{B(t)})$ in line 9 of the algorithm. Using (Eqs. 11 and 13)
we see that this conditional probability is a ratio of the two marginal
probabilities

$\langle
y_{A}x_{B}|\mathrm{Tr}_{C}(|\psi_{t}\rangle\langle\psi|_{t})|y_{A}x_{B}\rangle$

and $P_{t,B}(x_{B})$. Since we are tracing out subsystem $C$, each of these
marginals can be computed by removing all gates of $U_{t}U_{t-1}\ldots U_{1}$
that lie outside of the so-called lightcone of $AB$. This gives a depth $d$
circuit $V$ acting on qubits of a subgrid with side length $L+2d$. Each of
these marginal probabilities can be computed using a classical tensor network
algorithm from Ref. Aaronson2017supremacy  (see Thm 4.3 of that work), which
uses runtime $T(L)=2^{O(d(L+d))}$. Thus, for constant-depth $d=O(1)$ circuits
with $m=\mathrm{poly}(n)$ gates and with the choice $L=O(\log(n))$, the
runtime of Algorithm 1 is $\mathrm{poly}(n)$.

Finally, we observe that Algorithm 1, when applied to simulate a quantum
circuit of depth $d$, can be parallelized to depth $O(d)$ if we allow
classical gates that act on $K=O(L^{2})$ bits. To see this, let us describe
how to parallelize all updates to the bit string $x$ in step 2. of the
algorithm for a single layer (depth-$1$ circuit) of quantum gates. To this end
note that all updates of $x$ corresponding to gates whose support is within a
square region of side length $L$ only depend on bits of $x$ in a larger square
region of side length $\sim 3L$. These updates can therefore be performed by a
single classical “gate” that acts on bits in the larger square region of side
length $3L$. By partitioning the grid into square regions with side length
$3L$ we can update $1/9$ of the bits of $x$ using a single layer of such gates
in parallel. We can then simulate the entire depth-$1$ circuit using a
classical circuit of depth $9$.

Algorithm 1 Simulation of circuits with short-range MIE (via the gate-by-gate
method bravyi2022simulate )

Input: An $n$-qubit 2D quantum circuit $U=U_{m}\cdots U_{2}U_{1}$ over the
gate set $\mathrm{CNOT}+\mathrm{SU}(2)$, and an integer $L$.
Output: $x\in\\{0,1\\}^{n}$ with prob. $\tilde{P}(x)$ satisfying Eq. 14.

1:$x\leftarrow 0^{n}$

2:for $t=1$ to $m$ do

3: if $U_{t}=\mathrm{CNOT}_{ij}$ then

4: $x_{j}\leftarrow x_{j}\oplus x_{i}$

5: else if $U_{t}\in SU(2)$ acts on qubit $k\in[n]$ then

6: $A(t)\leftarrow k$

7: $B(t)\leftarrow\mathrm{Square}_{L}(A(t))$

8: $C(t)\leftarrow[n]\setminus A(t)\cup B(t)$

9: Sample $y\in\\{0,1\\}$ from the conditional probability distribution
$\tilde{q}_{t}(y|x_{B(t)})$

10: $x\leftarrow y_{A(t)}x_{B(t)}x_{C(t)}$

11: end if

12:end for

13:return $x$

##  V Long-range tripartite MIE implies unconditional quantum advantage in any
architecture

In this section we prove Theorem 3. We begin by describing what we mean by a
circuit architecture and the associated family of random Clifford circuits.
Then we consider the long-range tripartite MIE property (3) and specialize it
to Clifford circuits, using the fact that a three qubit stabilizer state that
is entangled with respect to any bipartition of the qubits (Cf. Eq. 3), is
locally Clifford equivalent to the GHZ state. Finally, we show random Clifford
circuits which satisfy the long-range tripartite MIE property cannot be
simulated by shallow probabilistic classical circuits.

Our proof strategy for lower bounding classical circuits which is based on
identifying GHZ-type measurement-induced entanglement is similar to the proof
strategy from Ref. bravyi2018quantum . The difference is that here we aim to
make this strategy work with Clifford circuits composed of uniformly random
gates, and we find that long-range tripartite MIE is all that we require for
quantum advantage.

###  V.1 Random Clifford circuits

######  Definition 8 ($n$-qubit circuit template).

An $n$-qubit circuit template $\mathcal{T}$ is a tuple of subsets
$(m_{1},m_{2},\ldots,m_{R})$ such that $m_{i}\subseteq[n]$ for $1\leq i\leq
R$. A quantum circuit in this template is a product $U_{R}U_{R-1}\ldots
U_{2}U_{1}$ of gates such that $U_{i}$ acts nontrivially only on qubits in
$m_{i}$. The template is said to be $k$-local if $|m_{i}|=k$ for all $1\leq
i\leq R$, and it is said to have depth $d$ if any quantum circuit in this
template can be implemented with circuit depth $d$.

######  Definition 9 (Circuit architecture).

A $k$-local, depth-$d$ circuit architecture
$\mathcal{A}=\\{\mathcal{T}_{n}\\}_{n\in\Gamma}$ is a sequence of $k$-local,
depth-$d$ circuit templates with an increasing number of qubits
$\Gamma=\\{n_{1},n_{2},n_{3}\ldots\\}$.

Any template $\mathcal{T}=(m_{1},m_{2},\ldots,m_{R})$ defines a random
Clifford circuit, obtained by choosing the gates $U_{1},U_{2},\ldots,U_{R}$ to
be uniformly random Clifford gates acting on their support. Similarly, an
architecture $\mathcal{A}$ is associated with a famiy of random Clifford
circuits.

We will be particularly interested in random Clifford circuits which produce
long-range tripartite entanglement in the sense of 3. We can specialize this
property to Clifford circuits as follows.

We say that a three-qubit stabilizer state $|\Phi\rangle$ is GHZ-type
entangled iff it is locally Clifford equivalent to the GHZ state. That is,
there exist single-qubit Clifford unitaries $C_{1},C_{2},C_{3}$ such that

$C_{1}\otimes C_{2}\otimes
C_{3}|\Phi\rangle=\frac{1}{\sqrt{2}}\left(|000\rangle+|111\rangle\right).$

It is a well-known fact that any three qubit stabilizer state which is not a
product state with respect to any bipartition of the qubits, is GHZ-type
entangled.

If $\phi$ is an $n$-qubit stabilizer state, we say that three qubits
$\\{h,i,j\\}\subseteq[n]$ exhibit GHZ-type MIE iff they share GHZ-type
entanglement after measuring all qubits in $[n]\setminus\\{h,i,j\\}$.

######  Property 4 (Long-range tripartite MIE, Clifford version).

The architecture $\mathcal{A}=\\{\mathcal{T}_{n}\\}_{n\in\Gamma}$ is said to
satisfy the long-range tripartite MIE property if there is an absolute
constant $c>0$ such that the following holds. Suppose $n\in\Gamma$ and
consider the circuit template $\mathcal{T}_{n}\in\mathcal{A}$. Suppose $U$ is
a random Clifford circuit with template $\mathcal{T}_{n}$, i.e. it is composed
of gates $U_{1},U_{2},\ldots,U_{R}$ chosen uniformly at random from the set of
$k$-qubit Clifford gates. Let $|\psi\rangle=U|0^{n}\rangle$. Choose a
uniformly random triple of qubits $\\{h,i,j\\}\subseteq[n]$. Then, with
probability at least $c>0$ (over the random choice of $U$ and the triple
$h,i,j$), the qubits $h,i,j$ exhibit GHZ-type MIE in the state $\psi$.

It is not hard to see that 4 is equivalent to 3 for the random Clifford
circuit family defined by an architecture $\mathcal{A}$. The condition Eq. 3
in the definition of long-range tripartite MIE property implies that the
three-qubit state $\rho_{\Omega}$ is not a product state with respect to any
bipartition of its qubits. Since in the case at hand it is also a stabilizer
state, it is GHZ-type entangled.

###  V.2 Requirements for classical simulation of GHZ-type MIE

Let us begin by considering what kinds of classical circuits are capable of
reproducing the measurement statistics of quantum states with GHZ-type MIE.

Suppose $U$ is an $n$-qubit Clifford circuit and
$|\psi\rangle=U|0^{n}\rangle$. Recall that we say that three qubits
$\\{h,i,j\\}\subseteq[n]$ exhibit GHZ-type measurement-induced entanglement
iff the state $\rho_{h,i,j}$ after measuring all other qubits in the
computational basis is locally Clifford equivalent to the GHZ state. We can
rephrase this definition in terms of the stabilizer group of $\psi$, as
follows: three qubits $\\{h,i,j\\}$ of $\psi$ exhibit GHZ-type measurement-
induced entanglement iff, for some tensor product $C_{h}\otimes C_{i}\otimes
C_{j}$ of single-qubit Clifford unitaries on $h,i,j$, the stabilizer group of
$C_{h}\otimes C_{i}\otimes C_{j}|\psi\rangle$ contains elements

$\displaystyle g_{1}$ $\displaystyle=X_{h}X_{i}X_{j}Z(s)$ $\displaystyle
g_{2}$ $\displaystyle=Z_{h}Z_{i}I_{j}Z(t)$ $\displaystyle g_{3}$
$\displaystyle=I_{h}Z_{i}Z_{j}Z(u),$ (16)

for some binary strings $s,t,u\in\\{0,1\\}^{n}$ such that
$s_{r}=t_{r}=u_{r}=0$ for $r\in\\{h,i,j\\}$.

In the following Lemma we consider a classical function
$m:\\{0,1,2\\}^{3}\rightarrow\\{0,1\\}^{n}$ which takes input
$b\in\\{0,1,2\\}^{3}$ describing measurement bases $X,Y,Z$ for qubits $h,i,j$
respectively, and produces output $m(b)\in\\{0,1\\}^{n}$. We are interested in
whether this function can simulate measurement of $\psi$ in the given bases
$b$ on qubits $h,i,j$ and the computational basis on all other qubits. Let
$Q(0),Q(1),Q(2)$ denote the single-qubit Clifford unitaries that change basis
from the $Z$ basis to the $X,Y,Z$ bases respectively (i.e.,
$Q(0)=(X+Z)/\sqrt{2},Q(1)=(Y+Z)/\sqrt{2},Q(2)=I$). Let $W(b)=Q(b_{h})\otimes
Q(b_{i})\otimes Q(b_{j})$ be the tensor product of single-qubit unitaries that
change basis to the one described by $b$. A necessary condition for such a
simulation of $\psi$ is that

$\langle m(b)|W(b)|\psi\rangle\neq 0,\quad b\in\\{0,1,2\\}^{3}.$ (17)

We show a condition under which Eq. 17 is not possible.

######  Lemma 3.

Suppose $h,i,j$ exhibit GHZ-type measurement-induced entanglement in the state
$|\psi\rangle=U|0^{n}\rangle$. Let $m:\\{0,1,2\\}^{3}\rightarrow\\{0,1\\}^{n}$
and write $m=m(b)$ with $b=b_{h}b_{i}b_{j}\in\\{0,1,2\\}^{3}$. Suppose that
each output bit $m_{r}$ depends on at most one of the input variables
$b_{h},b_{i},b_{j}$, and that

  * •

$m_{h}$ is independent of $b_{i},b_{j}$

  * •

$m_{i}$ is independent of $b_{h},b_{j}$

  * •

$m_{j}$ is independent of $b_{h},b_{i}$.

Then

$\mathrm{Pr}_{b\sim\mathrm{unif}(\\{0,1,2\\}^{3})}\left[\langle
m(b)|W(b)|\psi\rangle=0\right]\geq 1/27.$ (18)

The proof of Eq. 18 is given in the Appendix. It says that classical circuits
that are capable of simulating GHZ-type measurement induced entanglement must
have certain kind of input-output correlations. In the next section we will
see that this constraint is even more restrictive when $\psi$ is an $n$-qubit
state and many triples of qubits exhibit GHZ-type MIE.

###  V.3 Lower bound for classical probabilistic simulation

In the following we shall view a random Clifford circuit as a fixed circuit
with a random input that specifies the gates. That is, we construct a
controlled Clifford circuit which takes the specification of all Clifford
gates $U_{1},U_{2},\ldots,U_{R}$ as an input and then applies the
corresponding Clifford circuit to an $n$-qubit register.

For any $k$-local, $n$-qubit circuit template
$\mathcal{T}_{n}=(m_{1},m_{2},\ldots,m_{R})$ we define a controlled-Clifford
circuit as follows. The circuit has a data register of $n$ qubits which are
initialized in the $|0^{n}\rangle$ state. In addition, there is one input
register $I_{j}$ of size $O(k^{2})$ for each gate $j\in R$ in the circuit,
that contains enough qubits to store the description of an arbitrary $k$-qubit
Clifford gate. The $j$th gate in the circuit applies Clifford unitary $C$ on
qubits $m_{j}$ of the data register, controlled on the state $|C\rangle$ of
the input register $I_{j}$. An architecture $\mathcal{A}$ defines a family of
controlled Clifford circuits in this way, which we denote $CC(\mathcal{A})$.

Suppose $\mathcal{A}=\\{\mathcal{T}_{n}\\}_{n\in\Gamma}$ is a depth-$d$,
$k$-local architecture. As noted above we can construct an associated family
$CC(\mathcal{A})$ of depth-$d$ quantum circuits composed of $O(k^{2})$-local
controlled-Clifford gates. Under what conditions can the input/output
behaviour of this family of quantum circuits, with random inputs, be simulated
by a constant-depth classical circuit?

Consider a family of probabilistic classical circuits which implement
functions $\\{F_{n}\\}_{n\in\Gamma}$ with the following input/output
properties:

  1. 1.

For each $n\in\Gamma$, $F_{n}$ takes as input a list
$U_{1},U_{2},\ldots,U_{R}$ of $k$-local Clifford gates that define a quantum
circuit $U=U_{R}\ldots U_{2}U_{1}$ of depth $d$ in the template
$\mathcal{T}_{n}$.

  2. 2.

$F_{n}$ also takes as input a random string $r\in\\{0,1\\}^{\ell(n)}$ drawn
from some probability distribution $q_{n}$. Here $\ell(n)$ can be any function
of $n$ and $q_{n}$ can be any probability distribution over $\ell(n)$ bit
strings.

  3. 3.

The function outputs a binary string

$z=F_{n}(U_{1},U_{2},\ldots,U_{R},r)\in\\{0,1\\}^{n}.$

For ease of notation, we sometimes write $z=F_{n}(U,r)$.

We shall be interested in the case where each function $F_{n}$ is implemented
by a classical circuit with gates of fan-in $K$ and circuit depth $D$. In this
case each output bit $z_{j}$ of $F_{n}(U,r)$ depends on at most $K^{D}$ input
bits. In particular this implies that each output bit $z_{j}$ depends on at
most $K^{D}$ of the gates in the circuit (each gate is specified by $O(k^{2})$
bits).

If we draw $r\sim q_{n}$ and compute $z=F_{n}(U,r)$ then $z\in\\{0,1\\}^{n}$
samples from a distribution that we denote

$P_{U}(z)\qquad z\in\\{0,1\\}^{n}.$

Let us also write $Q_{U}(z)=|\langle z|U|0^{n}\rangle|^{2}$ for the true
output distribution.

######  Lemma 4.

Suppose $\mathcal{A}$ is a $k$-local, depth-$d$ circuit architecture with the
long-range tripartite MIE property (4). Suppose $n\in\Gamma$ satisfies
$n\geq(10d)^{4}$ and let $F_{n}$ be a function with input/outputs as described
above. Suppose further that each output bit of
$z=F_{n}(U_{1},U_{2},\ldots,U_{R},r)$ depends on at most $n^{1/4}$ of the
$k$-qubit Clifford gates $U_{1},U_{2},\ldots,U_{R}$. Then for any
$r\in\\{0,1\\}^{\ell(n)}$, we have

$\mathrm{Pr}_{U_{1},U_{2},\ldots,U_{R}\sim\mathcal{D}_{k}}\left[\langle
F_{n}(U,r)|U|0^{n}\rangle=0\right]\geq\frac{c}{27}-O(n^{-1/4}),$

where $c>0$ is the absolute constant from 4 and $\mathcal{D}_{k}$ is the
uniform distribution on $k$-qubit Clifford unitaries.

###### Proof.

In the following we fix $r\in\\{0,1\\}^{\ell(n)}$ and write
$z=F_{n}(U)=F_{n}(U,r)$.

Let $U_{1},U_{2},\ldots,U_{R}$ be the $k$-qubit gates that describe $U$. Here
$R\leq nd/k$. These are arranged in $d$ layers. For each $t\in[n]$ there is
exactly one $k$-qubit gate that is the last one to act on qubit $t$. Call this
gate $V_{t}$. Note that we may have $V_{t}=V_{\ell}$ for $t\neq\ell$.

For each gate $w\in[R]$, let $\mathcal{L}^{\rightarrow}(U_{w})\subseteq[n]$
consist of $\mathrm{supp}(U_{w})$ as well as all output bits of $F_{n}$ that
depend on gate $U_{w}$. Here $\mathrm{supp}(U_{w})$ denotes the support of
$U_{w}$ (the $k$ qubits on which it acts nontrivially). Let us consider a
bipartite graph $G$ with a vertex for each gate $U_{w}$ with $1\leq w\leq R$,
and a vertex for each output bit $v\in[n]$, and an edge $\\{U_{w},v\\}$
whenever $v\in\mathcal{L}^{\rightarrow}(U_{w})$. Since each output bit depends
on at most $n^{1/4}$ input gates, and each output bit can be in the support of
at most $d$ gates in the circuit, the maximum degree of any output bit is at
most $d+n^{1/4}\leq 1.1n^{1/4}$ (since $n\geq(10d)^{4}$), and therefore the
total number of edges in $G$ is

$\sum_{w=1}^{R}|\mathcal{L}^{\rightarrow}(U_{w})|\leq 1.1n^{5/4}.$ (19)

Let

$\mathrm{Bad}=\\{t\in[n]:|\mathcal{L}^{\rightarrow}(V_{t})|\geq
n^{1/2}\\}\quad\text{and}\quad\mathrm{Good}=[n]\setminus\mathrm{Bad}.$

Then from Eq. 19 we have

$|\mathrm{Bad}|\leq 1.1n^{3/4}$

and therefore

$|\mathrm{Good}|\geq n(1-1.1n^{-1/4}).$ (20)

Now let us consider a graph $G^{\prime}$ with vertex set $\mathrm{Good}$ and
an edge $\\{s,t\\}$ iff

$\mathcal{L}^{\rightarrow}(V_{s})\cap\mathcal{L}^{\rightarrow}(V_{t})\neq\emptyset.$

The maximum degree $\Delta$ of $G^{\prime}$ satisfies

$\Delta\leq\max_{t\in\mathrm{Good}}|\mathcal{L}^{\rightarrow}(V_{t})|\cdot(d+n^{1/4})\leq
n^{1/2}\cdot 1.1n^{1/4}=1.1n^{3/4}.$

Now suppose we choose a triple of qubits $\\{h,i,j\\}\subseteq[n]$ uniformly
at random. From Eq. 20 we see that the probability that
$\\{h,i,j\\}\subseteq\mathrm{Good}$ is $1-O(n^{-1/4})$. Conditioned on this
event, the probability that $\\{h,i,j\\}$ form an independent set in
$G^{\prime}$ can also be lower bounded as $1-O(n^{-1/4})$. To see this note
that since the maximum degree of $G^{\prime}$ is at most $O(n^{3/4})$, two
randomly chosen vertices in $\mathrm{Good}$ have an edge between them with
probability at most $O(n^{-1/4})$. Then apply this to the three pairs
$\\{h,i\\},\\{i,j\\}$ and $\\{h,j\\}$ and use the union bound.

Let $\mathcal{E}$ be the event that our three qubits $h,i,j$ are an
independent set in $G^{\prime}$. Then we have shown
$\mathrm{Pr}[\mathcal{E}]\geq 1-O(n^{-1/4})$. Moreover, if $\mathcal{E}$
occurs then

$\displaystyle\mathcal{L}^{\rightarrow}(V_{h})\cap\mathcal{L}^{\rightarrow}(V_{i})$
$\displaystyle=\emptyset$ (21)
$\displaystyle\mathcal{L}^{\rightarrow}(V_{i})\cap\mathcal{L}^{\rightarrow}(V_{j})$
$\displaystyle=\emptyset$ (22)
$\displaystyle\mathcal{L}^{\rightarrow}(V_{h})\cap\mathcal{L}^{\rightarrow}(V_{j})$
$\displaystyle=\emptyset.$ (23)

Now suppose that $U_{1},U_{2},\ldots,U_{R}\sim\mathcal{D}_{k}$ are uniformly
random $k$-qubit Clifford gates. Let $|\psi\rangle=U|0^{n}\rangle$ be the
output state of the circuit $U$. Let $\mathcal{E}^{\prime}$ denote the event
that qubits $h,i,j$ exhibit GHZ-type measurement-induced entanglement. That
is, event $\mathcal{E}^{\prime}$ occurs iff there is GHZ-type entanglement
between qubits $h,i,j$ after measuring all other qubits of $\psi$ in the
computational basis. By the long-range GHZ property, event
$\mathcal{E}^{\prime}$ occurs with probability at least $c>0$.

By the union bound, the probability that both events $\mathcal{E}$ and
$\mathcal{E}^{\prime}$ occur is at least

$\mathrm{Pr}[\mathcal{E}\text{ and }\mathcal{E}^{\prime}]\geq c-O(n^{-1/4}).$

Now let us suppose that events $\mathcal{E}$ and $\mathcal{E^{\prime}}$ both
occur. Starting with our circuit $U_{1},U_{2},\ldots,U_{R}$ we define a set of
$27$ quantum circuits as follows. For each of the qubits $h,i,j$ there are
three choices for a single-qubit Pauli basis $X,Y,Z$. Let us index these
choices by a tuple $b=b_{h}b_{i}b_{j}\in\\{0,1,2\\}^{3}$, where $0,1,2$
correspond to $X,Y,Z$ respectively. Recall that we write $Q(0),Q(1),Q(2)$ for
the single-qubit Clifford unitaries that change basis from the $Z$ basis to
the $X,Y,Z$ bases respectively (i.e.,
$Q(0)=(X+Z)/\sqrt{2},Q(1)=(Y+Z)/\sqrt{2},Q(2)=I$). For
$b_{h},b_{i},b_{j}\in\\{0,1,2\\}^{3}$, let

$\displaystyle V_{h}(b_{h})$ $\displaystyle=Q(b_{h})V_{h}$ $\displaystyle
V_{i}(b_{i})$ $\displaystyle=Q(b_{i})V_{i}$ $\displaystyle V_{j}(b_{j})$
$\displaystyle=Q(b_{j})V_{j}.$

and let $U(b)$ denote the circuit obtained from $U_{1},U_{2},\ldots,U_{R}$ by
making the replacements $V_{h}\leftarrow V_{h}(b_{h}),V_{i}\leftarrow
V_{i}(b_{i}),V_{j}\leftarrow V_{j}(b_{j})$.

Define a function $m:\\{0,1,2\\}^{3}\rightarrow\\{0,1\\}^{n}$ by
$m(b)=F_{n}(U(b))$. From Eqs. 21, 22 and 23 we see that each output bit
$m_{j}$ depends on at most one of the bits $b_{h},b_{i},b_{j}$, and that

  * •

$m_{h}$ is independent of $b_{i},b_{j}$

  * •

$m_{i}$ is independent of $b_{h},b_{j}$

  * •

$m_{j}$ is independent of $b_{h},b_{i}$.

Therefore, from Eq. 18 we conclude that

$\langle F_{n}(U(b))|U(b)|0^{n}\rangle=0\quad\quad\text{for some
}b\in\\{0,1,2\\}^{3}.$

Note that each of the circuits $U(b)$ with $b\in\\{0,1,2\\}^{3}$ occurs in our
random ensemble with the same probability as $U$. Therefore

$\displaystyle\mathrm{Pr}_{U_{1},U_{2},\ldots,U_{R}\sim\mathcal{D}_{k}}\left[\langle
F_{n}(U)|U|0^{n}\rangle=0\right]$
$\displaystyle\geq\frac{\mathrm{Pr}[\mathcal{E}\text{ and
}\mathcal{E}^{\prime}]}{27}$ $\displaystyle=c/27-O(n^{-1/4}).$

∎

######  Theorem 10 (Formal version of Theorem 3).

Suppose $\mathcal{A}=\\{\mathcal{T}_{n}\\}_{n\in\Gamma}$ is a $k$-local,
depth-$d$ circuit architecture with the long-range tripartite MIE property
(4). There exists a positive constant $\alpha>0$ and positive integer $n_{0}$
such that the following holds. Suppose $n\in\Gamma$ satisfies
$n\geq\max\\{n_{0},(10d)^{4}\\}$. Suppose there is a depth-$D$ probabilistic
classical circuit composed of gates of fan-in $K$ with output distribution
$P_{U}$ on input circuit $U$ satisfying

$\mathbb{E}_{U_{1},U_{2},\ldots,U_{R}\sim\mathcal{D}_{k}}\left[\|P_{U}-Q_{U}\|_{1}\right]<\alpha,$

where $\mathcal{D}_{k}$ is the uniform distribution on $k$-qubit Clifford
unitaries, and $Q_{U}(z)=|\langle z|U|0^{n}\rangle|^{2}$ is the true output
distribution. Then $D\geq\frac{1}{4}\frac{\log(n)}{\log(K)}$.

###### Proof.

Let $F_{n}$ be the function which describes the classical circuit. Recall that
$F_{n}$ takes as input the gates $U_{1},U_{2},\ldots,U_{R}$ in the circuit as
well as a random string $r\in\\{0,1\\}^{\ell(n)}$, and outputs a binary string
$z=F_{n}(U_{1},U_{2},\ldots,U_{R},r)=F_{n}(U,r)$.

Suppose $D<\frac{1}{4}\frac{\log(n)}{\log(K)}$. Then every output bit of the
classical circuit depends on at most $K^{D}<n^{1/4}$ input bits. In
particular, each output bit depends on at most $n^{1/4}$ of the input gates
$U_{1},U_{2},\ldots,U_{R}$. Then

$\displaystyle\mathbb{E}_{U_{1},U_{2},\ldots,U_{R}\sim\mathcal{D}_{k}}\bigg{(}\sum_{x\in\\{0,1\\}^{n}}|P_{U}(x)-Q_{U}(x)|\bigg{)}$
$\displaystyle\geq\mathbb{E}_{U_{1},U_{2},\ldots,U_{R}\sim\mathcal{D}_{k}}\bigg{(}\sum_{x:Q_{U}(x)=0}P_{U}(x)\bigg{)}$
$\displaystyle=\mathbb{E}_{U_{1},U_{2},\ldots,U_{R}\sim\mathcal{D}_{k}}\mathrm{Pr}_{r}\left[\langle
F_{n}(U,r)|U|0^{n}\rangle=0\right]$
$\displaystyle=\mathbb{E}_{r}\mathrm{Pr}_{U_{1},U_{2},\ldots,U_{R}\sim\mathcal{D}_{k}}\left[\langle
F_{n}(U,r)|U|0^{n}\rangle=0\right]$
$\displaystyle\geq\mathbb{E}_{r}\frac{c-O(n^{-1/4})}{27}$
$\displaystyle=\frac{c-O(n^{-1/4})}{27}$

where $c>0$ is the constant appearing in the definition of 4, and where we
used Lemma 4. We choose $n_{0}$ large enough so that $O(n^{-1/4})$ is at most
$c/2$ and then set $\alpha=c/54$. ∎

##  VI Coarse-grained architecture

Here we discuss the “coarse-grained” two-dimensional circuit architecture
where we are able to establish rigorous statements concerning measurement-
induced entanglement and quantum advantage. In particular, we prove Theorem 4.
The coarse-grained architecture shares salient features of shallow quantum
circuits in the usual brickwork architecture; most importantly, there is a
locality parameter $\tau$ that determines the linear size of the lightcone of
a given qubit.

Consider a family of random quantum circuits, shown in Fig. 4, acting on $n$
qubits arranged on a $\sqrt{n}\times\sqrt{n}$ grid lattice. Each circuit $U$
in this family consist of two layers of gates $V$ and $W$ applied
consecutively such that

$U|0^{n}\rangle=\underbrace{\left(W_{m^{2}}\otimes\cdots\otimes
W_{1}\right)}_{W}\cdot\underbrace{\left(V_{(m-1)^{2}}\otimes\cdots\otimes
V_{1}\right)}_{V}|0^{n}\rangle.$

We refer to the gates $V_{1},\dots,V_{(m-1)^{2}}$ in $V$ as the first layer
and $W_{1},\dots,W_{m^{2}}$ in $W$ as the second layer gates.

We shall consider two families of quantum circuits in this architecture. The
first is obtained by choosing each gate to be a Haar-random unitary acting on
a square of $\tau\times\tau$ qubits such that $m^{2}\tau^{2}=n$. We will call
a circuit $U$ drawn from this family a _random coarse-grained universal
circuit_. The second family we consider is obtained by choosing each gate to
be a uniformly random $\tau^{2}$-qubit Clifford unitary. We refer a circuit
$D$ drawn from this family as a _random coarse-grained Clifford circuit._

Figure 4: Coarse-grained circuit with two layers of gates for $m=4$ and
$\tau=4$. The shaded region denotes the support of the first layer gates
$V_{1},\dots,V_{9}$. The gates with green boundaries represent the second-
layer gates $W_{1},\dots,W_{16}$.

###  VI.1 Subsystem anticoncentration and long-range MIE

Below we show that random coarse-grained Clifford circuits exhibit subsystem
anticoncentration in the sense described in the Introduction. In particular,
we consider a tripartition $[n]=ABC$ of the qubits such that $|A|=1$, and the
corresponding set $S$ defined in Eqs. 5 and 6. We then give an upper bound on
$\mathbb{E}_{D}[S]$ that approaches zero as $|C|,n\rightarrow\infty$. From our
upper bound it follows directly that the family of random coarse-grained
Clifford circuits satisfies the long-range MIE property. We use Eq. 7 to infer
that the family of random coarse-grained universal circuits also satisfies the
long-range MIE property (2).

To upper bound the expected size of $S$, we first bound the probability that a
random Pauli operator becomes $Z$-type when it is evolved backwards in time
through a random coarse-grained Clifford circuit.

Given a Pauli operator $P$ defined on the qubits $[n]$, let
$\operatorname{supp}(P)\subseteq[n]$ be set of qubits on which $P$ takes a
value other than the identity. For any Pauli operator $P$ and random coarse-
grained Clifford circuit $D$, it is relatively easy to see that the
probability of $D^{\dagger}PD$ being $Z$-type is determined entirely by the
overlap of $\operatorname{supp}(P)$ with the second layer of gates
$W_{1},\ldots,W_{m^{2}}$. To keep track of this overlap, for any Pauli $P$ we
let the _cluster_ $\mathcal{G}(P)$ denote the set of all second layer gates
with non-trivial overlap with $\operatorname{supp}(P)$. Such a cluster can be
specified by filling in squares of an $m\times m$ grid. This grid
representation leads naturally to the notion of the _size_ and _perimeter_ of
a cluster $\mathcal{G}(P)$, which we define next.

######  Definition 11.

Given any cluster $\mathcal{G}(P)$, identify it with a subset of the $m\times
m$ grid in the natural way. Then let the _size_ of the cluster, denoted
$\lvert\mathcal{G}(P)\rvert$ be the number of grid squares contained in the
cluster. Also let the _perimeter_ of the cluster, denoted
$\mathrm{Per}(\mathcal{G}(P))$ be the number of grid edges on the boundary of
the cluster, excluding edges running along the outside of the grid (see Fig.
5).

Figure 5: A cluster $\mathcal{G}(P)$ indicated in gray, with size
$\lvert\mathcal{G}(P)\rvert=11$ and perimeter
$\mathrm{Per}(\mathcal{G}(P))=19$. Note edges of the cluster running along the
exterior of the grid do not contribute to the perimeter.

The following theorem bounds the probability that a Pauli is $Z$-type after
conjugation by a random coarse-grained Clifford circuit.

######  Lemma 5.

Let $P$ be a Pauli operator, and let $D$ be a random coarse-grained Clifford
circuit. Also let $a=\lvert\mathcal{G}(P)\rvert$ and
$l=\mathrm{Per}(\mathcal{G}(P))$ denote the size and perimeter of
$\mathcal{G}(P)$, respectively. Then

$\displaystyle\Pr[D^{\dagger}PD\text{ is
$Z$-type}]\leq\left(\frac{1}{2}\right)^{a\tau^{2}+\frac{1}{4}l(\tau^{2}/12-1)}.$
(24)

Now let us consider the measurement-induced entanglement scenario in the case
where $A$ and $C$ are single qubits. We will use first-moment methods to
establish the existence of measurement-induced entanglement in the coarse-
grained architecture for $\tau=\Omega(\sqrt{\log(m)})$.

We first bound the expected number of binary strings $s\in S$ such that the
perimeter of the cluster $\mathcal{G}(DZ(s)D^{\dagger})$ has a given length
$l$.

######  Lemma 6.

Let $D$ be a random coarse-grained Clifford circuit and let $l$ be a positive
integer. Let $A\subseteq[n]$ contain a single qubit and $C\subseteq[n]$
contain at least one qubit, with $A$ and $C$ disjoint. Then

$\displaystyle\mathbb{E}_{D}\left[\lvert\\{s\in
S:\mathrm{Per}(\mathcal{G}(DZ(s)D^{\dagger}))=l\\}\rvert\right]$
$\displaystyle\hskip 100.0pt\leq 2^{l(2\log(m)-\tau^{2}/48+5)}.$

###### Proof.

Expanding out the definition of $S$ gives

$\displaystyle\lvert\\{s\in
S:\mathrm{Per}(\mathcal{G}(DZ(s)D^{\dagger}))=l\\}\rvert$ $\displaystyle\hskip
10.0pt=|\\{s\in\\{0,1\\}^{n}:DZ(s)D^{\dagger}=(-1)^{\alpha}P_{A}\otimes
Z(r)_{B}\otimes I_{C}$ $\displaystyle\hskip 24.0pt\text{ for some
}r\in\\{0,1\\}^{|B|},\alpha\in\\{0,1\\},P\in\\{X,Y,Z\\}$ $\displaystyle\hskip
24.0pt\textbf{ and }\mathrm{Per}(\mathcal{G}(DZ(s)D^{\dagger}))=l\\}|.$

But for any fixed $r$ and $P$ we have

$\displaystyle\exists
s\in\\{0,1\\}^{n}:DZ(s)D^{\dagger}=(-1)^{\alpha}P_{A}\otimes Z(r)_{B}\otimes
I_{C}$ $\displaystyle\hskip 40.0pt\Leftrightarrow
D^{\dagger}\left(P_{A}\otimes Z(r)_{B}\otimes I_{C}\right)D\text{ is
$Z$-type.}$

Then we also have

$\displaystyle\lvert\\{s\in
S:\mathrm{Per}(\mathcal{G}(DZ(s)D^{\dagger}))=l\\}\rvert$
$\displaystyle=|\\{(r,P):\mathrm{Per}(\mathcal{G}(P_{A}\otimes Z(r)_{B}\otimes
I_{C}))=l,\textbf{ and }$ $\displaystyle\hskip
30.0ptD^{\dagger}\left(P_{A}\otimes Z(r)_{B}\otimes I_{C}\right)D\text{ is
$Z$-type}\\}|.$ (25)

We can then bound the expected size of this set as follows. For a given
cluster $\mathcal{G^{\prime}}$, let $\Gamma(\mathcal{G^{\prime}})$ denote the
set of all pairs $r\in\\{0,1\\}^{|B|}$ and $P\in\\{X,Y,Z\\}$ such that
$\mathcal{G}(P_{A}\otimes Z(r)_{B}\otimes I_{C})=\mathcal{G}^{\prime}$. Then

$\displaystyle\mathbb{E}_{D}\left[\lvert\\{s\in
S:\mathrm{Per}(\mathcal{G}(DZ(s)D^{\dagger}))=l\\}\rvert\right]$
$\displaystyle=\sum_{\begin{subarray}{c}\mathcal{G}^{\prime}:\\\
\mathrm{Per}(\mathcal{G}^{\prime})=l\end{subarray}}\;\sum_{\begin{subarray}{c}(r,P)\\\
\in\Gamma(\mathcal{G^{\prime}})\end{subarray}}\Pr[D^{\dagger}\left(P_{A}\otimes
Z(r)_{B}\otimes I_{C}\right)D\text{ is $Z$-type.}]$
$\displaystyle\leq\sum_{\begin{subarray}{c}\mathcal{G}^{\prime}:\\\
\mathrm{Per}(\mathcal{G}^{\prime})=l\end{subarray}}\;\sum_{(r,P)\in\Gamma(\mathcal{G^{\prime}})}2^{-\lvert\mathcal{G}^{\prime}\rvert\tau^{2}-\frac{1}{4}l(\tau^{2}/12-1)}$
$\displaystyle\leq 3\sum_{\begin{subarray}{c}\mathcal{G}^{\prime}:\\\
\mathrm{Per}(\mathcal{G}^{\prime})=l\end{subarray}}2^{-\frac{1}{4}l(\tau^{2}/12-1)}$
$\displaystyle\leq 6\binom{2m(m-1)}{l}2^{-\frac{1}{4}l(\tau^{2}/12-1)}$
$\displaystyle\leq 2^{l(2\log(m)-\tau^{2}/48+5)}.$ (26)

where we used Lemma 5 to go from the first line to the second and that there
are at most $2^{\lvert\mathcal{G}^{\prime}\rvert\tau^{2}}$ strings
$r\in\\{0,1\\}^{n}$ such that $\mathcal{G}(P_{A}\otimes Z(r)_{B}\otimes
I_{C})=\mathcal{G}^{\prime}$ to go from the second line to the third. To go
from the third line to the fourth we count the number of clusters
$\mathcal{G}^{\prime}$ with perimeter $l$. Any such cluster can be specified
by first choosing the location of the $l$ edges of the cluster, and then
specifying the interior and exterior of the cluster. A crude upper bound gives
that there are at most $\binom{2m(m-1)}{l}$ ways to chose the $l$ edges of the
cluster, and then two possible options for how to specify the interior and
exterior of the cluster once the edges are fixed. This argument gives
$\lvert\\{\mathcal{G}^{\prime}:\mathrm{Per}(\mathcal{G}^{\prime})=l\\}\rvert\leq
2\binom{2m(m-1)}{l}$, which is the bound used above. ∎

Finally, we upper bound the expected size of $S$.

######  Lemma 7.

In the setting of Lemma 6 and choosing $\tau\geq\sqrt{1000\log_{2}(m)}$, we
have

$\displaystyle\mathbb{E}_{D}[\lvert S\rvert]\leq\frac{3}{2^{\lvert
C\rvert+1}}+2\cdot 2^{-\tau^{2}/100}.$ (27)

###### Proof.

We first observe

$\displaystyle\mathbb{E}_{D}[\lvert
S\rvert]\leq\sum_{l=0}^{\infty}\mathbb{E}_{D}\left[\lvert\\{s\in
S:\mathrm{Per}(\mathcal{G}(DZ(s)D^{\dagger}))=l\\}\rvert\right].$

Then Lemma 6 and our assumption on the size of $d$ gives

$\displaystyle\sum_{l=1}^{\infty}\mathbb{E}_{D}[\lvert\\{s\in S:$
$\displaystyle\mathrm{Per}(\mathcal{G}(DZ(s)D^{\dagger}))=l\\}\rvert]$
$\displaystyle\leq\sum_{l=1}^{\infty}2^{l(2\log_{2}(m)-\tau^{2}/48+5)}$
$\displaystyle=\sum_{l=1}^{\infty}2^{l(2\log_{2}(m)-\tau^{2}/96+5)-l\tau^{2}/96}$
$\displaystyle\leq\sum_{l=1}^{\infty}2^{l(-\tau^{2}/96)}$ $\displaystyle\leq
2\cdot 2^{-\tau^{2}/100}$

where in the second-to-last line we used the fact that
$2\log_{2}(m)-\tau^{2}/96+5)\leq 2\log_{2}(m)-10\log_{2}(m)+5\leq 0$. It
remains to show a bound when $l=0$. In this case, by the same logic what was
used in the proof of Lemma 6, we have

$\displaystyle\mathbb{E}_{D}\left[\lvert\\{s\in
S:\mathrm{Per}(\mathcal{G}(DZ(s)D^{\dagger}))=0\\}\rvert\right]$
$\displaystyle\hskip 20.0pt=\mathbb{E}_{D}\big{[}|\\{r\in\\{0,1\\}^{\lvert
B\rvert},P\in\\{X,Y,Z\\}:$ $\displaystyle\hskip
40.0pt\mathrm{Per}(\mathcal{G}(P_{A}\otimes Z(r)_{B}\otimes I_{C}))=0\textbf{
and }$ $\displaystyle\hskip 40.0ptD^{\dagger}\left(P_{A}\otimes
Z(r)_{B}\otimes I_{C}\right)D\text{ is $Z$-type}\\}|\big{]}.$ (28)

But we have $\mathrm{Per}(\mathcal{G}(P_{A}\otimes Z(r)_{B}\otimes I_{C}))=0$
only if the cluster $\mathcal{G}(P_{A}\otimes Z(r)_{B}\otimes I_{C})$ is the
entire $m\times m$ grid. This cluster has size $m^{2}$ and there are at most

$\displaystyle 3(2^{\lvert B\rvert})=3(2^{n-\lvert A\rvert-\lvert
C\rvert})=3(2^{n-1-\lvert C\rvert})$

Pauli strings satisfying this condition. Then a straightforward application of
Lemma 5 gives

$\displaystyle\mathbb{E}_{D}\left[\lvert\\{s\in
S:\mathrm{Per}(\mathcal{G}(DZ(s)D^{\dagger}))=0\\}\rvert\right]$
$\displaystyle\hskip 40.0pt\leq 3(2^{n-1-\lvert
C\rvert})(2^{-m^{2}\tau^{2}})=3(2^{-\lvert C\rvert-1})$ (29)

and the result follows. ∎

######  Theorem 12 (Formal version of Theorem 4, part 1).

The family of random coarse-grained universal circuits with
$\tau\geq\sqrt{1000\log_{2}(m)}$ and $n$ sufficiently large satisfies the
long-range MIE property. The same statement holds for random coarse-grained
Clifford circuits.

###### Proof.

Let $[n]=ABC$ be a tripartition of the qubits such that $|A|=1$ and $B$ is a
square shielding region with side length $L$, centred at $A$ (see Fig. 2).
Here $L$ is chosen so that $|C|\neq 0$. Note that due to the 2D geometry, this
implies $|C|=\Omega(\sqrt{n})$.

Let $U$ be a random coarse-grained universal circuit with
$\tau\geq\sqrt{1000\log_{2}(m)}$. Plugging the upper bound from Lemma 7 into
Eq. 7 we get

$\mathbb{E}_{U}\mathbb{E}_{x}\mathrm{Tr}(\rho(x)^{2})\leq\frac{1}{2}+O(1/\mathrm{poly}(m))=\frac{1}{2}+O(1/\mathrm{poly}(n)).$

Taking $n$ sufficiently large we can ensure the RHS is less than any constant
$c\in(1/2,1)$.

If we replace $U$ with a random coarse-grained Clifford circuit, then we can
use Lemma 7 along with Lemma 1 and Markov’s inequality to arrive at the same
conclusion. ∎

###  VI.2 Long-range tripartite MIE

We have shown that random coarse-grained universal or Clifford circuits have
the long-range MIE property (2), as a consequence of the subsystem
anticoncentration expressed in Lemma 7. Below we specialize to random coarse-
grained Clifford circuits, and we show that Lemma 7 also implies long-range
tripartite MIE. As discussed in the Introduction, this gives rise to an
unconditional quantum advantage.

We first review some facts about entanglement in stabilizer states. For any
graph $G=(V,E)$, the $\lvert V\rvert$-vertex graph state $|\Phi_{G}\rangle$ is
defined to be the stabilizer state with stabilizer group generated by

$\displaystyle g_{v}=X_{v}\left(\prod_{u:(u,v)\in E}Z_{u}\right).$ (30)

It is known that any (finite dimensional) stabilizer state is locally Clifford
equivalent to a graph state van2004graphical .

The following lemma shows that GHZ-type entanglement can always be produced by
making computational basis measurements on a connected graph state with
sufficiently many vertices.

######  Lemma 8.

Let $G=(V,E)$ be a connected graph with at least 3 vertices and let
$|\Phi_{G}\rangle$ be the associated graph state. Then there exist indices
$h,i,j\in V$ such that, for any $x\in\\{0,1\\}^{\lvert V\rvert-3}$, the state

$\displaystyle|\Phi_{h,i,j}\rangle=\langle
x|_{V\backslash\\{h,i,j\\}}|\Phi_{G}\rangle$ (31)

is locally Clifford equivalent to a GHZ state (up to normalization).

###### Proof.

The post-measurement state after measuring a qubit $v$ of a graph state
$\Phi_{G}$ in the computational basis and obtaining outcome $y\in\\{0,1\\}$ is

$\bigg{(}\prod_{w:\\{v,w\\}\in
E(G)}Z^{y}_{w}\bigg{)}|\Phi_{G(V\setminus\\{v\\})}\rangle$

where $G(V\setminus\\{v\\})$ is the induced subgraph of $G$ on all
$V\setminus\\{v\\}$, obtained from $G$ by removing vertex $v$ and all edges
incident to it. Starting from a connected graph $G$ with at least three
vertices, we choose $3$ vertices $\Omega=\\{h,i,j\\}$ such that the subgraph
$G(\Omega)$ of $G$ induced by $\Omega$ is a connected three-vertex graph.
Using the above fact about computational basis measurement, we see that after
measuring all vertices in $V\setminus\\{h,i,j\\}$ the postmeasurement state is
locally Clifford equivalent to the graph state $|\Phi_{G(\Omega)}\rangle$
where $G(\Omega)$ is a connected three-vertex graph. Finally, we use the well-
known fact that any 3 vertex connected graph state is locally Clifford
equivalent to a GHZ state (this can be confirmed by a direct calculation). ∎

Now consider a random coarse-grained Clifford circuit with
$\tau\geq\sqrt{1000\log_{2}(m)}$ as in Lemma 7. In this setting, a
straightforward consequence of Lemmas 1 and 7 is that measuring all but two
output qubits of the randomly chosen circuit in the computational basis
produces a two-qubit entangled stabilizer state on the unmeasured qubits with
probability at least $1/4-\exp(-\Omega(\tau^{2}))$. The next theorem shows
that tripartite GHZ-type entanglement is also ubiquitous.

######  Theorem 13 (Formal version of Theorem 4, part 2).

Random coarse-grained Clifford circuits with $\tau\geq\sqrt{1000\log_{2}(m)}$
satisfy the long-range tripartite MIE property (4). In particular, let $D$ be
an $n$-qubit random coarse-grained Clifford circuit, with
$\tau\geq\sqrt{1000\log_{2}(m)}$. Let $\\{h,i,j\\}$ be a uniformly random
triple of qubits. Then $\\{h,i,j\\}$ exhibit GHZ-type MIE with probability at
least $0.005$ over the random choice of $D$ and the random choice of
$\\{h,i,j\\}$.

###### Proof.

Let $D$ be an $n$-qubit random coarse-grained Clifford circuit with
$\tau\geq\sqrt{1000\log_{2}(m)}$.

Let us say that $\\{h,i,j\\}\subseteq[n]$ is a good triple, iff qubits
$\\{h,i,j\\}$ share GHZ-type entanglement after all other qubits have been
measured with probability at least $0.05$ over the random choice of $D$.

Below we prove the following: for any set of qubits $V\subseteq[n]$ with
$\lvert V\rvert=5$, there exists a good triple $\\{h,i,j\\}\subseteq V$.

The theorem then follows from this statement. To see this, consider the
following procedure. First, choose a uniformly random subset of qubits
$V\subseteq[n]$ of size $|V|=5$, and then choose a uniformly random triple
$\\{h,i,j\\}\subseteq V$. By the above, the probability that we are lucky and
choose a good triple is at least $1/\binom{5}{3}=1/10$.

Moreover, clearly this procedure samples a triple $\\{h,i,j\\}$ from the
uniform distribution over all $\binom{n}{3}$ triples.

It remains to show that for any set of qubits $V\subseteq[n]$ with $\lvert
V\rvert=5$, there exists a good triple $\\{h,i,j\\}\subseteq V$.

We first consider the state of the qubits in $V$ after the circuit $D$ is
applied and all other qubits are measured in the computational basis. For any
qubit $v\in V$, Lemmas 1 and 7 give that there is no post-measurement
entanglement between qubit $v$ and qubits in the set $V\backslash\\{v\\}$ with
probability at most

$3/2^{5}+2\cdot 2^{-\tau^{2}/100}\leq 3/2^{5}+2\cdot 2^{-10}<0.1.$

Then the union bound gives that there exists a qubit $v^{\prime}\in V$ with no
post-measurement entanglement between $v^{\prime}$ and the qubits
$V\backslash\\{v^{\prime}\\}$ with probability at most

$\displaystyle\lvert V\rvert\cdot 0.1<0.5.$

Equivalently, there is post measurement entanglement between each qubit
$v^{\prime}\in V$ and qubits $V\backslash\\{v^{\prime}\\}$ with probability at
least $1/2$. But then the post measurement state of the qubits $V$ is locally
Clifford equivalent to a graph state $|\Phi_{G}\rangle$ corresponding to a 5
vertex graph with no isolated vertices (this is because there is no
entanglement between qubits corresponding to disconnected vertices of a graph
state). It follows that the graph $G$ must have either a 3 or 5 vertex
connected component. If $G$ has a 3 vertex connected component the qubits
corresponding to this component are in a state locally Clifford equivalent to
a GHZ state, and we are done. Otherwise, the graph state has a 5 vertex
connected component. But then by Lemma 8 there are vertices $h,i,j\in V$ such
that, for any $x\in\\{0,1\\}^{2}$ we have that

$\displaystyle|\Phi_{hij}\rangle=\langle
x|_{V\backslash\\{h,i,j\\}}|\Phi_{G}\rangle$ (32)

is locally Clifford equivalent to a GHZ state. Now let $|\Psi_{V}\rangle$
denote the post measurement state of the qubits in the set $V$. Since this
state is locally Clifford equivalent to $|\Phi_{G}\rangle$ we have

$\displaystyle|\Psi_{V}\rangle=\bigotimes_{v\in V}C_{v}|\Phi_{G}\rangle$

where each $C_{v}$ is a $1$-qubit Clifford unitary. Furthermore, since the
distribution of coarse-grained Clifford circuits is unchanged under local
Clifford operations, we can assume the Clifford unitaries $C_{v}$ are chosen
uniformly at random. Then the post measurement state of qubits $h,i,j$ when
the remaining two qubits of $V$ are measured in the computational basis and
outcome $x\in\\{0,1\\}^{2}$ is observed is given by

$\displaystyle|\Psi_{h,i,j}\rangle$ $\displaystyle=\langle
x|_{V\backslash\\{h,i,j\\}}\bigotimes_{v\in V}C_{v}|\Phi_{G}\rangle.$ (33)

Comparing with Eq. 32 we see this is locally Clifford equivalent to a GHZ
state provided the state

$\displaystyle\bigotimes_{v\in
V\backslash\\{h,i,j\\}}C_{v}^{\dagger}|x\rangle_{V\backslash\\{h,i,j\\}}$

is a computational basis state. But since we can take the $C_{v}$ to be random
Cliffords this occurs with probability exactly $1/9$. Putting this all
together we see that $\\{h,i,j\\}$ is a good triple: the state
$|\Psi_{h,i,j}\rangle$ is locally Clifford to a GHZ state with probability at
least $\frac{1}{9}\cdot\frac{1}{2}\geq 0.05$ over the random choice of $D$. ∎

###  VI.3 Approximate implementation of coarse-grained circuits with two-qubit
gates

Lastly, we demonstrate that coarse-grained circuits can be approximately
implemented using two-qubit gates, instead of gates that act on blocks of
$\tau\times\tau$ qubits. We shall see that this yields a family of
$O(\log(n))$-depth quantum circuits composed of Haar-random two-qubit gates
that satisfy the long-range MIE property.

Our construction replaces each $\tau\times\tau$ Haar random gate in a random
coarse-grained universal circuit by an $\varepsilon$-approximate unitary
2-design for a sufficiently small approximation error
$\varepsilon=2^{-\Omega(\tau^{2})}$. Such unitary $2$-designs can, for
instance, be implemented using a 1D brickwork quantum circuit of depth
$O(\tau^{2})$ composed of Haar random two-qubit gates which is arranged in a
snake-like pattern (or more formally, along a Hamiltonian path) on the square
of $\tau\times\tau$ qubits brandao2016local ; hunter2019unitary . This results
in a distribution of $n$-qubit random quantum circuits with an overall depth
of $O(\tau^{2})$. We denote these compiled random coarse-grained circuits by
$\tilde{\mathcal{U}}$. We can analogously define $\tilde{\mathcal{D}}$ to be
the family of random Clifford circuits obtained by replacing the Haar random
two-qubit gates in $\tilde{\mathcal{U}}$ by random two-qubit Clifford gates.

######  Theorem 14 (Long-range MIE in compiled coarse-grained circuits with
$2$-qubit gates).

The family of complied random coarse-grained circuits $\tilde{\mathcal{U}}$
satisfies the long-range MIE property when $\tau\geq\sqrt{1000\log_{2}(m)}$
and $n$ sufficiently large. The same statement holds for compiled random
coarse-grained Clifford circuits $\tilde{\mathcal{D}}$.

###### Proof.

We begin by applying Equation 7, which allows us to reduce the analysis of the
long-range MIE property in $\tilde{\mathcal{U}}$ to that in
$\tilde{\mathcal{D}}$. To establish the long-range MIE property in
$\tilde{\mathcal{D}}$, we focus on bounding the expected size of the
set$~{}S$. In the Appendix, we demonstrate that the family of random Clifford
circuits $\tilde{\mathcal{D}}$ satisfies the bound in Eq. 27 of Lemma 7. We
can then employ the same reasoning as in the proof of Theorem 12 to establish
the long-range MIE property for circuits drawn from $\tilde{\mathcal{U}}$, as
stated in 2. ∎

_Note added:_ As we finalized this paper, we became aware of concurrent works
schuster2024random ; laracuente2024approximate  that also study the 2D coarse-
grained architecture introduced here. While we focus on establishing quantum
advantage, long-range MIE, and anti-concentration properties, these works
demonstrate that with a suitable choice of $\log(n)$-sized coarse-grained
gates, a similar architecture can also exhibit the unitary $k$-design
property.

##  VII Acknowledgments

DG acknowledges the support of the Natural Sciences and Engineering Research
Council of Canada through grant number RGPIN-2019-04198. DG is a fellow of the
Canadian Institute for Advanced Research, in the quantum information science
program. Research at Perimeter Institute is supported in part by the
Government of Canada through the Department of Innovation, Science and
Economic Development Canada and by the Province of Ontario through the
Ministry of Colleges and Universities. MS is supported by AWS Quantum
Postdoctoral Scholarship and funding from the National Science Foundation NSF
CAREER award CCF-2048204. Institute for Quantum Information and Matter is an
NSF Physics Frontiers Center.

## References

  * [1] Barbara M. Terhal and David P. DiVincenzo.  Adaptive quantum computation, constant depth quantum circuits and arthur-merlin games.  Quantum Info. Comput., 4(2):134–145, mar 2004.
  * [2] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al.  Quantum supremacy using a programmable superconducting processor.  Nature, 574(7779):505–510, 2019.
  * [3] Aram W Harrow and Ashley Montanaro.  Quantum computational supremacy.  Nature, 549(7671):203–209, 2017.
  * [4] Scott Aaronson and Lijie Chen.  Complexity-theoretic foundations of quantum supremacy experiments.  In Proceedings of the 32nd Computational Complexity Conference, CCC ’17, Dagstuhl, DEU, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [5] Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J Bremner, John M Martinis, and Hartmut Neven.  Characterizing quantum supremacy in near-term devices.  Nature Physics, 14(6):595–600, 2018.
  * [6] Yunchao Liu, Matthew Otten, Roozbeh Bassirianjahromi, Liang Jiang, and Bill Fefferman.  Benchmarking near-term quantum computers via random circuit sampling.  arXiv preprint arXiv:2105.05232, 2021.
  * [7] Matthew PA Fisher, Vedika Khemani, Adam Nahum, and Sagar Vijay.  Random quantum circuits.  Annual Review of Condensed Matter Physics, 14:335–379, 2023.
  * [8] John C. Napp, Rolando L. La Placa, Alexander M. Dalzell, Fernando G. S. L. Brandão, and Aram W. Harrow.  Efficient classical simulation of random shallow 2d quantum circuits.  Phys. Rev. X, 12:021021, Apr 2022.
  * [9] Yimu Bao, Maxwell Block, and Ehud Altman.  Finite-time teleportation phase transition in random quantum circuits.  Phys. Rev. Lett., 132:030401, Jan 2024.
  * [10] Hanchen Liu, Tianci Zhou, and Xiao Chen.  Measurement-induced entanglement transition in a two-dimensional shallow circuit.  Phys. Rev. B, 106:144311, Oct 2022.
  * [11] Brian Skinner, Jonathan Ruhman, and Adam Nahum.  Measurement-induced phase transitions in the dynamics of entanglement.  Phys. Rev. X, 9:031009, Jul 2019.
  * [12] Amos Chan, Rahul M. Nandkishore, Michael Pretko, and Graeme Smith.  Unitary-projective entanglement dynamics.  Phys. Rev. B, 99:224307, Jun 2019.
  * [13] Yaodong Li, Xiao Chen, and Matthew P. A. Fisher.  Quantum zeno effect and the many-body entanglement transition.  Phys. Rev. B, 98:205136, Nov 2018.
  * [14] Google Quantum AI and Collaborators.  Measurement-induced entanglement and teleportation on a noisy quantum processor.  Nature, 622(7983):481–486, 2023.
  * [15] Sergey Bravyi, David Gosset, and Robert König.  Quantum advantage with shallow circuits.  Science, 362(6412):308–311, 2018.
  * [16] Sergey Bravyi, David Gosset, Robert König, and Marco Tomamichel.  Quantum advantage with noisy shallow circuits.  Nature Physics, 16(10):1040–1045, 2020.
  * [17] Adam Bene Watts, Robin Kothari, Luke Schaeffer, and Avishay Tal.  Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, page 515–526, New York, NY, USA, 2019. Association for Computing Machinery.
  * [18] Matthew Coudron, Jalex Stark, and Thomas Vidick.  Trading locality for time: certifiable randomness from low-depth circuits.  Comm. Math. Phys., 382(1):49–86, 2021.
  * [19] François Le Gall.  Average-case quantum advantage with shallow circuits.  In 34th Computational Complexity Conference, volume 137 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 21, 20. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2019.
  * [20] Daniel Grier and Luke Schaeffer.  Interactive shallow clifford circuits: Quantum advantage against nc¹ and beyond.  In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, page 875–888, New York, NY, USA, 2020. Association for Computing Machinery.
  * [21] Libor Caha, Xavier Coiteux-Roy, and Robert Koenig.  Single-qubit gate teleportation provides a quantum advantage.  arXiv preprint arXiv:2209.14158, 2022.
  * [22] Libor Caha, Xavier Coiteux-Roy, and Robert Koenig.  A colossal advantage: 3d-local noisy shallow quantum circuits defeat unbounded fan-in classical circuits.  arXiv preprint arXiv:2312.09209, 2023.
  * [23] Craig Gidney.  Stim: a fast stabilizer circuit simulator.  Quantum, 5:497, July 2021.
  * [24] Alexander M. Dalzell, Nicholas Hunter-Jones, and Fernando G. S. L. Brandão.  Random quantum circuits anticoncentrate in log depth.  PRX Quantum, 3:010333, Mar 2022.
  * [25] Yinchen Liu.  Moments of random quantum circuits and applications in random circuit sampling.  Master’s thesis, University of Waterloo, 2021.
  * [26] Boaz Barak, Chi-Ning Chou, and Xun Gao.  Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits.  In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), volume 185 of Leibniz International Proceedings in Informatics (LIPIcs), pages 30:1–30:20, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
  * [27] Sergey Bravyi, David Gosset, and Yinchen Liu.  How to simulate quantum measurement without computing marginals.  Phys. Rev. Lett., 128:220503, Jun 2022.
  * [28] In particular, if $U$ is a coarse-grained circuit and $O_{j}$ is an operator acting on qubit $j$, then the support of $UO_{j}U^{\dagger}$ is contained within a square region of size $O(\tau^{2})$ centered at $j$.
  * [29] Maarten Van den Nest, Jeroen Dehaene, and Bart De Moor.  Graphical description of the action of local clifford transformations on graph states.  Physical Review A, 69(2):022316, 2004.
  * [30] Fernando GSL Brandao, Aram W Harrow, and Michał Horodecki.  Local random quantum circuits are approximate polynomial-designs.  Communications in Mathematical Physics, 346:397–434, 2016.
  * [31] Nicholas Hunter-Jones.  Unitary designs from statistical mechanics in random quantum circuits.  arXiv preprint arXiv:1905.12053, 2019.
  * [32] Thomas Schuster, Jonas Haferkamp, and Hsin-Yuan Huang.  Random unitaries in extremely low depth.  arXiv preprint arXiv:2407.07754, 2024.
  * [33] Nicholas LaRacuente and Felix Leditzky.  Approximate unitary $k$-designs from shallow, low-communication circuits.  arXiv preprint arXiv:2407.07876, 2024.
  * [34] Shivan Mittal and Nicholas Hunter-Jones.  Local random quantum circuits form approximate designs on arbitrary architectures.  arXiv preprint arXiv:2310.19355, 2023.

##  Appendix A Analysis of Algorithm 1

Here we prove Eq. 14. The proof is obtained by combining the fidelity bound
from Lemma 2 with the robustness property of the gate-by-gate algorithm
established in Ref. [27]. Our setting differs slightly from the one considered
there (this is due to the fact that $\tilde{\rho}_{t}(\omega_{B})$ is not a
pure state in general); below we adapt the proof to our setting.

The gate-by-gate algorithm of Ref. [27] is obtained from Algorithm 1 by making
a small but consequential replacement: replacing $\tilde{q}_{t}(y|x_{B(t)})$
with $q_{t}(y|x_{B(t)}x_{C(t)})$ in line 9. We shall analyze Algorithm 1 by
comparing it to the gate-by-gate algorithm and using the performance guarantee
of the latter algorithm. Specifically, in Ref. [27] it is shown that the
binary string $x$ at the end of the $t$th iteration of the for loop of the
gate-by-gate algorithm is distributed according to

$P_{t}(x)\equiv|\langle x|U_{t}U_{t-1}\ldots U_{1}|0^{n}\rangle|^{2}\qquad
x\in\\{0,1\\}^{n}.$

Write $W_{t}(x)$ for the probability of sampling $x\in\\{0,1\\}^{n}$ at the
end of the $t$th iteration of the for loop of Algorithm 1.

First suppose that $t\in\Gamma$, so that $U_{t}$ is a single-qubit gate. Let
$A=A(t),B=B(t)$, and $C=C(t)$. Then

$\displaystyle W_{t}(x)$
$\displaystyle=\sum_{y:y_{BC}=x_{BC}}W_{t-1}(y)\tilde{q}_{t}(x_{A}|x_{B})$
$\displaystyle=\sum_{y:y_{BC}=x_{BC}}\left(W_{t-1}(y)-P_{t-1}(y)\right)\tilde{q}_{t}(x_{A}|x_{B})+\sum_{y:y_{BC}=x_{BC}}P_{t-1}(y)\tilde{q}_{t}(x_{A}|x_{B})$
$\displaystyle=\sum_{y:y_{BC}=x_{BC}}\left(W_{t-1}(y)-P_{t-1}(y)\right)\tilde{q}_{t}(x_{A}|x_{B})+\sum_{y:y_{BC}=x_{BC}}P_{t-1}(y)\left(\tilde{q}_{t}(x_{A}|x_{B})-q_{t}(x_{A}|x_{B}x_{C})\right)+P_{t}(x),$
(34)

where we used the fact that
$P_{t}(x)=\sum_{y:y_{BC}=x_{BC}}P_{t-1}(y)q_{t}(x_{A}|x_{B}x_{C})$. Now using
Eq. 34, summing over $x\in\\{0,1\\}^{n}$, and using the triangle inequality,
we get

$\displaystyle\|W_{t}-P_{t}\|_{1}$
$\displaystyle\leq\sum_{x_{BC}\in\\{0,1\\}^{BC}}\sum_{y:y_{BC}=x_{BC}}|\left(W_{t-1}(y)-P_{t-1}(y)\right)|\sum_{x_{A}\in\\{0,1\\}^{|A|}}\tilde{q}_{t}(x_{A}|x_{B})$
$\displaystyle+\sum_{x_{BC}\in\\{0,1\\}^{BC}}\sum_{y:y_{BC}=x_{BC}}P_{t-1}(y)\sum_{x_{A}\in\\{0,1\\}^{|A|}}\left|\tilde{q}_{t}(x_{A}|x_{B})-q_{t}(x_{A}|x_{B}x_{C})\right|$
$\displaystyle=\|W_{t-1}-P_{t-1}\|_{1}+\mathbb{E}_{z\sim
P_{t-1,BC}}\left(\|q_{t}(\cdot|z_{B}z_{C})-\tilde{q}_{t}(\cdot|z_{B})\|_{1}\right).$
(35)

Using Eqs. 12 and 13 and the relationship between trace distance and quantum
fidelity, we have

$\|q_{t}(\cdot|z_{B}z_{C})-\tilde{q}_{t}(\cdot|z_{B})\|_{1}\leq\|\rho_{t}(z_{B}z_{C})-\tilde{\rho}_{t}(z_{B})\|_{1}\leq
2\sqrt{1-F(\rho_{t}(z_{B}z_{C}),\tilde{\rho}_{t}(z_{B}))}.$ (36)

Plugging Eq. 36 into Eq. 35 and using the fact that
$\mathbb{E}[\sqrt{X}]\leq(\mathbb{E}[X])^{1/2}$ for any non-negative random
variable $X$ gives

$\displaystyle\|W_{t}-P_{t}\|_{1}$
$\displaystyle\leq\|W_{t-1}-P_{t-1}\|_{1}+2\left(\mathbb{E}_{z\sim
P_{t-1,BC}}\left[1-F(\rho_{t}(z_{B}z_{C}),\tilde{\rho}_{t}(z_{B}))\right]\right)^{1/2}$
$\displaystyle\leq\|W_{t-1}-P_{t-1}\|_{1}+2\left(1-\mathbb{E}_{z_{B}\sim
P_{t-1,B}\left[\mathrm{Tr}(\tilde{\rho}_{t}(z_{B})^{2})\right]}\right)^{1/2}\qquad
t\in S.$ (37)

where we used Lemma 2 and the fact that $P_{t-1,BC}=P_{t,BC}$ (since the
unitary gate $U_{t}$ acts only on qubit $A$ and does not change the marginal
distribution on $BC$).

Next suppose $t\notin\Gamma$, so $U_{t}=\mathrm{CNOT}_{ij}$ for some pair of
qubits $i\neq j$. Let $f_{t}(x)$ be the function applied to $x$ in line $4$ of
Algorithm 1; that is, it updates $x$ by replacing $x_{j}\leftarrow x_{i}\oplus
x_{j}$. Then

$W_{t}(x)=W_{t-1}(f_{t}(x))\quad\text{ and }\quad P_{t}(x)=P_{t-1}(f_{t}(x)),$

so in this case

$\|W_{t}-P_{t}\|_{1}=\|W_{t-1}-P_{t-1}\|_{1}\qquad t\notin\Gamma.$ (38)

Applying Eqs. 37 and 38 for $t=1,2,\ldots,m$ and using the fact that
$P_{0}=W_{0}$, we arrive at

$\|W_{m}-P_{m}\|_{1}\leq 2\sum_{t\in\Gamma}\left(1-\mathop{\mathbb{E}}_{z\sim
P_{t-1,B}}\left[\mathrm{Tr}(\tilde{\rho}_{t}(z)^{2})\right]\right)^{1/2}=2\sum_{t\in\Gamma}\left(1-\mathop{\mathbb{E}}_{z\sim
P_{t,B}}\left[\mathrm{Tr}(\tilde{\rho}_{t}(z)^{2})\right]\right)^{1/2}$

where in the last equality we used the fact that $U_{t}$ is a single-qubit
gate acting on qubit $A$, so $P_{t-1,B}=P_{t,B}$. This completes the proof of
Eq. 14.

##  Appendix B Proof of Lemma 5

Before proving this theorem we require a preliminary result about the effect
of conjugating Pauli operators through random Clifford circuits.

######  Lemma 9.

Let $P_{1},P_{2},\ldots,P_{r}$ be uniformly random non-identity Pauli strings
of various lengths, chosen so that $P_{1}\otimes P_{2}\otimes\cdots\otimes
P_{r}$ defines a Pauli string of length $n$. Denote this Pauli string
$P_{[n]}$ and for any $Q\subseteq[n]$ let $P_{Q}$ denote the corresponding
truncation of this string. Let $C$ be a uniformly random $t$-qubit Clifford
operator. Then

  1. (a)

For any $Q\subseteq[n]$ with $\lvert Q\rvert=t$:

$\displaystyle\Pr\left[C^{\dagger}P_{Q}C\text{ is
$Z$-type}\right]\leq\left(\frac{1}{2}\right)^{t}.$ (39)

  2. (b)

For any $Q\subseteq[n]$ with $\lvert Q\rvert=k<t$:

$\displaystyle\Pr\left[C^{\dagger}\left(P_{Q}\otimes I^{\otimes
t-k}\right)C\text{ is
$Z$-type}\right]\leq\left(\frac{1}{4}\right)^{k}+\left(\frac{1}{2}\right)^{t}.$
(40)

Moreover, these bounds still hold even after arbitrary conditioning on the
value of Paulis in the complimentary string $P_{[n]\backslash Q}$.

###### Proof.

We first argue that for any $Q$ the probability of $P_{Q}$ being identity is
at most $4^{-\lvert Q\rvert}$, even after conditioning on an arbitrary value
for $P_{[n]\backslash Q}$. If the Pauli’s $P_{1},P_{2},\ldots,P_{r}$ were
uniformly random (including the possibility of being the identity) then each
individual Pauli in $P_{[n]}$ would be chosen uniformly at random and this
statement would be immediate, with the bound $4^{-\lvert Q\rvert}$ holding
exactly. That is, if we let
$P_{1}^{\prime},P_{2}^{\prime},\ldots,P_{r}^{\prime}$ be uniformly random
Pauli strings which may be the identity we have

$\displaystyle\Pr\left[\left(P_{1}^{\prime}\otimes
P_{2}^{\prime}\otimes\cdots\otimes
P_{r}^{\prime}\right)_{Q}=I\;|\;\left(P_{1}^{\prime}\otimes
P_{2}^{\prime}\otimes\cdots\otimes P_{r}^{\prime}\right)_{[n]\backslash
Q}=K^{\prime}\right]=4^{-\lvert Q\rvert}$ (41)

for any choice of $Q$ and Pauli string $K^{\prime}$. But now we observe that
further enforcing that each $P_{i}^{\prime}$ is non-identity in the above
equation can only increase the probability that $\left(P_{1}^{\prime}\otimes
P_{2}^{\prime}\otimes\cdots\otimes P_{r}^{\prime}\right)_{Q}$ is non-identity
since, by Bayes’ rule,

$\displaystyle\frac{\Pr\left[\left(P_{1}^{\prime}\otimes
P_{2}^{\prime}\otimes\cdots\otimes
P_{r}^{\prime}\right)_{Q}=I\;|\;\left(P_{1}^{\prime}\otimes
P_{2}^{\prime}\otimes\cdots\otimes P_{r}^{\prime}\right)_{[n]\backslash
Q}=K^{\prime}\textbf{ and
}P_{1}^{\prime},P_{2}^{\prime},\ldots,P_{r}^{\prime}\neq
I\right]}{\Pr\left[\left(P_{1}^{\prime}\otimes
P_{2}^{\prime}\otimes\cdots\otimes
P_{r}^{\prime}\right)_{Q}=I\;|\;\left(P_{1}^{\prime}\otimes
P_{2}^{\prime}\otimes\cdots\otimes P_{r}^{\prime}\right)_{[n]\backslash
Q}=K^{\prime}\right]}$ $\displaystyle\hskip
30.0pt=\frac{\Pr\left[P_{1}^{\prime},P_{2}^{\prime},\ldots,P_{r}^{\prime}\neq
I\;|\;\left(P_{1}^{\prime}\otimes P_{2}^{\prime}\otimes\cdots\otimes
P_{r}^{\prime}\right)_{[n]\backslash Q}=K^{\prime}\textbf{ and
}\left(P_{1}^{\prime}\otimes P_{2}^{\prime}\otimes\cdots\otimes
P_{r}^{\prime}\right)_{Q}=I\right]}{\Pr\left[P_{1}^{\prime},P_{2}^{\prime},\ldots,P_{r}^{\prime}\neq
I\;|\;\left(P_{1}^{\prime}\otimes P_{2}^{\prime}\otimes\cdots\otimes
P_{r}^{\prime}\right)_{[n]\backslash Q}=K^{\prime}\right]}$

and the quantity on the on the right hand side of the above equation is
clearly bounded above by one. The statement follows.

A similar logic can be applied to prove statements $(a)$ and $(b)$ directly
but, for concreteness, we will take a slightly more involved route. We start
with $(a)$. The random Clifford $C$ will map a non-identity Pauli to a
uniformly random non-identity Pauli on $t$ qubits. There are $4^{t}-1$ such
Paulis and $2^{t}-1$ of them are $Z$-type, so

$\displaystyle\Pr\left[C^{\dagger}P_{Q}C\text{ is $Z$-type}\right]$
$\displaystyle=\Pr[P_{Q}\text{ is identity}]+\Pr[P_{Q}\text{ is non-
identity}]\left(\frac{2^{t}-1}{4^{t}-1}\right)$ $\displaystyle\leq
4^{-t}+(1-4^{-t})\left(\frac{2^{t}-1}{4^{t}-1}\right)$
$\displaystyle=\frac{1}{4^{t}}+\frac{2^{t}-1}{4^{t}}=\frac{1}{2^{t}},$ (42)

where we used our upper bound on the probability of $P_{Q}$ begin the identity
along with the fact that $\frac{2^{t}-1}{4^{t}-1}\leq 1$ to go from the first
line to the second.

To prove $(b)$ we begin with a similar expression and find

$\displaystyle\Pr\left[C^{\dagger}\left(P_{Q}\otimes I^{\otimes
t-k}\right)C\text{ is $Z$-type}\right]$ $\displaystyle=\Pr[P_{Q}\text{ is
identity}]+\Pr[P_{Q}\text{ is non-
identity}]\left(\frac{2^{t}-1}{4^{t}-1}\right)$ $\displaystyle\leq
4^{-k}+(1-4^{-k})\left(\frac{2^{t}-1}{4^{t}-1}\right)$ $\displaystyle\leq
4^{-k}+\left(\frac{2^{t}-1}{4^{t}-1}\right)\leq 4^{-k}+2^{-t},$ (43)

as desired. ∎

We now proceed to the proof of Lemma 5.

###### Proof (Lemma 5).

We write $D=WV$ where $V$ and $W$ denote the first and second layer of random
Clifford circuits, respectively. We first consider the Pauli string obtained
by conjugating $P$ by just the second layer of Cliffords, which we can write
as $P^{\prime}=W^{\dagger}PW$. This string consists of a random non-identity
Pauli string acting on every $\tau\times\tau$ patch of qubits in the support
of $\mathcal{G}(P)$, and is identity elsewhere. There are $a$ such patches by
definition, and so $a\tau^{2}$ qubits on which this random Pauli string can
potentially be non-identity. Let $Q^{\prime}$ denote the set of all these
qubits.

Now we consider the first layer of random Clifford unitaries. Recall from the
definition of random coarse-grained circuits that we have $V=V_{1}\otimes
V_{2}\otimes\cdots\otimes V_{(m-1)^{2}}$, where each $V_{i}$ is a random
$\tau\times\tau$ Clifford. For any $1\leq i\leq(m-1)^{2}$ let
$Q^{\prime}_{i}=Q^{\prime}\cap\operatorname{supp}(V_{i})$ and let
$P^{\prime}_{i}$ be the restriction of the Pauli string $P^{\prime}$ to the
support of $V_{i}$. Finally let
$Q_{0}^{\prime}=Q^{\prime}\backslash(\cup_{i}Q^{\prime}_{i})$ and
$P^{\prime}_{0}$ be the restriction of $P^{\prime}$ to $Q^{\prime}_{0}$. Also,
as a notational convenience, let $V_{0}$ denote the identity gate acting on
the qubits in $Q_{0}^{\prime}$. (This is to accommodate qubits in $Q^{\prime}$
which lie on the boundary of the circuit, and thus are not in the support of
any $V_{i}$ for $i\geq 1$). We want to bound the quantity

$\displaystyle\Pr[D^{\dagger}PD\text{ is $Z$-type}]$
$\displaystyle=\Pr\left[V_{i}^{\dagger}P^{\prime}_{i}V_{i}\text{ is $Z$-type
for all $0\leq i\leq(m-1)^{2}$}\right]$
$\displaystyle=\prod_{i=0}^{(m-1)^{2}}\Pr\left[V_{i}^{\dagger}P^{\prime}_{i}V_{i}\text{
is $Z$-type}\;|\;V_{j}^{\dagger}P^{\prime}_{j}V_{j}\text{ is $Z$-type for all
$0\leq j<i$}\right].$ (44)

It is immediate from definitions that

$\displaystyle\Pr[V_{0}^{\dagger}P_{0}^{\prime}V_{0}\text{ is
$Z$-type}]=\Pr[P_{0}^{\prime}\text{ is $Z$-type}]\leq 2^{-\lvert
Q_{0}^{\prime}\rvert}.$ (45)

Then let $\mathcal{V}_{\text{int}}$ be the set of all $V_{i}$ with
$0<i\leq(m-1)^{2}$ whose support is contained entirely in $Q^{\prime}$, and
$\mathcal{V}_{\text{perim}}$ be the set of all $V_{i}$ ith $0<i\leq(m-1)^{2}$
whose support overlaps partially with $Q^{\prime}$. As an immediate
consequence of Lemma 9 (a) we see that for any
$V_{i}\in\mathcal{V}_{\text{int}}$

$\displaystyle\Pr\left[V_{i}^{\dagger}P^{\prime}_{i}V_{i}\text{ is
$Z$-type}\;|\;V_{j}^{\dagger}P^{\prime}_{j}V_{j}\text{ is $Z$-type for all
$j<i$}\right]\leq 2^{-\tau^{2}}=2^{-\lvert Q_{i}^{\prime}\rvert}.$ (46)

Similarly, for any $V_{i}\in\mathcal{V}_{\text{perim}}$, Lemma 9 (b) gives
that

$\displaystyle\Pr\left[V_{i}^{\dagger}P^{\prime}_{i}V_{i}\text{ is
$Z$-type}\;|\;V_{j}^{\dagger}P^{\prime}_{j}V_{j}\text{ is $Z$-type for all
$j<i$}\right]\leq 4^{-\lvert Q_{i}^{\prime}\rvert}+2^{-\tau^{2}}.$ (47)

For any $V_{i}\in\mathcal{V}_{\text{perim}}$ we have that at least $1/4$ and
at most $3/4$’s of the qubits in the support of $V_{i}$ overlap with
$Q^{\prime}$, and hence $\tau^{2}/4\leq\lvert Q_{i}^{\prime}\rvert\leq
3\tau^{2}/4$. Then we can also write

$\displaystyle\Pr\left[V_{i}^{\dagger}P^{\prime}_{i}V_{i}\text{ is
$Z$-type}\;|\;V_{j}^{\dagger}P^{\prime}_{j}V_{j}\text{ is $Z$-type for all
$j<i$}\right]$ $\displaystyle\leq 4^{-\lvert Q_{i}^{\prime}\rvert}+2^{-4\lvert
Q_{i}^{\prime}\rvert/3}$ $\displaystyle=2^{-\lvert
Q_{i}^{\prime}\rvert}\left(2^{-\lvert Q_{i}^{\prime}\rvert}+2^{-\lvert
Q_{i}^{\prime}\rvert/3}\right)$ $\displaystyle\leq 2^{-\lvert
Q_{i}^{\prime}\rvert-(\tau^{2}/12)+1}.$ (48)

Combining Eqs. 45, 46 and 48 gives

$\displaystyle\Pr[D^{\dagger}PD\text{ is $Z$-type}]$ $\displaystyle\leq
2^{-\lvert
Q_{0}^{\prime}\rvert}\left(\prod_{V_{i}\in\mathcal{V}_{\text{int}}}2^{-\lvert
Q_{i}^{\prime}\rvert}\right)\left(\prod_{V_{j}\in\mathcal{V}_{\text{perim}}}2^{-\lvert
Q_{j}\rvert-\tau^{2}/12+1}\right)$
$\displaystyle=2^{-\lvert\mathcal{V}_{\text{perim}}\rvert(\tau^{2}/12-1)-\sum_{i=0}^{(m-1)^{2}}\lvert
Q^{\prime}_{i}\rvert}$
$\displaystyle=2^{-\lvert\mathcal{V}_{\text{perim}}\rvert(\tau^{2}/12-1)-\lvert
Q^{\prime}\rvert}.$ (49)

We observed previously that $\lvert Q^{\prime}\rvert=a\tau^{2}$. Every gate
$V_{i}\in\mathcal{V}_{\text{perim}}$ intersects with four edges, and in the
worst case, all four of the edges could be perimeter edges. At the same time,
every perimeter edge intersects with at least one gate in
$\mathcal{V}_{\text{perim}}$. Therefore,
$|\mathcal{V}_{\text{perim}}|\geq\frac{1}{4}l$. Inserting those two values
into the equation above completes the proof.

∎

##  Appendix C Compiling the coarse-grained architecture to random quantum
circuits

Here we consider the setup of Theorem 14 which involves compiled random
coarse-grained circuits $\tilde{\mathcal{U}}$ and their Clifford versions
$\tilde{\mathcal{D}}$ composed of two-qubit gates. We show that an equivalent
version of Lemma 5 holds for $\tilde{\mathcal{D}}$ with sufficiently small
$\varepsilon$. The gates in the non-compiled coarse-grained circuits act on
blocks of $\tau\times\tau$ qubits. Define $t=\tau^{2}$. Let $\mathcal{D}_{t}$
denote the uniform distribution over $t$-qubit Clifford operators. Let
$\tilde{\mathcal{D}}_{t}$ be a distribution of $t$-qubit random Clifford
circuits forming an $\varepsilon$-approximate unitary $2$-design w.r.t the
operator norm. The approximate $2$-design property of
$\tilde{\mathcal{D}}_{t}$ in this notion implies that for every
$2^{t}$-by-$2^{t}$ matrix $A,B$ with $\lVert A\rVert_{F}=\lVert
B\rVert_{F}=1$, it holds that

$\left|\mathop{\mathbb{E}}_{\tilde{C}\sim\tilde{\mathcal{D}}_{t}}\left[\text{Tr}(B\tilde{C}^{\dagger}A\tilde{C})^{2}\right]-\mathop{\mathbb{E}}_{C\sim\mathcal{D}_{t}}\left[\text{Tr}(BC^{\dagger}AC)^{2}\right]\right|\leq\varepsilon.$
(50)

While the compilation is agnostic to any specific construction of
$\varepsilon$-approximate $2$-design, for concreteness, we could implement the
circuits in $\tilde{\mathcal{D}}_{t}$ using 1D brickwork random Clifford
circuits with depth $O(\log(1/\varepsilon))$ [30, 31]. Alternatively, we can
consider a local random quantum circuit architecture with
$O(t\log(1/\varepsilon))$ gates where at each time step, a random $2$-qubit
Clifford gate is applied to a randomly chosen qubit and one of its neighbours
on the 2D grid [34]. We note that the constructions in [30, 31, 34] are known
to from an $\varepsilon$-approximate $2$-design if the circuits are composed
of Haar random two-qubit gates or random gates drawn from a universal gate
set. However, we observe that the same constructions yield
$\varepsilon$-approximate $2$-design if the gates are chosen randomly from
$2$-qubit Clifford gates. This is the case because the $2$-design bounds in
[30, 31, 34] are established by analyzing mathematical objects defined solely
using the second moment operator associated with the $2$-qubit Haar measure
$\mathcal{U}_{2}$

$\mathop{\mathbb{E}}_{U\sim\mathcal{U}_{2}}\left[U^{\otimes
2}\otimes\left(\overline{U}\right)^{\otimes 2}\right],$ (51)

and the architecture template—for example by lower bounding the spectral gap
of a local Hamiltonian defined in terms of Eq. 51. Since the uniform
distribution over $2$-qubit Clifford gates $\mathcal{D}_{2}$ forms an exact
unitary $2$-design,

$\mathop{\mathbb{E}}_{C\sim\mathcal{D}_{2}}\left[C^{\otimes
2}\otimes\left(\overline{C}\right)^{\otimes
2}\right]=\mathop{\mathbb{E}}_{U\sim\mathcal{U}_{2}}\left[U^{\otimes
2}\otimes\left(\overline{U}\right)^{\otimes 2}\right].$

Mirroring the proof strategy for Lemma 5, we begin by establishing a direct
analog of Lemma 9 in Appendix B.

######  Lemma 10.

Let $K$ be an arbitrary non-identity $t$-qubit Pauli operator, draw a
$\tilde{C}\sim\tilde{\mathcal{D}}_{t}$, and define
$P=\tilde{C}^{\dagger}K\tilde{C}$. Let $h,s\geq 1$ satisfy $h+s=t$. Decompose
$P$ as $P=\pm P_{1}\otimes P_{2}$ such that $P_{1}$ and $P_{2}$ are $h$\- and
$s$-qubit Pauli operators respectively. Let
$\emptyset\neq\mathcal{P}\subseteq\\{I,X,Y,Z\\}^{\otimes s}$. Then for every
$\varepsilon\leq\frac{1}{3(4^{t}-1)}$, it holds that

$\Pr(P_{1}=I^{\otimes
h}|P_{2}\in\mathcal{P})\leq\frac{1}{4^{h}}(1+3(4^{t}-1)\varepsilon).$ (52)

###### Proof.

In the following, we make use of the fact that for every non-identity Pauli
$W\in\\{I,X,Y,Z\\}^{\otimes t}\setminus\\{I^{\otimes t}\\}$,

$\Pr(P=\pm
W)=\frac{1}{4^{t}}\mathop{\mathbb{E}}_{\tilde{C}\sim\tilde{\mathcal{D}}_{t}}\left[\text{Tr}(W\tilde{C}^{\dagger}K\tilde{C})^{2}\right].$
(53)

Thus, by Eq. 50,

$\frac{1}{4^{t}-1}-\varepsilon\leq\Pr(P=\pm
W)\leq\frac{1}{4^{t}-1}+\varepsilon.$ (54)

Since $\mathcal{P}\neq\emptyset$, either $I^{\otimes s}\notin\mathcal{P}$ or
$I^{\otimes s}\in\mathcal{P}$. First consider the case where $I^{\otimes
s}\notin\mathcal{P}$. In this case, we have

$\displaystyle\Pr(P_{1}=I^{\otimes h}|P_{2}\in\mathcal{P})$
$\displaystyle=\frac{\Pr(P_{1}=I^{\otimes h}\text{ and
}P_{2}\in\mathcal{P})}{\Pr(P_{2}\in\mathcal{P})}$
$\displaystyle\leq\frac{|\mathcal{P}|\left(\frac{1}{4^{t}-1}+\varepsilon\right)}{|\mathcal{P}|4^{h}\left(\frac{1}{4^{t}-1}-\varepsilon\right)}$
$\displaystyle\leq\frac{1}{4^{h}}(1+3(4^{t}-1)\varepsilon)$ (55)

where in the last line, we use the fact that $\frac{1+x}{1-x}\leq 1+3x$ for
every $0\leq x\leq\frac{1}{3}$. Secondly, for the case where $I^{\otimes
s}\in\mathcal{P}$, we have

$\displaystyle\Pr(P_{1}=I^{\otimes h}|P_{2}\in\mathcal{P})$ $\displaystyle=$
$\displaystyle\frac{\Pr(P_{1}=I^{\otimes h}\text{ and
}P_{2}\in\mathcal{P})}{\Pr(P_{2}\in\mathcal{P})}$ $\displaystyle\ =$
$\displaystyle\frac{\Pr(P_{1}=I^{\otimes h}\text{ and }P_{2}=I^{\otimes
s})+\Pr(P_{1}=I^{\otimes h}\text{ and
}P_{2}\in\mathcal{P}\setminus\\{I^{\otimes s}\\})}{\Pr(P_{2}=I^{\otimes
s})+\Pr(P_{2}\in\mathcal{P}\setminus\\{I^{\otimes s}\\})}$ $\displaystyle\leq$
$\displaystyle\frac{(|\mathcal{P}|-1)(\frac{1}{4^{t}-1}+\varepsilon)}{(4^{h}|\mathcal{P}|-1)(\frac{1}{4^{t}-1}-\varepsilon)}$
$\displaystyle\leq$ $\displaystyle\frac{1}{4^{h}}(1+3(4^{t}-1)\varepsilon).$
(56)

∎

######  Lemma 11.

Let $r\in\\{1,2,3,4\\}$. Let $K_{1},\ldots,K_{r}$ be arbitrary non-identity
$t$-qubit Pauli operators. For every $i\in\\{1,\ldots,r\\}$, draw an
independent $\tilde{C}_{i}\sim\tilde{\mathcal{D}}_{t}$, define
$P_{i}=\tilde{C}_{i}^{\dagger}K_{i}\tilde{C}_{i}$, and write $P_{i}=\pm
E_{i}\otimes F_{i}$ such that $E_{i}$ and $F_{i}$ are $\frac{t}{4}$\- and
$\frac{3t}{4}$-qubit Pauli operators respectively. Define
$P_{Q}=\bigotimes_{i=1}^{r}E_{i}$, $P_{Q}^{\prime}=\bigotimes_{i=1}^{r}F_{i}$,
and $k=\frac{rt}{4}$. Let
$\emptyset\neq\mathcal{P}\subseteq\\{I,X,Y,Z\\}^{3k}$. Then

  1. 1.

for $r=4$,

$\Pr_{(\tilde{C}_{1},\ldots,\tilde{C}_{r},\tilde{C})\sim\tilde{\mathcal{D}}_{t}}[\tilde{C}^{\dagger}P_{Q}\tilde{C}\text{
is
$Z$-type}|P_{Q}^{\prime}\in\mathcal{P}]\leq\left(\frac{1}{2}\right)^{t-2^{2t+2}\varepsilon},$
(57)

  2. 2.

for $r\in\\{1,2,3\\}$, for every $\varepsilon\leq\frac{1}{8^{t}}$,

$\Pr_{(\tilde{C}_{1},\ldots,\tilde{C}_{r},\tilde{C})\sim\tilde{\mathcal{D}}_{t}}[\tilde{C}^{\dagger}(P_{Q}\otimes
I^{\otimes t-k})\tilde{C}\text{ is
$Z$-type}|P_{Q}^{\prime}\in\mathcal{P}]\leq\frac{1}{4^{k}}+\frac{2}{2^{t}}.$
(58)

###### Proof.

For every non-identity $t$-qubit Pauli operator $W\in\\{I,X,Y,Z\\}^{\otimes
t}\setminus\\{I^{\otimes t}\\}$, it holds that

$\Pr_{\tilde{C}\sim\tilde{\mathcal{D}}_{t}}\left(\tilde{C}^{\dagger}W\tilde{C}\text{
is
$Z$-type}\right)=2^{t}\mathop{\mathbb{E}}_{\tilde{C}\sim\tilde{\mathcal{D}}_{t}}\left[\langle
0^{n}|\tilde{C}^{\dagger}\frac{W}{\sqrt{2^{t}}}\tilde{C}|0^{n}\rangle^{2}\right]\leq\frac{1}{2^{t}+1}+2^{t}\varepsilon.$
(59)

By the previous lemma and the independence among $F_{1},\ldots,F_{r}$,

$\displaystyle\Pr(P_{Q}=I^{\otimes k}|P_{Q}^{\prime}\in\mathcal{P})$
$\displaystyle\leq\frac{1}{4^{k}}(1+3(4^{t}-1)\varepsilon)^{r}$
$\displaystyle\leq\frac{1}{4^{k}}+\frac{15(4^{t}-1)}{4^{k}}\varepsilon$ (60)

where we use the fact that $(1+x)^{r}\leq(1+x)^{4}\leq 1+5x$ for every $0\leq
x\leq 0.15$. Thus, for $r=4$, we get by convexity that

$\displaystyle\Pr(\tilde{C}^{\dagger}P_{Q}\tilde{C}\text{ is
$Z$-type}|P_{Q}^{\prime}\in\mathcal{P})$ $\displaystyle\leq$
$\displaystyle\Pr(P_{Q}=I^{\otimes
k}|P_{Q}^{\prime}\in\mathcal{P})+(1-\Pr(P_{Q}=I^{\otimes
k}|P_{Q}^{\prime}\in\mathcal{P}))\left(\frac{1}{2^{t}+1}+2^{t}\varepsilon\right)$
$\displaystyle\leq$
$\displaystyle\frac{1}{4^{t}}+15\varepsilon+\left(1-\frac{1}{4^{t}}-15\varepsilon\right)\left(\frac{1}{2^{t}+1}+2^{t}\varepsilon\right)$
$\displaystyle\leq$ $\displaystyle\frac{1}{2^{t}}+(2^{t}+15)\varepsilon$
$\displaystyle=$ $\displaystyle 2^{-t+\log(1+2^{t}(2^{t}+15)\varepsilon)}$
$\displaystyle\leq$ $\displaystyle 2^{-t+2^{2t+2}\varepsilon}$ (61)

where in the last line, we use the fact that $\log_{2}(1+x)\leq 2x$ for every
$x\geq 0$. For the second bound, we have

$\displaystyle\Pr(\tilde{C}^{\dagger}(P_{Q}\otimes I^{\otimes
t-k})\tilde{C}\text{ is $Z$-type}|P_{Q}^{\prime}\in\mathcal{P})$
$\displaystyle\leq$
$\displaystyle\frac{1}{4^{k}}+\frac{15(4^{t}-1)}{4^{k}}\varepsilon+\left(1-\frac{1}{4^{k}}-\frac{15(4^{t}-1)}{4^{k}}\varepsilon\right)\left(\frac{1}{2^{t}+1}+2^{t}\varepsilon\right)$
$\displaystyle\leq$
$\displaystyle\frac{1}{4^{k}}+\frac{1}{2^{t}}+\left(\frac{15(4^{t}-1)}{4^{k}}+2^{t}\right)\varepsilon$
$\displaystyle\leq$
$\displaystyle\frac{1}{4^{k}}+\frac{1}{2^{t}}+\frac{1}{2^{t}}$ (62)

since $\varepsilon\leq\frac{1}{8^{t}}$. ∎

######  Theorem 15.

Let $P$ be an $n$-qubit Pauli operator, and let $\tilde{D}$ be a compiled
random Clifford circuit. Also let $a=\lvert\mathcal{G}(P)\rvert$ and
$l=\mathrm{Per}(\mathcal{G}(P))$ denote the size and perimeter of
$\mathcal{G}(P)$, respectively. Assume $\tau\geq\Omega(\sqrt{\log(m)})$ and
choose $\varepsilon=2^{-ct}=2^{-c\tau^{2}}$ for some large enough $c$ so that
$(m-1)^{2}2^{2t+2}\varepsilon\leq 1$. Then

$\displaystyle\Pr[\tilde{D}^{\dagger}P\tilde{D}\text{ is
$Z$-type}]\leq\left(\frac{1}{2}\right)^{a\tau^{2}+\frac{1}{4}l(\tau^{2}/12-2)-1}.$
(63)

###### Proof.

It suffices to establish bounds analogous to the ones appearing in the proof
of Lemma 5 for compiled random Clifford circuits. We inherit all the
definitions from the proof of Lemma 5. For every
$V_{i}\in\mathcal{V}_{\text{int}}$,

$\displaystyle\Pr\left[V_{i}^{\dagger}P^{\prime}_{i}V_{i}\text{ is
$Z$-type}\;|\;V_{j}^{\dagger}P^{\prime}_{j}V_{j}\text{ is $Z$-type for all
$j<i$}\right]\leq 2^{-\tau^{2}+2^{2t+2}\varepsilon}=2^{-\lvert
Q_{i}^{\prime}\rvert+2^{2t+2}\varepsilon}.$ (64)

For every $V_{i}\in\mathcal{V}_{\text{perim}}$,

$\displaystyle\Pr\left[V_{i}^{\dagger}P^{\prime}_{i}V_{i}\text{ is
$Z$-type}\;|\;V_{j}^{\dagger}P^{\prime}_{j}V_{j}\text{ is $Z$-type for all
$j<i$}\right]$ $\displaystyle\leq 4^{-\lvert
Q_{i}^{\prime}\rvert}+2^{-\tau^{2}+1}$ $\displaystyle\leq 4^{-\lvert
Q_{i}^{\prime}\rvert}+2^{-4\lvert Q_{i}^{\prime}\rvert/3+1}$
$\displaystyle=2^{-\lvert Q_{i}^{\prime}\rvert}\left(2^{-\lvert
Q_{i}^{\prime}\rvert}+2^{-\lvert Q_{i}^{\prime}\rvert/3+1}\right)$
$\displaystyle\leq 2^{-|Q^{\prime}|-\tau^{2}/12+2}.$ (65)

Finally,

$\displaystyle\Pr[D^{\dagger}PD\text{ is $Z$-type}]$ $\displaystyle\leq
2^{-\lvert
Q_{0}^{\prime}\rvert+2^{2t+2}\varepsilon}\left(\prod_{V_{i}\in\mathcal{V}_{\text{int}}}2^{-\lvert
Q_{i}^{\prime}\rvert+2^{2t+2}\varepsilon}\right)\left(\prod_{V_{j}\in\mathcal{V}_{\text{perim}}}2^{-\lvert
Q_{j}\rvert-\tau^{2}/12+2}\right)$ $\displaystyle\leq
2^{-\lvert\mathcal{V}_{\text{perim}}\rvert(\tau^{2}/12-2)-\sum_{i=0}^{(m-1)^{2}}\lvert
Q^{\prime}_{i}\rvert+(m-1)^{2}2^{2t+2}\varepsilon}$ $\displaystyle\leq
2^{-\lvert\mathcal{V}_{\text{perim}}\rvert(\tau^{2}/12-2)-\lvert
Q^{\prime}\rvert+1}.$ (66)

To finish the proof, we recall from the proof of Lemma 5 that
$|Q_{i}|=a\tau^{2}$ and $|\mathcal{V}_{\text{perim}}|\geq\frac{1}{4}l$. ∎

##  Appendix D Proof of Eq. 18

###### Proof.

Without loss of generality let us fix a local basis so that
$C_{h},C_{i},C_{j}$ are identity, and the stabilizer group of $\psi$ contains
stabilizers $g_{1},g_{2},g_{3}$ in Eq. 16. By taking products of these
stabilizers $g_{1},g_{2},g_{3}$ we see that the stabilizer group of $\psi$
contains the following elements:

$\displaystyle g_{1}$ $\displaystyle=X_{h}X_{i}X_{j}Z(s)$ $\displaystyle
g_{2}$ $\displaystyle=Z_{h}Z_{i}I_{j}Z(t)$ $\displaystyle g_{3}$
$\displaystyle=I_{h}Z_{i}Z_{j}Z(u)$ $\displaystyle g_{4}$
$\displaystyle=-Y_{h}Y_{i}X_{j}Z(s\oplus t)$ $\displaystyle g_{5}$
$\displaystyle=-X_{h}Y_{i}Y_{j}Z(s\oplus u)$ $\displaystyle g_{6}$
$\displaystyle=-Y_{h}X_{i}Y_{j}Z(s\oplus t\oplus u)$ $\displaystyle g_{7}$
$\displaystyle=Z_{h}I_{i}Z_{j}Z(u\oplus t).$ (67)

Let us assume, to reach a contradiction, that $m$ satisfies Eq. 17. Write

$m_{s}=\prod_{v\in[n]}m_{v}^{s_{v}}\qquad
m_{t}=\prod_{v\in[n]}m_{v}^{t_{v}}\qquad m_{u}=\prod_{v\in[n]}m_{v}^{u_{v}}.$

Note that our function $m$ must only output binary strings that are consistent
with stabilizers that are diagonal in the measurement basis $b$. In this way
each of the stabilizers Eq. 67 places a constraint on the possible outputs of
$m$.

For example, from the stabilizer $g_{2}$ we infer that

$m_{h}\cdot m_{i}\cdot m_{t}=1\qquad\text{whenever}\quad b_{h}=b_{i}=2.$ (68)

Since each output bit depends on only one input bit, and $m_{h},m_{i}$ are
independent of $b_{j}$, we can infer from the above that $m_{t}$ is
independent of $b_{j}$. We now explain this in more detail. Let
$L_{h},L_{i},L_{j}\subseteq[n]$ be the set of output bits $m_{v}$ that depend
on inputs $b_{h},b_{i},b_{j}$ respectively, so that

$m_{t}=(-1)^{a}\prod_{v\in L_{h}}m_{v}(b_{h})\prod_{v\in
L_{i}}m_{v}(b_{i})\prod_{v\in L_{j}}m_{v}(b_{j})$ (69)

for some $a\in\\{0,1\\}$. Then Eq. 68 implies

$\prod_{v\in L_{j}}m_{v}(b_{j})=(-1)^{a}m_{h}(2)\cdot m_{i}(2)\cdot\prod_{v\in
L_{h}}m_{v}(2)\prod_{v\in L_{i}}m_{v}(2)\qquad b_{j}\in\\{0,1,2\\}.$ (70)

where $b\in\\{0,1\\}$ is fixed. Plugging Eq. 70 into Eq. 69 gives

$m_{t}=\prod_{v\in L_{h}}m_{v}(b_{h})\prod_{v\in
L_{i}}m_{v}(b_{i})\left[m_{h}(2)\cdot m_{i}(2)\cdot\prod_{v\in
L_{h}}m_{v}(2)\prod_{v\in L_{i}}m_{v}(2)\right]$

which shows that $m_{t}$ is independent of $b_{j}$.

In exactly the same way, from the stabilizers $g_{3},g_{7}$ we infer that
$m_{u}$ is independent of $b_{h}$ and that $m_{u}\cdot m_{t}$ is independent
of $b_{i}$.

Next consider the subset of inputs $b_{h},b_{i},b_{j}\in\\{0,1\\}$ which
correspond to measuring these qubits in the $X$ or $Y$ bases. Since $m_{t}$ is
independent of $b_{j}$ and $m_{U}$ is independent of $b_{h}$, there exist
affine functions $e,f,g,h:\\{0,1\\}\rightarrow\\{0,1\\}$ such that

$m_{t}=(-1)^{e(b_{h})+f(b_{i})}\quad m_{u}=(-1)^{g(b_{i})+h(b_{j})}\qquad
b_{h},b_{i},b_{j}\in\\{0,1\\}.$ (71)

Since $m_{t}\cdot m_{u}$ is independent of $b_{i}$ we may set

$g(b_{i})=f(b_{i}).$ (72)

From the stabilizers $g_{1},g_{4},g_{5},g_{6}$ we infer

$i^{b_{h}+b_{i}+b_{j}}m_{h}m_{i}m_{j}m_{s}m_{t}^{b_{h}}m_{u}^{b_{j}}=1\qquad
b_{h}\oplus b_{i}\oplus b_{j}=0\qquad b_{h},b_{i},b_{j}\in\\{0,1\\}.$ (73)

Plugging Eqs. 71 and 72 into Eq. 73 gives, for
$b_{h},b_{i},b_{j}\in\\{0,1\\}$,

$i^{b_{h}+b_{i}+b_{j}}m_{h}m_{i}m_{j}m_{s}(-1)^{b_{h}(e(b_{h})+f(b_{i}))}(-1)^{b_{j}(f(b_{i})+h(b_{j}))}=1\qquad
b_{h}\oplus b_{i}\oplus b_{j}=0.$ (74)

Now since each output bit $m_{v}$ depends on at most one of the variables
$b_{h},b_{i},b_{j}$, from the above we infer that for
$b_{h},b_{i},b_{j}\in\\{0,1\\}$ we have

$i^{b_{h}+b_{i}+b_{j}}(-1)^{\alpha_{0}+\alpha_{1}b_{h}+\alpha_{2}b_{i}+\alpha_{3}b_{j}}(-1)^{\beta
b_{h}b_{i}}(-1)^{\beta b_{i}b_{j}}=1\qquad b_{h}\oplus b_{i}\oplus b_{j}=0$
(75)

for some coefficients

$\alpha_{0},\alpha_{1},\alpha_{2},\alpha_{3},\beta\in\\{0,1\\}$ (76)

The claim below shows that we have reached a contradiction and we conclude
that Eq. 17 is not satisfied by any function $m$ of the form described in the
theorem statement. Eq. 18 then follows directly.

######  Claim 1.

Eq. 75 is not satisfied for any choice of coefficients Eq. 76.

###### Proof.

Assume, to reach a contradiction, that Eq. 75 holds. We’ll plug in values of
$b_{h},b_{i},b_{j}$ and infer a set of linear equations that must be satisfied
by the coefficients $\alpha_{0},\alpha_{1},\alpha_{2},\alpha_{3},\beta$. By
plugging in $b_{h}=b_{i}=b_{j}=0$ we infer $\alpha_{0}=0$. Next setting
$(b_{h},b_{i},b_{j})=\\{(1,1,0),(1,0,1),(0,1,1)\\}$ we get

$\displaystyle\alpha_{1}+\alpha_{2}+\beta$ $\displaystyle=1\mod 2$
$\displaystyle\alpha_{1}+\alpha_{3}$ $\displaystyle=1\mod 2$
$\displaystyle\alpha_{2}+\alpha_{3}+\beta$ $\displaystyle=1\mod 2$

Summing these three equations we are led to a contradiction ($0=1\mod 2$) and
therefore there is no solution. ∎

∎