# Phase transitions in sampling and error correction in local Brownian
circuits

Subhayan Sahu<EMAIL_ADDRESS>Perimeter Institute for Theoretical
Physics, Waterloo, Ontario N2L 2Y5, Canada  Shao-Kai Jian<EMAIL_ADDRESS>Department of Physics and Engineering Physics, Tulane University, New Orleans,
Louisiana, 70118, USA

###### Abstract

We study the emergence of anticoncentration and approximate unitary design
behavior in local Brownian circuits. The dynamics of circuit averaged moments
of the probability distribution and entropies of the output state can be
represented as imaginary time evolution with an effective local Hamiltonian in
the replica space. This facilitates large scale numerical simulation of the
dynamics in $1+1d$ of such circuit-averaged quantities using tensor network
tools, as well as identifying the various regimes of the Brownian circuit as
distinct thermodynamic phases. In particular, we identify the emergence of
anticoncentration as a sharp transition in the collision probability at $\log
N$ timescale, where $N$ is the number of qubits. We also show that a specific
classical approximation algorithm has a computational hardness transition at
the same timescale. In the presence of noise, we show there is a noise-induced
first order phase transition in the linear cross entropy benchmark when the
noise rate is scaled down as $1/N$. At longer times, the Brownian circuits
approximate a unitary 2-design in $O(N)$ time. We directly probe the
feasibility of quantum error correction by such circuits, and identify a first
order transition at $O(N)$ timescales. The scaling behaviors for all these
phase transitions are obtained from the large scale numerics, and corroborated
by analyzing the spectrum of the effective replica Hamiltonian.

###### Contents

  1. I Introduction
    1. I.1 Main results and outline of paper
  2. II Local Brownian circuits
    1. II.1 Effective Hamiltonian description
    2. II.2 Replica permutation symmetry
    3. II.3 Effective Hamiltonian with local noise
  3. III Anticoncentration and computational hardness of sampling Brownian circuits
    1. III.1 Anticoncentration
    2. III.2 Hardness of classical simulation
  4. IV Noisy Brownian circuits
    1. IV.1 Cross-entropy benchmarking
    2. IV.2 XEB in the replica model
    3. IV.3 Noise-induced transition
    4. IV.4 Hardness of simulating noisy Brownian circuits
  5. V Quantum error correcting codes from Brownian circuits
    1. V.1 Decoupling by Random circuits
    2. V.2 Approximate error correction in Brownian circuits
    3. V.3 Numerical results in 1d
    4. V.4 Coding transitions
  6. VI Concluding remarks
  7. A Quantum Error Correcting codes generated by Brownian circuits
    1. A.1 Error correction bound with mutual purity
    2. A.2 Replica computation of mutual purity
    3. A.3 Maximal complexity encoding by Haar random circuits

##  I Introduction

Random quantum circuits (RQC) play a pivotal role in both quantum dynamics
theory and quantum information theory, offering insights into fundamental
aspects such as quantum chaos, out-of-time correlation functions, and
entanglement entropy [1, 2, 3, 4, 5]. Closely related to RQC, random tensor
network serves as a valuable tool for investigating the AdS/CFT
correspondence, a theory aiming to understand quantum gravity through quantum
entanglement [6]. Additionally, random quantum circuits find extensive
applications in quantum information theory, including quantum advantage [7, 8,
9, 10], quantum error correction [11, 12, 13], etc.

Random circuits are expected to be a toy model capturing the following
properties of generic quantum circuits: they output states of high complexity
and generate maximal entanglement between initially disconnected regions. An
important question is characterizing the time (depth) required for achieving
the high complexity. How do we characterize the complexity of random circuits?
In this work, we focus on two distinct features: anticoncentration and unitary
design.

Figure 1: We consider local Brownian circuits acting on qubits on a chain.
Averaging the replica dynamics $U\otimes U^{*}\otimes U\otimes U^{*}$ leads to
an imaginary time evolution with a local Hamiltonian in replica space,
$H_{\text{eff}}$. We can simulate this imaginary time evolution in $1+1d$
efficiently with tensor networks. We study three scenarios: anticoncentration,
noisy circuit benchmarking, and approximate unitary design (and consequently,
error correction), and find distinct quantum informational phases at different
time and noise regimes, separated by phase transitions. These results are
corroborated using large scale numerics and analyzing the spectrum of
$H_{\text{eff}}$.

Consider a circuit $C$ acts on an initial simple state (the product state of
$\ket{0}$ on all qubits) and the output state is measured in the computational
basis to obtain a distribution over measurement outcomes,
$p_{C}(s)=\left|\bra{s}C\ket{0}\right|^{2}$. Anticoncentration is the property
that $p_{C}(s)$ is well spread over all bitstrings $s$. Certifying that the
circuit is anticoncentrated is crucial in guaranteeing that the RQC simulation
is classically hard, and is a promising route towards demonstrating quantum
advantage [14, 15, 7, 9, 10].

At long enough depths, RQC has a stronger notion of complexity: it becomes an
approximate unitary design. A unitary ensemble is said to be $k-$design if it
approximates a global Haar random unitary in its first $k$ moments. In
particular, ensuring that a RQC has achieved the 2-design property is enough
for the RQC to be maximally decoupling. Consider a system $A$, initially
maximally entangled with a reference $R$, is subjected to a circuit $C$,
before being coupled to an environment $E$. The initial encoding via $C$ is
said to have the decoupling property if the joint density matrix on $R\cup E$
is approximately factorizable $\rho_{RE}\approx\rho_{R}\otimes\rho_{E}$. This
can also be associated with the RQC dynamically generating a quantum error
correcting code [11, 12, 13].

Several avenues of research on RQC have established that anticoncentration and
unitary design occur at parametrically distinct timescales. Suppose we
consider circuits with spatial local connectivity in $d$ dimensions. Past
research has shown that ensembles of RQC with Haar random local gates achieve
anticoncentration and unitary design in $O(\log N)$ [16] and $O(N^{1/d})$ [17,
18, 19] timescales, respectively, where $N$ denotes the number of qubit. Note
that both anti-concentration and 2-design property are diagnosed by non-linear
properties of the quantum state generated by the circuits. This makes
numerically simulating these properties for local Haar random circuits hard
and limited to modest system sizes and for short times. Hence, much of the
research on RQC has depended on proving analytical bounds, classically
simulable Clifford circuits, and perturbations around semi-classical limits,
such as large local Hilbert space dimensions.

In this work, we provide a minimal model which allows us to do efficient and
guaranteed numerical simulation of the quantum informational quantities
probing anticoncentration and 2-design property of large-sized random circuits
using tensor network technology. We take the approach of directly representing
the informational quantities averaged over the circuit ensemble as a linear
observable in a replicated Hilbert space. Here, replicas are simply exact
copies of the original system, and the informational observables probe the
correlation between different replicas. We study a particular ensemble of RQC,
namely local Brownian circuits [20, 21, 22, 23, 24].

These Brownian qubit models can be defined in any graph where each vertex
hosts a qubit, with nearest neighbor Brownian interaction generating the
unitary evolution. Remarkably, the real-time evolution of circuit averaged
non-linear observables of the density matrix can now be realized as imaginary
time evolution in the replica space. The Hilbert space for $k$ replicas is
simply the combination of a forward contour and a backward contour for real-
time evolution for each replica; so the local Hilbert space encompasses $2k$
spins. After averaging of Brownian couplings, the quantum dynamics reduces to
a Hermitian replica qubit Hamiltonian with the same locality properties as the
initial interaction graph. This model not only establishes a clear mapping
between various quantum information quantities and those of a quantum spin
model, but also transforms the problem of quantum dynamics into a
thermodynamic problem.

Furthermore, imaginary time evolution with local Hamiltonians is guaranteed to
be efficient in 1$d$ using simple matrix product state and Time Evolving Block
Decimation (TEBD) algorithms [25, 26, 27]. This allows us to perform large-
scale simulations of these informational quantities in $1+1$ dimensional
circuit. As an example, we can simulate the averaged Rényi-2 entanglement
properties of a Brownian circuit on $N\sim O(100)$ qubits for $t\sim O(N)$
depths in a few minutes on a standard laptop.

The effective Hamiltonian approach also provides a statistical mechanical
description of different regimes of RQC as distinct ‘phases’, separated by
phase transitions. These phases can be described within a generalized Landau
framework involving multiple replicas, where the relevant symmetry is the
replica permutation symmetry [28] (when we introduce multiple identical copies
of the system, they can be permuted amongst each other without changing the
effective description). Specifically, in the two replica scenario that we
focus on in this work, the effective Hamiltonian has a $\mathbb{Z}_{2}$
symmetry corresponding to a relative swap between the two real-time contours,
which turns out to be the relevant symmetry for non-linear observables of the
density matrix. This effective Hamiltonian is essentially a $\mathbb{Z}_{2}$
Ising model in the replica space, and the phases of quantum information and
their phase transitions are associated with the various phases and critical
properties of this Ising model.

Using large scale numerics of the Brownian circuit model we can directly probe
the dynamical properties of the quantum informational quantities, and identify
the saturation to anticoncentration (at $\sim\log N$ depth) and 2-design
property (at $\sim N$ depth) of the RQC as sharp transitions, confirmed by
careful finite-size scaling of the numerical data. This can be understood
analytically by investigating the spectral properties of the effective
Hamiltonian. The anticoncentration transition can also be directly associated
with a transition in the computational hardness of classically simulating the
output distribution. To show this, we show that a specific algorithm for
simulating the output distribution [29] undergoes a hardness transition in
$\sim\log N$ depth.

In order to study the 2-design transition, we focus on investigating the
feasibility of the Brownian circuit as a quantum error-correcting code, by
directly simulating a quantity akin to the mutual information between the
reference and environment in the decoupling setup, named ‘Mutual Purity’ [30].
The mutual purity is a 2-replica quantity, and has recently been shown to
provide a bound for the error correction capabilities of RQC in [30]. We show
that the mutual purity undergoes a first order transition in $O(N)$ time,
after which the Brownian circuit approximates the global Haar random unitary
for coding purposes. This coding transition is a first order pinning
transition, driven by boundary conditions determining the mutual purity, akin
to [13]. Furthermore, the mutual purity contributes to a bound for the failure
probability for correcting errors after the encoding by the RQC. By
numerically computing the mutual purity for different error models after the
2-design transition, we can also find a first order threshold transition for
the code distance.

As mentioned earlier, sampling of RQC outcome states is one of the most
promising routes towards demonstration of quantum advantage in near term
quantum devices [14, 7, 9, 10, 15]. However, real quantum devices suffer from
noise. In order to benchmark that the noisy quantum device, an estimate of the
fidelity of the output state is desirable. One proposal for an efficient
estimate for the fidelity is the linear cross-entropy benchmark
$\chi_{\text{XEB}}$, and a high score in this benchmark suggests that the RQC
simulation is classically hard [14]. However, it has recently been understood
that with local noise models, there is a noise-induced phase transition (NIPT)
in the linear cross entropy benchmarking [8, 31, 32, 33]. In the weak noise
regime, $\chi_{\text{XEB}}$ provides a reliable estimate of fidelity, and in
the strong noise regime, it fails to accurately reflect fidelity. Furthermore,
this implies that in the strong noise regime, classical simulation can yield a
high score in the cross-entropy benchmark [34, 35], without necessarily
solving the sampling task. The noise model can be incorporated in our Brownian
circuit setup, where the noise serves as an explicit replica-permutation
symmetry breaking field [36]. Using a combination of numerical and analytical
tools, we characterize the NIPT in benchmarking by identifying it as a first
order phase transition in the effective Hamiltonian picture.

###  I.1 Main results and outline of paper

Table 1: The transition point, nature of the transition, and the asymptotic
scaling for various information quantities for the Brownian circuit are shown
in this table.

We first briefly summarize the results of the paper. The main results of the
paper are represented in Fig. 1 and Table 1.

  * •

Anticoncentration: We probe anticoncentration in the $1+1$d Brownian circuit
$U$ by computing the ‘collision probability’ [16], defined as the circuit
averaged probability that two independent samples of the RQC (acting on the
$\ket{0^{\otimes N}}$ state of $N$ qubits) produce the same result, defined as
$Z=\mathbb{E}\sum_{x}\left|\bra{x}U\ket{0^{\otimes N}}\right|^{4}$, where the
averaging $\sim\mathbb{E}$ is done over all realizations of the circuit.

In the context of the effective Ising Hamiltonian ($H_{\text{eff}}$)
description, we demonstrate that $Z$ equates to the transition probability
between an imaginary-time evolved state from the initial state and a quantum
paramagnetic state (defined in a later section). The imaginary time evolution
gradually projects the initial state onto the ground state of
$H_{\text{eff}}$, which corresponds to $Z\sim 2^{-N}$. However, in finite time
$t$, excited states contributions result in $Z=2^{-N}+S_{\Delta}e^{-\Delta
t}$, where $\Delta$ ($S_{\Delta}$) denotes the energy gap (entropy) of the
excitation 111In a one-dimensional chain with local couplings, the elementary
excitation manifests as a domain wall, with a finite gap independent of the
system size and an entropy proportional to the system size. The
anticoncentration transition, thus occurs at $t=\frac{1}{\Delta}\log
S_{\Delta}\sim\log N$, representing a depth-induced computational transition.
The $\log N$ results arise from the nature of the elementary excited states of
the Ising model, and can be confirmed by direct large scale simulation of the
imaginary time evolution.

  * •

