[initials=PhF,color=phfcc5]phf

# Quantum complexity phase transitionsin monitored random circuits

Ryotaro Suzuki<EMAIL_ADDRESS>Dahlem Center for Complex Quantum
Systems, Freie Universität Berlin, Berlin 14195, Germany  Jonas Haferkamp
Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, Berlin
14195, Germany  School of Engineering and Applied Sciences,Harvard University,
Cambridge, MA 02318, USA  Jens Eisert  Dahlem Center for Complex Quantum
Systems, Freie Universität Berlin, Berlin 14195, Germany  Philippe Faist
Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, Berlin
14195, Germany

###### Abstract

Recently, the dynamics of quantum systems that involve both unitary evolution
and quantum measurementshave attracted attention due to the exotic phenomenon
of measurement-induced phase transitions. The latter refers to a sudden change
in a property of a state of $n$ qubits, such as itsentanglement entropy,
depending on the rate at which individual qubits are measured.At the same
time, quantum complexity emerged as a key quantity for the identification of
complex behaviour in quantum many-body dynamics.In this work, we investigate
the dynamics of the quantum state complexity in monitored random circuits,
where $n$ qubits evolve according to a random unitary circuitand are
individually measured with a fixed probability at each time step.We find that
theevolutionof the exact quantum state complexity undergoes a phase
transitionwhen changing the measurement rate.Below a critical measurement
rate, the complexity grows at least linearly in time until saturating to a
value $e^{\Omega(n)}$.Above, the complexity does not exceed
$\operatorname{poly}(n)$.In our proof, we make use of percolation theory
tofindpaths along whichan exponentially long quantum computation can be run
below the critical rate, and to identify events where the state complexity is
reset to zero above the critical rate.We lower bound the exact state
complexity in the former regime using recently developedtechniquesfrom
algebraic geometry.Our results combine quantum complexity growth, phase
transitions, and computation with measurementsto help understand the behavior
of monitored random circuits and to make progress towards determiningthe
computational power of measurements in many-body systems.

##  I Introduction

The evolution of quantum complexity in many-body quantum systems offers a new
approach to understandphenomena in quantum computation, quantum many-body
systems, and black holephysics [1]:Complexity is able to capture the long-time
behaviour of the quantum dynamics beyond the pointwhere many physical
quantities, such as the entanglement entropy,equilibrate to their limiting
value [2, 3].Quantum complexity might be viewed as a measure of the timefor
which asuitably chaotic system has been evolving [2]: Brown and Susskind
conjecturedthat complexity grows linearly in time for generic quantum dynamics
of an $n$-qubit system untilsaturating at times exponential in $n$ [4]. In
contrast, the entanglemententropy typically saturates after a time linear in
$n$.Versions of this conjecture have been proven in the context ofrandom
circuits [5, 6, 7].Many recent results at the interface of quantum complexity
and many-body systems havemainly been driven by the central role that quantum
complexity appears to play in theanti-de-Sitter space/conformal field theory
(AdS/CFT) correspondence [8, 9, 10, 4, 11]:The quantum complexity of the
quantum state in a CFT is believed tocorrespond to some physical property,
such as the volume, of a wormhole contained in thecorresponding AdS space [2,
12, 13, 14].Overall, quantum complexity is a measure of the intricacy of the
entanglement that is presentin an $n$-qubit state; its physical and
operational interpretations in the context ofmany-body physics are still being
uncovered [4, 15, 16, 17].To study the evolution of complexity of a CFT,one
often resorts to the simpler model oflocal random quantum circuits, in which
the evolution of an $n$-qubit system is modeled by applying 2-qubit gates
chosen at random on neighboring qubits.Local random circuits are expected to
reproduce a number of interesting features of chaoticsystems [18, 19, 20, 21,
22]while being technically more convenient to analyze than chaotic
Hamiltoniandynamics [23].In the model of random quantum circuits,the quantum
complexityhas been proven to grow sublinearly in time until saturating attimes
exponential in $n$ [24, 25, 5],using the toolbox of unitary $t$-designs [26,
27].The linear growth of the exact circuit complexityfor local random quantum
circuitswas eventually proved in Ref. [6] by exploitinggeometric
arguments.More precisely,the toolbox of algebraic geometryenables a
quantificationof the dimension of the set of all possible unitaries that can
be achieved with a fixednumber of gates in a specific circuit layout. This
dimension, called _accessible dimension_ , yields a lower bound the exact
quantum complexity of therandom circuit. The main result of Ref. [6] is a
consequence ofthe fact that the accessible dimension grows linearly in time
untilsaturating at a time exponential in $n$ (cf. also simplified proofs
inRef. [7]). We heavily rely uponthis powerful mathematical toolkit in this
work.A different line of research at the interface of computational complexity
theoryand many-body physics concerns complexity phase transitions.The latter
refer to situations where the complexity of solving a particular task
undergoesa sudden and drastic change when a parameter in the problem
isvaried.Such complexity phase transitions have initially been discussed when
studying the hardness regime of the random $k$-SATproblem [28, 29].More
recently, the complexity ofclassically simulating quantum circuits has been
foundto undergo a transitionfor instantaneousquantum polynomial (IQP)circuits
[30, 31, 32],linear optical circuits [33, 34, 35, 36],random quantum circuits
[37, 38],and dual-unitary circuits [39, 40, 41, 42, 43].Such transitions are
of particular interest fordrawingand delineating theboundaries between the
power of classical and quantum computing [44].

Figure 1: Our setup and the summary of the result.(a) We consider monitored
random circuits consisting of two-qubit Haar-random gates (green
boxes)arranged in staggered layers, where at each time step the individual
qubits undergo a measurementin the computational basis (thick blue points)
with probability $p$.The state vector $\ket{\psi}$ is obtained by applying the
circuit onto the computational basisstate vector $\ket{0^{n}}$ and
conditioning on all the measurement outcomes.(b)We find that the complexity
phase diagram of the monitored random circuitexhibits a phase transition at
the critical measurementrate $p_{c}=0.5$. The measure of
complexity,$C(\ket{\psi})$, is defined as theminimal number of two-qubit gates
required to prepare $\ket{\psi}$ exactly, in any circuit layout.In the
$C$-complex phase ($p<p_{c}$), the complexity $C$ grows at least linearly
until saturating to a value that is exponential in the system size.In the
$C$-uncomplex phase ($p>p_{c}$), the quantity $C$ saturates to a value
$\operatorname{poly}(n)$ after a time no more than $O(\log(n))$.The result
regarding the uncomplex phase agrees with earlier numerical results on the
area law[45]of Rényi-0 entropy in the regime $p>p_{c}$ in Ref. [46].Moreover,
another earlier numerical result [47] point to a description of the state
$\ket{\psi}$in terms of a Matrix-Product State (MPS) [48] with
$\operatorname{poly}(n)$ bond dimensionin the region $p\gtrsim
p_{c,\textup{MPS}}$,with $p_{c,\textup{MPS}}<0.5$. Given that a robust measure
of complexity wouldsaturate after a time $\sim\operatorname{poly}(n)$ in this
region, it is likely the region$p_{c,\textup{MPS}}<p<p_{c}$ yields examplesof
states generated by monitored random circuits whose exact complexity grows to
large values yet remainclose in trace norm to a state of low complexity.

Moreover,the effect of measurements on the dynamics of a complex many-body
quantum systemhas drawn significant interest in the many-bodyphysics
community. A common model combining measurements and unitary evolution is a
_monitored random quantum circuit_ on $n$ qubits and with measurement rate
$p\in[0,1]$:At each time step, randomly chosen two-qubit gates are applied
between neighboring qubits;furthermore, each individual qubit undergoes a
measurement in the computational basis with aprobability $p$. This simple
model has recently attracted substantial attention from the condensed
matterphysics community because such circuits may exhibit _measurement-induced
phase transitions_ [49, 46, 50, 51, 47, 52, 53, 54, 55, 56, 57, 58, 59, 60,
61, 62, 63, 63, 64, 65].The latter are an exotic type of phase transition that
depends on the rate $p$ at whichmeasurements are performed: The state’s
entanglement entropy then commonlytransitions from a scaling in the area of
the region considered [45] at high $p$(the _area law phase_) to a scaling in
the volume of the region at low $p$(the _volume law phase_).The goal of our
work is to combine the ideas of (i) complexity growth in many-body
systems,(ii) complexity phase transitions, and (iii) measurement-induced phase
transitions,to prove the existence of a sharp transition in the evolution of
quantum complexityin monitored quantum circuits depending on rate at which
measurements are applied.We thereby introduce the distinct notion of quantum
state complexity into the study of monitored quantum circuits.Specifically, we
prove rigorously that the growth of the exact state complexityin a monitored
random circuit on $n$ qubitsmakes a sharp transition at a critical rate
$p_{c}=0.5$ at which measurementsare applied (sketched in Fig. 1).Below the
threshold, the quantum complexity growsat least linearly in time until
saturatingto a value $e^{\Omega(n)}$(the _complex phase_).Above the threshold,
the state’s complexitysaturates to a value $\operatorname{poly}(n)$ after a
time no more than $O(\log(n))$(the _uncomplex phase_).We quantify the state’s
quantum complexity in terms of the number of two-qubit unitarygates required
to prepare that state exactly.We establish a framework of the study of
complexity of monitored random circuits as follows.We draw deep inspiration
from the seminal work on measurement-induced phase transitionsin the dynamics
of entanglement [46], including the use of techniques frompercolation theory
[66],while adapting tothe techniques to lower bound the exact quantum circuit
complexity usingsemi-algebraic geometry of Ref. [6].The complexity phase
transition that we find concerns the quantum complexity of the output state of
the monitored circuit,and might be of different nature than the phase
transitionin the classical complexity of sampling outcomes from randomcircuits
[38] and monitored linear optical circuits [36].Our results reinforce
monitored random circuits as a promising model to investigate quantum
complexity phase transitionsand the influence of measurements on the
complexity of a quantum circuit’s output state.The remainder of this work is
organized as follows.In Section II, we review monitored quantum circuits and
methods of lower-bounding the state complexity.In Section III, we summarize
our main results, discuss their core implications, and sketch our proof
strategy.In Section IV, we give a proof of our main result.Section V is
devoted to conclusion and discussion.

##  II Setting

In this section, we review the definitions ofmonitored random quantum
circuits, of the exact state complexity,and of the accessible dimension.

###  II.1 Monitored random quantum circuits

Throughout this work, we considera system of $n$ qubits. The qubits might be
realized, for instance, as individual spins of a quantum many-body system.For
technical convenience, we assume that $n$ is an even number.The computational
basisof the system is denoted by $\ket{i_{1},i_{2},\dots,i_{2n}}$,where
$i_{j}=0,1$ indicates the state of the $j$-th qubit.A _monitored random
quantum circuit with measurement rate $p\in[0,1]$_is a quantum circuit with
staggered layers of two-qubitgates on nearest neighbors, or the brick-wall
architecture, in which each qubit has a probability $p$ at each time stepto be
measured in its computational basis and be projected into the resulting
outcome[Fig. 1(a)].It is defined as

$V^{M}(t):=\prod_{\tau=1}^{t/2}M(2\tau)U^{(e)}(2\tau)M(2\tau-1)U^{(o)}(2\tau-1),$
(1)

where

$\displaystyle U^{(o)}(2\tau-1)$
$\displaystyle:=\prod_{i=1}^{\frac{n}{2}}U_{2i-1,2i}(2\tau-1),$ (2)
$\displaystyle U^{(e)}(2\tau)$
$\displaystyle:=\prod_{i=1}^{\frac{n}{2}-1}U_{2i,2i+1}(2\tau),$ (3)
$\displaystyle M(\tau)$ $\displaystyle:=\prod_{i=1}^{n}M_{i}(\tau).$ (4)

Here, $t$ is an even number, $U_{i,j}(\tau)$ is a Haar-random unitary
gateacting on qubits $i$ and $j$ at time $\tau$, and
$M_{i}(\tau)\in\\{\sqrt{1-p}I_{i},\sqrt{p}\outerproduct{0}{0}_{i},\sqrt{p}\outerproduct{1}{1}_{i}\\}$.The
latter are Kraus operators of the channel that implements a measurement in the
computationalbasis with probability $p$.We say that the qubit $i$ is
_measured_ at time $\tau$ if $M_{i}(\tau)$is either
$\sqrt{p}\outerproduct{0}{0}_{i}$ or $\sqrt{p}\outerproduct{1}{1}_{i}$. The
_measurement configuration_ $M:=\\{M_{i}(\tau)\\}_{i,\tau}$, is the collection
of allmeasurement outcomes at each space-time point of the circuit.By
construction, $M$ contains all the information about the layout of thecircuit,
including $n$ and $t$, along with which qubits were measured at which time,and
what the projective measurement outcomes were.Note that the time evolution
operator $V^{M}(t)$ inEq. (1) is _not_ unitary, i.e.,

$V^{M}(t)^{\dagger}\neq V^{M}(t)^{-1},$ (5)

except in the situation when the measurement rate $p$ is exactly zero.That
$V^{M}(t)$ is not unitary corresponds to the fact that we measure the system
and condition theevolution on the measurement outcomes specified by $M$.Our
results concern the output of a monitored quantum circuit when it is
appliedonto the initial state vector $\ket{0^{n}}$.The state vector
$V^{M}(t)\ket{0^{n}}$ represents the unnormalizedoutput of the monitored
quantum circuit, projected according to the measurement configuration $M$.Its
squared norm $\expectationvalue{V^{M}(t)^{\dagger}V^{M}(t)}{0^{n}}$ isthe
probability that a measurement configuration $M$ is observedfor fixed choices
of gates $U_{i,j}(\tau)$. Our results concern the complexity of the
normalizedoutput quantum state vector

$\displaystyle\ket{\phi^{M}}:=\frac{V^{M}(t)\ket{0^{n}}}{\lVert
V^{M}(t)\ket{0^{n}}\rVert}\ .$ (6)

This state is the output of the monitored quantum circuit afterconditioning on
themeasurement outcomes $M$.

###  II.2 State complexity

The complexity of a quantum state vector $\ket{\psi}$ refers to the minimal
number of elementary operations,such as two-qubit gates,that need to be
composed in order to prepare $\ket{\psi}$ starting from the referencestate
vector $\ket{0^{n}}$.The complexity of a state is ordinarily defined by
considering two-qubit unitary gates as the elementaryoperations. We call this
complexity measure the _$C$ -complexity_:

######  Definition 1 (Exact $C$ state complexity).

The _$C$ state complexity_ of a normalized state vector $\ket{\psi}$ is the
minimal number oftwo-qubit gates required to prepare $\ket{\psi}$ from the
state vector $\ket{0^{n}}$. The gates can be any elementsof $SU(4)$ and the
circuit may have any chosen connectivity.

We also consider a stronger notion of complexity in which the
elementaryoperations also include measurements with post-selection [67].A
post-selected circuit is defined as a quantum circuit consisting of two-qubit
unitary gates and single-qubit measurements in the computational basis where
the measurement outcomes are post-selected to the desired measurement
outcomes, for example, $0$ for all outcomes.At any time in a post-selected
circuit, arbitrary qubits, for instance the $i$-th qubit,of a state vector
$\ket{\psi}$ can be measured in the computational basis and be post-selectedto
the desired measurement outcome $0$, resulting in the
state$({\lVert\bra{0}_{i}\ket{\psi}\rVert})^{-1}{\outerproduct{0}{0}_{i}\ket{\psi}}$.The
exact state complexity $C$ with post-selected circuits is defined as follows:

######  Definition 2 (Exact $C_{m}$ state complexity).

For a state vector $\ket{\psi}$with $0<\innerproduct{\psi}{\psi}\leq 1$,the
exact $C_{m}$ state complexity $C_{m}(\ket{\psi})$ is the minimal number of
two-qubit gates in an arbitrary post-selected circuit that prepares
$({\lVert\ket{\psi}\rVert})^{-1}\ket{\psi}$ from the initial state vector
$\ket{0^{n}}$. The post-selected circuit consists of two-qubit unitary gates
with arbitrary connectivity and where an arbitrary number of single-
qubitcomputational basis measurements can be applied, with post-selection on a
desired outcome, atany space-time points of the circuit.

The set of post-selected quantum circuits includes unitary circuits as a
special case,implying thatthe measure of complexity $C_{m}$ is a lower bound
on the usual state complexity $C$.

###  II.3 Accessible dimension

The _accessible dimension_ [6] has been defined as the dimension ofthe set of
all possible unitary circuits that can be achieved with a fixed circuit
layout, byvarying the individual choices of the gates in that circuit.Here, we
adapt this definition to our setting, and show that it serves lower-bounds,
analogously to the proof in Ref. [6], on the $C$\- and $C_{m}$\- complexity of
a monitored random circuit below the critical measurement probability.For a
monitored random circuit with a fixed measurement configuration $M$, we define
the _contraction map_ from a collection of two-qubit unitary gates to the
output state as

$\displaystyle F^{M}:[\textrm{SU}(4)]^{\times R}\xrightarrow{}B_{1}^{2\times
2^{n}}\subset\mathbb{C}^{2^{n}},$ (7) $\displaystyle
F^{M}(U_{1},U_{2},\dots,U_{R})=V^{M}(t)\ket{0^{n}},$ (8)

where $B_{1}^{2\times 2^{n}}$ is the real unit ball with the center at the
origin, where$R$ is the total number of two-qubit unitary gatesin the
monitored random circuit specified through $M$,and where each two-qubit
unitary gate in Eq. (1)is set to the corresponding unitary $U_{j}$.That the
image of $F^{M}$ includes sub-normalized $n$-qubit states is a consequenceof
$V^{M}(t)$ not being unitary.We denote the image of $F^{M}$ by
$\mathcal{S}^{M}$, that is, the set of all outputstates generated by the
monitored random quantum circuit with $M$.(See additional technical details in
Appendix A.)We define the _rank_ of $F^{M}$ as the number of independent
degrees of freedom required tospecify a perturbation of the image of $F^{M}$
when we perturb the gates $\\{U_{1},\ldots U_{R}\\}$.More specifically,the
rank of $F^{M}$ at a point $\\{U_{1},U_{2},\dots,U_{R}\\}$,denoted by
$\rank_{U_{1},\ldots,U_{R}}(F^{M})$, is defined by the dimension of the real
linear space spanned by the set of output state vectors

$\displaystyle\\{F^{M}(U_{1},\dots,(\alpha\otimes\beta)U_{j},\dots,U_{R})\\}_{j,\alpha,\beta},$
(9)

where $j\in\\{1,2,\dots,R\\}$ and $\alpha$, $\beta$ $\in\\{I,X,Y,Z\\}$ are
Pauli operatorssuch that $(\alpha,\beta)\neq(I,I)$.We then define the
_accessible dimension_ as the maximal rank of $F^{M}$ over all unitary gates:

######  Definition 3 (Accessible dimension).

For a monitored random quantum circuit with a measurement configuration $M$,
the accessible dimension $d_{M}$ is the maximal rank of $F^{M}$ over all two-
qubit unitary gates $\\{U_{1},U_{2},\dots,U_{R}\\}$, where
$U_{j}\in\textrm{SU}(4)$.

A strategy to lower bound the accessible dimension $d_{M}$ is to lower bound
the rank of $F^{M}$ atany chosen point $\\{U_{1},\ldots U_{R}\\}$.The
accessible dimension $d_{M}$ is also the dimension of the set$\mathcal{S}^{M}$
(see Appendix A).We prove that the complexity measure $C_{m}$ is lower bounded
in terms of $d_{M}$, which is analogous to the proof in Ref. [6].

######  Lemma 4 (Complexity by dimension).

Let $\ket{\psi}\in\mathcal{S}^{M}$be distributed according to the output of a
monitored random quantum circuitwith a fixed measurement configuration $M$,in
which all unitary gates are chosen at randomfrom the Haar measure.
Then$C_{m}(\ket{\psi})\geq({d_{M}}-3n-2)/13$ with unit probability.

The above lemma serves in our proof to reduce the problem of findinga lower
bound on $C_{m}$ for a monitored random quantum circuit to finding a lower
bound on $d_{M}$.

##  III Main result: Complexity phase transition in monitored random quantum
circuits

We prove that both of the $C$\- and $C_{m}$-complexity of the output state of
a monitored random quantum circuit exhibita phase transition at a critical
measurement probability $p_{c}=0.5$.

######  Theorem 5 (Complexity growth in monitored circuits).

Let $\ket{\psi}$ be the output state vector of the monitored random circuit
with measurement rate $p$, conditioned on the outcomes of the measurement that
were applied in the monitored circuit.If $p<p_{c}$, $C(\ket{\psi})$ and
$C_{m}(\ket{\psi})$ grow at least linearly and linearly in $t$, respectively,
until they saturate to values $e^{\Omega(n)}$,with probability
$1-e^{-\Omega(n)}$.If $p>p_{c}$, and for any $0<\epsilon<1$,we have
$C(\ket{\psi})\leq\operatorname{poly}(n/\epsilon)$ and $C_{m}(\ket{\psi})\leq
O\bigl{(}n\log(n/\epsilon)\bigr{)}$ exceptwith probability at most $\epsilon$.

Our bounds on both complexities do not depend on the specific measurement
outcomes $M$,even though the output state vector $\ket{\psi}$ is conditioned
on $M$.Our proof exploits techniques from percolation theory [66]to prove a
sharp transition between these two regimes at the critical measurement rate
$p_{c}=0.5$.Above this rate, measurements percolate across the width of the
circuit,periodically resetting the state’s complexity.This implies the upper
bound of the complexity by $\operatorname{poly}(n)$.Below the critical rate,
it turns out multiple paths without any measurementscan percolate along the
length of the circuit,supporting a computation whose complexity grows linearly
in time untiltimes exponential in $n$.The growth of $C(\ket{\psi})$ in the
regime $p<p_{c}$ follows from the general bound$C_{m}(\ket{\psi})\leq
C(\ket{\psi})$.Our core technical result is a lower bound on the accessible
dimensionof a monitored random quantum circuit in the regime $p<p_{c}$ By
Lemma 4, this bound immediatelytranslates into a corresponding bound on the
$C_{m}$-complexity.

######  Lemma 6 (Growth of the accessible dimension in monitored circuits).

If $p<p_{c}$, $d_{M}$ grows linearly in $t$ until an exponential time
$t=e^{\Omega(n)}$ with probability $1-e^{-\Omega(n)}$.

We now provide a sketch of the proof of Lemma 6. Twoseparate arguments are
developed in the regimes $p>p_{c}$ and $p<p_{c}$.In the regime $p>p_{c}=1/2$,
percolation theory states that measurements will regularlypercolate throughout
the width of the circuit, resetting the state vector to $\ket{0^{n}}$
alongthose paths (Fig. 3(a)). Such measurement percolation occurs within the
last $n$ layers of gates inthe monitored circuit with probability
$1-e^{-\Omega(n)}$, meaning thatthe set of output statesof the circuit cannot
havethe $C_{m}$-complexity cannot exceed $O(n^{2})$.The argument can be
further reinforced to upper-bound $C$-complexity by$\operatorname{poly}(n)$,
and to bound the $C$ and $C_{m}$ complexity measuresin the case where the
toleratedfailure probability is arbitrary.In the regime $p<p_{c}=1/2$, we
lower-bound the accessible dimension as follows.We first show that for a fixed
configuration of measurements $M$,there are paths without any measurements
that percolate throughout the length of thecircuit.We call such paths
_measurement-free paths_. Then we show that these paths can be used to run an
exponentially long quantumcomputation.The main challenge is to construct an
embedding of an arbitrary quantumcircuit on $\Omega(n)$ qubits and of depth
$\Omega(t)$into the monitored random quantum circuit with a fixedconfiguration
of measurements $M$.The main idea of the embedding is to associateone qubit of
the $\Omega(n)$ sized circuit to a measurement-free path, and tochoose the
gates of the monitored random circuit so that theyensure the qubit’s
information is carried along the measurement-free path andthat they implement
the gates of the $\Omega(n)$ sized circuit on those qubits.There are two
specific challengesthat one faces when constructing this embedding:One must
show that (a) the computation can proceed even if a measurement-free pathis
not _causal_ , i.e., if it momentarily wraps back in time by following
legsbetween gates in a direction opposite to the circuit’s time direction,
and(b) two-qubit gates can be implemented between two such paths (Fig.
3(b)).Challenge (a) is addressed as follows. If a measurement-free path
follows a leg ofa unitary gate in a direction contrary to the circuit’s
forward time direction,then we can exploit the existence of ameasurement
immediately after that gate to teleport the qubit being carriedby the path
further along the path, even if the information is carriedbackwards with
respect to the circuit’s direction. This is possible because themeasurement
configuration $M$ is fixed, meaning that the measurement immediately afterthe
gate has a predetermined outcome onto which the state is projected.To address
challenge (b), we exploit the fact that paths with no measurementsalso
percolate vertically across the width of the circuit; these paths can be used
toimplement a CNOT gate across two measurement-free paths using a
teleportation-based scheme.Both arguments addressing challenges (a) and (b)
rely on the existence of measurements oncertain qubits that are neighboring
the measurement-free path. Yet such measurementsmight not always exist at the
desired locations.We prove that for any measurement configuration $M$, one can
always select additionalqubits to be measured without increasing the
accessible dimensionof the monitored random circuit.Therefore, should a
measurement at a given location be required by ourembedding scheme, it can
always be added if necessarywhile still yielding a lower bound on the
accessible dimension of the monitoredcircuit in the original measurement
configuration.We believe that the following lemma might be of independent
interest, as it providesa rigorous quantitative statement about the
impossibility of measurements to increasea quantity, the accessible dimension,
which is a proxy quantity for complexityfor monitored random circuits.

######  Lemma 7 (Measurements cannot increase the accessible dimension).

Let $M$ be a measurement configuration, and let $M^{\prime}$ be a
configuration obtained by changing some space-time locationsin $M$ from being
unmeasured to being measured.Then $d_{M^{\prime}}\leq d_{M}$.

Intuitively, the dimension of the set of states generated by a random
monitoredcircuit for a given measurement configuration cannot increase if one
inserts an additionalprojector in the circuit.We present a proof of this
statementas Lemma 16 inAppendix B.

Figure 2: A mapping from the bond structure of a monitored random circuit to a
percolation model. Each measured and unmeasured bond is mapped to closed (with
scissors) and open edge (without scissors), respectively.

##  IV Proof of the main result

In this section, we prove Theorem 5.A central ingredient of our proof is the
use of techniques from percolation theory. We brieflyreview these techniques
in Section IV.1.We then apply these techniques in Section IV.2to obtain an
upper bound on the $C$ complexity in the regime $p>p_{c}$.Finally, we complete
the proof of Theorem 5 inSection IV.3by proving a lower bound on the $C$
complexity in the regime $p<p_{c}$.

###  IV.1 Percolation theory