Computational Hardness transition: We probe the computational hardness of
classically simulating the probability distribution in the measurement outcome
in the earlier setup, i.e. $p_{U}(x)=\left|\bra{x}U\ket{0^{\otimes
N}}\right|^{2}$. By studying the Rényi-2 version of conditional mutual
information (CMI) of $p_{U}(x)$ using numerics of the imaginary time
evolution, we probe the hardness of a specific classical algorithm (‘Patching
algorithm’) for approximately simulating the output distribution as introduced
in [29]. We find that the CMI undergoes a phase transition at $O(\log N)$
time, with the same scaling behavior as the collision probability, signalling
a computational hardness phase transition at the same depth.

  * •

Phase transition in cross-entropy benchmarking of noisy Brownian circuits:
Here we consider the following setup of two copies of the Brownian circuit,
one that is affected by noise (denoted by the noisy channel $\mathcal{N}$),
and the other copy undergoes the noise-free Brownian circuit. We can now
update the effective Hamiltonian with explicit noise in one of the replicas,
$H_{\text{eff}}\to H_{\text{eff}}^{\prime}$. We can compute the fidelity
$F=\text{Tr}[\mathcal{N}(\rho)\rho]$ of the noisy simulation by doing
imaginary time evolution with $H_{\text{eff}}^{\prime}$ (with local noise
models, $H_{\text{eff}}^{\prime}$ remains local). We also compute the linear
cross entropy benchmark, defined as
$\chi_{\text{XEB}}=2^{N}\sum_{x}p(x)q(x)-1$, where $p(x)$ and $q(x)$ represent
the output distribution in the noise-free and the noisy cases respectively
[14].

In $H_{\text{eff}}^{\prime}$, noise explicitly breaks the Ising symmetry and
subsequently pins the Ising spins. Consider a local (unital) noise model, with
$\lambda$ strength for each qubit (to be explicitly defined later). Noise
generically undermines the ferromagnetic phase that leads to
anticoncentration, and leads to erosion of the quantum advantage. This holds
true for constant rate noise $\lambda\sim O(1)$. Through the mapping to the
quantum Ising model, we discover that noise behaves as a relevant perturbation
with a scaling dimension of one. Therefore, when the noise rate scales
inversely with respect to the size of the chain, $\lambda\sim 1/N$, we get a
noise-induced computational transition at some critical $\lambda^{*}\sim
O(1/N)$. This transition essentially resembles a field-induced first-order
transition and conforms to finite size scaling with $\nu=1/2$, which we
confirm numerically. Moreover, if the rate scales less (greater) than $1/N$,
the noise is deemed irrelevant (relevant). This result is consistent with
recent results on Noise-induced phase transitions in cross entropy
benchmarking [8, 32, 31].

We also study whether this transition signals a transition in the
computational hardness in the simulation of noisy Brownian circuits. By
studying the Rényi-2 CMI of $p_{\mathcal{N}(U)}(x)$, we find that it does not
undergo a hardness transition with depth for large enough depths, and actually
exponentially decays with time. This suggests that the $1+1$d noisy random
circuits are efficiently simulable in the long-time limit, even in the
presence of infinitesimal scaled noise.

  * •

Coding transitions: We encode some local information (a reference qubit $R$)
in the entire system $A$ using the Brownian circuit, and probe the
effectiveness of this encoding as a quantum error correcting code. After
encoding, the state on $A$ is affected by noise, which can be identified as a
unitary coupling with the environment $E$. Mutual purity $\mathcal{F}_{RE}$
[30] is a two replica quantity which upper bounds the trace distance between
the initial encoded state and the error affected encoded state after error
correction using a recovery channel [38, 39].

From the effective Hamiltonian perspective, the mutual purity can be
represented as a transition probability between two ferromagnetic states. In
particular, we find that at short times the mutual purity decays
exponentially, which can be identified with domain wall configurations pinned
between the initial and final states; while after $t\sim O(N)$ time the domain
walls get depinned, resulting in the saturation of the Mutual Purity to a
global Haar value, i.e. realizes an approximate 2-design. Using large-scale
numerics, we are able to directly probe this transition to a 2-design as a
first order depinning transition. Furthermore, since the mutual purity
determines the feasibility of error correction after the application of noise,
we find a first order threshold transition in the fraction of qubits which are
affected by noise. The critical fraction can be identified as a lower bound
for the ‘code distance’ of the Brownian circuit as a quantum error correcting
code.

The paper is organized as follows. Section II presents an introduction to the
Brownian circuit model and a derivation of the effective Hamiltonian for $k=2$
replicas. In section II.2, we describe the symmetries of the effective
Hamiltonian, and provide heuristic description of the phase diagrams. In
section III we discuss the anticoncentration and computational hardness
transition. In section IV we investigate the noise-induced phase transition in
benchmarking noisy Brownian circuits. In section V we study the error-
correcting properties of the Brownian circuit and probe the transition to an
approximate 2-design. We conclude by discussing the implications of this work
and future directions in section VI.

##  II Local Brownian circuits

We consider a Brownian circuit on $N$ qubits in a chain, with the Hamiltonian

$\displaystyle H_{t}=\sum_{\langle
i,j\rangle}^{N}\sum_{\alpha,\beta}J_{t,ij}^{\alpha\beta}\
\sigma_{i,\alpha}\sigma_{j,\beta},$ (1)

where $\alpha,\beta$ label the Pauli indices of the local Pauli matrices
$\sigma_{i}$, interacting between nearest neighbor pairs $\langle i,j\rangle$.
$J_{t,\alpha\beta}$ is a normal random variable uncorrelated in time, defined
via the following properties

$\displaystyle\mathbb{E}\left[J_{t,ij}^{\alpha\beta}\right]=0$
$\displaystyle\mathbb{E}\left[J_{t,ij}^{\alpha\beta}J_{t^{\prime},ij}^{\alpha^{\prime}\beta^{\prime}}\right]=\frac{J\delta_{tt^{\prime}}}{\delta
t}\delta_{\alpha\alpha^{\prime}}\delta_{\beta\beta^{\prime}}.$ (2)

$\mathbb{E}$ denotes the average according to the distribution.

###  II.1 Effective Hamiltonian description

We integrate over the random couplings to get an effective Hamiltonian in the
replica space. To this end, let’s first consider a unitary evolution of a
density matrix, $\rho^{\prime}=U\rho U^{\dagger}$. Explicitly writing out the
indices, it is

$\displaystyle\rho^{\prime}_{a^{\prime}b^{\prime}}=\sum_{a,b}U_{a^{\prime}a}\rho_{ab}U^{\dagger}_{bb^{\prime}}=\sum_{a,b}U_{a^{\prime}a}U^{\ast}_{b^{\prime}b}\rho_{ab}.$
(3)

In the second term, we transpose $U^{\dagger}$, and use the fact that
$(U^{\dagger})^{T}=U^{\ast}$. Viewed as a tensor, the time evolution can be
expressed by an operator $U\otimes U^{\ast}$ acting on a state
$\sum_{ab}\rho_{ab}|a\rangle\otimes|b\rangle$. This is essentially the
Choi–Jamiołkowski isomorphism (the operator-state mapping) [40, 41]. Now we
can extend this to two replicas. Since most of our discussion is focused on
two replicas, we derive an effective Hamiltonian for two replicas. Notice that
it is straightforward to generalize the derivation to $k$ replicas and to
arbitrary number of qubits on each node [24]. Because the random couplings at
different time are uncorrelated, the central quantity is the instantaneous
time evolution (for a small time interval $\delta t$) operator for the four
contours,

$\displaystyle U_{1}(\delta t)\otimes U_{2}(\delta t)^{\ast}\otimes
U_{3}(\delta t)\otimes U_{4}(\delta t)^{\ast},$ (4)

where $U_{a}$, $a=1,2,3,4$ denotes the unitary evolution operator generated by
the Brownian spin Hamiltonian $U_{a}(\delta t)=e^{-i\delta tH_{t,a}}$ acting
on the four Hilbert spaces. It includes two replicas, each of which contains a
forward contour $a=1,3$ and a backward contour $a=2,4$. The complex conjugate
is due to the Choi–Jamiołkowski isomorphism, as demonstrated above.

The average over the random coupling reads

$\displaystyle\mathbb{E}\left[U_{1}(\delta t)\otimes U_{2}(\delta
t)^{\ast}\otimes U_{3}(\delta t)\otimes U_{4}(\delta t)^{\ast}\right]$
$\displaystyle=$ $\displaystyle\int DJP[J]\exp\left(\sum_{a}(-i)^{a}\delta
t\sum_{\langle
i,j\rangle}\sum_{\alpha,\beta}J_{t,ij}^{\alpha\beta}\tau_{i,a}^{\alpha}\tau_{j,a}^{\beta}\right),$

where $\tau_{i,1}^{\alpha}=\tau_{i,3}^{\alpha}=\sigma_{i}^{\alpha}$, and
$\tau_{i,2}^{\alpha}=\tau_{i,4}^{\alpha}=(\sigma_{i}^{\alpha})^{\ast}$,
$\alpha=1,2,3$. Here $\sigma^{\alpha}$ denotes the Pauli matrix, and the
complex conjugate for the $a=2,4$ contour is due to the backward evolution.
$DJ=\prod_{\langle i,j\rangle}\prod_{\alpha,\beta}dJ_{t,ij}^{\alpha\beta}$,
and $P[J]$ denotes the Gaussian distribution specified by (II). Integrating
over the random couplings results in an effective Hamiltonian,

$\displaystyle\mathbb{E}\left[U_{1}(\delta t)\otimes U_{2}(\delta
t)^{\ast}\otimes U_{3}(\delta t)\otimes U_{4}(\delta
t)^{\ast}\right]=e^{-\delta tH_{\text{eff}}},$ (6)

with

$\displaystyle H_{\text{eff}}=\frac{J}{2}\sum_{\langle
i,j\rangle}\sum_{a,b}(-1)^{a+b}(\vec{\tau}_{i,a}\cdot\vec{\tau}_{i,b})(\vec{\tau}_{j,a}\cdot\vec{\tau}_{j,b}).$
(7)

This Hamiltonian describes a spin chain with four spins per site, denoted by
$\vec{\tau}_{i,a}$, $a=1,2,3,4$. In the following, we will see that this
Hamiltonian can describe various information phases and phase transitions,
such as dynamical computational transition, error correcting transition, etc.
Similarly, for a finite time evolution, we have

$\displaystyle\mathbb{U}\equiv\mathbb{E}\left[U_{t}\otimes U_{t}^{\ast}\otimes
U_{t}\otimes U_{t}^{\ast}\right]=e^{-H_{\text{eff}}t}.$ (8)

Here we use $U_{t}=e^{-\int dtH_{t}}$ to denote the unitary generated by the
Brownian circuit for a time interval $t$.

#### Numerical Implementation

We simulate imaginary time evolution in the replica Hilbert space using the
TEBD algorithm. The local Hilbert space is $\mathbb{C}_{2}^{\otimes 4}$,
reflecting the two replicas and two time contours per replica. To simulate
$\exp\left(-tH_{\text{eff}}\right)$ we now need to Trotterise the TEBD
evolution with $\Delta t$ as the time step, we take the energy-scale
$J=1/\Delta t$. This ensures that $\Delta t\cdot H_{\text{eff}}$ is
dimensionless with the energy scale set to $1$, and with the evolved time $t$
as non-negative integers. All calculations are performed using the TeNPy
Library [42].

###  II.2 Replica permutation symmetry

The Hamiltonian Eq. 7 is invariant under replica re-labelings, and has the
symmetry group,

$\displaystyle\left(S_{2}\times S_{2}\right)\rtimes\mathbb{Z}_{2},$ (9)

where $S_{2}\times S_{2}$ is the permutation group on the two replica labels.
The outer $\mathbb{Z}_{2}$ arises from the symmetry of shuffling between the
two time-conjugated copies after taking the complex conjugation 222Note that
since the variance of coupling is independent of $\alpha=x,y,z$, the resulted
Hamiltonian also enjoys a $SU(2)$ symmetry for each site. But our results do
not rely on this symmetry.. Put simply, each of the $S_{2}$ transformation
swaps $\tau_{i,1}^{\alpha}\leftrightarrow\tau_{i,3}^{\alpha}$ or
$\tau_{i,2}^{\alpha}\leftrightarrow\tau_{i,4}^{\alpha}$, whereas the
$\mathbb{Z}_{2}$ exchanges
$\tau_{i,1}^{\alpha}\leftrightarrow\tau_{i,2}^{\alpha}$ and
$\tau_{i,3}^{\alpha}\leftrightarrow\tau_{i,4}^{\alpha}$ simultaneously.

It is easy to see that the Hamiltonian can be brought into a sum of squares,

$\displaystyle H_{\text{eff}}=\frac{J}{2}\sum_{\langle
i,j\rangle}\sum_{\alpha,\beta}\left(\sum_{a}(-1)^{a}\tau_{i,a}^{\alpha}\tau_{j,a}^{\beta}\right)^{2}.$
(10)

Therefore, the eigenvalues are no less than zero. Two ground states are
$|\text{id}\rangle\rangle^{\otimes N}$ and
$|\text{swap}\rangle\rangle^{\otimes N}$, where