In percolation theory, we consider a graph whose edges can be in one of two
states, open or closed,where the state of each edge is chosen to be open or
closedindependently with probability $q$ and $1-q$, respectively [66].Bond
percolation theory is concerned with the existence or absence of a
pathconsisting of connected open edges in the graph. A well-studied setting is
the existence of a path that crosses from left to right in a $L\times L$
square latticewhile passing only through open edges.In the large $L$ limit,
there is a critical probability $q_{c}$ below which there does not exist a
left-right crossing with the probability $1-e^{-\Omega(L)}$, but above which
such crossings appear with probability $1-e^{-\Omega(L)}$.Moreover, for a
square lattice in two spatial dimensions,the critical probability is
$q_{c}=1/2$. We refer to Appendix D for a more in-depth review of percolation
theory,including percolation on rectangular lattices.Our application of
percolation theory follows similar techniques used to computethe Rényi-0
entropy in Ref. [46].In order to formally apply techniques from percolation
theory to monitoredrandom quantum circuits, wemap a monitored random circuit
to a graph with edges that are randomly open or closed.We define a graph by
mapping each two-qubit unitary gate and its unmeasured bonds to a vertex and
the open edges incident with it, respectively (Fig. 2).With this mapping, the
measurement rate $p$ is equal to the probability of closing an edge
$1-q$.Moreover, percolation results for the square lattice extend naturally to
the diagonally tilted square latticeas in Fig. 2, given that percolations from
the left to the right of thetilted lattice can be constructed from left-right
and top-bottom percolations on the original, untiltedlattice (cf. Appendix D).

Figure 3: Monitored random circuits above and below the critical measurement
probability. (a)Above the threshold, pathsof measurements cut across the
circuit from top to bottom. Their effect is to resetthe state along the path
to a product state, whose complexity vanishes.The region delimited by the red
broken line is an example of an _open cluster_.(b) Below the threshold, a
linear number of measurement-free paths cross from the beginningto the end of
the circuit. These paths can be used to embed a unitary circuit into the
monitored circuit.A bridge (black line) is a vertical path of open edgesused
to implement two-qubit gates in theembedded unitary circuit.

###  IV.2 The uncomplex phase

As a warm-up and to build additional intuition with the proof techniques we
use,we first provide a simple upper bound on the $C_{m}$-complexity in the
regime $p>p_{c}$:Consider a circuit of depth $t>n$, and consider the last $n$
layers of that circuit.Our strategy is to use percolation theory to conclude
that there exist measurements that cut through thewidth of the circuit in
those last $n$ layers, resetting the state vector to $\ket{0^{n}}$ at the
location of thosemeasurements [Fig. 3 (a)].We apply percolation theory to the
dual lattice of the percolation model introducedin Fig. 2, depicted in Fig. 3
(a).For $p>p_{c}$, percolation theory states that with probability
$1-e^{-\Omega(n)}$ there existpaths of measurements in the dual lattice that
connect the top of the circuit with the bottom side of the circuit. For such a
path, there is no unmeasured bond connecting the gates on the left side of the
path to the gates on the right side of the path. (Thisproperty would not have
been guaranteed had we applied percolation theory directlyto the graph in Fig.
2 rather than to its dual lattice.)The measurements therefore reset the state
vector along the path to $\ket{0^{n}}$.Since there are at most $O(n^{2})$
gates after this path, both the accessible dimension $d_{M}$ as well as the
output state complexity $C(\ket{\psi})$ cannot exceed $O(n^{2})$.Therefore, if
$p>p_{c}$, then $C_{m}\leq O(n^{2})$ except with probability
$e^{-\Omega(n)}$.We now present our the part of the proof of Theorem 5
pertainingto the uncomplex phase.Our proof proceeds byupper bounding the size
of regions consisting of connected open edges,or _open clusters_ , on the
graph in Fig. 2.Open clusters correspond toconnected bonds of gates in the
circuit which are not measured (inside the broken line in Fig. 3 a).The output
state only depends on the unitary gates whose bonds are in the openclusters
and contain the boundary at the final time. Indeed, single-qubit measurements
at the boundaryof the open clusters reset each qubit to $\ket{0}$.There are no
more than$n/2$ open clusters containing the bonds at the final time.We now
upper bound the size of such open clusters by $O(\log(n))$.Let
$\\{C_{i}\\}_{1}^{m}$, where $m\leq n/2$, be the set of the distinct open
clusters containing the bonds at the final time and $|C_{i}|$ be the number of
edges, or bonds, in
$C_{i},i\in\\{1,2,{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\dots},m\\}$.
Then, the following lemma holds.

######  Lemma 8 (Small unmeasured regions).

Assume $p>p_{c}$. For any $0<\epsilon<1$, it holds:

$\displaystyle|C_{i}|=O\left(\log\left(\frac{n}{\epsilon}\right)\right),$ (10)

for all
$i\in\\{1,2,{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\dots},m\\}$,
with probability $1-\epsilon$.

We give a proof of the above lemma inAppendix D.2 (stated thereas Lemma
19).Because of Lemma 8, the output state is generated by a
$O(\log(n/\epsilon))$-depth post-selected quantum circuit, implying
that$C_{m}\leq O(n\log(n/\epsilon))$ with probability $1-\epsilon$.Moreover,
it indicates that the Schmidt rank of the output state in any bi-partition is
$\operatorname{poly}(n/\epsilon)$, implying that the output state can be
efficiently represented by a _matrix product state_(MPS) [68], and therefore
it is prepared by a unitary circuits with $\operatorname{poly}(n)$ complexity
[69, 70].Overall, for the output state vector $\ket{\psi}$, our argument gives
upper bounds$C(\ket{\psi})\leq\operatorname{poly}(n/\epsilon)$.This proof also
recovers the upper bound for $C_{m}$ obtained in our initial
percolationargument (cf. warm-up proof above) when $\epsilon$ is chosen
exponentially small.Plugging $\epsilon=e^{-cn}$ for fixed $c>0$ yields the
upper bound$C_{m}\leq O(n\log(n)+cn^{2})=O(n^{2})$.

###  IV.3 The complex phase

The $C$-complex phase refers to the phase in which the $C$ complexitygrows at
least linearly until saturating to a value $e^{\Omega(n)}$. We show that this
phaseoccurs in monitored random circuits whenever $p<p_{c}$.Our proof proceeds
as follows. For a fixed measurement configuration $M$,the goal is to prove a
lower bound on the accessible dimension $d_{M}$ in orderto apply Lemma 4.The
strategy to lower bound $d_{M}$ is to show that, for some $m=\Omega(t)$, it
ispossible to embed any depth-$m$ unitary circuit with arbitrary single-
qubitgates and CNOT gates into a set of paths along the monitored quantum
circuitthat avoid measurements. We then show that the accessible dimension of
such unitarycircuits grows linearly in $m$, thereby showing that
$d_{M}=\Omega(m)$.The bulk of this section is concerned with constructing such
an embedding.When $p<p_{c}$, there are $\Omega(n)$ measurement-free paths even
forexponentially long monitored random quantum circuits:

######  Lemma 9 (Existence of measurement-free paths).

If $p<p_{c}$, there exist $\Omega(n)$ disjoint measurement-free paths
thatpercolate throughout the length of the circuit in time $e^{\Omega(n)}$,
with probability $1-e^{-\Omega(n)}$.

We give a proof of Lemma 9 inAppendix D.1.2 (stated asLemma 18).Without loss
of generality, we can assume that all measurement outcomes in the monitored
circuitare $0$ without changing the accessible dimension associated with the
measurement configuration $M$.Indeed, the gates are chosen at random from the
unitarily invariant Haar measure on $SU(4)$;thus, for any measurement outcome
$1$, we can map the setting to an equivalent onewhere the measurement is $0$
and where additional $X$ gates are applied immediately beforeand immediately
after that measurement.We now seek to construct an embedding of a quantum
unitary circuit of $\Omega(n)$ qubits into themonitored random quantum
circuit, where each measurement-free path carries one qubit ofthe unitary
circuit.We first construct this embedding in a simpler situation with some
additionalconvenient assumptions. We then present the embedding in the general
case, liftingall the simplifying assumptions.Let us assume thatall
measurement-free paths always traverse gates from an input leg ofthe gate to
an output leg of the gate.Following such measurement-free paths, one does not
goback in the time direction, and we say the paths are _causal_.Each path is
assigned to carry one qubit while avoiding measurements.We apply the
identitygate or the SWAP gate so that the qubit state follows the legs of the
path (Eq. (11)).In this way, qubit states are transferred along the
measurement-free paths without being measured.We can apply an arbitrary
single-qubit gate to the qubit by multiplying a single-qubit gate to
theidentity gate or the SWAP gate.Let us furthermore assumethat nearest
neighbour paths meet at some points, that is, nearest neighbourpaths include
the legs of the same unitary gates, and the number of the unitary gates is
$\Omega(t)$ for each path.At the point two paths meet, we can apply a CNOT
gate, which results in performing a CNOT gateon the two qubits carried by
thenearest neighbour paths.The two-qubit gates which are outside the
measurement-free paths are chosen to be identity gates.The case described
above is graphically exemplified as

$\includegraphics[width=199.16928pt]{embedding_simple.png}.$ (11)

Here, there are three such paths, i.e., it simulates a unitary circuit with
three qubits, and weapply the suitable two-qubit gate along the paths and at
the points they meet, for example weapplied $I$, SWAP, CNOT in the broken
circles as shown.Single-qubit gates can be multiplied into these two-qubit
gates to enable universalcomputation in the embedded unitary circuit.In the
above setting, the output states at the end of measurement-free paths is equal
toa state generated by a depth-$\Omega(t)$ unitary circuit consisting of
single-qubit gates andCNOT gates with the brick-wall architecture.Because
arbitrary single-qubit gates and CNOT gates form a universal gate set [71],we
can embed a universal unitary circuit into a monitored circuit with such a
measurement configuration $M$.Let $S^{0}$ be the set of the output states of a
random unitary circuit with the brick-wall architecture and two-qubit random
unitary gates

$\displaystyle U=\left(u_{1}\otimes v_{1}\right)W\left(u_{2}\otimes
v_{2}\right),$ (12)

where $u_{1,2}$, $v_{1,2}$ are Haar random single-qubit gates and $W$ is
chosen from {$I$, CNOT} uniformly randomly.We denote by $d_{0}$ the accessible
dimension of $S^{0}$, where the accessible dimension of the randomunitary
circuit is defined as per Definition 3 with a measurement configuration that
containsno measurements and with single-qubit perturbations:
$(\alpha,\beta)=(I,\sigma),(\sigma,I)$ for $\sigma\in\\{X,Y,Z\\}$ in Eq.
(9).The reason for the restriction of the perturbations to single-qubit gates
is because only single-qubit gates in Eq. (12) are parametrized continuously
and can be, therefore, perturbed.Then, because the perturbed output states of
the random unitary circuit are equal to some perturbed output states of the
monitored random circuit in Eq. (9)with $M$ simulating the random unitary
circuit,up to real scalar factors, we obtain the inequality

$\displaystyle d_{M}\geq d_{0}.$ (13)

Then, we use an argument following Ref. [6] to lower bound $d_{0}$. We specify
the depth of the unitary circuit by $d_{0}(t)$, which is $d_{0}$ of depth-$t$
random unitary circuits defined above. Then we prove the following lemma.

######  Lemma 10 (Lower bound on $d_{0}$).

Let $t\geq 0$ be an integer. Then, $d_{0}$ grows linearly in depth as

$\displaystyle d_{0}(t)\geq\left\lfloor\frac{2t}{3n}\right\rfloor,$ (14)

until it saturates in a depth exponential in $n$.

We give a proof of Lemma 10 in Appendix A (stated as Lemma 15).Moreover, with
Lemma 4, it implies that $C_{m}(\ket{\psi})$ and $C(\ket{\psi})$, where
$\ket{\psi}$ is an output state vector of monitored random circuits with the
above measurement configurations,also grows linearly and at least linearly in
$t$, respectively, until saturating to a value $e^{\Omega(n)}$.What is left to
be shown is that a unitary circuit can be embedded to a monitored circuit with
the general conditions, such that measurement-free paths are not always
causal, and they do not meet at some space-time points.First, we generalize
the embedding to the case where measurement-free paths are not causal,that is,
the paths include the legs of two inputs or two outputs of a two-qubit unitary
gate.For now, we assume that there are measurements at the points where the
path changes the timedirection (the broken circles in Eq. (15)).(We discuss
below how to remove this assumption usingLemma 7.)In this case, the path is
graphically shown as

$\includegraphics[width=199.16928pt]{measurement_free.png},$ (15)

where we marked with broken circles at which the path changes the time
direction. Still, the qubit state can be protected from the measurements by
using a scheme similar to the entanglement teleportation. To see this, we need
the following simple equality: If we choose the two-qubit gate as
$U=\textrm{CNOT}(H\otimes I)$, then we have

$\includegraphics[width=227.62204pt]{teleportation_3.png},$ (16)

where we have omitted the constant factor in the last equality, which is not
important for our proof.Here, we can interpret it as the measurement in the
Ball basis, with a post-selection on the outcome.With Eq. (16) in mind, we fix
the unitary gate at which the path changesdirection to go backwards in time
(the bottom broken circle in Eq. (15))so that the qubit state is measured in
the Bell basis.We also fix the unitary gate at which the path changesdirection
to go forwards again in time (the top broken circle in Eq. (15)) so thata Bell
state is prepared.The qubit state can therefore be transferred along the
path,i.e., the input state of the measurement-free path is equal to its
output. Next, we discuss how to apply a CNOT gate between two nearest-
neighbour paths which do not share a unitary gate, and give a lower-bound on
the number of CNOT gates that can be performed.Here, we make use of
measurement-free paths which percolate through the width of the circuit, i.e.,
from the top to the bottom.To perform a CNOT gate, we are only interested in a
segment of the top-bottom measurement-free paths between the two paths
carrying the quantum state, and we call such segment _bridge_. They are
graphically exemplified as