$\displaystyle|\text{id}\rangle\rangle$ $\displaystyle=$
$\displaystyle\frac{1}{2}(|0000\rangle+|0011\rangle+|1100\rangle+|1111\rangle),$
$\displaystyle|\text{swap}\rangle\rangle$ $\displaystyle=$
$\displaystyle\frac{1}{2}(|0000\rangle+|1001\rangle+|0110\rangle+|1111\rangle).$
(11)

Here, we use $\left|0\right>$ and $\left|1\right>$ to denote $\pm$ eigenstates
of the $\sigma_{z}$ Pauli operator. The name of the state indicates that
$\left|\text{id}\right>\rangle$ is a product of an EPR state of the first and
second spins and an EPR state of the third and fourth spins, and
$\left|\text{swap}\right>\rangle$ is a product of an EPR state of the first
and fourth spins and an EPR state of the second and third spins. Using the
properties of EPR pairs, namely,
$\tau_{1}|\text{id}\rangle\rangle=\tau_{2}|\text{id}\rangle\rangle$,
$\tau_{3}|\text{id}\rangle\rangle=\tau_{4}|\text{id}\rangle\rangle$,
$\tau_{1}|\text{swap}\rangle\rangle=\tau_{4}|\text{swap}\rangle\rangle$,
$\tau_{2}|\text{swap}\rangle\rangle=\tau_{3}|\text{swap}\rangle\rangle$ we can
see that every square in the Hamiltonian vanishes, so that these two states
are ground states with zero energy.

The permutation symmetry is spontaneously broken by the ground state, and when
the low-energy physics is concerned, our model is essentially equivalent to an
Ising model. Notice that we can organize the permutation transformation such
that one of them permutes the second and the fourth spins (we denote this by
$S_{2}^{r}:\tau_{i,2}^{\alpha}\leftrightarrow\tau_{i,4}^{\alpha}$), while the
other permutes both the first and the third spins as well as the second and
the fourth spins. Then $S_{2}^{r}$ can transform one ground state to the
other, and only $S_{2}^{r}$ is spontaneously broken.

Our model Eq. 6 transforms the real-time evolution along the four contours
into an imaginary-time evolution that progressively projects onto the ground
state subspace of the Hamiltonian described in Eq. 7. This imaginary-time
evolution allows us to capture the dynamics of several important quantum
information quantities. One such quantity is the collision probability, which
measures the degree of anticoncentration and corresponds in the replica model
to the overlap between the time-evolved state and a final state (to be
specified later). The magnitude of this overlap is determined by the
excitation gap present in the Hamiltonian Eq. 7. In one-dimensional systems,
the elementary excitation takes the form of domain walls, which possess a
finite energy gap and exhibit logarithmic entropy. As a result, the process of
anticoncentration requires a timescale proportional to $\log N$, where $N$
represents the system size.

###  II.3 Effective Hamiltonian with local noise

Since we would also like to investigate the effect of quantum noise, we now
consider imperfect time evolution due to the presence of quantum errors. The
unitary time evolution operators are replaced by a quantum channel. A local
depolarization channel is given by

$\displaystyle\rho\rightarrow(1-\lambda)\rho+\frac{\lambda}{3}\sum_{\alpha=1,2,3}\sigma_{i}^{\alpha}\rho\sigma_{i}^{\alpha},$
(12)

where $0\leq\lambda<3/4$ for complete positivity.

Using the operator-state mapping, this can be mapped to,

$\displaystyle\mathcal{N}_{i}^{\text{depol}}(\lambda)$ $\displaystyle=$
$\displaystyle(1-\lambda)I^{\otimes
2}+\frac{\lambda}{3}\sum_{\alpha=1,2,3}\sigma_{i}^{\alpha}\otimes(\sigma_{i}^{\alpha})^{\ast},$
(13)

where $I$ denotes the identity operator.

The noise can induce a transition of random circuit sampling [8, 31]. An
observable of such a transition is the cross-entropy benchmarking (XEB), which
we will describe in detail later. For now, let us just mention that XEB
contains two distributions: one from a noiseless quantum circuit, and the
other from a noisy quantum circuit. Therefore, we are again concerned with
only two replicas. Without loss of generality, we assume the noisy replica is
described by the first two contours $a=1,2$ and the noisy replica is described
by the last two contours $a=3,4$. We upgrate the quantum channel into

$\displaystyle\mathcal{N}_{i}^{\text{depol}}(\lambda)\rightarrow\mathcal{N}_{i}^{\text{depol}}(\lambda)\otimes
I\otimes I.$ (14)

The identity operators for the last two Hilbert space is clear since the
second replica is noiseless. Thus, the noise occurs for the first replica with
the first and second copies of the Hilbert space.

It is not hard to see that the channel can be equivalently described by a
perturbation described by the following effective Hamltonian,

$\displaystyle H_{\text{depol}}(\lambda)=\frac{3}{4\delta
t}\log(\frac{1}{1-\frac{4}{3}\lambda})\sum_{i}\left(1-\frac{1}{3}\sum_{\alpha}\tau_{i,1}^{\alpha}\tau_{i,2}^{\alpha}\right).$
(15)

Here, we assume the noise occurs at each site with the same strength. Since
$0\leq\lambda<\frac{3}{4}$ for the depolarizing channel, the prefactor is
positive.

Essentially, the perturbation explicitly breaks the permutation symmetry. The
state $\left|\text{id}\right>\rangle^{\otimes N}$ is still an eigenstate of
these two perturbations with eigenvalue zero, whereas, the state
$\left|\text{swap}\right>\rangle^{\otimes N}$ obtains a finite positive
energy, i.e.,

$\displaystyle\langle\left<\text{swap}\right|^{\otimes
N}H_{\text{depol}}(\lambda)\left|\text{swap}\right>\rangle^{\otimes
N}=\frac{3N}{4\delta t}\log(\frac{1}{1-\frac{4}{3}\lambda}).$ (16)

Therefore, the presence of noise effectively lifts the degeneracy between the
two ground states and biases the system towards the state
$\left|\text{id}\right>\rangle^{\otimes N}$. In the regime of low-energy
physics, the noise can be treated as an external field that explicitly breaks
the Ising symmetry and favors a particular state. For notation simplicity, we
denote the local Zeeman energy as $\epsilon$. For the depolization channel,
the effective Zeeman energy is $\epsilon=\frac{3}{4\delta
t}\log(\frac{1}{1-\frac{4}{3}\lambda})$. When $\lambda$ is small, we can
deduce that $\epsilon\approx\frac{\lambda}{\delta t}$. Note that $\lambda$ is
dimensionless and $\delta t$ is the unit of energy.

In the symmetry breaking phase, the external field acts as a relevant
perturbation with a scaling dimension of one. Consequently, a first-order
transition occurs at an infinitesimally small noise strength, which is
independent of the system size. However, if the noise strength is
appropriately scaled down by a factor of $1/N$, which compensates for its
relevant scaling dimension, the transition can take place at a finite, size-
dependent noise strength given by $\epsilon\sim 1/N$. This noise-induced
transition also manifests as a first-order phase transition. The first-order
transition exhibits a finite size scaling, and is distinguished from a second-
order transition [44]. We will confirm it via a systematic finite size
scaling.

##  III Anticoncentration and computational hardness of sampling Brownian
circuits

###  III.1 Anticoncentration

It is well-known that random circuits generate output states that are anti-
concentrated, which roughly means that the probability distribution of the
classical bitstrings generated by measuring the output state of a random
circuit in the computational basis, is well spread out and not concentrated on
a few bit-strings. Naturally, this also implies that classical sampling of
these bitstrings will be hard. Two key ingredients underpin random circuit
sampling. Firstly, anticoncentration asserts that the distribution deviates
only slightly from a uniform distribution. This property is typically required
in hardness proofs. However, anticoncentration can be easily attained by
applying a Hadamard gate to all qubits. Therefore, we need the second
ingredient, randomness, to eradicate any discernible structure in the circuit.
Given that randomness is inherent in our model, we are intrigued by whether
the distribution exhibits anticoncentration and, if so, at what time (depth)
it occurs. This indicates a transition in computational complexity, wherein
the system shifts from a region that is easily achievable by classical means
to a region that becomes challenging for classical algorithms.

When the random circuits are generated by a particular ensemble of local
quantum gates, a key diagnostic of the complexity of the ensemble is the time
it takes to anti-concentrate the output states. Concretely, we can compute the
collision probability, which is defined as the probability that the
measurement outcomes of two independent copies of the random circuit agree
with each other, i.e. $\sum_{s}p_{U}(s)^{2}$, where
$p_{U}(s)=\left|\bra{s}U\ket{0}\right|^{2}$, for a given bitstring $s$. We are
interested in the ensemble averaged collision probability which can be readily
expressed as transition amplitude in the replicated dynamics,

$\displaystyle Z$
$\displaystyle=\mathbb{E}_{J}\sum_{s}p_{U}(s)^{2}=\sum_{s}\langle\langle
s^{\otimes 4}|\mathbb{U}|0^{\otimes 4}\rangle\rangle,$ (17)

where $\mathbb{U}=\mathbb{E}\left[U_{t}\otimes U_{t}^{\ast}\otimes
U_{t}\otimes U_{t}^{\ast}\right]$ can be represented by an imaginary time
evolution with a replica Hamiltonian defined in Eq. 7.

We identify the circuit to have reached anti-concentration if $Z\approx
c2^{-N}$ and to not have anti-concentration if $Z\geq e^{N^{c}}2^{-N}$ for
some $O(1)$ constant $c$.

Figure 2: Anticoncentration in Brownian circuit: In (a) we show that $Z\sim
2^{-N}$ in $t/\log N=\tau^{*}\approx 1.5$ time. In (b) we show the data
collapse, which is consistent with Eq. 18

In Fig. 2 we study the averaged collision probability in a 1d Brownian circuit
by the tensor network simulations. We find that the Brownian circuit anti-
concentrates in $\log{N}$ depth, which is consistent with the fact that local
Haar random circuits anti-concentrate in $\Omega(\log N)$ depth in 1d [16].
Furthermore, in Fig. 2b, we show data collapse which is consistent with the
following approximate form for the collision probability,

$\displaystyle 2^{N}Z=2+c_{1}e^{-c_{2}(t-\tau^{*}\log N)},$ (18)

for some $O(1)$ constants $c_{1}$ and $c_{2}$. This expression can be
justified by the effective Hamiltonian picture as follows.

Because $\mathbb{U}=e^{-Ht}$, with $H$ given by Eq. 7, it effectively projects
the initial state $\left|0^{\otimes 4}\right>\rangle$ to the ground state
$2^{N}\mathbb{U}\left|0^{\otimes
4}\right>\rangle\approx\left|\text{id}\right>\rangle^{\otimes
N}+\left|\text{swap}\right>\rangle^{\otimes N}+\text{excitations}$. The
leading contribution of excitations is given by a single domain wall (since we
have used open boundary condition, a single domain wall is allowed),
$\left|\text{DW}_{k}\right>\rangle\approx\left|\text{swap}\right>\rangle^{\otimes
k}\otimes\left|\text{id}\right>\rangle^{\otimes(N-k)}$, $k=1,...,N-1$.
Therefore, the multiplicity of such an excitation is proportional to $N$. The
excitation energy $\Delta$, on the other hand, is a constant independent of
$N$, and it contributes to an exponential function $e^{-\Delta t}$. Therefore,
according to this picture, the prediction for the collision probability reads

$\displaystyle 2^{N}Z\approx 2+Ne^{-\Delta
t}=2+e^{-\Delta(t-\frac{1}{\Delta}\log N)},$ (19)

where we have noticed that
$\sum_{s}\langle\left<s|\text{id}\right>\rangle=\sum_{s}\langle\left<s|\text{swap}\right>\rangle=\sum_{s}\langle\left<s|\text{DW}_{k}\right>\rangle=1$.
This result is consistent with the data collapse. In particular, it is clear
that the transition time $\log N$ is due to the entropy of the domain wall
excitation.

###  III.2 Hardness of classical simulation

As a consequence of anticoncentration and randomness, classical simulation of
the output probabilities of the Brownian circuits after $\log N$ depth is
expected to be hard. In this section, we show that, with respect to a
particular algorithm for approximate classical simulation, there is a
computational hardness transition at $t\sim\log N$ depth.

We study the computational hardness of the Patching algorithm introduced in
[29, 45]. Heuristically, the algorithm attempts to sample from the marginal
probability distribution of spatially separated patches, and then combine the
results together. This succeeds in $poly(N)$ time if the output distribution
of the state generated by the circuit has decaying long-range correlations.
Without going into the details of the algorithm itself, we study the condition
on the long-range correlations for which the algorithm is expected to
successfully sample from the output distribution.

Consider a tripartition of $N$ qubits into $A\cup B\cup C$, such that
$dist(A,C)\geq l$. For the output probability distribution
$p_{U}(s)=\left|\bra{s}U\ket{0}\right|^{2}$, we consider the conditional
mutual information between the regions $A$ and $C$ conditioned on $B$, as in
$I(A:C|B)_{p}=S(AB)_{p}+S(BC)_{p}-S(B)_{p}-S(ABC)_{p}$, where the $S(A)$
refers to the entropy of the marginal distribution of $p$ on the region $A$.
The output distribution is defined to have $f(l)-$ Markov property if
$I(A:C|B)_{p}\leq f(l)$.