$\includegraphics[width=241.84842pt]{Make_bridge.png},$ (17)

where the red lines are the paths carrying two-qubit state.For now, we assume
again that there are measurement at the followingdesired locations: (1) the
legs of the unitary gates at which the top-bottom pathschange direction in
time (analogous to the broken circles in Eq. (15))and (2) the fourth legof the
unitary gates at the intersection of the horizontal measurement-free paths
andthe top-bottom measurement-free path(the broken circles in Eq. (17)).If we
fine tune the unitary gates along the bridge,we can perform a CNOT gate
between nearest-neighbour measurement-free paths.Specifically,we choose the
unitary gates along a bridgesuch that the bridge protects a qubit statefrom
being measured as with the unitary gates in the measurement-free paths,using a
SWAP gate or an identity gate if the bridge traverses the gate from an input
legto an output leg, or the scheme in Eq. (16) if the bridge traversesthe gate
through two input legs or through two output legs.Also, for two unitary gates
at the edge of the bridge (the broken circles in Eq. (17)),we choose them as
CNOT and $\textrm{CNOT}(I\otimes H)$ or $(I\otimes H)\textrm{CNOT}$,possibly
multiplied by SWAP if required to ensure the qubit continues to be transferred
alongthe horizontal measurement-free path. The target qubit of CNOT and the
order of $I\otimes H$ and CNOT depend on the locations of legs belonging to
the bridge and the path at the edge of the bridge, i.e., the shape of the path
and the bridge in the broken circles in Eq. (17).In the example in Eq. (17),
CNOT is performed as

$\includegraphics[width=241.84842pt]{Bridge_CNOT.png},$ (18)

where we chose the unitary gates along measurement-free paths and inside the
bridge as the specificones so that they carry qubit states, we apply
$(I\otimes H)\textrm{CNOT}$ and CNOTat the edge of the bridge, and we omit the
constant factor in the last equality.Other bridge configurations, such as if
the bridge is attached on both ends toinput legs of unitary gates on the
horizontal measurement-free paths, can betreated similarly (cf. Appendix
C).For every of the $n$ time steps,that is every of the squares of the
monitored circuit from $(i+1)$-th time step to $(i+n)$-th time step, where $i$
is a multiple of $n$,there are $O(n)$ top-bottom measurement-free paths with
probability $1-e^{-\Omega(n)}$ (Fact 3 in Appendix D) until an exponential
number of time steps in $n$.Then, we can apply $\Omega(t)$ layers of CNOT
gates with the brick-wall architecture using the bridges made by the top-
bottom paths.We can therefore embed any depth-$m$ unitary circuit, where
$m=\Omega(t)$, with arbitrary single-qubitgates and CNOT gates into a
monitored circuit with such measurement configuration.In the discussion above,
we have assumed that there are measurements at certain desired locations:
around the points where the measurement-free paths and the bridges change
direction in time, and on the fourth leg of each junction of the paths and the
bridges.Below, we show how a lower-bound on the accessible dimension is
obtained without the measurements at the desired locations.We consider a
measurement configuration $M$ which does not include measurements at such
locations.Then, we set up another configuration $M^{\prime}$ by adding
measurements to $M$ at the desired locations.Here, by adding measurements, we
mean that $M^{\prime}$ is made by changing some $\sqrt{1-p}I$ in $M$ to
projections $\sqrt{p}\outerproduct{0}{0}$ or
$\sqrt{p}\outerproduct{1}{1}$.Because we have assumed that the measurement
outcomes are all $0$, we replace $\sqrt{1-p}I$ by
$\sqrt{p}\outerproduct{0}{0}$.For example, we add measurements to the points
which a measurement-free path changes the time direction as

$\includegraphics[width=241.84842pt]{before_after_adding.png}.$ (19)

Then, using Eq. (16) again, a qubit state can be transferred along the path
with the measurement configuration $M^{\prime}$ in Eq. (19).A key lemma to
lower-bound $d_{M}$ by considering $M^{\prime}$ is that the accessible
dimensioncannot increase by adding measurement (Lemma 7):If $M^{\prime}$ is
made up by adding measurements to $M$, then $d_{M^{\prime}}\leq
d_{M}$.Therefore, a lower-bound on $d_{M^{\prime}}$ immediately implies one on
$d_{M}$.However, adding measurements to qubits neighboring a measurement-free
path mightinadvertently break another measurement-free path in the
circuit.Such a situation can occur if a measurement-free path shares a unitary
gate with anearest-neighbour path at which it changes direction in time.Still,
the number of measurement-free paths that survive after adding the required
measurementsremains $\Omega(n)$because we can pick up at least half of the
paths in $M$ such that any pair of two pathsdo not share the same unitary
gates.In summary,a depth-$t$ monitored circuit with $M^{\prime}$, where
measurement are added at the desired locations, can simulate a
depth-$\Omega(t)$ unitary circuit, which implies that
$d_{M^{\prime}}=\Omega(t)$.This lower-bound holds until an exponential time in
$n$, because linear number of measurement-free paths in $n$ and linear number
of bridges in $t$ exist until then with probability $1-e^{-\Omega(n)}$Then,
because $d_{M^{\prime}}$ lower-bounds $d_{M}$, we obtain $d_{M}=\Omega(t)$,
which means that the accessible dimension of a monitored circuit with
measurement rate $p<p_{c}$ grows linearly in $t$ until a time $e^{\Omega(n)}$.

##  V Conclusion and discussion

Our work combines techniques from quantum complexity and monitored quantum
circuits toshow that the quantum complexity of a state —akin to other physical
quantities including the entanglement entropy— undergoes phase transitions in
a many-body system subject to measurements.Our results, therefore, contribute
to reinforcing the interpretationof quantum complexity as a meaningful
physical quantity,given its ability to identify different regimes of behavior
of the evolutionof a quantum many-body system. Indeed, the $C$\- ($C_{m}$-)
complexity undergoes a drastictransition, depending on the rate at which
measurements are applied,between a regime where it saturates quickly and a
regime in which it increasesat least linearly until saturating to a values
exponentially in the number of qubits.Our conclusions follow from rigorous
mathematical arguments which do not rely on anycomplexity-theoretic
assumptions.We expect our results to extend beyond the brick-wall circuit
layout of Fig. 1 to more general circuit architectures. Given any circuit
layout, the percolation properties of the corresponding graph is expected to
determine the complexity phase transition of the corresponding monitored
circuit.Our results are also anticipated to extend beyond the measurement
model considered inour work, where measurements in the computational basis
occur probabilistically. Any schemeinvolving a variant of a weak measurement
of the individual qubits is expected to lead to asimilar complexity phase
transition as in our setting, so as long as the measurements resultinto the
projection of the state onto a post-measurement outcome.The complexity measure
$C_{m}$ we discuss here is defined with respect toa computational model that
naturallyreflects our setting, by accommodating post-selective measurements
alongside unitary gates.A measurement outcome can be post-selected to a
desired one if there is non-zero probability with which we obtain the outcome
without post-selection.Such state transformation with non-zero probability has
been also discussed in the context of the state conversion bystochastic local
operations andclassical communication (SLOCC) [72, 73].Also, this
computational model is more powerful than the computational model without
post-selective measurements [67];the measure of complexity $C_{m}$ is thus a
lower bound on the usual unitary circuit complexity.Our result therefore
indicates that the accessible dimension is a powerful mathematical tool that
can also enable us to prove linear growth of such a stronger notion of
complexity,the $C_{m}$-complexity.Lemma 7 provides additional insight into
theadded computational power offered by measurements in monitored quantum
circuits.It suggests that while the addition of measurements can enhance the
computationalpower of circuits (e.g., to prepare topologically ordered states
[74, 75, 76, 77] usingconstant depth quantum circuits, which is impossible
without measurements)they do not explore a set of operations that is larger
when measuredin terms of accessible dimension. As such,our work offers an
approach to quantify the resourcefulnessof measurements when tasked with
preparing a target state on $n$ qubits.It is natural to consider other
definitions of state complexity, such as someapproximate notion of state
complexity, the _strong complexity_ [5],the _complexity entropy_ [17], and the
_spread complexity_ [78].The strong complexity, loosely defined as the circuit
size required to successfullydistinguish a state from the maximally mixed
state,displays a markedly different behavior than the $C$-complexityin
monitored random circuits. This behavior is due to the strong complexity
beingsensitive to the measurement of even a single qubit.Indeed, for any
measurement rate $p$,the presence of a single measurement on an outputqubit
resets that qubit to the state vector $\ket{0}$, ensuring that the output
state is distinguishablefrom the maximally mixed state. The strong complexity,
therefore, saturates quickly for anymeasurement rate in the large system size
limit.This argument furthermore rules out the possibility of monitored random
quantum circuitsforming a _state $t$-design_ [27](or complex spherical
$t$-design),sinceforming a $t$-design implies reaching a large strong
complexity [5].Moreover, our arguments agree with a recent numerical analysis
indicating the absence of ameasurement-induced phasetransition in monitored
random circuitswhen judged according to the extent themonitored random circuit
approximates a$t$-design;the latterstatement has been judged based on
theresults of an application of amachinelearning algorithm [79]. To make
robust statements about complexity growth, one would need to smooth
thecomplexity measures $C(\ket{\psi})$ and $C_{m}(\ket{\psi})$ by minimizing
thecorresponding complexity measure over all states thatare $\epsilon$-close
to $\ket{\psi}$ in some reasonable metric.Evidence points to a robust version
of quantum complexity indeed growinglinearly in random circuits: arguments
based on $k$-designs prove robust sublineargrowth [5], and variants of this
method yield increasingly better properties towards robustness [80].Proving a
similar robustness property of our results appears challenging. It is
unclear,for instance, whether arguments based on $k$-designs can be adapted to
circuitswith measurements.In fact, there is growing evidence that states
output by a monitoredquantum circuit should have efficient representations
even in some region below $p_{c}$ (in the$C$-complex phase). Indeed, numerical
and analytical results [47]highlight an area law behaviorof the Rényi-$\alpha$
entropies for $\alpha<1$ for$p\gtrsim 0.2\text{--}0.35$,implying that such
states have an efficient representation in terms of MPS [68, 81].In this
regime, a robust definition of state complexity would not exceed
$\operatorname{poly}(n)$.It remains an open problem to establish the size of
the gap between robust andexact complexity measures in this regime, as well as
to determine the precise thresholdat which a robust definition of complexity
grows linearly until exponential times.Any region with $p<p_{c}$ where the
monitored circuit’s output state would neverthelessobey an area law would
provide more concrete examples of states that are naturallydescribed by a
circuit but which have shortcuts.Finding shorter circuits that implement a
given circuit is usually hard. Theregime $p<p_{c}$ is also one where we might
not expect measurements to percolate across the circuit,possibly ruling out
the obvious shortcut that corresponds to the original monitored circuitsimply
resetting the state to a product state at some point during its evolution.This
behavior contrasts starkly with random circuits without measurements, where
suchshortcuts are not expected to occur with any significantprobability [13,
5, 80].We discuss briefly the implication of our result onthe AdS/CFT
correspondence in the context of holography.The “complexity=volume conjecture”
[12] suggeststhat the complexity of a CFT state corresponds to the volume of a
wormholein the dual AdS space.Under the assumption that a random circuit can
be regarded as a reasonable proxy to studyquantum chaotic CFT dynamics, one
mayargue that monitored randomcircuits can be seen as proxies of CFT dynamics
with localmeasurements [82, 83, 84].Therefore, in a simplified model where the
CFT dynamicsis represented by a random circuitwith measurements,our results
suggest that the volume of a wormhole in the AdS space alsoundergoes a phase
transition by changing the holographic dual of the measurement rate.This work
invites a number of future research directions.First, it would be interesting
to study the critical behaviour of the accessibledimension in the monitored
circuit in the vicinity of the critical point.It would then be interesting to
investigate if the critical exponent of the accessible dimensionagrees with
that of entanglement entropy [46].Second, one could give a better lower-bound
of the $C$-complexity in the complex phase.The post-selected measurements can
increase the computational power of quantumcomputers [67].Similarly, we might
expect that measurementscould increase the state complexity, which might grow
faster than linearly in time.Recently, it has been shown inRef. [85] that the
entanglement velocity—referring to the velocity at whicha pair of well-
separated regions can become entangled intime—in a monitored circuitbelow a
critical measurement ratewith the maximally mixed initial state is larger than
that of unitary circuits.It would be interesting to ask if the state
complexity grows super-linearly as well in monitored circuits at low
measurement rate.Finally, important future directions of research would
address the growth of a robustmeasure of quantum complexity in random
monitored circuits as well as in a monitoredcontinuous-time evolution [60, 61,
62, 63, 64]In particular, recent proof techniques of Ref. [80] basedon the
Fourier analysis of Boolean functions appear promising to address these
objectives. It may also helpto use the analogy of random circuits withthe
evolution under time-fluctuating Hamiltonians[86]to establish a result of this
type: Afterall, thelatter–just like random circuits–give rise toapproximate
unitary designs with high probabilityas time goes on.Overall, our work offers
new insights on monitored quantum circuits, in which unitary dynamics and
measurementsare combined together, through the lens of quantum complexity.

##  VI Acknowledgements

The authors would like to thank Keisuke Fujii and Michael Gullans for useful
discussions on monitored quantum circuits, as well as Tomohiro Yamazaki and
Sumeet Khatri for useful feedback on an earlier version of this manuscript. We
would like to thank the DFG (CRC 183, FOR 2724), the Einstein Foundation
(Einstein Research Unit on Quantum Devices) and the FQXi for support.

##  Appendix A Accessible dimension from algebraic geometry

This section reviews the original definition of the accessible dimension based
on semi-algebraic geometry and the results of Ref. [6] and discusses their
extensions to monitored random quantum circuits in order to establish Lemma
4.The facts from algebraic geometry and differential geometry and lemmashere
follow the corresponding statements in the Appendix of Ref. [6], where there
are more detailed references.A key observation there is that the set of the
all output states $\mathcal{S}^{A}$ forms a semi-algebraic set, and its
“dimension” can bemeaningfully defined and bounded, although it is neither a
vector space nor a manifold.First, we introduce some basic notions of
algebraic geometry.A subset $V\subseteq\mathbb{R}^{m}$ is called an _algebraic
set_ , if for a set of polynomial maps $\\{f_{j}\\}_{j}$,

$V=\\{x\in\mathbb{R}^{m}|f_{j}(x)=0\ \textrm{for all}\ j\\}.$ (20)

Also, we call a subset $W\subseteq\mathbb{R}^{m}$ a _semi-algebraic set_ , if
for sets of polynomial maps $\\{f_{j}\\}_{j}$ and $\\{g_{k}\\}_{k}$,

$W=\\{x\in\mathbb{R}^{m}|f_{j}(x)=0,\ g_{k}(x)\leq 0\ \textrm{for all}\ j\
\textrm{and}\ k\\}.$ (21)

The following observation is an immediate consequence of the _Tarski-
Seidenberg principle_ , which states that for a polynomial map $F$ and a semi-
algebraic set $W$, $F(W)$ is again a semi-algebraic set.

######  Observation 11 (The set of output states issemi-algebraic).

$\mathcal{S}^{M}$ is a semi-algebraic set.

###### Proof.

A set $[\textrm{SU}(4)]^{\times R}$ is an algebraic set, because it is the set
of operators whose matrix elements satisfy polynomial equations equivalent to
$U^{\dagger}U=I$ and ${\rm det}\,U=1$.Besides, the contraction map $F^{M}$ is
a polynomial map, that is, the map to output states is a polynomial function
of matrix elements of $\\{U_{j}\\}_{j=1}^{R}$.Therefore, by the Tarski-
Seidenberg principle, we arrive at the stated observation.∎

In a next step, we introduce a notion of a dimension for a semi-algebraic set.
It originates from the fact that all semi-algebraic sets can be decomposed
into a setof smooth manifolds.

######  Fact 1 (Semi-algebraic sets and smooth manifolds).

For a semi-algebraic set $W$, there exist a set of smooth manifolds
$\\{N_{j}\\}_{j}$ such that $W=\bigcup_{j}N_{j}$.Moreover,
$\max_{j}\\{\dim(N_{j})\\}$ does not depend on the decomposition of $W$.

######  Definition 12 (Dimension of semi-algebraic sets).

For a semi-algebraic set $W$, with decomposition into smooth manifolds
$W=\bigcup_{j}N_{j}$, the dimension of $W$ is defined as
$d:=\max_{j}\\{\dim(N_{j})\\}$.

Using the same argument as in Lemma 1 in Ref. [6], one can show that the above
dimension of $\mathcal{S}^{M}$ is equal to the accessible dimension laid out
in Definition 3.

######  Lemma 13 (Equivalence of two definitions of dimension).

Let $\dim\mathcal{S}^{M}$ be the dimension of the semi-algebraic set
$\mathcal{S}^{M}$, defined by Definition 12.Then $\dim\mathcal{S}^{M}$ is
equal to the accessible dimension $d_{M}$, defined by Definition 3.

Then, we prove Lemma 4.

######  Lemma 14 (Restatement of Lemma 4).

If $d_{M}\geq k$ for an integer $k$, then

$C(\ket{\psi})\geq\frac{1}{11}\left(k-3n-2\right),$ (22)

$\ket{\psi}\in\mathcal{S}^{A}$, with unit probability, that is, for almost all
unitary gates.

###### Proof.

The proof goes similarly to that of Theorem 1 in Ref. [6], and we refer to
that reference for further details. The only difference with the argument
presented there is that the shorter circuit in Ref. [6] becomes a post-
selected quantum circuit and the state vectors in $\mathcal{S}^{M}$ are not
normalized in general. The latter means that unitary gates are realized with
the probability specified by the Born rule
$\expectationvalue{V^{M}(t)^{\dagger}V^{M}(t)}{0^{n}}\prod_{i=1}^{R}d\mu_{\textrm{Haar}}(U_{i})$,
where $d\mu_{\textrm{Haar}}$ is the Haar measure on SU($4$).The strategy is to
show that for $\mathcal{S}^{M}$ with $d_{M}\geq k$, the set of states in
$\mathcal{S}^{M}$ generated by a unitary circuit with $R^{\prime}$ two-qubit
gates, which is less than $(k-n-2)/13$, is measure zero.We explain it in more
detail below.Let $\mathcal{S^{\prime}}$ be the set of the all unnormalized
output state vectors of a short post-selected quantum circuit consisting of
$R^{\prime}$ two-qubit unitary gates with an arbitrary architecture and
measurement configuration.Then, $\mathcal{S^{\prime}}$ is also a semi-
algebraic set.Recall that the accessible dimension of $S^{\prime}$,
$d^{\prime}$, is the number of linearly independent vectors of

$\displaystyle\\{F^{M}(U_{1},\dots,(\alpha\otimes\beta)U_{j},\dots,U_{R})\\}_{j,\alpha,\beta},$
(23)

where $j\in\\{1,2,\dots,R^{\prime}\\}$ and $\alpha$, $\beta$
$\in\\{I,X,Y,Z\\}$ are Pauli operatorssuch that $(\alpha,\beta)\neq(I,I)$.The
number of state vectors in Eq. (23) is at most $15R^{\prime}$, and we find
that $\dim(\mathcal{S^{\prime}})\leq 15R^{\prime}$.We can improve the upper-
bound to $11R^{\prime}+3n$, by considering the contraction of two-qubit gates
$U_{i-1,i}$, acting on qubits $i-1$ and $i$, followed by $U_{i,i+1}$ that
shares a bond of the gates, that is $i$-th qubit.Indeed, if there is no
measurement on qubit $i$ just after $U_{i-1,i}$, the state vector in Eq. (23)
generated by contracting the perturbed $U_{i-1,i}$,
$(I\otimes\alpha)U_{i-1,i}$, and other two-qubit gates is equal to the vector
generated by contracting $U_{i,i+1}(\alpha\otimes I)$ and others for any non-
identity Pauli operator $\alpha$.It means that $3\times 2$ parameters are
redundant for each two-qubit gate in a circuit’s bulk.For the first
$\frac{n}{2}$ gates, the parameters are not cancelled, and so are not $3n$
parameters.Similarly if there is a projector on qubit $i$, the perturbations
of $(I\otimes Z)U_{i-1,i}$ and $U_{i,i+1}(Z\otimes I)$ result in the same
vector, and also the perturbations of $(I\otimes X)U_{i-1,i}$ and $(I\otimes
Y)U_{i-1,i}$ result in vectors linearly dependent with each other.It means
that $2\times 2$ parameters are redundant in this case. Therefore, we obtain

$\displaystyle\dim(\mathcal{S^{\prime}})$ $\displaystyle\leq
15R^{\prime}-3(2R^{\prime}-m)-2m+3n$ (24) $\displaystyle=9R^{\prime}+m+3n$
$\displaystyle\leq 11R^{\prime}+3n,$

where $m$ is the number of measurements in the post-selected circuit, and we
used $0\leq m\leq 2R^{\prime}$ in the last inequality.A quantum state vector
$\ket{\psi}\in\mathcal{S}^{M}$ is generated by a short post-selected quantum
circuit if there exists a $\ket{\phi}\in\mathcal{S^{\prime}}$ such that
$\ket{\psi}=c\ket{\phi}$ for some $c\in\mathbb{C}$.We show that the set of
such state vectors

$\\{\ket{\psi}\in\mathcal{S}^{M}|\ket{\psi}=c\ket{\phi},\ \textrm{for}\
\ket{\phi}\in\mathcal{S^{\prime}},c\in\mathbb{C}\\}$ (25)

is of measure zero in $\mathcal{S}^{M}$, and so its preimage by $F^{A}$ in
$SU(4)^{R}$ is.By Fact 1, the set of the elements of $\mathcal{S^{\prime}}$
multiplied by arbitrary complex numbers, can be decomposed into smooth
manifolds. Then, the maximal dimension of them is upper bounded by
$11R^{\prime}+3n+2$, because complex coefficients add at most two real
parameters.Then, if $R^{\prime}<(k-3n-2)/11$, $d_{M}$ is greater the dimension
of the maximal manifold.Therefore, the intersection
$\\{\ket{\psi}\in\mathcal{S}^{M}|\ket{\psi}=c\ket{\phi},\ \textrm{for}\
\ket{\phi}\in\mathcal{S^{\prime}},c\in\mathbb{C}\\}$ has Haar measure zero,
because the manifolds in $\mathcal{S^{\prime}}$ multiplied by arbitrary
complex numbers have smaller dimensions than the maximal dimension of that in
$S^{M}$.This implies that the set of unitary gates in $SU(4)^{R^{\prime}}$,
with $R^{\prime}<(k-3n-2)/11$, that generate states in the intersection is
also Haar measure zero [6].Because
$\expectationvalue{V^{M}(t)^{\dagger}V^{M}(t)}{0^{n}}$ is upper-bounded by
finite value, that is $1$,it is still measure zero for the product measure of
the Haar measure and the Born probability, that is
$\expectationvalue{V^{M}(t)^{\dagger}V^{M}(t)}{0^{n}}\prod_{i=1}^{R}d\mu_{\textrm{Haar}}(U_{i})$.Therefore,
the output states of the monitored circuit with the dimension $k$ cannot be
generated by shorter quantum circuits consisting of fewer than $(k-3n-2)/11$
gates with unit probability, which implies the desired lower-bound of the
state complexity.∎

Finally, we prove Lemma 10.We have considered a lower-bound for the accessible
dimension of unitary circuits $d_{0}(t)$, with the brick-wall architecture and
with depth $t$, consisting of the following random unitary gates:

$\displaystyle U=\left(u_{1}\otimes v_{1}\right)W\left(u_{2}\otimes
v_{2}\right),$ (26)

where $u_{1,2}$, $v_{1,2}$ are Haar-random single-qubit gates and $W$ is
chosen from {$I$, CNOT} uniformly randomly.

######  Lemma 15 (Restatement of Lemma 10).

Let $t\geq 0$ be an integer. Then, $d_{0}$ grows linearly in depth $t$ as

$\displaystyle d_{0}(t)\geq\left\lfloor\frac{2t}{3n}\right\rfloor,$ (27)

until it saturates in a depth exponential in $n$.

###### Proof.

Recall that $d_{0}$ is the maximum dimension of the following vector space
over unitary gates $\\{U_{1},U_{2},\dots,U_{R}\\}$ in the form of Eq. (26),

$\displaystyle\\{U_{R}\dots(\alpha\otimes\beta)U_{j}\dots
U_{1}\ket{0^{n}})\\}_{j,\alpha,\beta},$ (28)

where $(\alpha\otimes\beta)$ is a single-qubit perturbation:
$(\alpha,\beta)=(I,\sigma),(\sigma,I)$ for $\sigma\in\\{X,Y,Z\\}$.In Ref. [6],
a unitary circuit consisting of Clifford gates is constructed in which $d_{0}$
grows linearly in depth. The strategy there is to construct a Clifford circuit
inductively such that a linear number in $t$ of vectors

$\displaystyle
P_{\alpha,\beta,j}\ket{0^{n}}\in\\{i^{\kappa}\ket{x}\\}_{x\in\\{0,1\\}^{n},\kappa\in\\{0,1\\}},$
(29)

where $P_{\alpha,\beta,j}=U_{1}^{\dagger}\dots
U_{j}^{\dagger}(\alpha\otimes\beta)U_{j}\dots U_{1}$, are linearly
independent.We define $C_{j}$ as a depth-$n/2$ Clifford circuit with arbitrary
Clifford two-qubit gates.In particular, there is a Clifford circuit such that
the vectors

$\displaystyle\\{C_{1}^{\dagger}\dots C_{j}^{\dagger}(Z\otimes I)C_{j}\dots
C_{1}\ket{0^{n}}\\}_{j=1}^{T},$ (30)

where $T=\lfloor\frac{2t}{n}\rfloor$, are linearly independent because of the
observation that a depth-$\frac{n}{2}$ Clifford circuit is enough to turn
$Z\otimes I$ into an arbitrary Pauli string by conjugating it [6].Moreover,
each two-qubit Clifford gate can be decomposed into at most three CNOT gates
with single-qubit gates [87].Therefore, every $\frac{3n}{2}$ time step can
increase the accessible dimension at least by one, and we obtain

$\displaystyle d_{0}(t)\geq\left\lfloor\frac{2t}{3n}\right\rfloor.$ (31)

∎

The dimension $d_{0}$ is upper-bounded by $2\times 2^{n}-1$, which is the
number of real parameters in normalized quantum states, and it grows linearly
until it saturates at the maximum value exponentially in $n$.

##  Appendix B Measurements cannot increase the accessible dimension

In this section, we prove that the accessible dimension of a monitored random
circuitcannot increase by adding a projection operator. Let $M$ be a
measurement configuration.We now construct a new measurement configuration
$M^{\prime}$ by changingan element $M_{i}(\tau)$such that
$M_{i}(\tau)=\sqrt{1-p}I$ into
$M_{i}^{\prime}(\tau)=\sqrt{p}\outerproduct{0}{0}$ or
$M_{i}^{\prime}(\tau)=\sqrt{p}\outerproduct{1}{1}$ and keeping the other
elements. We denote by $|M|$ the number ofprojections in $M$, and hereafter we
rename the set of projectors as $\\{M_{i}\\}_{i=1}^{|M|}$.We call such
$M^{\prime}_{i}$ the additional measurement.Then the following statement
holds.