We quote the main Theorem about the condition for successful Patching
algorithm from [29]:

######  Theorem.

Patching algorithm succeeds in $poly(N)$ time to sample from a probability
distribution arbitrarily close in total variation distance to the exact output
distribution $p_{U}(s)$ of a quantum circuit on $N$ qubits, if $p_{U}(s)$ has
$e^{-\Omega(l)}$ Markov property, for a suitable choice of the length-scale
parameter $l$.

Figure 3: Phase transition in the Rényi-2 CMI of $p_{U}(s)$: Consider an equal
tripartition of the spin chain such that $|A|=|B|=|C|=N/3$, with $B$
separating the regions $A$ and $C$, and we plot Rényi-2 CMI $I^{(2)}(A:C|B)$
in (a) and (b). As $N$ is increased, for $t<\tau^{*}\log N$ ($\tau^{*}\approx
1.2$), the CMI decays with $N$ as $\sim e^{-N}$. For larger times
$t>\tau^{*}\log N$ the CMI doesn’t decay with $N$ and asymptotes to $\log 2$.

In the local Brownian circuits introduced earlier, we can directly compute the
averaged Rényi-2 version of the conditional mutual information (CMI) of the
output distribution $p_{U}(x)$, i.e.
$I^{(2)}(A:C|B)_{p}=S^{(2)}(AB)_{p}+S^{(2)}(BC)_{p}-S^{(2)}(B)_{p}-S^{(2)}(ABC)_{p}$,
as a function of time $t$. In Fig. 3a and b, we study the Rényi-2 CMI for an
equal tripartition of the qubit chain (i.e. $|A|=|B|=|C|=N/3$), and find that
there is a transition at $\log N$ depth. In particular, at long times,
$I^{(2)}(A:C|B)_{p}$ asymptotes to $\log 2$, indicating long-range
correlations in the output probability distribution. At short times, the data
is consistent with $I^{(2)}(A:C|B)_{p}\sim O(e^{-N})$. There is, furthermore,
a sharp transition at $t\sim\tau^{*}\log N$ at $\tau^{*}\approx 1.2$. The data
collapses as a function of $t-\tau^{*}\log N$ as shown in Fig. 3b inset,
indicating the same statistical mechanical interpretation as the collision
probability. Even though this result is for the Rényi-2 version of the CMI,
and not the actual CMI itself, it provides evidence that the anticoncentration
transition corresponds to an actual phase transition in computational hardness
of classical estimation of the output probabilities of the random circuit.

##  IV Noisy Brownian circuits

Random circuit sampling is widely implemented in experiments to show quantum
advantage. However, sufficiently large noise can diminish the quantum
advantage. It was reported recently a noise induced phase transition in random
circuit sampling [8, 31, 32, 33]. For weak noise, the cross-entropy
benchmarking provides a reliable estimate of fidelity. Whereas, for strong
noise, it fails to accurately reflect fidelity.

###  IV.1 Cross-entropy benchmarking

In the random circuit sampling, we start from a product state
$\rho_{0}=\left|0\right>^{\otimes N}\left<0\right|^{\otimes N}$ (The initial
state does not really matter, and we choose this just for simplicity), and
evolve the state using the Brownian spin Hamiltonian. For brevity, we denote
the unitary generated by the Brownian spin model as $U$. In an ideal case,
i.e., there is no noise, the final state is

$\displaystyle\rho=U\rho_{0}U^{\dagger}.$ (20)

A measurement is performed on the computational basis, and this will generate
a probability distribution,

$\displaystyle p(s)=\langle s|\rho|s\rangle,$ (21)

where $s$ denotes the bit string.

In a real experiment, the implementation of Brownian spin Hamiltonian is not
ideal because errors can occur. In this case, the time evolution of the system
is, in general, not unitary and should be described by a quantum channel,

$\displaystyle\rho_{\text{err}}=\mathcal{N}(\rho_{0}).$ (22)

Here, $\mathcal{N}$ denotes the noise channel. The probability distribution
for a bit string $s$ is now given by

$\displaystyle q(s)=\langle s|\rho_{\text{err}}|s\rangle.$ (23)

We are interested in the cross entropy benchmarking (XEB), defined as follows,

$\displaystyle\chi_{\text{XEB}}=2^{N}\sum_{s}p(s)q(s)-1,$ (24)

where $p(s)$ is an ideal distribution (which in practice can be estimated by
classical simulations), and $q(s)$ is the probability distribution sampled
from real experiments. Since the circuit involves Brownian variables, we
consider the average over these random variables,
$\mathbb{E}(\chi_{\text{XEB}})$.

###  IV.2 XEB in the replica model

Using the operator-state mapping,

$\displaystyle\sum_{s}q(s)p(s)=\sum_{s}\langle\langle s|\mathcal{N}\otimes
U\otimes U^{\ast}|0\rangle\rangle,$ (25)

where $U$ is the unitary generated by the Brownian spin model, and
$\mathcal{N}$ denotes the channel generated by both the Brownian spin model
and the errors. For simplicity, we will denote $\mathbb{E}[\mathcal{N}\otimes
U\otimes U^{\ast}]=\mathbb{U}_{\text{err}}$. And the initial and final states
are the same as in the collision probability. Actually, the collision
probability is closely related to the noiseless XEB.

Consider imperfect time evolution due to the presence of quantum errors. To
this end, after integrating over the Brownian variable, we arrived at the
imaginary-time evolution given by

$\displaystyle\sum_{s}\langle\langle
s|\mathbb{U}_{\text{err}}|0\rangle\rangle=\sum_{s}\langle\langle
s|e^{-(H+H^{\prime}(\lambda))t}|0\rangle\rangle,$ (26)

where $H^{\prime}(\lambda)$ is the perturbation caused by the noise. The
example of dephasing and depolarizing channels are given by Eq. 15. The
average XEB then reads

$\displaystyle\mathbb{E}[\chi_{\text{XEB}}]=2^{N}\sum_{s}\langle\langle
s|e^{-(H+H^{\prime}(\lambda))t}|0\rangle\rangle-1,$ (27)

On the other hand, the average fidelity is given by

$\displaystyle\mathbb{E}[F]$ $\displaystyle=$ $\displaystyle
2^{N}\langle\langle\text{swap}|^{\otimes N}\mathbb{E}[\mathcal{N}\otimes
U\otimes U^{\ast}]|0^{\otimes 4}\rangle\rangle$ (28) $\displaystyle=$
$\displaystyle 2^{N}\langle\langle\text{swap}|^{\otimes
N}e^{-(H+H^{\prime}(\lambda))t}|0^{\otimes 4}\rangle\rangle.$ (29)

Comparing it with the XEB, we can see that the difference comes from the final
state.

As discussed before, the noise lifts the degeneracy and behaves as an external
field. We denote the local Zeeman energy by $\epsilon$. The Zeeman field is a
relevant perturbation even in the symmetry breaking phase. We will show that
the competition between one of the lifted ground state and the excited state
leads to a first-order transition at a finite noise rate $\epsilon N\sim$
const. We will also perform a finite size scaling analysis to verify such a
first-order transition in the following.

We consider the evolution of XEB as a function of time. In the long-time
limit, we expect the time-evolved state is a superposition of the ground state
with a few low-lying excitations. It can be approximately written as

$\displaystyle 2^{N}\mathbb{U}_{\text{err}}\left|0^{\otimes
4}\right>\rangle\approx\left|\text{id}\right>\rangle^{\otimes N}+e^{-N\epsilon
t}\left|\text{swap}\right>\rangle^{\otimes N}$ (30) $\displaystyle+e^{-\Delta
t}\sum_{k}e^{-k\epsilon
t}\left|\text{DW}_{k}\right>\rangle+\sum_{k}e^{-(2\Delta+\epsilon)t}\left|\text{SF}_{k}\right>\rangle$

where $\Delta$ is the local energy cost of a domain wall, and $\epsilon$ are
the local energy cost and the Zeeman energy of a local spin flip. We have
included both domain wall excitations and local spin flips,
$\left|\text{SF}_{k}\right>\rangle=\left|\text{id}\right>\rangle^{\otimes
k-1}\otimes\left|\text{swap}\right>\rangle\otimes\left|\text{id}\right>\rangle^{\otimes
N-k}$. Note that the domain wall excitation can lead to an extensive energy
cost, but we need to include them because the external field scales
$\epsilon\sim 1/N$. Therefore, the average XEB at late time is

$\displaystyle\mathbb{E}[\chi_{\text{XEB}}]$ $\displaystyle=$ $\displaystyle
e^{-N\epsilon t}+e^{-\Delta t}\sum_{k=1}^{N-1}e^{-k\epsilon
t}+Ne^{-(2\Delta+\epsilon)t},$

On the other hand, the average fidelity is

$\displaystyle\mathbb{E}[F]=e^{-N\epsilon t}.$ (32)

Actually, the fidelity is lower bounded by $2^{-N}$. This is because
$\left|\text{id}\right>\rangle^{\otimes N}$ and
$\left|\text{swap}\right>\rangle^{\otimes N}$ are orthogonal only at the
thermodynamic limit $N\rightarrow\infty$. For a finite $N$, their overlap is
$(\langle\left<\text{id}\right|^{\otimes
N})(\left|\text{swap}\right>\rangle^{\otimes N})=2^{-N}$.

It is clear that for the XEB to well estimate the fidelity, we require
$e^{-N\epsilon t}\gg e^{-\Delta t}$. If we consider the ratio between them

$\displaystyle\frac{\mathbb{E}[F]}{\mathbb{E}[\chi_{\text{XEB}}]}\approx\frac{1}{1+e^{-\Delta
t+N\epsilon t}}.$ (33)

To the leading order in $N$, there is a noise-induced phase transition at
$\epsilon_{c}=\frac{\Delta}{N}$, separating between a weak noise phase, where
the XEB well estimates the fidelity, and a strong noise phase, where they do
not match. This is consistent with the scaling dimension analysis.

###  IV.3 Noise-induced transition

In the short-time region, all kinds of excitations contribution to the XEB,
and its evolution is non-universal. A crude estimate of the XEB is given as
follows,

$\displaystyle\mathbb{E}[\chi_{\text{XEB}}]\approx(1+e^{-(2\Delta+\epsilon)t})^{N}-1.$
(34)

This estimate comes from the superposition of all possible spin flips at each
site 333For a more accurate estimate, we need to rescale $N$ by a factor
$c_{3}<1$. This is because spin flips do not interact with each other only
when they are dilute enough. . Here $\Delta$ is the effective local energy
cost of a spin flip. The XEB is exponential in the system size
$\sim\exp[Ne^{-(2\Delta+\epsilon)t}]$, but this behavior decays exponentially
fast. Then the XEB will transition to the late-time behavior. In the long-time
limit, since we are at the weak noise phase, we expect the XEB matches
fidelity. To verify this, We plot the time evolution of XEB (solid curves) and
fidelty (dahsed curves) in Fig. 4 for a fixed noise rate. At the long-time
limit, their evolution follows closely. The fact that the deviation is larger
for a bigger $N$ is because we have fixed $\epsilon$. It is also clear that
the XEB curves exhibit a crossover from a short-time non-universal region to a
long-time universal region.

In order to show the noise-induced phase transition in our replica model, we
plot the time-evolution of the XEB for different noise rates in Fig. 5a. It is
clear that when the noise rate is less than $\lambda^{\ast}\approx 0.84/N$,
the XEB tracks the fidelity very well. Here the fidelity is shown by a dashed
curve. Note also that the fidelity has a lower bound given by $2^{-N}$.

Next, to connect this to the statistical mechanical model and implement a
finite size scaling analysis, we consider scaling $t\sim N$ to feature an
equal space-time scaling. The ratio between the fidelity and XEB is plotted in
Fig. 5b for different system sizes. The crossing indicates a transition at
$\lambda^{\ast}N\approx 0.84$. The inset shows data collapse for different
sizes as a function of $(\lambda-\lambda^{\ast})N^{2}$, which shows $1/\nu=2$.

To understand this exponent, we briefly review the finite size scaling at
first-order phase transitions. The finite size scaling near a first-order
phase transition is studied in Ref. [44]. We briefly repeat the argument here.
In a classical Ising model in $d$ dimensional cube with size $L^{d}$, the
probability distribution of the magnetization $P_{L}(s)$ in the ferromagnetic
phase can be well approximated by a double Gaussian distribution

$\displaystyle P_{L}(s)\propto
e^{-(s-M)^{2}L^{d}/\chi}+e^{-(s+M)^{2}L^{d}/\chi},$ (35)

here $\chi$ denotes the susceptibility, and $M$ is the average magnetization.
To incorporate the external field, notice that the probability distribution
can be expressed as $P_{L}(s)\propto e^{-fL^{d}}$, where $f$ is the free
energy density. From the Ising transition, the free energy is given by

$\displaystyle f$ $\displaystyle=$ $\displaystyle
f_{0}+\frac{r}{2}s^{2}+\frac{u}{4}s^{4}-sH$ (36) $\displaystyle=$
$\displaystyle f^{\prime}_{0}+\frac{u}{4}(s^{2}-M^{2})^{2}-sH,$ (37)