######  Lemma 16 (Rank bound).

For $\rank(F^{M^{\prime}})$ on an arbitrary point $x^{\prime}\in SU(4)^{\times
R}$, there exists a point $x\in SU(4)^{\times R}$, on which $\rank(F^{M})$
satisfies the inequality:

$\displaystyle\rank(F^{M^{\prime}})\leq\rank(F^{M}).$ (32)

###### Proof.

We fix $R$ gates mapped by $F^{M^{\prime}}$ as
$x^{\prime}=\\{U_{R},\dots,U_{1}\\}$. By definition, the rank $r^{\prime}$ of
$F^{M^{\prime}}$ is

$\displaystyle r^{\prime}=\dim\left(\textrm{span}\left\\{U_{R}\cdots
M^{\prime}_{|M^{\prime}|}\cdots
M^{\prime}_{k}U_{m}\phantom{(\alpha\otimes\beta)}\right.\right.$
$\displaystyle\left.\left.\cdots(\alpha\otimes\beta)U_{j}\cdots
M^{\prime}_{1}\cdots U_{1}\ket{0^{n}}\right\\}_{j,\alpha,\beta}\right),$ (33)

where $M^{\prime}_{k}$ is the additional measurement
$M^{\prime}_{k}=\sqrt{p}\outerproduct{0}{0}$ (we assume here that the outcome
of $M_{k}$ is $+1$, but the case of $-1$ works as well).Because of
$\outerproduct{0}{0}=({I+Z})/{2}$, Eq. (33) becomes

$\displaystyle r^{\prime}=\dim\left(\textrm{span}\left\\{U_{R}\cdots
M^{\prime}_{|M^{\prime}|}\cdots(I+Z)U_{m}\phantom{(\alpha\otimes\beta)}\right.\right.$
$\displaystyle\left.\left.\cdots(\alpha\otimes\beta)U_{j}\cdots
M^{\prime}_{1}\cdots U_{1}\ket{0^{n}}\right\\}_{j,\alpha,\beta}\right),$ (34)

where $U_{m}$ is the unitary gate which is just followed by the measurement
$M_{k}$.By the definition of dimension, there are $r^{\prime}$ linearly
independent vectors $\ket{v_{i}}:=U_{R}\cdots
M_{|M|}\cdots(I+Z)U_{m}\cdots(\alpha\otimes\beta)U_{j}\cdots M_{1}\cdots
U_{1}\ket{0^{n}}$, $i=1,\dots,r$, where the index $i$ denotes the
configuration of $\alpha$, $\beta$, and $j$.Now, we set $x$ as the same as
$x^{\prime}$ except for $m$-th gate, which is $e^{i(I+Z)\theta}U_{m}$.Then,
$\textrm{rank}(F^{M})$ is the dimension of the vector space spanned by the
vectors

$\displaystyle\left\\{U_{R}\cdots M_{|M|}\cdots
e^{i(I+Z)\theta}U_{m}\cdots(\alpha\otimes\beta)U_{j}\cdots
U_{1}\ket{0^{n}}\right\\}_{j,\alpha,\beta},$ (35)

which are equal to

$\displaystyle\left\\{U_{R}\cdots M_{|M|}\cdots
U_{m}\cdots(\alpha\otimes\beta)U_{j}\cdots M_{1}\cdots
U_{1}\ket{0^{n}}\right.$ $\displaystyle\ \ +U_{R}\cdots
M_{|M|}\cdots(e^{i\theta}-1)(I+Z)U_{m}$ $\displaystyle\ \ \ \ \ \
\left.\cdots(\alpha\otimes\beta)U_{j}\cdots M_{1}\cdots
U_{1}\ket{0^{n}}\right\\}_{j,\alpha,\beta}.$ (36)

Using the vectors $\\{\ket{v_{i}}\\}$, we can find $r$ independent vectors in
Eq. (36).Specifically, we can find some $\theta$ such that the $r$ vectors

$\displaystyle\ket{u_{i}}+(e^{i\theta}-1)\ket{v_{i}}$
$\displaystyle=U_{R}\cdots M_{|M|}\cdots
U_{m}\cdots(\alpha\otimes\beta)U_{j}\cdots M_{1}\cdots U_{1}\ket{0^{n}}$
$\displaystyle+(e^{i\theta}-1)U_{R}\cdots
M_{|M|}\cdots(I+Z)U_{m}\cdots(\alpha\otimes\beta)U_{j}$ $\displaystyle\ \ \ \
\ \cdots M_{1}\cdots U_{1}\ket{0^{n}}$ (37)

are linearly independent for $i=1,\dots,r$, where we have defined
$\ket{u_{i}}$ and $(e^{i\theta}-1)\ket{v_{i}}$ as the first term and the
second term of the right-hand side of the equation, respectively.To see this,
first, we make $r$ orthonormal vectors $\\{\ket{\tilde{v}_{i}}\\}$ from
$\\{\ket{v_{i}}\\}$ by the Gram-Schmidt decomposition.By these vectors,
$\\{\ket{v_{i}}\\}$ is decomposed as
$\ket{v_{i}}=\sum_{k=1}^{i}d_{i}^{k}\ket{\tilde{v}_{k}}$, for some
coefficients $d_{i}^{k}$ such that $d_{i}^{i}\neq 0$ for all $i$. Next,
decompose $\ket{u_{i}}$ as

$\ket{u_{i}}=\sum_{k=1}^{r}c^{k}_{i}\ket{\tilde{v}_{k}}+c^{\bot}_{i}\ket{v_{i}^{\bot}},$
(38)

for some coefficients $c^{k}_{i},\ c^{\bot}_{i}$ and some vector
$\ket{v_{i}^{\bot}}$ in the orthogonal complement of
span$\\{\ket{v_{i}}\\}$.Let us define the function
$f:\mathbb{R}\rightarrow\mathbb{C}$ as

$f(\theta):=e^{i\theta}-1.$ (39)

Then, Eq. (B) becomes

$\displaystyle\sum_{k\leq
i}(c_{i}^{k}+f(\theta)d_{i}^{k})\ket{\tilde{v}_{k}}+\sum_{k>i}c_{i}^{k}\ket{\tilde{v}_{k}}+c^{\bot}\ket{v_{i}^{\bot}}.$
(40)

Again, we make $r$ orthonormal vectors $\\{\ket{\tilde{v}^{\bot}_{i}}\\}$ from
$\\{\ket{{v^{\bot}}_{i}}\\}$ by the Gram-Schmidt decomposition, and
$\ket{{v^{\bot}}_{i}}=\sum_{k=1}^{i}e_{i}^{k}\ket{\tilde{v}^{\bot}_{k}}$ for
some coeffients $e_{i}^{k}$.Consider a linear map $A$, which maps
$\ket{\tilde{v}_{i}}$ to Eq. (40).In the matrix representation with the basis
$\\{\ket{\tilde{v}_{i}},\ket{\tilde{v}_{i}^{\bot}}\\}_{i=1,\dots,r}$,

$\displaystyle
A=\begin{pmatrix}c_{1}^{1}+f(\theta)d_{1}^{1}&c_{2}^{1}+f(\theta)d_{2}^{1}&\cdots&c_{r}^{1}+f(\theta)d_{r}^{1}\\\
c_{1}^{2}&c_{2}^{2}+f(\theta)d_{2}^{2}&\cdots&c_{r}^{2}+f(\theta)d_{r}^{2}\\\
\vdots&\vdots&\ddots&\vdots\\\
c_{1}^{r}&c_{2}^{r}&\cdots&c_{r}^{r}+f(\theta)d_{r}^{r}\\\
e_{1}^{1}&e_{2}^{1}&\cdots&e_{r}^{1}\\\ 0&e_{2}^{2}&\cdots&e_{r}^{2}\\\
\vdots&\vdots&\ddots&\vdots\\\ 0&0&\cdots&e_{r}^{r}\\\ \end{pmatrix},$ (41)

where it is an $2r\times r$ matrix.Let $A^{r\times r}$ be the top $r\times r$
sub-matrix of $A$.Note that if the $\textrm{rank}(A^{r\times r})=r$, then
$\textrm{rank}(A)=r$, and it implies that the vectors
$\\{\ket{u_{i}}+(e^{i\theta}-1)\ket{v_{i}}\\}_{i=1,\dots,r}\\}$ are linearly
independent.This condition is equivalent to that $A^{r\times r}$ has a non-
zero determinant.Moreover, we can always choose $\theta$ such that
$\textrm{rank}(A^{r\times r})=r$.This is because the determinant of
$A^{r\times r}$ is a polynomial of $F(\theta)$ such that its zeros imply
$\textrm{rank}(A^{r\times r})<r$, and by virtue of the fundamental theorem of
algebra, the number of zeros of the polynomial is the same as its degree,
which is $r$.We can choose $\theta$ such that it is not any zeros of the
polynomials, because $\theta$ is a continuous variable.Hence, such $\theta$
gives rank($F^{M}$) which is greater than or equal to rank($F^{M^{\prime}}$).∎

Because the accessible dimension is the maximal rank over $R$ unitary gates,
the above lemma implies that single-qubit measurement, or projection, cannot
increase the accessible dimension. Applying the above lemma recursively, we
can show that adding any number and space-time point of measurements cannot
increase the dimension.

##  Appendix C Two-qubit gate between nearest-neighbour measurement-free paths

In this section, we show how unitary gates at the edge of the bridge are fixed
to implement a CNOT gate between two neraest-neighbour measurement-free paths.
For completeness, we begin with restating the method in the main text, where
we consider the following paths and bridge,

$\includegraphics[width=99.58464pt]{Bridge_causal_causal.png}.$ (42)

Then, CNOT can be implemented as Eq. (18), and we restate it here as

$\includegraphics[width=241.84842pt]{Bridge_CNOT.png}.$ (43)

In this case, both of the paths in Eq. (42) are causal in the broken circles,
that is, they include both an input and an output of the unitary gates in the
circles.In general, in such case we can perform CNOT, by applying a CNOT gate,
multiplied by $I\otimes H$, with the control qubit being measured and another
CNOT gate with the target qubit state being measured at the edge of the
bridge, such as Eq. (43).If this is not the case, we can still implement a
CNOT gate, as we explain below. We consider the case where one path is causal,
and another path is not causal at the edge of a bridge, for example

$\includegraphics[width=184.9429pt]{causal_acausal.png},$ (44)

where in the right-hand side, we highlighted the paths, the bridge, and two-
qubit gates at the edge of the bridge.We can also perform CNOT in such case,
by applying a CNOT gate, multiplied by $I\otimes H$, with the control qubit
state being measured and another CNOT gate with the target qubit state being
measured.For the above example, it is performed as the following:

$\includegraphics[width=241.84842pt]{CNOT_causal_acausal.png}.$ (45)

The difference with the earlier case is that here the qubit state carried by a
bridge is an output state of one measurement-free path.Finally, we consider
the case where both of the paths are not causal at the edge of a bridge, for
example

$\includegraphics[width=184.9429pt]{acausal_acausal.png}.$ (46)

Again, we can perform CNOT in such case, by a similarchoice of two-qubit gates
at the edge of the bridge. For the above example,

$\includegraphics[width=241.84842pt]{CNOT_acausal_acausal.png}.$ (47)

##  Appendix D Percolation theory

In this work, techniques frompercolation theory feature strongly. For
thisreason, here wereview some aspects of percolation theory, following Ref.
[66].Specifically, we focus on thepercolation theory on a rectangle featuring
a large aspect ratio.Especially important are notions of _bond percolation_ on
two-dimensional square lattices.A square lattice is defined as
$\mathbb{Z}^{2}$ with edges between all nearest-neighbor pairs
$x,y\in\mathbb{Z}^{2}$. We denote by $\mathbb{E}$ the set of _edges_.We define
a measurable space ($\Omega$, $\mathcal{F}$) as follows.For the sample space,
we take $\Omega=\prod_{e\in\mathbb{E}}\\{0,1\\}$, called the edge
configuration ($0$ and $1$ represent closed and open edge, respectively), and
$\mathcal{F}$ is the $\sigma$-algebra on it.Each element in $\Omega$ is
represented as a function $\omega:\mathbb{E}\rightarrow\\{0,1\\}$.We say
$\omega\leq\omega^{\prime}$ if $\omega(e)\leq\omega^{\prime}(e)$ for all
$e\in\mathbb{E}$.Let $A\in\mathcal{F}$ be an _increasing event_ , i.e.,

$I_{A}(\omega)\leq I_{A}(\omega^{\prime})$ (48)

whenever $\omega\leq\omega^{\prime},\omega,\omega^{\prime}\in\Omega$.Here,
$I_{A}:\Omega\rightarrow\\{0,1\\}$is the _indicator function_ of $A$:
$I_{A}(\omega)=1$ if $\omega\in A$ and otherwise $I_{A}(\omega)=0$.For an
event $A$, we denote the probability of the occurrence of the event by
$P_{q}(A)$ when an edge opens with probability $q$.(This $q$ is contrary to
that in the section 2.1. There, a measurement closes, or “cut” a bond, at
probability “$p$” but in this section, bond is open at probability $q$.)For
two increasing events$A$ and $B$, theinequality

$P_{q}(A\cap B)\geq P_{q}(A)P_{q}(B)$ (49)

is well known as the _FKG inequality_ in the literature of percolation
theory.Intuitively, the FKG inequality tells us that if we know an increasing
event $A$ occurs, another increasing event $B$ is more or equally likely to
occur.Bond percolation theory is concerned with the existence or absence of
_left-right crossings_ on a $L\times L$ square, which is an open path
connecting from some vertex on the left side of the square to the right side
of it.With probability exponentially close to one in $L$, above the critical
probability $q_{c}$, there exists such crossings, and below it, there does
not. Moreover, the critical point of bond percolation in two-dimensional
square lattice is known to be $q_{c}=1/2$ [66].In the following subsections,
we show several lemmas to establish Theorem 5.

###  D.1 Suppercritical phase

A main goal here is to derive a lower-bound of the expected number ofleft-
right crossings on a rectangle with a various aspect ratio in the regime
$q>q_{c}=\frac{1}{2}$.

####  D.1.1 Percolation on a square

We start the argument by discussing the case of a square.Let $M_{L}$ be the
maximal number of edge-disjoint left-right crossings of the box
$[0,L]\times[0,L]$ for an integer $L$.In this appendix, we use the shorthand
$[0,a]\times[0,b]$ to designate the rectangular lattice of pointsof height $a$
and width $b$.In the supercritical phase the probability of the event $A$,
where there exists an left-right crossing in the box $[0,L]\times[0,L]$, is
exponentially close to one [66]:

$\displaystyle P_{q}(A)\geq 1-e^{-\alpha L},$ (50)

for some constant $\alpha=\alpha(q)$.The event $A$ is an increasing event,
because adding open edges does not decrease the number of left-right
crossings.Now we define the _interior_ of $A$, $J_{r}(A)$, as the set of
configurations in $A$ which are still in $A$ after changing arbitrarily the
configurations at most $r$ edges (deleting or adding edges).The following fact
states the stability of an increasing event.

######  Fact 2 (Theorem 2.45 in Ref. [66]).

Let $A$ be an increasing event. Then

$1-P_{q_{2}}(J_{r}(A))\leq\left(\frac{q_{2}}{q_{2}-q_{1}}\right)^{r}(1-P_{q_{1}}(A))$
(51)

for any $0\leq q_{1}<q_{2}\leq 1$.

Roughly speaking, it states that if the event $A$ happens with probability
$q_{1}$, the modified event $J_{r}$ is also likely to happen when probability
exceeds $q_{1}$.The above fact is useful for finding a lower-bound of the
number of crossings of a rectangle.$J_{r}(A)$ is the events that there exists
at least $r+1$ left-right crossing (because if there are less than $r+1$
crossings, deleting $r$ edges can cut all the crossings).Combining Eq. 50 with
Fact 2, the following statement is obtained.

######  Fact 3 (Lemma 11.22 in Ref. [66]).

For $q>1/2$, there exists strictly positive constants $\beta(q)$ and
$\gamma(q)$, which are independent in n, such
that$P_{q}(M_{L}\geq\beta(q)L)\geq 1-e^{-\gamma(q)L}$ for all $L\geq 1$.

###### Proof.

One starts by choosing $r$ in Fact 2 as $\beta(q)L$, and the set $A$ as being
the event that there exists at least one left-right crossing. Then Fact 2
implies

$1-e^{-L\left(\alpha(q^{\prime})-\beta(q)\log\frac{q}{q-q^{\prime}}\right)}\leq
P_{q}(M_{n+1}\geq\beta(q)L),$ (52)

where $q>q^{\prime}>1/2$.Now we find

$\gamma(q)=\alpha(q^{\prime})-\beta(q)\log\frac{q}{q-q^{\prime}}.$ (53)

For a fixed $1\geq q>\frac{1}{2}$, we can choose a strictly positive constant
$\beta(q)$ and $q^{\prime}$ such that $\gamma(q)$ is also strictly positive.∎

The above statement implies that if a left-right crossing exists at a high
probability in a square lattice, we can find a number of edge-disjoint left-
right crossings, which scale in the length of the side of a square, at a high
probability.It ensures the existence of a linear number of measurement-free
paths.We mention that Refs. [88, 89, 90] havemade a similar use of Facts 2 and
3 as well.

####  D.1.2 Percolation on a rectangle with a various aspect ratio

Next we consider a square lattice on a rectangle $[0,L]\times[0,LT]$ for some
aspect ratio $T>1$.We can show the existence of a scalable number of left-
right crossings until some exponential aspect ratio.It is true in the case of
both bond and site percolation.We make use of following facts. Let $A_{T}$ be
an event that there exists a right-left crossing on $[0,L]\times[0,LT]$
rectangle.

######  Fact 4 (Lemma 11.73 and 11.75 in Ref. [66]).

If $P_{q}(A_{1})=\tau$, then

$\displaystyle P_{q}\left(A_{\frac{3}{2}}\right)\geq(1-\sqrt{1-\tau})^{3},$
(54) $\displaystyle P_{q}(A_{2})\geq
P_{q}(A_{1})P_{q}\left(A_{\frac{3}{2}}\right).$ (55)

These insights(_FKG inequality_) assist us in provingthe following lemma.

######  Lemma 17 (Large aspect ratios).

If $P_{q}(A_{1})=\tau$, then

$\displaystyle P_{q}(A_{T})$ $\displaystyle\geq
P_{q}(A_{1})^{T-2}P_{q}\left(A_{2}\right)^{T-1}$ (56)
$\displaystyle\geq\tau^{2T-3}(1-\sqrt{1-\tau})^{3(T-1)}.$

###### Proof.

To start with, note that if there are top-bottom crossings in every square
except for both ends and left-right crossings in every nearest-neighbor two
squares, then there exists at least one left-right crossing over the entire
rectangle, or, graphically,

,

where the broken line is the left-right crossing over the rectangle.Besides,

$\displaystyle\left(\bigcap_{i=1}^{T-2}A_{1}\right)\bigcap\left(\bigcap_{i=1}^{T-2}A_{2}\right)\subset
A_{T},$ (57)

and it can be straightforwardly shown that $A_{1}$ and $A_{2}$ are increasing
events.Hence, by the FKG inequality, the inequality Eq. (56) holds, and
together with Fact 4, we arrive at the validity of the second inequality as
well.∎

From the above lemma together with Fact 2, we can guarantee a linear number of
edge-disjoint left-right crossings.Let $M_{L}^{T}$ be the maximal number of
edge-disjoint open left-right crossings of the box $[0,L]\times[0,LT]$.

######  Lemma 18 (Linear paths).

For $q>1/2$, there exists strictly positive constants$\beta(q)$ and
$\gamma(q)$, which are independent of $n$, such that

$P_{p}(M_{L}^{T}\geq\beta(q)L)\geq 1-e^{-\gamma(q)L}$ (58)

for all $L\geq 1$.

###### Proof.

For $q>1/2$, because of

$\tau\geq 1-e^{-\alpha(p)L}$ (59)

andLemma 17,we obtain

$\displaystyle P_{q}(A_{T})\geq$
$\displaystyle\left(1-e^{-\frac{\alpha(q)}{2}L}\right)^{3(T-1)}$ (60)
$\displaystyle\times\left(1-e^{-\alpha(q)L}\right)^{(2T-3)}$
$\displaystyle\geq$ $\displaystyle\left(1-e^{-\frac{\alpha(q)}{2}L+\log
3(T-1)}\right)$ $\displaystyle\times\left(1-e^{-\alpha(q)L+\log(2T-3)}\right)$
$\displaystyle\geq$ $\displaystyle 1-e^{-\frac{\alpha(q)}{2}L+\log
3(T-1)}-e^{-\alpha(q)L+\log(2T-3)}$ $\displaystyle\geq$ $\displaystyle
1-2e^{-\frac{\alpha(q)}{2}L+\log 3(T-1)},$

where, in the second inequality, we have used the Bernoulli’s inequality

$(1+x)^{y}\geq 1+xy$ (61)

for any real numbers $x\geq-1,y\geq 1$.Using Fact 2, this implies that the
number of left-rightcrossings scales in the system size.Specifically,

$\displaystyle P_{q}(M_{L}^{T}\geq\beta(q)L)\geq
1-e^{-\left(\frac{\alpha(q^{\prime})}{2}-\beta(q)\log\frac{q}{q-q^{\prime}}\right)L+\log
6(T-1)}$ (62)

where $q>q^{\prime}>1/2$.We find that

$\displaystyle\gamma(q)=\frac{\alpha(q^{\prime})}{2}-\beta(q)\log\frac{q}{q-q^{\prime}}-\frac{1}{L}\log
6(T-1).$ (63)

We can pick a strictly positive constant $\beta(p)>0$ and
$\frac{1}{2}<q^{\prime}<q$ such that $\gamma(q)$ is also strictly positive.∎

This lemma ensures that at below critical measurement probability, there
exists a linear number of measurement-free paths until some exponential
time.Specifically, if

$\displaystyle T<\frac{e^{\frac{\gamma^{\prime}(q)}{2}n}}{3}$ (64)

for some strictly positive

$\displaystyle\gamma^{\prime}(q)<\frac{\alpha(q^{\prime})}{2}-\beta(q)\log\frac{q}{q-q^{\prime}},$
(65)

there exists $\lfloor\beta(q)L\rfloor$left-right crossings on a rectangle
almost surely in the large $L$ limit.

###  D.2 Subcritical phase

Next, we consider the size of a set of connected open edges in the subcritical
phase $q<q_{c}$.The _open cluster_ $C(x)$ at a vertex $x$ of the square
lattice is defined by the set of the connected open edges containing $x$, and
$|C(x)|$ denotes the number of the edges in $C(x)$.Then, the probability that
the size $|C(x)|$ is large is upper bounded as follows.

######  Fact 5 (Theorem 6.75 in Ref. [66]).

Let $C(x)$ be an open cluster containing a vertex $x$.If
$q<q_{c}=\frac{1}{2}$, there exists $\lambda(q)>0$ such that for any integer
$k\geq 1$,

$\displaystyle P_{q}(|C(x)|\geq k)\leq e^{-k\lambda(q)}.$ (66)

The independence of $x$ in the right-hand side is due to translational
invariance of the square lattice.Now, we upper-bound the probability of the
event that all size of $m$ open clusters,

$\displaystyle\\{C(x_{1}),C(x_{2}),{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\dots},C(x_{m})\\},$
(67)

is upper-bounded by an integer $k$, which we define by

$\displaystyle P_{q}\left(\bigcup_{i=1}^{m}\\{|C(x_{i})|\geq k\\}\right).$
(68)

######  Lemma 19 (Small open clusters).

For $q<1/2$, there exists $\lambda(q)>0$ such that for any real number
$0<\epsilon<1$ and any integer
$k\geq\frac{1}{\lambda(q)}\log(\frac{m}{\epsilon})$,

$P_{q}\left(\bigcup_{i=1}^{m}\\{|C(x_{i})|\geq k\\}\right)\leq\epsilon.$ (69)

###### Proof.

By the union bound and Fact 5, we obtain

$\displaystyle P_{q}\left(\bigcup_{i=1}^{m}\\{|C(x_{i})|\geq k\\}\right)\leq$
$\displaystyle\sum_{i=1}^{m}P_{q}\left(|C(x_{i})|\geq k\right)$ (70)
$\displaystyle\leq$ $\displaystyle me^{-k\lambda(q)}.$ (71)

Then, by the condition

$\displaystyle k\geq\frac{1}{\lambda(q)}\log(\frac{m}{\epsilon}),$ (72)

we obtain Eq. (69).∎

###  D.3 Tilted lattice and untilted lattice

As shown in Fig. 2 in the main text, a monitored circuit is mapped to a tilted
square lattice.In percolation theory, however, bond percolation on a square
lattice is ordinarily considered for an untilted square lattice, consisting of
horizontal edges. We show how they are related by proving that the critical
points of them are same.We consider bond percolation on an $2n\times 2n$
ordinary square lattice above the critical point, and the $n\times n$ tilted
square whose corners are at the middle of the edges of the $2n\times 2n$
square lattice.Then, with probability $1-e^{-\Omega(n)}$, there exist at least
one left-right and one top-bottom crossings in rectangles
$[0,\lfloor\frac{n}{2}\rfloor]\times[0,2n]$ just above the middle horizontal
line and right next to the middle vertical line, respectively, or graphically,

,

where the square with broken lines is the $n\times n$ tilted square, and we
assumed the crossings are straight.It implies by the FKG inequality that there
exists at least one left-right crossing in the tilted square lattice. Also,
one can show conversely that left-right and top-bottom crossings in a
$2n\times 2n$ tilted lattice implies a crossing in an $n\times n$ ordinary
square lattice inside it by the same argument. Therefore, the critical points
of percolation on both lattices are the same.