where $H$ denotes the external field, $M=\sqrt{-\frac{r}{u}}$ is the average
magnetization when $r<0$, and $f_{0},f^{\prime}_{0}$ are unimportant
constants. If we approximate the magnetization around $\pm M$, then the double
Gaussian distribution reads

$\displaystyle P_{L}(s)\propto e^{-((s-M)^{2}-s\chi
H)L^{d}/\chi}+e^{-((s+M)^{2}-s\chi H)L^{d}/\chi},$ (38)

where $\chi=-r$. It is clear that the distribution will be shifted, and the
one near $s=M$ will be amplified. This probability distribution can serve as a
starting point for finite size scaling analysis. The external field is
equipped with scaling dimension $L^{-d}$, implying $\nu=1/d$. Now in our
analysis, the Hamiltonian Eq. 7 corresponds to a 1d quantum system or a 2d
classical Ising model, which leads to $\nu=1/2$, consistent with our scaling
data collapse in Fig. 5b.

Figure 4: In the presence of noise, there is a depth driven crossover at
$t^{*}\sim O(1)$; for $t<t^{*}$ the linear XEB $\chi\sim e^{N}$ and for
$t>t^{*}$ $\chi\sim e^{-N\epsilon t}$. We consider a constant noise strength
of $\lambda=0.01$. Figure 5: Noise driven transition for scaled noise
$\lambda\sim c/N$ In (a) we plot $\chi$ for $N=40$ and for different values of
$\lambda N$. We find that for $\lambda N\leq\lambda^{*}N\approx 0.84$ $\chi$
approximates the Fidelity $F$ after an initial fast decay. For $\lambda
N>\lambda^{*}N$, however, $\chi$ behaves differently from $F$, which results
in a sharp phase transition as shown in (b) in the order parameter $F/\chi$,
evaluated at a time $t>t^{*}=O(1)$ of initial decay. The scaling collapse is
shown in the inset.

###  IV.4 Hardness of simulating noisy Brownian circuits

As we have described, the linear cross-entropy benchmark can be described in
the 2-replica formalism, where the noise acts on only one of the replicas. In
this section we briefly comment on the hardness of classical simulation of
noisy Brownian circuits, by analysing the Rényi-2 conditional mutual
information of the output distribution $p(s)$ of the noisy circuit, as in Sec.
III.2. In this formulation the noise acts on both replicas. In Fig. 6 we plot
the Rényi-2 CMI as a function of time for two instances of weak and strong
scaled local depolarization channels, with strength $\lambda=\mu/N$ with
$\mu=0.1,2.0$ respectively. The plots show that the CMI doesn’t asymptote to
$\log 2$ as the noise-free case, and ultimately decays as $e^{-\mu t}$ without
any signature of crossing. This suggests that in the long-time limit, even in
the presence of scaled noise, the output distribution remains efficiently
estimable using the Patching algorithm [29].

Figure 6: Dynamics of the Rényi-2 CMI of the classical output distribution of
the noisy Brownian circuit for two noise levels, $\lambda=0.1/N$ and
$\lambda=2.0/N$ respectively.

These numerical results provide evidence that the noise-induced phase
transition in the linear cross-entropy benchmark does not signal a phase
transition in the hardness of classical simulability of the output
distribution of the noisy random circuits. In fact, in the presence of noise,
$1+1$d random circuits remain efficiently simulable by the Patching algorithm.

##  V Quantum error correcting codes from Brownian circuits

Random circuits scramble local information into global correlations of a
state, in a way which is inaccessible to local probes. As a result of this,
the encoded information can be protected from local noise, thereby leading to
the notion of random circuits generating quantum error correcting codes [11,
12, 13].

###  V.1 Decoupling by Random circuits

Figure 7: Unitary encoding $U_{\text{enc}}$ of reference $R$ into system $A$.
Any noise in $A$ after the encoding can be represented by a unitary operation
$U_{\text{err}}$ coupling the part of $A$ where the error acted ($A_{4}$ in
the figure), with an environment $E$.

The intuition as to why random circuits are able to dynamically generate a
quantum error correcting code comes from the decoupling principle. Consider
the setup in Fig. 7, where initial quantum information is initialized in the
entangled state between reference $R$ (code subspace) and part of the system
$A_{1}\subset A$, such that the dimensions match, $|R|=|A_{1}|$. Now $A$ is
subjected to an encoding through the random circuit $U_{\text{enc}}$. Suppose
a part of the system $A_{4}\subset A$ is subjected to a noise channel
$\mathcal{N}$. By Stinespring dilation, the noise channel can be identified as
a unitary coupling with an environment $E$, as shown in Fig. 7. If
$U_{\text{enc}}$ forms an approximate 2-design, the circuit is able to
decouple effectively [47], i.e., the environment $E$ has bounded access to the
information encoded in $R$.

Concretely, let us consider local qubit degrees of freedom, such that the
Hilbert space dimension of any set $A$ is $d_{A}=2^{|A|}$. Consider the
isometric encoding $V:\mathcal{H}_{R}\to\mathcal{H}_{A}$ generated by the
circuit $U_{\text{enc}}$, which transforms the basis vectors as follows,

$\displaystyle\ket{\phi_{i}}_{A}\equiv
V\ket{i}_{R}=U_{\text{enc}}\ket{i}_{A_{1}}\ket{0}_{A_{2}}.$ (39)

Any density matrix $\rho_{R}$ of R is encoded as $V\rho_{R}V^{\dagger}$.
Suppose the encoded state is now subjected to noise, resulting in the density
matrix $\rho_{\text{err}}=\mathcal{N}\left(V\rho_{R}V^{\dagger}\right)$. A
convenient probe is the noise-affected encoding of a maximally entangled state
between the code subspace $R$ and $A_{1}$. By introducing an auxiliary
environment $E$ the effect of the noise channel can be represented by a
unitary on the combined system and environment, $A\cup E$,

$\displaystyle\ket{\Psi^{\prime}}=\frac{1}{\sqrt{d_{R}}}\sum_{i=1}^{d_{R}}\ket{i}_{R}U_{\text{err}}\left(\ket{\phi_{i}}_{A}\ket{e_{0}}_{E}\right).$
(40)

Here, $d_{R}$ refers to the Hilbert space dimension for $R$; if the local
degrees of freedom are $q$ dimensional qudits, then $d_{R}=q^{|R|}$.

By the decoupling theorem, for $U_{\text{enc}}$ which are approximate 2
designs and small enough error, we have a factorized reduced density matrix on
$R\cup E$,
$\rho_{RE}^{\Psi^{\prime}}\approx\rho_{R}^{\Psi^{\prime}}\otimes\rho_{E}^{\Psi^{\prime}}$.
The time required by random circuits with locality to approximately form a 2
design is upper bounded by $O(N^{1/d})$ in $d$ dimensions [17, 18]. A probe of
the extent of decoupling is the mutual information [38],
$I_{\Psi^{\prime}}(R:E)=S(\rho^{\prime}_{R})+S(\rho^{\prime}_{E})-S(\rho^{\prime}_{RE})$.

A central theorem in quantum error correction is the existence of an optimal
recovery channel $\mathcal{R}$ that undoes the effect of noise
$\mathcal{R}\left(\rho_{\text{err}}\right)=\rho_{R}$, if perfect decoupling
has occurred, i.e. $I_{\Psi^{\prime}}(R:E)=0$ [38]. This can be generalized to
approximate error correction in the presence of approximate decoupling [39,
48]. In particular, the trace distance between the recovered state by a near-
optimal recovery channel $\mathcal{R}$, and any encoded state can be bounded
by the mutual information computed for $\Psi^{\prime}$,

$\displaystyle\bigg{|}\bigg{|}\mathcal{R}\left(\rho_{\text{err}}\right)-\rho_{R}\bigg{|}\bigg{|}_{1}\leq\left(I_{\Psi^{\prime}}(R:E)\right)^{1/4}.$
(41)

###  V.2 Approximate error correction in Brownian circuits

Recently [30] derived a similar bound as Eq. 41, with the right-hand side
replaced by a different entropic quantity rather than the mutual information.
Mutual information is difficult to analytically study because of the
associated replica limit in the definition of the von Neumann entropy. They
instead introduce the mutual purity of the noise-affected state in Eq. 40,
which is defined as,

$\displaystyle\mathcal{F}_{\Psi^{\prime}}(R:E)=\text{Tr}\left(\rho_{RE}^{\prime
2}-\rho_{R}^{\prime 2}\otimes\rho_{E}^{\prime 2}\right).$ (42)

They showed that for the same approximate recovery channel as [39], the trace
distance between the recovered state and the encoded state can be bounded by
the mutual purity,

$\displaystyle\bigg{|}\bigg{|}\mathcal{R}\left(\rho_{\text{err}}\right)-\rho_{R}\bigg{|}\bigg{|}_{1}\leq
d_{R}^{5/2}d_{E}^{1/2}\left(\mathcal{F}_{\Psi^{\prime}}(R:E)\right)^{1/4}.$
(43)

We provide a description of the recovery channel and the sketch of the proof
of this bound in Appendix A.1. This bound can be computed using just a two-
replica computation for local Brownian circuits in $1+1$d with the imaginary
TEBD protocol that we have introduced earlier.

###  V.3 Numerical results in 1d

Figure 8: 2-design transition in the Brownian circuit: In (a) we encode 1
qubit on the left end, and have erasures (depolarization channel of strength
$\lambda=0.75$) act on $p$ fraction of qubits on the left of the chain. (b)
The Mutual purity for the setup in (a) with $p=0.25$ is plotted as a function
of time. (c) $\mathcal{F}$ saturates to $\mathcal{F}_{\text{Haar}}\approx
O(2^{-N})$ after $t\sim O(N)$ time. We scale the time linearly with $N$ and
find that there is a transition at $t=\tau^{*}N$, with $\tau^{*}\approx 0.77$.
The scaling collapse of this transition is shown in the inset. (d) We plot the
RHS of the error correction bound of Eq. 43 for different values $p$, with the
saturated mutual purity after $t\sim N$ time of encoding by the Brownian
circuit. There is a threshold transition $p_{c}\approx 0.17$, and below this
fraction, the error is correctable. The scaling collapse of this transition is
shown in the inset. (e) The transition in the mutual purity can be related to
a first order pinning transition between two domain wall configurations
separating domains of two ordered states consistent with the boundary
conditions set by the definition of mutual purity. As described in the text,
the trace structure in the definition of mutual purity forces the boundary
state to certain ordered states. In the initial time boundary, the state is
‘swap’ ordered in the part where the reference qubit is encoded (red), and has
free boundary condition elsewhere (no ordered state). The time-like boundaries
on the left and right are also free by the open boundary condition. In the
final state, the ‘swap’ (red) part refers to the erasure errors, and the ‘id’
(blue) part refers to the partial trace in the definition of mutual purity.
Figure 9: Mutual Purity with erasures of $p=0.25$ fraction of qubits on random
locations. The data presented is averaged over 80 (20) random instances of the
erasure locations for $N=20,24,28,(32)$ chains. Figure 10: A single qubit
reference is encoded on right end of chain, while erasures of $p=0.25$
fraction of qubits on left of chain (setup shown in (a)). Only a specific
domain wall configuration (c) contributes to the mutual purity dynamics as
plotted in (b).

Using the replicated Hilbert space formalism, we can represent the mutual
purity for the $1+1$d local Brownian circuit by the following expression,

$\displaystyle\mathcal{F}^{\Psi^{\prime}}_{RE}=\langle\langle\psi_{\text{err}}|\mathbb{U}_{\text{enc}}|\psi_{\text{in}}\rangle\rangle=\langle\langle\psi_{\text{err}}|e^{-tH_{\text{eff}}}|\psi_{\text{in}}\rangle\rangle,$
(44)

where $\mathbb{U}_{\text{enc}}=\mathbb{E}\left[U_{\text{enc}}\otimes
U^{\dagger}_{\text{enc}}\otimes U_{\text{enc}}\otimes
U^{\dagger}_{\text{enc}}\right]$, and appropriately defined states
$|\psi_{\text{in}}\rangle\rangle,|\psi_{\text{err}}\rangle\rangle$ in the
replicated Hilbert space, given by,

$\displaystyle|\psi_{\text{in}}\rangle\rangle=\left(|\text{swap}\rangle\rangle-\frac{1}{2}|\text{id}\rangle\rangle\right)^{\otimes
A_{1}}\otimes|0000\rangle\rangle^{\otimes A_{2}}$ (45)
$\displaystyle|\psi_{\text{err}}\rangle\rangle=2^{N}\sum_{m,n=0}^{d_{E}-1}E_{m}E_{n}^{*}E_{n}E_{m}^{*}|\text{id}\rangle\rangle^{\otimes
A}.$ (46)

Notice that both $|\psi_{\text{in}}\rangle\rangle$
$|\psi_{\text{err}}\rangle\rangle$ are not normalized.

The operators $E_{m}$ are non-unitary operators implementing the error on the
systems $A$,

$\displaystyle U_{\text{err}}\ket{\psi}_{A}\ket{e_{0}}_{E}=\sum_{m}E^{m}_{A}.$
(47)

The derivation is provided in Appendix A.2. The replica order of the initial
state $|\psi_{\text{in}}\rangle\rangle$ reveals that the state breaks the
replica symmetry to ‘swap’ in the region $A_{1}$ (reflecting the encoded
qubit), and preserves the replica symmetry in $A_{2}$. As for the final state,
$|\psi_{\text{err}}\rangle\rangle$, the replica order is ‘id’ in the region
where the error doesn’t act, and ‘swap’ in the region where error acts.

To diagnose the error correcting properties of the Brownian circuit, we need
to take specific noise models. In this section, we focus on local
depolarization channels acting on a few qubits, say a fraction $p$ of them.
The depolarization channel of strength $\lambda$ acts on the density matrix as
follows,

$\displaystyle\mathcal{N}_{i}(\rho)=(1-\lambda)\rho+\frac{\lambda}{3}\left(\sum_{\alpha=x,y,z}\sigma_{i,\alpha}\rho\sigma_{i,\alpha}\right).$
(48)

In Fig. 8a we present the plot of the mutual purity of the $1+1$d Brownian
circuit as a function of time, where a single qubit in $R$ is encoded in the
system $A$ of size $N$. The noise model is chosen to depolarization channel of
$\lambda=0.05$ acting on $p=0.25$ fraction of qubits. It is clear from the
plot that the mutual purity initially exponentially decays, until it saturates
to the global Haar value which is $O(2^{-N})$. The time taken for the
saturation scales as $t\propto N$. In Appendix A.3 we derive the explicit
result for mutual purity with globally Haar random encoding
$\mathcal{F}_{\text{Haar}}=O(2^{-N})$. This numerical result demonstrates that
the Brownian circuit approximates a two design in $O(N)$ times, and we show in
Fig. 8b that the 2 design transition occurs after time $\tau^{*}N$, where
$\tau^{*}\sim 0.77$. The scaling collapse of the transition reveals
$\mathcal{F}/\mathcal{F}_{\text{Haar}}\sim f(t-\tau^{*}N)$.

Furthermore, we can study the mutual purity and the RHS of the quantum error
correction bound Eq. 43 for different values of $p$. In Fig. 8d we plot the
saturation value of the RHS of Eq. 43 (after the Brownian circuit has run for
$t=N$ steps) for different values of $p$ and system sizes $N$, for a single
qubit encoding, and depolarization channel of strength $\lambda=0.05$. We find
that the RHS of the error correction bound undergoes a transition at
$p^{*}\approx 0.17$, which can be identified as the threshold of this quantum
error correction code. Note the quantum error correction bound in Eq. 43
guarantees that for $p<p^{*}$ the Brownian circuit generates a quantum error
correction code whose errors are correctable using the recovery channel
outlined in Appendix A.1.

We don’t expect this threshold to be tight, as the error correction bound with
the mutual purity is expected to be looser than the bound from mutual
information. However, the numerical results strongly indicate that the quantum
error correction transition with $t$, the depth in the Brownian circuit (the
time when the circuit approximates a 2 design) and the threshold transition
both correspond to a first-order domain wall pinning transition.

###  V.4 Coding transitions

As discussed in the previous section, the mutual purity is given by the
amplitude,
$\mathcal{F}^{\Psi^{\prime}}_{RE}=\langle\langle\psi_{\text{err}}|\mathbb{U}_{\text{enc}}|\psi_{\text{in}}\rangle\rangle$.
It is convenient to view the space-time layout of the Brownian circuit as a
two-dimensional statistical model. In our setting, this is nothing but the
mapping from a $d$ dimensional quantum system to a $d+1$ dimensional classical
system. It is important to note that in the wave function
$\left|\psi_{\text{in}}\right>\rangle$, the encoded $|A_{1}|$ qubits is mapped
to a projection to $\left|\text{swap}\right>\rangle$, i.e.,

$\displaystyle\langle\left<\text{id}\right|\left(|\text{swap}\rangle\rangle-\frac{1}{2}|\text{id}\rangle\rangle\right)=0.$
(49)

Whereas the wave function of the rest $|A_{2}|$ qubits behaves as a free
boundary condition, i.e.,
$\langle\left<\text{id}|0000\right>\rangle=\langle\left<\text{swap}|0000\right>\rangle=\frac{1}{2}$.

On the other hand, $\left|\psi_{\text{err}}\right>\rangle$ can effectively
change the boundary condition on the top layer. In particular, for the single-
qubit depolarization channel at site $i$, the wave function becomes a
superposition of two spins,

$\displaystyle\left|\psi_{\text{err},i}\right>\rangle=(1-\frac{4}{3}\lambda)^{2}\left|\text{id}\right>\rangle+\frac{4}{3}\lambda(1-\frac{2}{3}\lambda)\left|\text{swap}\right>\rangle.$
(50)

Note that when $\lambda=\frac{3}{4}$, the wave function is given by
$\left|\text{swap}\right>\rangle$ only. Therefore, the statistical mechanical
picture is that in the symmetry breaking phase of the Ising model, the
boundary condition caused by the noise channel
$\left|\psi_{\text{err}}\right>\rangle$ will induce different domains in the
bulk. Namely, these are domains denoted by either ‘id’ or ‘swap’
(equivalently, the two Ising values) as shown schematically in Fig. 8(e). The
mutual purity is only nonzero when the encoded qubit is located in the ’swap’
domain.

To understand better the coding transition, we perform a finite scaling
analysis of mutual purity as a function of depth and discussion different
cases in the following.

  * •

Noisy region overlaps the encoding qubit. As shown in Fig. 8a, the reference
qubit is encoded on the left-most edge, and the noise occurs in a contiguous
region that is also on the left edge. In this case, there are many domain wall
configurations that can contribute to the mutual purity. To simplify the
discussion, we focus on two different domain walls: one ends on the bottom
layer, and the other ends on the right edge. A schematic plot of these two
domain walls is shown in Fig. 8e. It is clear that their contributions are

$\displaystyle\mathcal{F}$ $\displaystyle\sim$ $\displaystyle e^{-\Delta
t}+e^{-\Delta^{\prime}(1-p)L}$ (51) $\displaystyle=$ $\displaystyle
e^{-\Delta^{\prime}(1-p)L}(1+e^{-\Delta t+\Delta^{\prime}(1-p)L}),$ (52)

where $\Delta$ and $\Delta^{\prime}$ denote the tension of the two kinds of
domain walls respectively. $L$ is the length of the chain. In the short-time
region, the first kind of domain wall dominates, while in the long-time
region, the second kind of domain wall dominates, and it becomes time
independent. There is an exchange of dominating domain configurations, as
demonstrated in Fig. 8e. The transition time is roughly
$\frac{\Delta^{\prime}(1-p)}{\Delta}L\propto N$. This explains the behavior in
Fig. 8b and c. Replacing the contribution from the second kind of domain wall
by $\mathcal{F}_{\text{Haar}}$, we can obtain
$\mathcal{F}/\mathcal{F}_{\text{err}}=1+e^{-(\Delta
t+\log\mathcal{F}_{\text{err}})}$, which is consistent with the data collapse
performed in the Fig. 8c.

  * •

Random noisy region. In this case, the noise occurs in random positions, as
shown in Fig. 9. The picture of exchange of two kinds of domain wall
configuration is still correct. The inset of Fig. 9 shows consistent data
collapse.

  * •

Noisy region does not overlap the encoding qubit. The encoding qubit and the
noisy region is shown in Fig. 10. In the calculation, we set $\lambda=3/4$.
The boundary condition creates a domain wall at the boundary between the noisy
qubits and the noiseless qubits. Due to the causality, the back propagation of
the domain wall is constrained in an emergent light cone. Thus, the mutual
purity is zero (up to an exponentially small number of $N$) when the encoding
coding qubit is still outside the back propagating light cone of the domain
wall. Moreover, unlike in the previous case where the first kind of domain
wall that ends on the bottom can lead to a finite mutual parity, here, only
the second kind of domain wall that ends on the right boundary can have a
significant contribution to the mutual purity. This is only possible when the
back propagating light one hits the right boundary. Therefore, this indicates
a dynamical transition at a timescale that is proportional to the system size.
In Fig. 10, the crossing of mutual parity in different sizes indicates such a
transition.

We also performed the data collapse in the inset of Fig. 10. Different from
the previous two cases, the scaling is given by $(t-\tau^{\ast}N)/\sqrt{N}$.
To understand this, note that the ‘id’ domain back propagates to the light
cone as shown in. In the symmetry breaking phase, the domain wall can
fluctuate away from the light cone 444Note that in the symmetry breaking
phase, there are still two phases for domain walls, the pinning and depinning
phases, separating by a pinning transition. For our case, since the coupling
at the top layer is the same as the coupling in the bulk, the depinning
transition is the same as the symmetry breaking transition. This means the
domain wall is depinned and can fluctuate.. The average position is $\sqrt{N}$
away from the domain wall [50]. Furthermore, the fluctuation of the domain
wall is captured by a universal function of $\alpha=\delta L/\sqrt{N}$ [50],
where $\delta L$ denotes the distance away from the light cone. More
concretely, the magnetization profile is a function of $\alpha$ at the
distance that is of the order $\sqrt{N}$ (outside this distance, the
magnetization is given either by one of the two spin polarization). We expect
that this function also captures the mutual purity because mutual purity in
this case prob the ‘swap’ spin at the right boundary. Now, since the light
cone reaches the right boundary at a time of order $N$, the mutual purity is
then a universal function of $(t-\frac{N}{v})/\sqrt{N}$, where $v$ is the
light speed. This explains the data collapse.

In summary, depending on whether the noise occurs in the encoding qubit, we
discover distinct coding transitions. If the noisy region covers the encoding
qubit, there are two kinds of domain wall configurations contributing to the
mutual purity. They are schematically shown in Fig. 8e. The exchange of
dominance between the two kinds of domain walls underlies the physics of the
coding transition in this situation. On the other hand, if the noisy region
does not cover the encoding qubit, the mutual purity is only nonzero when the
noise back propagates to the encoding qubit. In this case, the transition is
induced by the fluctuating domain walls and captured by a different scaling,
$N^{-1/2}$, as shown in the data collapse.

##  VI Concluding remarks

In this paper, we have used the effective replica Hamiltonian mapping for
local Brownian circuits to probe timescales of complexity growth in random
quantum circuits, namely anti-concentration and approximate unitary-design
generation. The effective replica model serves two purposes: we can perform
large-scale numerics to simulate several quantum informational quantities for
long times, using tensor network tools. This makes local Brownian circuits as
efficient numerical tools to study unitary quantum many-body dynamics.
Secondly, it transforms the question of time-scales in the real-time dynamics
into questions of energy-scales in a corresponding thermodynamic problem,
which allows us to make analytical progress.

We have shown that local Brownian circuits in $1+1$d anticoncentrate in $\log
N$ time, consistent with earlier results in local Haar random circuits [16].
Furthermore, we have analyzed the success condition of an approximate
classical algorithm [29] to sample from the output distribution of Brownian
circuits, and have identified that there is a sharp transition in the
computational hardness of simulation at the same timescale. The
anticoncentration transition arises from the transition in dominance of
different low-energy states of the effective Hamiltonian in the collision
probability. In particular, the collision probability (a probe of
anticoncentration) gets contribution from eigenstates of the effective
Hamiltonian with domain walls and the timescale where this becomes relevant
can be related to the logarithm of the number of such domain wall states
(which in $1d$ is $\sim N$).

In the presence of noise, we showed that there is a noise-induced phase
transition in linear cross entropy benchmark ($\chi_{\text{XEB}}$), as has
been recently demonstrated for related noisy random circuit models in [8, 31].
This can be seen as a consequence of explicit replica symmetry breaking in the
effective Hamiltonian model in the presence of noise acting on a single
replica of the system. By relating the $\chi_{\text{XEB}}$ to specific
transition amplitudes in the corresponding replica model, we identify the
noise-induced transition in the cross entropy benchmarking as the transition
in the dominance of certain domain wall states in the presence of explicit
bulk symmetry breaking field. The critical properties of the transition can be
related to those of external field-induced first-order transitions in the
classical Ising model in $2d$ [44].

Finally, we probed the generation of approximate unitary design by Brownian
circuits. By directly probing the quantum error-correcting properties of the
Brownian circuit, namely a 2-replica quantity called Mutual Purity [30], we
find that the $1+1$d Brownian circuits become good quantum error correcting
codes in $O(N)$ time. This transition can be identified as first-order
transitions between certain space-time domain wall configurations, which are
related to first-order boundary-driven pinning transitions in classical Ising
models.

There can be several avenues of future research based on this work. Here we
have demonstrated $1+1$d Brownian circuits as a useful numerically accessible
tool for studying the dynamics of quantum information. A natural question is
whether the same numerical feasibility extends to higher dimensions. Here, we
speculate the dynamics and transitions in informational quantities in higher
dimensional Brownian circuits $d>1$ (here $d$ is the spatial dimension of the
Brownian circuit, $N$ is total number of qubits, we also use the volume
$L^{d}\sim N$ with $L$ denotes the length scale):

  * •

Collision probability. It is still true that in higher dimensions, the
collision probability at long enough time is dominated by two grounds states
and elementary excitations. Distinct from the situation in 1d, now the lowest
excitation is given by local spin flips with an energy that is independent of
system sizes. Nevertheless, the entropy of such a local excitation is
proportional to the system size $N$. Therefore, we expect that the Brownian
circuit anti-concentrates on a $\log N$ timescale, similar to that in 1d [16].

  * •