## References

  * Aaronson [2016] S. Aaronson, arXiv:1607.05256 (2016).
  * Susskind [2016a] L. Susskind, Fortschritte Phy. 64, 49 (2016a).
  * Eisert [2021] J. Eisert, Phys. Rev. Lett. 127, 020501 (2021).
  * Brown and Susskind [2018] A. R. Brown and L. Susskind, Phys. Rev. D 97, 086015 (2018).
  * Brandão  _et al._ [2021] F. G. Brandão, W. Chemissany, N. Hunter-Jones, R. Kueng, and J. Preskill, PRX Quantum 2, 030316 (2021).
  * Haferkamp  _et al._ [2022] J. Haferkamp, P. Faist,N. B. Kothakonda,J. Eisert, and N. Yunger Halpern, Nature Phys. 18, 528 (2022).
  * Li [2022] Z. Li, arXiv:2205.05668 (2022).
  * Stanford and Susskind [2014] D. Stanford and L. Susskind, Phys. Rev. D 90, 126007 (2014).
  * Brown  _et al._ [2016] A. R. Brown, D. A. Roberts,L. Susskind, B. Swingle, and Y. Zhao, Phys. Rev. Lett. 116,191301 (2016).
  * Chapman  _et al._ [2017] S. Chapman, H. Marrochio,and R. C. Myers, JHEP 2017(62), 1.
  * Chapman  _et al._ [2019] S. Chapman, J. Eisert, L. Hackl, M. P.Heller, R. Jefferson, H. Marrochio, and R. C. Myers, SciPost Phys. 6, 034 (2019).
  * Susskind [2016b] L. Susskind, Fortschritte Phys. 64, 24 (2016b).
  * Susskind [2018] L. Susskind, in  _2018 Prospectsin Theoretical Physics (PiTP) summer school_ (Princeton, NJ, 2018) 1810.11563 .
  * Belin  _et al._ [2022] A. Belin, R. C. Myers,S.-M. Ruan, G. Sárosi, and A. J. Speranza, Phys. Rev. Lett. 128,081602 (2022).
  * Huang and Chen [2015] Y. Huang and X. Chen,Phys. Rev. B 91,195143 (2015).
  * Liu  _et al._ [2020] F. Liu, S. Whitsitt,J. B. Curtis, R. Lundgren, P. Titum, Z.-C. Yang, J. R.Garrison, and A. V.Gorshkov, Phys. Rev. Res. 2,013323 (2020).
  * Yunger Halpern  _et al._ [2022] N. Yunger Halpern, N. B. T. Kothakonda, J. Haferkamp, A. Munson,J. Eisert, and P. Faist, Phys. Rev. A 106, 062417 (2022).
  * Fisher  _et al._ [2023] M. P. A.Fisher, V. Khemani, A. Nahum,and S. Vijay, Ann. Rev. Cond. Matt. Phys. 14, 335 (2023).
  * Piroli  _et al._ [2020a] L. Piroli, C. Sünderhauf, and X.-L.Qi, JHEP 2020 (63), 1.
  * Hayden and Preskill [2007] P. Hayden and J. Preskill, JHEP 2007 (9), 120.
  * Chan  _et al._ [2018] A. Chan, A. De Luca, and J. T. Chalker, Phys. Rev. X 8, 041019 (2018).
  * Bertini and Piroli [2020] B. Bertini and L. Piroli, Phys. Rev. B 102, 064305 (2020).
  * Balasubramanian  _et al._ [2020] V. Balasubramanian, M. DeCross, A. Kar, andO. Parrikar, JHEP 2020(134), 1.
  * Brandao  _et al._ [2016] F. G. Brandao, A. W.Harrow, and M. Horodecki, Commun. Math. Phys. 346,397 (2016).
  * Roberts and Yoshida [2017] D. A. Roberts and B. Yoshida, JHEP 2017 (4), 1.
  * Dankert  _et al._ [2009] C. Dankert, R. Cleve, J. Emerson, and E. Livine, Phys. Rev. A 80, 012304 (2009).
  * Gross  _et al._ [2007] D. Gross, K. Audenaert, and J. Eisert, J. Math. Phys. 48, 052104 (2007).
  * Cheeseman  _et al._ [1991] P. C. Cheeseman, B. Kanefsky, and W. M. Taylor, in  _IJCAI_ (1991) pp.331–340.
  * Mitchell  _et al._ [1992] D. G. Mitchell, B. Selman,and H. J. Levesque,in  _AAAI_ (1992) pp. 459–465.
  * Bremner  _et al._ [2011] M. J. Bremner, R. Jozsa,and D. J. Shepherd,Proc. Roy. Soc. A 467, 459 (2011).
  * Fujii and Tamate [2016] K. Fujii and S. Tamate,Scientific Rep. 6, 1 (2016).
  * Park and Kastoryano [2022] C.-Y. Park and M. J. Kastoryano, arXiv:2204.08898 (2022).
  * Aaronson and Arkhipov [2011] S. Aaronson and A. Arkhipov, in  _Proc. 43rd. Ann. ACM Symp. Th. Comp._ (2011) pp. 333–342.
  * Deshpande  _et al._ [2018] A. Deshpande, B. Fefferman, M. C. Tran,M. Foss-Feig, andA. V. Gorshkov, Phys. Rev. Lett. 121,030501 (2018).
  * Maskara  _et al._ [2022] N. Maskara, A. Deshpande,A. Ehrenberg, M. C. Tran, B. Fefferman, and A. V. Gorshkov, Phys. Rev. Lett. 129,150604 (2022).
  * Van Regemortel  _et al._ [2022] M. Van Regemortel, O. Shtanko, L. P. García-Pintos, A. Deshpande, H. Dehghani,A. V. Gorshkov, andM. Hafezi, Phys. Rev. Res. 4,L032021 (2022).
  * Bouland  _et al._ [2019] A. Bouland, B. Fefferman,C. Nirkhe, and U. Vazirani, Nature Phys. 15, 159 (2019).
  * Napp  _et al._ [2022] J. C. Napp, R. L. La Placa,A. M. Dalzell, F. G. S. L. Brandão, andA. W. Harrow, Phys. Rev. X 12, 021021 (2022).
  * Gopalakrishnan and Lamacraft [2019] S. Gopalakrishnan and A. Lamacraft, Phys. Rev. B 100, 064309 (2019).
  * Bertini  _et al._ [2019] B. Bertini, P. Kos, andT. Prosen, Phys. Rev. Lett. 123,210601 (2019).
  * Piroli  _et al._ [2020b] L. Piroli, B. Bertini,J. I. Cirac, andT. Prosen, Phys. Rev. B 101, 094304 (2020b).
  * Claeys and Lamacraft [2021] P. W. Claeys and A. Lamacraft, Phys. Rev. Lett. 126, 100603 (2021).
  * Suzuki  _et al._ [2022] R. Suzuki, K. Mitarai,and K. Fujii, Quantum 6, 631 (2022).
  * Aharonov [2000] D. Aharonov, Phys. Rev. A 62, 062311 (2000).
  * Eisert  _et al._ [2010] J. Eisert, M. Cramer,and M. B. Plenio,Rev. Mod. Phys. 82,277 (2010).
  * Skinner  _et al._ [2019] B. Skinner, J. Ruhman,and A. Nahum, Phys. Rev. X 9, 031009 (2019).
  * Bao  _et al._ [2020] Y. Bao, S. Choi, andE. Altman, Phys. Rev. B 101, 104301 (2020).
  * Perez-Garcia  _et al._ [2007a] D. Perez-Garcia, F. Verstraete, M. M. Wolf, and J. I. Cirac, Quant. Inf. Comp. 7, 401–430 (2007a).
  * Li  _et al._ [2018] Y. Li, X. Chen, andM. P. Fisher, Phys. Rev. B 98, 205136 (2018).
  * Chan  _et al._ [2019] A. Chan, R. M. Nandkishore, M. Pretko, and G. Smith, Phys. Rev. B 99, 224307 (2019).
  * Li  _et al._ [2019] Y. Li, X. Chen, andM. P. Fisher,Phys. Rev. B100, 134306 (2019).
  * Gullans and Huse [2020] M. J. Gullans and D. A. Huse, Phys. Rev. X 10, 041020 (2020).
  * Jian  _et al._ [2020] C.-M. Jian, Y.-Z. You,R. Vasseur, and A. W. W. Ludwig, Phys. Rev. B 101, 104302 (2020).
  * Choi  _et al._ [2020] S. Choi, Y. Bao, X.-L. Qi, and E. Altman, Phys. Rev. Lett. 125,030505 (2020).
  * Ippoliti  _et al._ [2021] M. Ippoliti, M. J. Gullans, S. Gopalakrishnan, D. A. Huse, and V. Khemani, Phys. Rev. X 11, 011030 (2021).
  * Lavasani  _et al._ [2021] A. Lavasani, Y. Alavirad,and M. Barkeshli, Nature Phys. 17, 342 (2021).
  * Nahum  _et al._ [2021] A. Nahum, S. Roy, B. Skinner, and J. Ruhman, PRX Quantum 2, 010352 (2021).
  * Sang and Hsieh [2021] S. Sang and T. H. Hsieh, Phys. Rev. Research 3, 023200 (2021).
  * Agrawal  _et al._ [2022] U. Agrawal, A. Zabalo,K. Chen, J. H. Wilson, A. C. Potter, J. H. Pixley, S. Gopalakrishnan, and R. Vasseur, Phys. Rev. X 12, 041002 (2022).
  * Cao  _et al._ [2019] X. Cao, A. Tilloy, andA. D. Luca, SciPost Phys. 7,024 (2019).
  * Tang and Zhu [2020] Q. Tang and W. Zhu,Phys. Rev. Res. 2, 013022 (2020).
  * Fuji and Ashida [2020] Y. Fuji and Y. Ashida,Phys. Rev. B 102,054302 (2020).
  * Jian  _et al._ [2021] S.-K. Jian, C. Liu, X. Chen, B. Swingle, and P. Zhang, Phys. Rev. Lett. 127,140601 (2021).
  * Minato  _et al._ [2022] T. Minato, K. Sugimoto,T. Kuwahara, andK. Saito, Phys. Rev. Lett. 128,010603 (2022).
  * Niroula  _et al._ [2023] P. Niroula, C. D. White,Q. Wang, S. Johri, D. Zhu, C. Monroe, C. Noel, andM. J. Gullans,arXiv:2304.10481 (2023).
  * Grimmett [1999] G. Grimmett,  _Percolation_ (Springer,1999).
  * Aaronson [2005] S. Aaronson, Proc. Roy. Soc. A 461, 3473 (2005).
  * Perez-Garcia  _et al._ [2007b] D. Perez-Garcia, F. Verstraete, M. M. Wolf, and J. I. Cirac, Quant. Inf. Comp. 7, 401–430 (2007b).
  * Schön  _et al._ [2005] C. Schön, E. Solano,F. Verstraete, J. I. Cirac, and M. M. Wolf, Phys. Rev. Lett. 95,110503 (2005).
  * Cramer  _et al._ [2010] M. Cramer, M. B. Plenio,S. T. Flammia, R. Somma, D. Gross, S. D. Bartlett, O. Landon-Cardinal, D. Poulin, and Y.-K.Liu, Nature Comm. 1, 149 (2010).
  * Barenco  _et al._ [1995] A. Barenco, C. H. Bennett, R. Cleve,D. P. DiVincenzo,N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter, Phys. Rev. A 52, 3457 (1995).
  * Bennett  _et al._ [2000] C. H. Bennett, S. Popescu,D. Rohrlich, J. A. Smolin, and A. V. Thapliyal, Phys. Rev. A 63, 012307 (2000).
  * Dür  _et al._ [2000] W. Dür, G. Vidal, andJ. I. Cirac, Phys. Rev. A 62, 062314 (2000).
  * Piroli  _et al._ [2021] L. Piroli, G. Styliaris,and J. I. Cirac, Phys. Rev. Lett. 127,220503 (2021).
  * Tantivasadakarn  _et al._ [2021] N. Tantivasadakarn, R. Thorngren, A. Vishwanath, and R. Verresen, arXiv:2112.01519 (2021).
  * Lu  _et al._ [2022] T.-C. Lu, L. A. Lessa,I. H. Kim, and T. H. Hsieh, PRX Quantum 3, 040337 (2022).
  * Tantivasadakarn  _et al._ [2022] N. Tantivasadakarn, A. Vishwanath, and R. Verresen, arXiv:2209.06202 (2022).
  * Balasubramanian  _et al._ [2022] V. Balasubramanian, P. Caputa, J. M. Magan,and Q. Wu, Phys. Rev. D 106, 046007 (2022).
  * Fujii  _et al._ [2022] M. Fujii, R. Kutsuzawa,Y. Suzuki, Y. Nakata, and M. Owari, arXiv:2205.14667 (2022).
  * Haferkamp [2023] J. Haferkamp, On the moments of randomquantum circuits and robust quantum complexity (2023),internal note.
  * Verstraete and Cirac [2006] F. Verstraete and J. I. Cirac, Phys. Rev. B 73, 094423 (2006).
  * Rajabpour [2015] M. A. Rajabpour, Phys. Rev. B 92, 075108 (2015).
  * Numasawa  _et al._ [2016] T. Numasawa, N. Shiba,T. Takayanagi, andK. Watanabe, JHEP 2016(77).
  * Antonini  _et al._ [2022] S. Antonini, G. Bentsen, C. Cao, J. Harper, S.-K. Jian,and B. Swingle, JHEP 2022(12), 1.
  * Sang  _et al._ [2022] S. Sang, Z. Li, T. H. Hsieh, andB. Yoshida, arXiv:2212.10634 (2022).
  * Onorati  _et al._ [2017] E. Onorati, O. Buerschaper, M. Kliesch, W. Brown,A. H. Werner, andJ. Eisert, Commun. Math. Phys. 355,905 (2017).
  * Vidal and Dawson [2004] G. Vidal and C. M. Dawson, Phys. Rev. A 69, 010301 (2004).
  * Browne  _et al._ [2008] D. E. Browne, M. B. Elliott,S. T. Flammia, S. T. Merkel, A. Miyake, and A. J. Short, New J. Phys. 10,023010 (2008).
  * Kieling and Eisert [2009] K. Kieling and J. Eisert, Percolation in quantum computation andcommunication, in  _Quantum and semi-classical percolation and breakdownin disordered solids_, Lecture Notes inPhysics (Springer, 2009)Chap. 10, pp. 287–319.
  * Kieling  _et al._ [2007] K. Kieling, T. Rudolph,and J. Eisert, Phys. Rev. Lett. 99,130501 (2007).