Computational transition in patching algorithm. The patching algorithm is
closely related to the symmetry breaking of the underlying 2-replica spin
model [29]. In higher dimensions, $d>1$, the discrete symmetry can be broken
in a finite depth. This contrasts with the 1d case, where even the discrete
symmetry can only be broken in a $\log$ depth. This means that the patching
algorithm will fail when the depth of the Brownian circuit exceeds a critical
depth that is independent of system sizes.

  * •

Noisy cross-entropy benchmarking. A noise $\epsilon$ behaves as an external
field and will lift the degeneracy between $\left|\text{id}\right>\rangle$ and
$\left|\text{swap}\right>\rangle$, i.e., $\left|\text{swap}\right>\rangle$
will be suppressed by a factor of $e^{-N\epsilon t}$. On the other hand, as
discussed in the collision probability, the elementary excitation is given by
local spin flips. With an external field, there is an additional cost, adding
up to a factor $\sim e^{-z\Delta t-\epsilon t}$, where $z$ is the coordination
number. Therefore, we expect that when the noise rate scales as $1/N=1/L^{d}$,
there will be a first-order phase transition with critical exponent given by
$1/\nu=d+1$.

  * •

Coding transition. The dynamical transition for the Brownian circuit to
achieve an approximate unitary 2-design is given by the transition of
dominance between two kinds of domain walls. It should be the same in higher
dimensions. Therefore, the transition occurs on a timescale $\sim L=N^{1/d}$
[18]. Next, consider the different regions of noise and the encoding qubit. We
expect the mutual purity transition is similarly given by transitions of
domain walls when the noisy region overlaps the encoding qubit. On the other
hand, when the noisy region does not overlap the encoding qubit, we expect the
fluctuation of domain wall dictates the coding transition.

Even in $1+1$d, this work paves the way towards exploration of quantum
information dynamics in symmetric Brownian circuits, by studying directly the
spectrum of the effective Hamiltonian in the presence of other circuit
symmetries. Another direction of interest is incorporating the effects of mid-
circuit measurements in the entanglement dynamics in Brownian circuit [51,
28]. We will present these results in a future work.

In this work, we have focused on only 2-replica quantities, such as collision
probabilities and mutual purities. In principle, any integer $k$ replica
quantities can be represented in the effective Hamiltonian picture, with
$q^{k}$ local Hilbert space dimension ($q$ being the dimension of the original
degrees of freedom), which makes numerical methods intractable at large sizes
for large $k$. An outstanding question is to develop controlled numerical
methods or analytical techniques to take the $k\to 1$ replica limit.

## Acknowledgements

We thank Timothy Hsieh, Tsung-Cheng Lu, Utkarsh Agrawal, and Xuan Zou for
useful discussions, and Tsung-Cheng Lu for detailed comments. We have used the
TeNPy package for the tensor network simulations [42]. The numerical
simulations were performed using the Symmetry HPC system at Perimeter
Institute (PI). Research at PI is supported in part by the Government of
Canada through the Department of Innovation, Science and Economic Development
and by the Province of Ontario through the Ministry of Colleges and
Universities. S.-K.J is supported by a startup fund at Tulane University.

## References

  * Nahum  _et al._ [2018] A. Nahum, S. Vijay, and J. Haah, Physical Review X 8, 10.1103/physrevx.8.021014 (2018).
  * von Keyserlingk  _et al._ [2018] C. von Keyserlingk, T. Rakovszky, F. Pollmann, and S. Sondhi, Physical Review X 8, 10.1103/physrevx.8.021013 (2018).
  * Zhou and Nahum [2019] T. Zhou and A. Nahum, Physical Review B 99, 10.1103/physrevb.99.174205 (2019).
  * Khemani  _et al._ [2018] V. Khemani, A. Vishwanath, and D. A. Huse, Physical Review X 8, 031057 (2018).
  * Rakovszky  _et al._ [2018] T. Rakovszky, F. Pollmann, and C. Von Keyserlingk, Physical Review X 8, 031058 (2018).
  * Hayden  _et al._ [2016] P. Hayden, S. Nezami, X.-L. Qi, N. Thomas, M. Walter, and Z. Yang, Journal of High Energy Physics 2016, 1 (2016).
  * Arute  _et al._ [2019] F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buell, _et al._ , Nature 574, 505 (2019).
  * Morvan  _et al._ [2023] A. Morvan, B. Villalonga, X. Mi, S. Mandrà, A. Bengtsson, P. Klimov, Z. Chen, S. Hong, C. Erickson, I. Drozdov, _et al._ , arXiv preprint arXiv:2304.11119 (2023).
  * Wu  _et al._ [2021] Y. Wu, W.-S. Bao, S. Cao, F. Chen, M.-C. Chen, X. Chen, T.-H. Chung, H. Deng, Y. Du, D. Fan, _et al._ , Physical review letters 127, 180501 (2021).
  * Zhu  _et al._ [2022] Q. Zhu, S. Cao, F. Chen, M.-C. Chen, X. Chen, T.-H. Chung, H. Deng, Y. Du, D. Fan, M. Gong, _et al._ , Science bulletin 67, 240 (2022).
  * Brown and Fawzi [2013] W. Brown and O. Fawzi, in  _2013 IEEE International Symposium on Information Theory_ (IEEE, 2013).
  * Brown and Fawzi [2015] W. Brown and O. Fawzi, Communications in Mathematical Physics 340, 867 (2015).
  * Gullans  _et al._ [2021] M. J. Gullans, S. Krastanov, D. A. Huse, L. Jiang, and S. T. Flammia, Phys. Rev. X 11, 031066 (2021).
  * Boixo  _et al._ [2018] S. Boixo, S. V. Isakov, V. N. Smelyanskiy, R. Babbush, N. Ding, Z. Jiang, M. J. Bremner, J. M. Martinis, and H. Neven, Nature Physics 14, 595 (2018).
  * Hangleiter and Eisert [2023] D. Hangleiter and J. Eisert, Computational advantage of quantum random sampling (2023), arXiv:2206.04079 [quant-ph] .
  * Dalzell  _et al._ [2022] A. M. Dalzell, N. Hunter-Jones, and F. G. S. L. Brandã o, PRX Quantum 3, 10.1103/prxquantum.3.010333 (2022).
  * Brandão  _et al._ [2016] F. G. S. L. Brandão, A. W. Harrow, and M. Horodecki, Communications in Mathematical Physics 346, 397 (2016).
  * Harrow and Mehraban [2023] A. W. Harrow and S. Mehraban, Communications in Mathematical Physics 10.1007/s00220-023-04675-z (2023).
  * Hunter-Jones [2019] N. Hunter-Jones, Unitary designs from statistical mechanics in random quantum circuits (2019), arXiv:1905.12053 [quant-ph] .
  * Lashkari  _et al._ [2013] N. Lashkari, D. Stanford, M. Hastings, T. Osborne, and P. Hayden, Journal of High Energy Physics 2013, 10.1007/jhep04(2013)022 (2013).
  * Onorati  _et al._ [2017] E. Onorati, O. Buerschaper, M. Kliesch, W. Brown, A. H. Werner, and J. Eisert, Communications in Mathematical Physics 355, 905 (2017).
  * Bentsen  _et al._ [2021] G. S. Bentsen, S. Sahu, and B. Swingle, Physical Review B 104, 10.1103/physrevb.104.094304 (2021).
  * Sahu  _et al._ [2022] S. Sahu, S.-K. Jian, G. Bentsen, and B. Swingle, Physical Review B 106, 10.1103/physrevb.106.224305 (2022).
  * Jian  _et al._ [2022] S.-K. Jian, G. Bentsen, and B. Swingle, arXiv preprint arXiv:2206.14205 (2022).
  * Vidal [2003] G. Vidal, Phys. Rev. Lett. 91, 147902 (2003).
  * White and Feiguin [2004] S. R. White and A. E. Feiguin, Phys. Rev. Lett. 93, 076401 (2004).
  * Daley  _et al._ [2004] A. J. Daley, C. Kollath, U. Schollwöck, and G. Vidal, Journal of Statistical Mechanics: Theory and Experiment 2004, P04005 (2004).
  * Jian and Swingle [2021] S.-K. Jian and B. Swingle, arXiv preprint arXiv:2108.11973 (2021).
  * Napp  _et al._ [2022] J. C. Napp, R. L. L. Placa, A. M. Dalzell, F. G. Brandão, and A. W. Harrow, Physical Review X 12, 10.1103/physrevx.12.021021 (2022).
  * Balasubramanian  _et al._ [2023] V. Balasubramanian, A. Kar, C. Li, O. Parrikar, and H. Rajgadia, Quantum error correction from complexity in brownian syk (2023), arXiv:2301.07108 [hep-th] .
  * Ware  _et al._ [2023] B. Ware, A. Deshpande, D. Hangleiter, P. Niroula, B. Fefferman, A. V. Gorshkov, and M. J. Gullans, A sharp phase transition in linear cross-entropy benchmarking (2023), arXiv:2305.04954 [quant-ph] .
  * Dalzell  _et al._ [2021] A. M. Dalzell, N. Hunter-Jones, and F. G. S. L. Brandão, Random quantum circuits transform local noise into global white noise (2021), arXiv:2111.14907 [quant-ph] .
  * Aharonov  _et al._ [2023] D. Aharonov, X. Gao, Z. Landau, Y. Liu, and U. Vazirani, in  _Proceedings of the 55th Annual ACM Symposium on Theory of Computing_ (ACM, 2023).
  * Barak  _et al._ [2020] B. Barak, C.-N. Chou, and X. Gao, Spoofing linear cross-entropy benchmarking in shallow quantum circuits (2020), arXiv:2005.02421 [quant-ph] .
  * Gao  _et al._ [2021] X. Gao, M. Kalinowski, C.-N. Chou, M. D. Lukin, B. Barak, and S. Choi, Limitations of linear cross-entropy as a measure for quantum advantage (2021), arXiv:2112.01657 [quant-ph] .
  * Jian  _et al._ [2021a] S.-K. Jian, C. Liu, X. Chen, B. Swingle, and P. Zhang, arXiv preprint arXiv:2106.09635 (2021a).
  * Note [1] In a one-dimensional chain with local couplings, the elementary excitation manifests as a domain wall, with a finite gap independent of the system size and an entropy proportional to the system size.
  * Schumacher and Nielsen [1996] B. Schumacher and M. A. Nielsen, Physical Review A 54, 2629 (1996).
  * Schumacher and Westmoreland [2001] B. Schumacher and M. D. Westmoreland, Approximate quantum error correction (2001), arXiv:quant-ph/0112106 [quant-ph] .
  * Choi [1975] M.-D. Choi, Linear Algebra and its Applications 10, 285 (1975).
  * Jamiołkowski [1972] A. Jamiołkowski, Reports on Mathematical Physics 3, 275 (1972).
  * Hauschild and Pollmann [2018] J. Hauschild and F. Pollmann, SciPost Phys. Lect. Notes , 5 (2018), code available from https://github.com/tenpy/tenpy, arXiv:1805.00055 .
  * Note [2] Note that since the variance of coupling is independent of $\alpha=x,y,z$, the resulted Hamiltonian also enjoys a $SU(2)$ symmetry for each site. But our results do not rely on this symmetry.
  * Binder and Landau [1984] K. Binder and D. Landau, Physical Review B 30, 1477 (1984).
  * Brandao and Kastoryano [2019] F. G. S. L. Brandao and M. J. Kastoryano, Finite correlation length implies efficient preparation of quantum thermal states (2019), arXiv:1609.07877 [quant-ph] .
  * Note [3] For a more accurate estimate, we need to rescale $N$ by a factor $c_{3}<1$. This is because spin flips do not interact with each other only when they are dilute enough.
  * Abeyesinghe  _et al._ [2009] A. Abeyesinghe, I. Devetak, P. Hayden, and A. Winter, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 465, 2537 (2009).
  * Bény and Oreshkov [2010] C. Bény and O. Oreshkov, Phys. Rev. Lett. 104, 120501 (2010).
  * Note [4] Note that in the symmetry breaking phase, there are still two phases for domain walls, the pinning and depinning phases, separating by a pinning transition. For our case, since the coupling at the top layer is the same as the coupling in the bulk, the depinning transition is the same as the symmetry breaking transition. This means the domain wall is depinned and can fluctuate.
  * Abraham [1980] D. Abraham, Physical Review Letters 44, 1165 (1980).
  * Jian  _et al._ [2021b] S.-K. Jian, C. Liu, X. Chen, B. Swingle, and P. Zhang, Physical review letters 127, 140601 (2021b).
  * Note [5] See Appendix. B in [30].

##  Appendix A Quantum Error Correcting codes generated by Brownian circuits

###  A.1 Error correction bound with mutual purity

In this section we will briefly recap the derivation of the error correction
bound Eq. 43 derived in [30]. We will assume the setup described in Fig. 7.
Consider first the encoding of the maximally entangled state between the
reference $R$ and system $A$,

$\displaystyle\ket{\Psi}_{RA}=\frac{1}{\sqrt{d_{R}}}\sum_{i=1}^{d_{R}}\ket{i}_{R}\ket{\phi_{i}}_{A},$
(S1)

before any application of error. After the error channel acts on $A$, we get
the following noise-affected state on $RAE$,

$\displaystyle\ket{\Psi^{\prime}}_{RAE}=\frac{1}{\sqrt{d_{R}}}\sum_{i=1}^{d_{R}}\ket{i}_{R}U_{\text{err}}\left(\ket{\phi_{i}}_{A}\ket{e_{0}}_{E}\right).$

The error recovery procedure $\mathcal{R}$ [39, 30] works by first measuring
$A$ using an ideal projective measurement that probes the effect of error in
$\ket{\Psi^{\prime}}_{RAE}$, followed by a unitary update of the state to
restore it to $\ket{\Psi}_{RA}$. We first introduce an an orthonormal basis of
states in $A$, $\ket{\phi_{ij}}_{A}$. The projective measurement is given by
the projection operators,

$\displaystyle\Pi_{j}=\sum_{i=1}^{d_{R}}\ket{\phi_{ij}}_{A}\bra{\phi_{ij}}_{A}.$
(S2)

Depending on the measurement outcome, a corrective unitary $U_{j,A}$ is
applied on system $A$. In order to study the effectiveness of the recovery
channel, we want to study the trace distance between the recovered state and
the encoded state,
$\bigg{|}\bigg{|}\mathcal{R}\left(\ket{\Psi^{\prime}}\bra{\Psi^{\prime}}\right),\ket{\Psi}\bra{\Psi}\bigg{|}\bigg{|}_{1}$.
In order to bound this, we introduce a fictitious state
$\tilde{\ket{\Psi}}_{RAE}$ which aids in the analysis.

Consider $\tilde{\rho}_{RE}=\rho^{\prime}_{R}\otimes\rho^{\prime}_{E}$, where
the reduced density matrices $\rho^{\prime}$ are obtained from the state
$\ket{\Psi^{\prime}}_{RAE}$. We now take the fictitious state
$\tilde{\ket{\Psi}}_{RAE}$ which is a purification of $\tilde{\rho}_{RE}$ such
that the trace distance between $\tilde{\ket{\Psi}}_{RAE}$ and
$\ket{\Psi^{\prime}}_{RAE}$ is minimal. This uniquely defines,

$\displaystyle\tilde{\ket{\Psi}}_{RAE}=\frac{1}{\sqrt{d_{R}}}\sum_{i=1}^{d_{R}}\sum_{j=1}^{d_{E}}\sqrt{\alpha_{j}}\ket{i}_{R}\ket{\phi_{ij}}_{A}\ket{e_{j}}_{E}.$
(S3)

Imagine we apply the recovery channel $\mathcal{R}$ on
$\tilde{\ket{\Psi}}_{RAE}$ instead. After the measurement, say the outcome $j$
is obtained. The measured fictitious state is now,

$\displaystyle\tilde{\ket{\Psi}}_{RAE}^{j}=\frac{1}{\sqrt{d_{R}}}\sum_{i=1}^{d_{R}}\ket{i}_{R}\ket{\phi_{ij}}_{A}\ket{e_{j}}_{E}.$
(S4)

We can now choose $U_{j}$ acting on $A$ such that
$U_{j,A}\ket{\phi_{ij}}_{A}=\ket{\phi_{i}}_{A}$, and we get,

$\displaystyle
U_{j,A}\tilde{\ket{\Psi}}_{RAE}^{j}=\ket{\Psi}_{RA}\ket{e_{j}}_{E}.$ (S5)

From the above relation, we find that,

$\displaystyle\bigg{|}\bigg{|}\mathcal{R}\left(\ket{\Psi^{\prime}}\bra{\Psi^{\prime}}\right),\ket{\Psi}\bra{\Psi}\bigg{|}\bigg{|}_{1}$
$\displaystyle=\bigg{|}\bigg{|}\mathcal{R}\left(\ket{\Psi^{\prime}}\bra{\Psi^{\prime}}\right),\mathcal{R}\left(\tilde{\ket{\Psi}}\tilde{\bra{\Psi}}\right)\bigg{|}\bigg{|}_{1}\leq\bigg{|}\bigg{|}\ket{\Psi^{\prime}}\bra{\Psi^{\prime}},\tilde{\ket{\Psi}}\tilde{\bra{\Psi}}\bigg{|}\bigg{|}_{1}.$
(S6)

where the last inequality follows from the monotonicity property of the trace
distance. In [30], the last expression is bounded by the Mutual Purity defined
in Eq. S13555See Appendix. B in [30]. We quote the result in Eq. 43.

###  A.2 Replica computation of mutual purity

We first represent the reduced density matrix of the noise-affected state
defined in Eq. 40,

$\displaystyle\rho^{\prime}_{RE}=\text{Tr}_{A}\ket{\Psi^{\prime}}\bra{\Psi^{\prime}}=\frac{1}{d_{R}}\sum_{i,j=1}^{d_{R}}\ket{i}\bra{j}_{R}\otimes\text{Tr}_{A}\left\\{U_{\text{err}}\left(U_{\text{enc}}\left(\ket{i}\bra{j}_{A_{1}}\otimes\ket{0}\bra{0}_{A_{2}}\right)U_{\text{enc}}^{\dagger}\otimes\ket{e_{0}}\bra{e_{0}}\right)U_{\text{err}}^{\dagger}\right\\}$
(S7)

The effect of the $U_{\text{err}}$ on the system and the environment can be
represented by Kraus operators acting on the system itself,

$\displaystyle
U_{\text{err}}\ket{\psi}_{A}\ket{e_{0}}_{E}=\sum_{m}E^{m}_{A}\ket{\psi}_{A}\ket{e_{m}}_{E}$
(S8) $\displaystyle
E_{A}^{m}:\mathcal{H}_{A}\to\mathcal{H}_{A},\quad\sum_{m}E^{m\dagger}_{A}E^{m}_{A}=\mathbf{1}_{A}.$

The squared density matrix $\rho^{\prime\otimes 2}_{RE}$ can be represented by
a state vector in the replicated Hilbert space
$\mathcal{H}\otimes\mathcal{H^{*}}\otimes\mathcal{H}\otimes\mathcal{H^{*}}$,
and the replicated unitaries $\mathbb{U}_{\text{enc}}=U_{\text{enc}}\otimes
U^{*}_{\text{enc}}\otimes U_{\text{enc}}\otimes U^{*}_{\text{enc}}$ and
$\mathbb{U}_{\text{err}}=U_{\text{err}}\otimes U^{*}_{\text{err}}\otimes
U_{\text{err}}\otimes U^{*}_{\text{err}}$ as follows,

$\displaystyle|\rho^{\prime\otimes
2}_{RE}\rangle\rangle=\frac{1}{d_{R}^{2}}\sum_{i,j,i^{\prime},j^{\prime}=1}^{d_{R}}|iji^{\prime}j^{\prime}\rangle\rangle_{R}\sum_{s,k=1}^{d_{A}}\langle\langle
sskk|_{A}\mathbb{U}_{\text{err}}\otimes\mathbb{U}_{\text{enc}}|iji^{\prime}j^{\prime}\rangle\rangle_{A_{1}}|0^{\otimes
4|A_{2}|}\rangle\rangle_{A_{2}}|e_{0}^{\otimes 4}\rangle\rangle_{E}.$ (S9)

While this representation looks cumbersome, it makes further computations
straightforward. The mutual purity is given by
$\mathcal{F}^{\Psi^{\prime}}_{RE}=\text{Tr}\rho_{RE}^{\prime
2}-\text{Tr}\rho_{R}^{\prime 2}\text{Tr}\rho_{E}^{\prime 2}$. Let us compute
each term.

It is convenient to express Eq. S9 pictorially, with 4-rank tensors for each
subsystem, representing
$\mathcal{H}\otimes\mathcal{H^{*}}\otimes\mathcal{H}\otimes\mathcal{H^{*}}$,

By unitarity of $U_{\text{err}}$ and $U_{\text{enc}}$ we have,

$\includegraphics[width=21.68231pt]{eq_replica_mp_2.png}.$

Using this result we find,

(S10)

In general, $d_{R}=2^{|A_{2}|}$, where the local Hilbert space dimension is 2.
We introduce notation for the following states in the replicated Hilbert space
on $A$,

$\displaystyle|\psi_{\text{in}}\rangle\rangle=\left(|\text{swap}\rangle\rangle-\frac{1}{2}|\text{id}\rangle\rangle\right)^{\otimes
A_{1}}\otimes|0000\rangle\rangle^{\otimes A_{2}}$ (S11)
$\displaystyle|\psi_{\text{err}}\rangle\rangle=2^{N}\sum_{m,n=0}^{d_{E}-1}E_{m}E_{n}^{*}E_{n}E_{m}^{*}|\text{id}\rangle\rangle^{\otimes
A}.$ (S12)

Note $|\psi_{\text{err}}\rangle\rangle$ is an unnormalized state and the
expression for $|\psi_{\text{err}}\rangle\rangle$ includes the case for no
error acting on the subsystem $A_{3}\subset A$ by choosing
$E_{m}=\mathbf{1}_{A_{3}}\otimes E_{m,A_{4}}$.

Combining all the expressions, the mutual purity is given by,

$\displaystyle\mathcal{F}^{\Psi^{\prime}}_{RE}=\langle\langle\psi_{\text{err}}|\mathbb{U}_{\text{enc}}|\psi_{\text{in}}\rangle\rangle.$
(S13)

The noise model for probing the extent of error correction enters the
computation of mutual purity only in the definition of
$|\psi_{\text{err}}\rangle\rangle$. Consider the local depolarization channel
of strength $\lambda$ on a subset $A_{4}\subset A$, such that number of qubits
undergoing noise is $|A_{4}|=p|A|$. The Kraus operators for the depolarization
channel are,

$\displaystyle
E_{0}=\sqrt{1-\lambda}\mathbf{1},E_{x,y,z}=\sqrt{\frac{\lambda}{3}}\sigma_{x,y,z}.$
(S14)

Local depolarization channel acting on each qubit can be purified using a
environment degree of freedom with $4$ levels $0,x,y,z$. The corresponding
$d_{\text{env}}=4^{p|A|}$.

###  A.3 Maximal complexity encoding by Haar random circuits

We can compute the mutual purity for any noise model for an encoding unitary
$U_{\text{enc}}$ which is a global Haar random unitary. Any unitary 2 designs
will exhibit this value of mutual purity. By examining the time it requires
for the Brownian circuit to achieve this value of mutual purity, we can
diagnose the time required for the Brownian circuit to realise a 2 design.

For a global Haar random unitary, we have,

$\displaystyle U_{\text{Haar}}\otimes U^{*}_{\text{Haar}}\otimes
U_{\text{Haar}}\otimes
U^{*}_{\text{Haar}}=\frac{1}{d^{2}-1}\left(|\text{id}\rangle\rangle\langle\langle\text{id}|+|\text{swap}\rangle\rangle\langle\langle\text{swap}|-\frac{1}{d}\left(|\text{id}\rangle\rangle\langle\langle\text{swap}|+|\text{swap}\rangle\rangle\langle\langle\text{id}|\right)\right).$
(S15)

Using this identity for $U_{\text{enc}}$ in Eq. S13, we get the following
terms in the expression for mutual purity,

$\displaystyle\mathbb{E}[\text{Tr}\rho_{RE}^{2}]=\left(\frac{1}{\sqrt{d_{R}}}\right)^{4}\frac{1}{d_{A}^{2}-1}\left(f_{\text{id}}(\lambda)d_{R}+f_{\text{swap}}(\lambda)d_{R}^{2}-\frac{1}{d_{A}}\left(f_{\text{id}}(\lambda)d_{R}^{2}+f_{\text{swap}}(\lambda)d_{R}\right)\right),$
$\displaystyle\mathbb{E}[\text{Tr}\rho_{E}^{2}]=\left(\frac{1}{\sqrt{d_{R}}}\right)^{4}\frac{1}{d_{A}^{2}-1}\left(f_{\text{id}}(\lambda)d_{R}^{2}+f_{\text{swap}}(\lambda)d_{R}-\frac{1}{d_{A}}\left(f_{\text{id}}(\lambda)d_{R}+f_{\text{swap}}(\lambda)d_{R}^{2}\right)\right),$

where we have introduced the notation,

$\displaystyle
f_{\text{id}}(\lambda)=\langle\langle\psi_{\text{err}}|\text{id}\rangle\rangle,\quad
f_{\text{swap}}(\lambda)=\langle\langle\psi_{\text{err}}|\text{swap}\rangle\rangle.$

Combining the results, we get,

$\displaystyle\mathcal{F}^{\text{Haar}}_{RE}=\frac{1}{d_{A}^{2}-1}\left(1-\frac{1}{d_{R}^{2}}\right)\left(f_{\text{swap}}-\frac{1}{d_{A}}f_{\text{id}}\right).$
(S16)

For the depolarization channel of strength $\lambda$ acting on a fraction $p$
of the qubits, we get the following expression,

$\displaystyle\mathcal{F}^{\text{Haar}}_{RE}=\frac{d_{A}}{d_{A}^{2}-1}\left(1-\frac{1}{d_{R}^{2}}\right)\left(1-g(\lambda)^{p|A|}\right),\quad
g(\lambda)=(1-\lambda)^{2}+\frac{\lambda^{2}}{3}.$ (S17)

If one qubit is encoded in $N$ qubits, i.e. $d_{R}=2$, $d_{A}=2^{N}$, we have
for $N\gg 1$,

$\displaystyle\mathcal{F}^{\text{Haar}}_{RE}=2^{-N+2}3\left(1-g(\lambda)^{pN}\right).$
(S18)