# Quantum Noise as a Symmetry-Breaking Field

Beatriz C. Dias  Max Planck Institute for the Physics of Complex Systems,
Nöthnitzer Str. 38, 01187 Dresden, Germany  CeFEMA, Instituto Superior
Técnico, Universidade de Lisboa, Av. Rovisco Pais, 1049-001 Lisboa, Portugal
Domagoj Perković  Max Planck Institute for the Physics of Complex Systems,
Nöthnitzer Str. 38, 01187 Dresden, Germany  Department of Physics, Cavendish
Laboratory, JJ Thomson Avenue, Cambridge, CB3 0HE, UK.  Masudul Haque
Institut für Theoretische Physik, Technische Universität Dresden, 01062
Dresden, Germany  Department of Theoretical Physics, Maynooth University, Co.
Kildare, Ireland  Max Planck Institute for the Physics of Complex Systems,
Nöthnitzer Str. 38, 01187 Dresden, Germany  Pedro Ribeiro  CeFEMA, Instituto
Superior Técnico, Universidade de Lisboa, Av. Rovisco Pais, 1049-001 Lisboa,
Portugal  Beijing Computational Science Research Center, Beijing 100084, China
Paul A. McClarty  Max Planck Institute for the Physics of Complex Systems,
Nöthnitzer Str. 38, 01187 Dresden, Germany

###### Abstract

We investigate the effect of quantum noise on the measurement-induced quantum
phase transition in monitored random quantum circuits. Using the efficient
simulability of random Clifford circuits, we find that the transition is
broadened into a crossover and that the phase diagram as a function of
projective measurements and noise exhibits several distinct regimes. We show
that a mapping to a classical statistical mechanics problem accounts for the
main features of the random circuit phase diagram. The bulk noise maps to an
explicit permutation symmetry breaking coupling; this symmetry is
spontaneously broken when the noise is switched off. These results have
implications for the realization of entanglement transitions in noisy quantum
circuits.

From the point of view of entanglement entropy, ground states of many-body
quantum systems with short-range interactions mostly fall into two classes:
those with area law entanglement, where entanglement entropy scales as
$L^{D-1}$, with $L$ the system’s linear extent and $D$ the dimension, or
critical phases with entanglement entropy scaling as $L^{D-1}\ln L$. Out of
equilibrium, it also becomes possible to generate volume law entanglement and
to induce continuous area to volume law transitions. Examples have been found
in disordered spin chains between thermalizing and localized phases Abanin
_et al._ (2019); Nandkishore and Huse (2015); Parameswaran and Vasseur (2018);
Alet and Laflorencie (2018) and in systems subject to measurements. One
example of a measurement-induced entanglement transition is a spin chain under
local random unitary gates and projective measurements Li  _et al._ (2018);
Chan  _et al._ (2019); Vasseur  _et al._ (2019); Skinner  _et al._ (2019); Li
_et al._ (2019); Choi  _et al._ (2020); Gullans and Huse (2020); Bao  _et al._
(2020); Tang and Zhu (2020); Jian  _et al._ (2020); Zabalo  _et al._ (2020);
Sierant and Turkeshi (2022); Zabalo  _et al._ (2022). In the absence of
measurements, repeated application of gates to an initial product of local
pure states leads to a linear build-up of the entanglement entropy Nahum  _et
al._ (2017); von Keyserlingk  _et al._ (2018); Nahum  _et al._ (2018)
saturating at the Page value Page (1993). The effect of carrying out local
projective measurements with rate $p$, in the limit where $p$ is large, is to
suppress the spread of quantum information completely so that the entanglement
obeys an area law. In between there is a continuous quantum phase transition
at which the volume law coefficient vanishes Li  _et al._ (2018); Chan  _et
al._ (2019); Skinner  _et al._ (2019). Measurement-induced entanglement
transitions of different sorts have by now been observed in free fermion
systems Alberton  _et al._ (2021); Buchhold  _et al._ (2021); Bao  _et al._
(2021); Ladewig  _et al._ (2022), in fully connected random circuits Nahum
_et al._ (2021), in systems with weak measurements Szyniszewski  _et al._
(2019), continuous monitoring Alberton  _et al._ (2021); Szyniszewski  _et
al._ (2020); Fuji and Ashida (2020); Turkeshi  _et al._ (2022); Minoguchi  _et
al._ (2022), and long-range interactions Minato  _et al._ (2022); Sharma  _et
al._ (2022); Hashizume  _et al._ (2022); Block  _et al._ (2022); Müller  _et
al._ (2022); Sierant  _et al._ (2022). The weight of evidence is that these
continuous phase transitions are much like their equilibrium counterparts with
emergent conformal invariance and associated critical exponents, though a
complete field theory description is lacking.

Figure 1:  (a)
$|I_{\mathrm{AB}}(L,p,q)-I_{\mathrm{AB}}(L,p,q=0)|/I_{\mathrm{AB}}(L,p,q=0)$
and (b) $|I_{\mathrm{AB}}(L,p,q)-f(L,p,q)|/I_{\mathrm{AB}}(L,p,q)$ for a
system with $L=500$. For each $p$, $f(L,p,q)=b(L,p)\log(1/q)+c(L,p)$ is fitted
to $I_{\mathrm{AB}}(L,p,q)$ with $q$ in region I, where
$I_{\mathrm{AB}}\sim\log(q)$. The three marked regions correspond to:
$I_{\mathrm{AB}}\sim\log(1/q)$ (I), $I_{\mathrm{AB}}\sim q^{0}$ (II) and
$I_{\mathrm{AB}}\sim\exp(-q)$ (III). (c) A 1D qubit chain is evolved by
applying random uniformly distributed Clifford gates (red blocks) to
neighboring pairs of sites in a brickwall pattern. After each Clifford
bilayer, an un monitored measurement is performed on each site with
probability $q$ (blue circles), and then a monitored measurement is performed
on each site with probability $p$ (yellow circles).

Since any physical system is always coupled to an environment, it is natural
to ask what becomes of these measurement-induced entanglement transitions in
the generic case where the system is noisy. Refs. Bao  _et al._ (2021);
Weinstein  _et al._ (2022) made the case that quantum noise breaks down a
symmetry present in the noise-free case and Ref. Weinstein  _et al._ (2022)
studied a model with noise at the boundary. In this paper, we address the
effect of noise in the bulk with projective measurements applied at rate $p$
and with some additional noise rate $q$. We find that the known transition at
$p=p_{c}$, $q=0$ is broadened and the finite $p,q$ phase diagram exhibits
three quantitatively distinct regimes separated by crossovers, Fig. 1(a,b). At
small $q$ this is reminiscent of a phase diagram where $q=0$ displays
spontaneous symmetry breaking and where $q$ plays the role of an explicit
symmetry breaking field. We show, through a replica construction, that this
picture can be made precise: the quantum noise appears as a new effective
coupling in an effective classical model that explicitly breaks a replica
permutation symmetry. Using the classical picture, we can account for the main
features of the random circuit phase diagram. In the following, we introduce
the protocol, discuss our numerical findings and motivate a classical model
that allows for their qualitative understanding.

Figure 2:  (a) Mutual information, $I_{\mathrm{AB}}(q)$, for a system with
$L=500$ and for $p\in\\{0.02,0.08,0.14,0.22,0.3\\}$. Solid lines are
$f(L,p)=b(L,p)\log(1/q)+c(L,p)$ fits to the points with
$q=0.00008,0.0008,0.002,0.004$. (b) Parameter $b(L,p)$ of the fit in (a). (c)
Zoom in of (b): the critical point of the transition at $q=0$ is
$p_{c}\in]0.30,0.31[$. The horizontal dashed line is $\beta(p_{c})\sim 1.6$ Li
_et al._ (2019) in $S_{\mathrm{A}}(L,p,q=0)=\alpha(p)L+\beta(p)\log
L+\gamma(p)$. (d) Mutual information, $I_{\mathrm{AB}}(q)$, for a system with
$L=500$ and for $p\in\\{0.34,0.4,0.5\\}$. Solid lines are
$b(L,p)\log(1/q)+c(L,p)$ fits to the points in region I of Fig. 1. One can see
that $I_{\mathrm{AB}}(q)\sim q^{0}$ for small $q$.

Circuit and Observables – We consider a circuit model consisting of a chain of
$L$ qudits with local Hilbert space dimension $d$. Each single discrete time
step of the circuit is composed of four layers (Fig. 1(c)). The first two
layers consist of local random unitary gates $\prod_{r}u_{2r,2r+1}$ followed
by $\prod_{r}u_{2r-1,2r}$ in a brick wall pattern. After the random unitary
bilayer, unmonitored measurements are performed on each site, $r$, with
probability $q$. These take the state $\rho$ to the mixed state
$\sum_{a}M_{r}^{a\dagger}\rho M_{r}^{a}$, where $M_{r}^{a}=|r,a\rangle\langle
r,a|$ for outcomes $a=1,\ldots,d$. The final layer performs monitored
(projective) measurements with probability $p$, taking the mixed state $\rho$
to $M_{r}^{a\dagger}\rho M_{r}^{a}/||M_{r}^{a\dagger}\rho M_{r}^{a}||$ with
probability $p_{a}=||M_{r}^{a\dagger}\rho M_{r}^{a}||$.

We characterize the system using the entropy of subsystem A,
$S_{\mathrm{A}}=-{\rm
Tr}_{\mathrm{A}}(\rho_{\mathrm{A}}\log\rho_{\mathrm{A}})$, with
$\rho_{\mathrm{A}}={\rm Tr}_{\mathrm{\text{B}}}\rho$ the reduced density
matrix of subsystem A, obtained by tracing out its complement, B. Since the
overall state of $\mathrm{A}\cup\mathrm{B}$ is no longer pure, we also
consider the mutual information,
$I_{\mathrm{AB}}=S_{\mathrm{A}}+S_{\mathrm{B}}-S_{\mathrm{AB}}$, with
$S_{\mathrm{AB}}$ the entanglement entropy of the subsystem
$\mathrm{A}\cup\mathrm{B}$. We note that $I_{\mathrm{AB}}=2S_{\mathrm{A}}$
when $q=0$ as $S_{\mathrm{AB}}$ vanishes in this case.

Numerical Phase Diagram $-$ In order to achieve system sizes up to a few
hundred sites, we set $d=2$ and make use of the efficient simulability of
Clifford circuits with both above-mentioned single-site measurements, i.e. of
stabilizer circuits Aaronson and Gottesman (2004). As uniformly sampled gates
within the stabilizer group constitute a $t$-design of order $t=3$ Webb
(2016); Zhu (2017), the second Renyi entropy of local random local Clifford
gates with monitored and unmonitored measurements reproduce the same result as
their local Haar-distributed counterpart van den Berg (2020); Li  _et al._
(2019); Gullans and Huse (2020). For convenience we take an entanglement cut
dividing the chain exactly in two.

We now analyze the numerical results of Fig. 1(a,b), starting from the
previously known $p=0$ line. For $p=q=0$, the circuit rapidly loses memory of
the initial state and the entanglement entropy grows linearly saturating at a
value that is proportional to $L$. For $q=0$, $p=1$, there is a projective
measurement at each site for every time step so the state is a product state
with short range entanglement. There is a transition in the entanglement at
$0.30<p_{c}<0.31$, $q=0$ 111The reported value in Ref. Li  _et al._ (2018) is
approximately half of this value i.e. $p_{c}=0.16$ because their circuit has
one measurement layer for each (even or odd) unitary layer.. The entanglement
entropy obeys an area law for $p>p_{c}$ and varies as
$S_{\mathrm{A}}(L,p_{c},q=0)=\beta(p_{c})\log L$ at criticality. Empirically,
for $p<p_{c}$, there is a volume law with a logarithmic correction,
$S_{\mathrm{A}}(L,p,q=0)=\alpha(p)L+\beta(p)\log L+\gamma(p)$, with
$\lim_{p\rightarrow p_{c}^{-}}\beta(p)\neq 0$ and $\lim_{p\rightarrow
p_{c}^{+}}\beta(p)=0$, and $\alpha(p)=(p_{c}-p)^{\nu}\Theta(p_{c}-p)$ with
$\nu\approx 1.3$ Li  _et al._ (2019).

Now we turn to the finite $q$ behavior. For $p=0$, $q\neq 0$, the state
asymptotes to the infinite temperature mixed state essentially because the
unmonitored measurements proliferate branches of measurement outcomes in the
density matrix leading to rapid decoherence. As the gates are uniformly
distributed, the circuit does not distinguish between measurement outcomes so
the diagonal entries in the measurement basis become equal.

For finite $p$ and $q$, the steady state density matrix is nontrivial as there
is competition between branch proliferation generated by $q$ and branch
reduction driven by $p$. We find three distinct finite $p$, $q$ regimes as
indicated in the phase diagram of Fig. 1. The $q=0$ transition is broadened
into a crossover at finite $q$. In addition, the mutual information obeys an
area law for all finite $q$. For $p>p_{c}$ and small $q$, the mutual
information $I_{\mathrm{AB}}$ is $q$ independent and equal to the area law
entanglement $S_{\mathrm{AB}}$ for $q=0$. In the region I of Fig. 1 (spanning
$p<p_{c}$) and small $q$ all the way to $p>p_{c}$ and large $q$ there is a
logarithmic regime $I_{\mathrm{AB}}(L,p,q)=b(L,p)\ln(1/q)+c(L,p)$. This
scaling is shown in Fig. 2(a) for $p<p_{c}$ and above the saturation regime
for $p>p_{c}$ in panel (d). At the transition point itself, the finite size
cuts off the logarithmic scaling at $b(L,p_{c})\ln L$. We find that the
coefficients $b(L,p_{c})$ and $\beta(p_{c})$ are compatible, as shown in Fig.
2(c). This has the important implication that the underlying correlation
length grows as a power law $\xi\sim 1/q^{\nu}$ with exponent $\nu=1$. For
$p<p_{c}$, the logarithmic divergence is cut off by the volume law
entanglement implying logarithmic growth of the correlation length. A third
scaling regime is observed for small $p$ and $q$ close to $1$ where
$I_{\mathrm{AB}}$ falls off exponentially in $q$ SM .

Mapping to a Classical Statistical Mechanics Model $-$ The smearing of the
phase transition into a crossover at finite $q$ is reminiscent of a classical
equilibrium statistical mechanics model where $q$ explicitly breaks the
symmetry that is spontaneously broken by tuning $p$. We now make this
connection more concrete by mapping the $p,q$ model to a classical statistical
mechanics problem building on work from Ref. Zhou and Nahum (2019) for random
unitary circuits and Ref. Jian  _et al._ (2020) for the $q=0$ model. It will
turn out that this mapping accounts for many other features of the $p,q$ phase
diagram.

For this section, we generalize the qubit ($2$-states per site) model
considered above to a model of qudits ($d$-states per site). We consider the
$n$th Rényi entropy $S_{A}^{\left(n\right)}=1/(1-n)\ln\left[{\rm
Tr}_{A}\left(\rho_{A}^{n}\right)\right]$, averaged over Haar random unitaries
$\left\\{U\right\\}$ within each layer of the circuit and measurement
outcomes, ${\bf m}$, taken to include both monitored and un-monitored
measurements

$\bar{S}_{A}^{\left(n\right)}=\int dU\sum_{{\bf m}}\
\frac{1}{1-n}\ln\left[\frac{{\rm Tr}_{A}\left(\rho_{A,{\bf
m}}^{n}\right)}{{\rm Tr}\left(\rho_{{\bf m}}\right)^{n}}\right]{\rm
Tr}\left(\rho_{{\bf m}}\right).$ (1)

We introduce the swap operator
$\Sigma_{A}^{\left(n\right)}=\sum_{\left[i\right]}\left|i_{g^{n}_{\text{cyc}}\left(1\right)}^{A}i_{1}^{B},\ldots,i_{g^{n}_{\text{cyc}}\left(n\right)}^{A}i_{n}^{B}\right\rangle\left\langle
i_{1}^{A}i_{1}^{B},\ldots,i_{n}^{A}i_{n}^{B}\right|,$ which performw a cyclic
permutation of $n$ replicas on $A$ while leaving B sites invariant. We also
use the identity $\ln x=\lim_{k\to 0}\frac{x^{k}-1}{k}$ to rewrite the
logarithms, introducing an additional replica index $k$, giving

$\displaystyle\bar{S}_{A}^{\left(n,k\right)}$
$\displaystyle=\frac{1}{k(1-n)}{\rm Tr}\left\\{\left[\Sigma_{n,A}^{\otimes
k}\otimes 1-1^{\otimes\left(nk+1\right)}\right]\right.$
$\displaystyle\left.\times\left[\int
dU\sum_{m}\rho_{m}^{\otimes\left(nk+1\right)}\right]\right\\}.$ (2)

In this form one may integrate over the random unitaries and the measurement
outcomes. Details are spelled out in SM . Here we report the outcome of the
averaging.

It turns out that $\bar{S}_{A}^{\left(n,k\right)}$ is related to the free
energy cost of a domain wall in a classical statistical mechanics model Zhou
and Nahum (2019). This classical lattice model has degrees of freedom $g_{i}$
on each site, which are elements of the permutation group $\mathcal{S}_{Q}$ of
$Q\equiv kn+1$ objects. The partition sum is:

$\displaystyle\mathcal{Z}_{A}$ $\displaystyle=\sum_{\left\\{g_{i}\in
S_{Q}\right\\}}\left[\prod_{\langle i,j\rangle\in\mathcal{E}_{\rm
V}}W(g_{i}g_{j}^{-1})\prod_{\langle i,j\rangle\in\mathcal{E}_{\rm
ZZ}}W_{KM}(g_{i},g_{j})\right.$ $\displaystyle\times$
$\displaystyle\left.\prod_{i\in\partial_{0}}d^{\left|g_{i}\right|}\prod_{i\in\partial_{T}\cap
B}d^{\left|g_{i}\right|}\prod_{i\in\partial_{T}\cap
A}d^{\left|g(n,k,1)^{-1}g_{i}\right|}\right].$ (3)

The anisotropic couplings are between nearest neighbors on a honeycomb lattice
(Fig. 3(b)). With $i,j$ as neighboring honeycomb sites and $\mathcal{E}_{\rm
V}$ denoting the vertical bonds and $\mathcal{E}_{\rm ZZ}$ the zigzag bonds,
the $W(g^{-1}_{i}g_{j})$ act on the $\mathcal{E}_{\rm V}$ bonds. These are
Weingarten functions originating from the average over unitaries. On the
$\mathcal{E}_{\rm ZZ}$ bonds, the weights for $q=0$ are
$\left.W_{KM}(g,g^{\prime})\right|_{q=0}=(1-p)^{Q}d^{\left|g^{-1}g^{\prime}\right|}+p^{Q}d^{Q}$.
Here $|g|$ means the number of cycles in permutation $g$. The second line in
Eq. 3 consists of the boundary conditions that bias permutation degrees of
freedom towards the trivial permutation on the early and late time boundaries
except along $A$ where they are fixed to permutation $g(n,k,1)$ SM .
Crucially, boundaries aside, the model has a global $S_{Q}\times
S_{Q}\rtimes\mathbb{Z}_{2}$ symmetry. From Eq. 3 and weights one sees that,
for large $p$, the local degrees of freedom fluctuate wildly while, for small
$p$, permutations on neighboring bonds tend to lock together. In fact, there
is a critical $p$, analogous to temperature, below which there is long-range
order that spontaneously breaks the symmetry down to
$S_{Q}\rtimes\mathbb{Z}_{2}$.

One may now understand features of the two phases from the classical model as
the averaged replicated Rényi entropy is
$\bar{S}_{A}^{\left(n\right)}=\frac{n}{1-n}\frac{\mathcal{Z}_{A}-\mathcal{Z}_{\emptyset}}{Q-1}$
where $\mathcal{Z}_{A}$ is defined in Eq. 3 and $\mathcal{Z}_{\emptyset}$ has
homogeneous boundary conditions corresponding to $A\rightarrow\emptyset$. In
fact, the averaged Rényi entropy is the free energy cost of a domain wall with
fixed permutations (Fig 3(d) unbiased between the two configurations shown).
Evidently, this costs $O(L)$ in the ordered phase and $O(L^{0})$ in the
paramagnetic phase corresponding to the volume and area law phases
respectively.

One may extend this calculation to include the un-monitored measurements. The
weights $W_{KM}$ then become

$\displaystyle
W_{KM}(g_{i},g_{j})=(1-p)^{Q}\left[(1-q)^{Q}d^{\left|gg^{\prime-1}\right|}\right.$
$\displaystyle\left.+\sum_{l=1}^{Q}q^{l}(1-q)^{Q-l}\sum_{\\{r_{1},\ldots,r_{l}\\}\in
B_{l,Q}}d^{|gg^{\prime-1}h_{r_{1}}^{t_{1}}\ldots
h_{r_{l}}^{t_{l}}|}\right]+p^{Q}d^{Q}$ (4)

where $B_{l,Q}$ is the set of subsets of ${1,2,\ldots,Q}$ with $l$ elements
and where $h_{r}=(g^{-1}(r)\ r)$ is a two-cycle that permutes replica index
$r$ and $g^{-1}(r)$ and $t_{k}=1/2+{\rm
sign}(|gg^{\prime-1}|-|gg^{\prime-1}h_{r_{k}}|)/2,$ is either 0 or 1. Despite
the notational complexity, the $h_{r}$ insertions have a relatively simple
effect. That is to say if, in the permutation $gg^{\prime-1}$, the elements
$g^{-1}(r)$ and $r$ belong to different cycles, then
$gg^{\prime-1}h_{r_{k}}^{t_{k}}$ joins the cycles to which $g^{-1}(k)$ and $k$
belong and $\left|gg^{\prime-1}\right|-|gg^{\prime-1}h_{r_{k}}|=1$. If the
elements $g^{-1}(k)$ and $k$ already belong to the same cycle, then
$\left|gg^{\prime-1}\right|-|gg^{\prime-1}h_{r_{k}}|=-1$ and $t_{k}=0$, such
that $gg^{\prime-1}h_{r_{k}}^{t_{k}}=gg^{\prime-1}$. Overall Eq. 4 reduces to
the $q=0$ weight quoted above.

Comparison of classical picture and quantum model $-$ We can now interpret the
random circuit results from the point of view of the classical model. The
primary effect of introducing quantum noise is an explicit breaking of the
symmetry of the model down to $S_{Q}\rtimes\mathbb{Z}_{2}$ to which, we
recall, it is spontaneously broken when $q=0$. This can be seen more
transparently by inspecting the large $d$, small $q$ limit. In this limit, the
$q=0$ model reduces to a $Q!$ state Potts model. Expanding Eq. 4 linearly in
$q$ and collecting the largest powers of $d$ we obtain SM

$W_{KM}(g_{i},g_{j})=d^{Q}\Big{(}(1-p)^{Q}\big{[}(1-q)+q|g_{j}|_{1}\big{]}\delta_{g_{i},g_{j}}+p^{Q}\Big{)}$
(5)

where $|g|_{1}$ denotes the number of 1-cycles in $g$. Thus the leading effect
of $q$ is to pick out the permutation with the largest number of cycles – the
trivial permutation from all $Q!$ states equivalent to applying directly a
symmetry-breaking field that biases the system towards the $e$ permutation
with an extensive contribution to the free energy (Fig. 3(d), now biased
towards the upper configuration).

Thus, for finite $p$, quantum noise drives the system to the infinite
temperature fixed point of the classical model. This accounts for the most
prominent feature of the phase diagram: the smearing of the transition into a
crossover for $q\neq 0$. For $p=0$, the system instead flows to the infinite-
field fixed point corresponding to the maximally mixed state.

Turning to the observables, we note that $S_{AB}$ vanishes for $q=0$ but
exhibits a volume law for $q\neq 0$. From the point of view of the classical
model, when $q=0$, $S_{AB}$ is the free energy difference of a system with
boundary degrees of freedom pinned to a nontrivial permutation across the
entire system and a system with a boundary pinned to the trivial permutation
(Fig. 3(d)). But, for $q=0$, the free energy is indifferent to the precise
pinning field so the free energy difference must vanish. This ceases to be the
case when $q\neq 0$ but $q$ distinguishes the trivial permutation leading to
an $O(L)$ free energy difference as observed in the quantum model. A similar
argument allows us to understand why $I_{AB}$ has an area law for $q\neq 0$:
the domain wall cost is a constant $\alpha$ times $L$ in $S_{AB}$ which is
cancelled off by the two $\alpha L/2$ contributions in $S_{A}$ and $S_{B}$.

Finally the classical model provides some insight into the $\log q$ dependence
of the mutual information. In the vicinity of the $q=1$ line, one may carry
out the analogue of a high temperature expansion with Boltzmann weights
$\exp(c\log q)$. Since $q$ is close to $1$, the appropriate expansion
parameter is $\log q$. Then for $p<p_{c}$, the only further scale that enters
the problem is $L$ but until this cutoff is reached there is nothing to
interfere with the $\log q$ growth from the high temperature expansion.

Figure 3:  Top: mapping from the quantum random circuit (a) with both
projective and un-monitored measurements to a classical model with permutation
degrees of freedom living on the sites of an anisotropic honeycomb lattice
(b). The vertical bonds carry weights coming from the random unitaries and the
half-shaded bonds carry weights depending on $p$ and $q$. Panel (c) is the
schematic phase diagram arising from the classical model. Panel (d) shows two
domain wall configurations with pinning on the upper boundary to $g(k,n,1)$ on
the left and $e$ on the right. In the spontaneously broken phase both
configurations can arise with equal weight whereas in the explicitly broken
phase the state is biased towards the upper plot with $e$ across the system.

Discussion and Conclusion $-$ We have introduced and studied a random circuit
model subjected to both projective and un-monitored measurements. We have
shown that, at finite $q$, the transition known for projective-only
measurements ($q=0$) is washed out and the phase diagram is reminiscent of
that of a finite temperature ferromagnet with $q$ playing the role of an
applied field. We have made this connection precise through a mapping to a
classical statistical mechanics model with finite replica index $Q$ (the
quantum model corresponding to replica index $Q\rightarrow 1$). In the
classical model, $q$ explicitly breaks down the global $S_{Q}\times
S_{Q}\rtimes\mathbb{Z}_{2}$ permutation symmetry of the model to
$S_{Q}\rtimes\mathbb{Z}_{2}$. Thus, quantum noise (originating, e.g., from
coupling to a bath) is a relevant operator driving the system to the infinite
temperature fixed point. We have seen that various features of the quantum
model follow from the classical statistical mechanics analogue. It is amusing
to note that the passage from pure to mixed states by switching on $q$ is
reflected in the classical model as a field that affects the response of the
system but not the state space. Indeed, in the classical model the difference
between the pure and mixed states is only apparent through boundary
conditions.

All quantum systems are subject to quantum noise coming from the environment.
Our result suggests that, in a realistic setting, the entanglement transition
driven by monitored measurements will be smeared out by the environment. In
addition, our work shows that nonequilibrium mixed state dynamics in Hilbert
space in the presence of a quantum bath can be viewed as breaking a delicate
symmetry that is only present for pure states. It would be of considerable
interest to devise a model with an entanglement transition in the presence of
bulk noise Choi  _et al._ (2020). Whether this is possible or not has a
bearing on the experimental simulability of these entanglement transitions as
well as implications for error corrected quantum computers Aharonov (2000).

###### Acknowledgements.

BD and PR acknowledge MPI PKS where part of this work was carried out.

## References

  * Abanin  _et al._ (2019) D. A. Abanin, E. Altman, I. Bloch, and M. Serbyn, Rev. Mod. Phys. 91, 021001 (2019).
  * Nandkishore and Huse (2015) R. Nandkishore and D. A. Huse, Annu. Rev. Condens. Matter Phys. 6, 15 (2015).
  * Parameswaran and Vasseur (2018) S. A. Parameswaran and R. Vasseur, Reports on Progress in Physics 81, 082501 (2018).
  * Alet and Laflorencie (2018) F. Alet and N. Laflorencie, Comptes Rendus Physique 19, 498 (2018), arXiv:1711.03145 [cond-mat.str-el] .
  * Li  _et al._ (2018) Y. Li, X. Chen, and M. P. A. Fisher, Phys. Rev. B 98, 205136 (2018).
  * Chan  _et al._ (2019) A. Chan, R. M. Nandkishore, M. Pretko, and G. Smith, Phys. Rev. B 99, 224307 (2019).
  * Vasseur  _et al._ (2019) R. Vasseur, A. C. Potter, Y.-Z. You, and A. W. W. Ludwig, Phys. Rev. B 100, 134203 (2019).
  * Skinner  _et al._ (2019) B. Skinner, J. Ruhman, and A. Nahum, Phys. Rev. X 9, 31009 (2019).
  * Li  _et al._ (2019) Y. Li, X. Chen, and M. P. A. Fisher, Phys. Rev. B 100, 134306 (2019).
  * Choi  _et al._ (2020) S. Choi, Y. Bao, X.-L. Qi, and E. Altman, Phys. Rev. Lett. 125, 30505 (2020).
  * Gullans and Huse (2020) M. J. Gullans and D. A. Huse, Phys. Rev. X 10, 41020 (2020).
  * Bao  _et al._ (2020) Y. Bao, S. Choi, and E. Altman, Phys. Rev. B 101, 104301 (2020).
  * Tang and Zhu (2020) Q. Tang and W. Zhu, Phys. Rev. Res. 2, 13022 (2020).
  * Jian  _et al._ (2020) C.-M. Jian, Y.-Z. You, R. Vasseur, and A. W. W. Ludwig, Phys. Rev. B 101, 104302 (2020).
  * Zabalo  _et al._ (2020) A. Zabalo, M. J. Gullans, J. H. Wilson, S. Gopalakrishnan, D. A. Huse, and J. H. Pixley, Phys. Rev. B 101, 060301 (2020).
  * Sierant and Turkeshi (2022) P. Sierant and X. Turkeshi, Phys. Rev. Lett. 128, 130605 (2022).
  * Zabalo  _et al._ (2022) A. Zabalo, M. J. Gullans, J. H. Wilson, R. Vasseur, A. W. W. Ludwig, S. Gopalakrishnan, D. A. Huse, and J. H. Pixley, Phys. Rev. Lett. 128, 050602 (2022).
  * Nahum  _et al._ (2017) A. Nahum, J. Ruhman, S. Vijay, and J. Haah, Phys. Rev. X 7, 31016 (2017).
  * von Keyserlingk  _et al._ (2018) C. W. von Keyserlingk, T. Rakovszky, F. Pollmann, and S. L. Sondhi, Phys. Rev. X 8, 021013 (2018).
  * Nahum  _et al._ (2018) A. Nahum, S. Vijay, and J. Haah, Phys. Rev. X 8, 021014 (2018).
  * Page (1993) D. N. Page, Phys. Rev. Lett. 71, 1291 (1993).
  * Alberton  _et al._ (2021) O. Alberton, M. Buchhold, and S. Diehl, Phys. Rev. Lett. 126, 170602 (2021).
  * Buchhold  _et al._ (2021) M. Buchhold, Y. Minoguchi, A. Altland, and S. Diehl, Phys. Rev. X 11, 41004 (2021).
  * Bao  _et al._ (2021) Y. Bao, S. Choi, and E. Altman, Ann. Phys. (N. Y). , 168618 (2021).
  * Ladewig  _et al._ (2022) B. Ladewig, S. Diehl, and M. Buchhold, Phys. Rev. Research 4, 033001 (2022).
  * Nahum  _et al._ (2021) A. Nahum, S. Roy, B. Skinner, and J. Ruhman, PRX Quantum 2, 10352 (2021).
  * Szyniszewski  _et al._ (2019) M. Szyniszewski, A. Romito, and H. Schomerus, Phys. Rev. B 100, 64204 (2019).
  * Szyniszewski  _et al._ (2020) M. Szyniszewski, A. Romito, and H. Schomerus, Phys. Rev. Lett. 125, 210602 (2020).
  * Fuji and Ashida (2020) Y. Fuji and Y. Ashida, Phys. Rev. B 102, 54302 (2020).
  * Turkeshi  _et al._ (2022) X. Turkeshi, M. Dalmonte, R. Fazio, and M. Schirò, Phys. Rev. B 105, L241114 (2022).
  * Minoguchi  _et al._ (2022) Y. Minoguchi, P. Rabl, and M. Buchhold, SciPost Phys. 12, 009 (2022).
  * Minato  _et al._ (2022) T. Minato, K. Sugimoto, T. Kuwahara, and K. Saito, Phys. Rev. Lett. 128, 010603 (2022).
  * Sharma  _et al._ (2022) S. Sharma, X. Turkeshi, R. Fazio, and M. Dalmonte, SciPost Phys. Core 5, 023 (2022).
  * Hashizume  _et al._ (2022) T. Hashizume, G. Bentsen, and A. J. Daley, Phys. Rev. Research 4, 013174 (2022).
  * Block  _et al._ (2022) M. Block, Y. Bao, S. Choi, E. Altman, and N. Y. Yao, Phys. Rev. Lett. 128, 010604 (2022).
  * Müller  _et al._ (2022) T. Müller, S. Diehl, and M. Buchhold, Phys. Rev. Lett. 128, 010605 (2022).
  * Sierant  _et al._ (2022) P. Sierant, G. Chiriacò, F. M. Surace, S. Sharma, X. Turkeshi, M. Dalmonte, R. Fazio, and G. Pagano, Quantum 6, 638 (2022).
  * Weinstein  _et al._ (2022) Z. Weinstein, Y. Bao, and E. Altman, Phys. Rev. Lett. 129, 080501 (2022).
  * Aaronson and Gottesman (2004) S. Aaronson and D. Gottesman, Phys. Rev. A 70, 52328 (2004).
  * Webb (2016) Z. Webb, Quantum Info. Comput. 16, 1379–1400 (2016).
  * Zhu (2017) H. Zhu, Phys. Rev. A 96, 062336 (2017).
  * van den Berg (2020) E. van den Berg, ArXiv e-prints (2020), arXiv:2008.06011 .
  * Note (1) The reported value in Ref. Li  _et al._ (2018) is approximately half of this value i.e. $p_{c}=0.16$ because their circuit has one measurement layer for each (even or odd) unitary layer.
  * (44) See Supplemental Material for further details and additional supporting data.
  * Zhou and Nahum (2019) T. Zhou and A. Nahum, Phys. Rev. B 99, 174205 (2019).
  * Aharonov (2000) D. Aharonov, Phys. Rev. A 62, 062311 (2000).

Supplementary Material: Quantum Noise as a Symmetry-Breaking Field

##  S.I Exponential regime (region III)

In the main text we reported that the small $p$, large $q$ region (region III)
displays an exponential decrease of $I_{AB}$ with $q$. In Figure S1 we present
numerical data displaying this behavior.

Figure S1:  Mutual information, $I_{\mathrm{AB}}(q)$, for a system with
$L=500$ and for $p\in\\{0.02,0.06,0.16,0.22,0.3\\}$. Solid lines are
$d(L,p)\exp(-e(L,p)q)$ fits to points with large $q$
($q=0.5,0.6,0.7,0.8,0.9,1.0$) belonging to the region III of Fig. 1 in the
main text, where $I_{\mathrm{AB}}(q)\sim\exp(-q)$.

##  S.II Classical Mapping for the Mixed State Circuit

As discussed in the main text, Ref. Jian  _et al._ (2020) (building on work
from Ref. Zhou and Nahum (2019)) presents a mapping of the suitably replicated
quantum random circuit model with projective measurements to a classical
lattice model at finite temperature. Within the classical statistical
mechanics model the volume to area entanglement transition is an order-
disorder transition involving a broken permutation symmetry in the volume law
phase. The entanglement scaling follows from the free energy cost of a domain
wall.

Here we review this work and generalize it to the case with both projective
measurements and un-monitored measurements.

###  S.II.A Replicas

We wish to compute the nth Rényi entropy

$\displaystyle S_{A}^{\left(n\right)}$
$\displaystyle=\frac{1}{1-n}\ln\left[\operatorname{tr}_{A}\left(\rho_{A}^{n}\right)\right]$
(S.1)

for the circuit model with Haar-random unitaries acting on $d$ dimensional
local degrees of freedom (qudits), projective measurements, $M$, and un-
monitored measurements, $K$. This is to be done by averaging over circuit
disorder and measurement outcomes as follows:

$\displaystyle S_{A}^{\left(n\right)}$ $\displaystyle=\int dU\sum_{m}\
\frac{1}{1-n}\ln\left[\frac{\operatorname{tr}_{A}\left(\rho_{A,m}^{n}\right)}{\operatorname{tr}\left(\rho_{m}\right)^{n}}\right]\operatorname{tr}\left(\rho_{m}\right)$
$\displaystyle=\int dU\sum_{m}\
\frac{1}{1-n}\left\\{\ln\left[\operatorname{tr}_{A}\left(\rho_{A,m}^{n}\right)\right]-\ln\left[\operatorname{tr}\left(\rho_{m}\right)^{n}\right]\right\\}\operatorname{tr}\left(\rho_{m}\right).$
(S.2)

Here the density matrix for some choice of measurements (indicated in the
subscript) is

$\displaystyle\rho_{m}$
$\displaystyle=\sum_{\mu}K_{\mu_{T}}M_{m_{T}}U_{T}...K_{\mu_{1}}M_{m_{1}}U_{1}\rho_{0}U_{1}^{\dagger}M_{m_{1}}^{\dagger}K_{\mu_{1}}^{\dagger}\ldots
U_{T}^{\dagger}M_{m_{T}}^{\dagger}K_{\mu_{T}}^{\dagger},$ (S.3)

where $T$ is the circuit depth, $L$ the circuit length and

$\displaystyle M_{0}$ $\displaystyle=\sqrt{1-p},$ (S.4) $\displaystyle
M_{i=1,\ldots,d}$ $\displaystyle=p\left|i\right\rangle\left\langle i\right|,$
(S.5) $\displaystyle K_{0}$ $\displaystyle=\sqrt{1-q},$ (S.6) $\displaystyle
K_{i=1,\ldots,d}$ $\displaystyle=q\left|i\right\rangle\left\langle i\right|.$
(S.7)

The integral is performed with the standard Haar measure. Using $\ln
x=\lim_{k\to 0}\frac{x^{k}-1}{k}$, we get a replica index $k$

$\displaystyle S_{A}^{\left(n\right)}$ $\displaystyle=\lim_{k\to
0}S_{A}^{\left(n,k\right)}=\lim_{k\to 0}\frac{1}{1-n}\frac{1}{k}\int
dU\sum_{m}\left\\{\left[\operatorname{tr}_{A}\left(\rho_{A,m}^{n}\right)\right]^{k}-\left[\operatorname{tr}\left(\rho_{m}\right)\right]^{nk}\right\\}\operatorname{tr}\left(\rho_{m}\right).$
(S.9)

Defining the swap operator

$\displaystyle\Sigma_{A}^{\left(n\right)}$
$\displaystyle=\sum_{\left[i\right]}\left|i_{g^{n}_{\text{cyc}}\left(1\right)}^{A}i_{1}^{B},\ldots,i_{g^{n}_{\text{cyc}}\left(n\right)}^{A}i_{n}^{B}\right\rangle\left\langle
i_{1}^{A}i_{1}^{B},\ldots,i_{n}^{A}i_{n}^{B}\right|,$ (S.10)

where $g^{n}_{\text{cyc}}$ is a cyclic permutation of $n$ replicas, and
$i_{r}^{A(B)}$ runs over a complete basis of replica $r$ of subsystem
$A$($B$), we can write

$\displaystyle S_{A}^{\left(n,k\right)}$
$\displaystyle=\frac{1}{1-n}\frac{1}{k}\operatorname{tr}\left\\{\left[\Sigma_{A}^{\left(n\right)}{}^{\otimes
k}\otimes 1-1^{\otimes\left(nk+1\right)}\right]\left[\int
dU\sum_{m}\rho_{m}^{\otimes\left(nk+1\right)}\right]\right\\}.$ (S.11)

Or, in vectorial notation and defining $Q\equiv nk+1$,

$\displaystyle S_{A}^{\left(n,k\right)}$
$\displaystyle=\frac{1}{1-n}\frac{1}{k}\left[\left\langle\left\langle\Sigma_{A}^{\left(n,k\right)}\right|\right|-\left\langle\left\langle
1\right|\right|\right]\left|\left|\bar{\rho}_{Q}\right\rangle\right\rangle,$
(S.12)

with

$\displaystyle\left|\left|\bar{\rho}_{Q}\right\rangle\right\rangle$
$\displaystyle=\int
dU\sum_{m}\left|\left|\rho_{m}\right\rangle\right\rangle^{\otimes Q},$ (S.13)
$\displaystyle\left|\left|\Sigma_{A}^{\left(n\right)}\right\rangle\right\rangle$
$\displaystyle=\left(\sum_{\left[i\right]}\left|i_{g^{n}_{\text{cyc}}\left(1\right)}^{A}i_{1}^{B},\ldots,i_{g^{n}_{\text{cyc}}\left(n\right)}^{A}i_{n}^{B}\right\rangle\otimes\left|i_{1}^{A}i_{1}^{B},\ldots,i_{n}^{A}i_{n}^{B}\right\rangle\right)^{\otimes
k}\otimes\left(\sum_{\left[i_{Q}\right]}\left|i_{Q}^{A}i_{Q}^{B}\right\rangle\otimes\left|i_{Q}^{A}i_{Q}^{B}\right\rangle\right),$
(S.14) $\displaystyle\left|\left|1_{Q}\right\rangle\right\rangle$
$\displaystyle=\left(\sum_{i}\left|i^{A}i^{B}\right\rangle\otimes\left|i^{A}i^{B}\right\rangle\right)^{\otimes
Q}.$ (S.15)

We use Eq. S.12 to introduce a classical partition function as indicated in
the main text. In particular, we define

$\displaystyle\bar{S}_{A}^{\left(n,k\right)}=\frac{n}{1-n}\frac{\mathcal{Z}_{A}-\mathcal{Z}_{\emptyset}}{Q-1}$
(S.16)

where

$\displaystyle\mathcal{Z}_{A}=\left\langle\left\langle\Sigma_{A}^{\left(n\right)}\middle\|\bar{\rho}_{Q}\right\rangle\right\rangle$
(S.17)

and

$\displaystyle\mathcal{Z}_{\emptyset}=\left\langle\left\langle
1\middle\|\bar{\rho}_{Q}\right\rangle\right\rangle.$ (S.18)

###  S.II.B Averaging Unitaries

The averaged replicated density matrix is given by

$\displaystyle\left|\left|\bar{\rho}_{Q}\right\rangle\right\rangle=$
$\displaystyle\int
dU\sum_{m}\left|\left|\rho_{m}\right\rangle\right\rangle^{\otimes Q},$ (S.19)

where

$\displaystyle\left|\left|\rho_{m}\right\rangle\right\rangle$
$\displaystyle=\left(\sum_{\mu_{T}}K_{\mu_{T}}\otimes
K_{\mu_{T}}^{*}\right)\left(M_{m_{T}}\otimes
M_{m_{T}}^{*}\right)\left(U_{T}\otimes
U_{T}^{*}\right)...\left(\sum_{\mu_{1}}K_{\mu_{1}}\otimes
K_{\mu_{1}}^{*}\right)\left(M_{m_{1}}\otimes
M_{m_{1}}^{*}\right)\left(U_{1}\otimes
U_{1}^{*}\right)\left|\left|\rho_{0}\right\rangle\right\rangle.$ (S.20)

Let us analyze the operators averaged over replica space:

$\displaystyle\mathcal{U}$ $\displaystyle=\int dU\left(U\otimes
U^{*}\right)^{\otimes Q},$ (S.21) $\displaystyle\mathcal{M}$
$\displaystyle=\sum_{m}\left(M_{m}\otimes M_{m}^{*}\right)^{\otimes Q},$
(S.22) $\displaystyle\mathcal{K}$
$\displaystyle=\left(\sum_{\mu}K_{\mu}\otimes K_{\mu}^{*}\right)^{\otimes Q}.$
(S.23)

For $U$ acting on two qubits we have

$\displaystyle\mathcal{U}_{12}$ $\displaystyle=\int dU\left(U_{12}\otimes
U_{12}^{*}\right)^{\otimes Q}=\sum_{g_{1}g_{2}\in
S_{Q}}W\left(g_{1}^{-1}g_{2}\right)\left|\left|g_{1}\right\rangle\right\rangle\left|\left|g_{1}\right\rangle\right\rangle\left\langle\left\langle
g_{2}\right|\right|\left\langle\left\langle g_{2}\right|\right|$ (S.24)

where $g_{1}$ and $g_{2}$ are permutations of $Q$ elements, and
$\left|\left|g\right\rangle\right\rangle$ is a state on the replica-copy space
of one of the qubits, given by

$\displaystyle\left|\left|g\right\rangle\right\rangle$
$\displaystyle=\sum_{\left[i\right]}\left|\left|i_{g\left(1\right)},\ldots,i_{g\left(Q\right)};i_{1},\ldots,i_{Q}\right\rangle\right\rangle.$
(S.25)

A schematic representation of this relation is given in Fig.S2 The coefficient
$W(g)$ is a Weingarten function on permutation $g$. In short, the average over
unitaries leads to the emergence of classical permutation variables - each
pairwise unitary operator gives two permutation degrees of freedom. Thus, on
the lattice, the brick wall pattern of unitaries maps to a lattice model with
permutation degrees of freedom on two sites for each unitary.

Figure S2:  Sketch of Eq. S.24. The integration over the Haar distributed
unities, $U_{1,2}$, acting individual on $Q$ replicas of qudits 1 and 2 and
their complex conjugate $U_{1,2}^{*}$, acting on copy-space on $Q$ sets of
qudits 1’ and 2’, is replaced by sums over permutation group of $Q$ elements
weighted by Weingarten functions. The kets
$\left|\left|g_{1,2}\right\rangle\right\rangle$ are defined in Eq. S.25.

We turn now to the averaged monitored measurements. For a single qubit the
average is given by

$\displaystyle\mathcal{M}$ $\displaystyle=\sum_{m}\left(M_{m}\otimes
M_{m}^{*}\right)^{\otimes
Q}=\left(1-p\right)^{Q}+p^{Q}\sum_{i}\left|\left|i,\ldots,i;i,\ldots,i\right\rangle\right\rangle\left\langle\left\langle
i,\ldots,i;i,\ldots,i\right|\right|.$ (S.26)

Finally, for the un-monitored measurements on a single qubit we find

$\displaystyle\mathcal{K}$ $\displaystyle=\left(\sum_{\mu}K_{\mu}\otimes
K_{\mu}^{*}\right)^{\otimes
Q}=\left[\left(1-q\right)+q\sum_{i}\left|\left|i;i\right\rangle\right\rangle\left\langle\left\langle
i;i\right|\right|\right]^{\otimes
Q}=\left[\sum_{ij}\left[\left(1-q\right)+q\delta_{i,j}\right]\left|\left|i;j\right\rangle\right\rangle\left\langle\left\langle
i;j\right|\right|\right]^{\otimes Q}$
$\displaystyle=\sum_{\left[i\right]\left[j\right]}\prod_{k=1}^{Q}\left[\left(1-q\right)+q\delta_{i_{k},j_{k}}\right]\left|\left|i_{1},\ldots,i_{Q};j_{1},\ldots,j_{Q}\right\rangle\right\rangle\left\langle\left\langle
i_{1},\ldots,i_{Q};j_{1},\ldots,j_{Q}\right|\right|$ (S.27)

###  S.II.C Matrix Elements and Symmetries

The matrix element between two $g$ states is given by

$\displaystyle\left\langle\left\langle
g\middle\|g^{\prime}\right\rangle\right\rangle$
$\displaystyle=\sum_{\left[i\right]}\left\langle\left\langle
i_{g\left(1\right)},\ldots,i_{g\left(Q\right)}\middle\|i_{g^{\prime}\left(1\right)},\ldots,i_{g^{\prime}\left(Q\right)}\right\rangle\right\rangle$
(S.28) $\displaystyle=\sum_{\left[i\right]}\left\langle\left\langle
i_{g^{\prime-1}g\left(1\right)},\ldots,i_{g^{\prime-1}g\left(Q\right)}\middle\|i_{1},\ldots,i_{Q}\right\rangle\right\rangle=d^{\left|gg^{\prime-1}\right|}$
(S.29)

and

$\displaystyle\left\langle\left\langle
g\middle\|i,\ldots,i;i,\ldots,i\right\rangle\right\rangle$ $\displaystyle=1.$
(S.30)

One can further show that

$\displaystyle\left\langle\left\langle
h_{L}gh_{R}^{-1}\middle\|h_{L}g^{\prime}h_{R}^{-1}\right\rangle\right\rangle$
$\displaystyle=\left\langle\left\langle
g\middle\|g^{\prime}\right\rangle\right\rangle$ (S.31)

so there is a double (left and right) permutation invariance for this matrix
element that is of great importance for this discussion.

It is useful to define operators $\mathcal{P}$ that implements the
permutations $h_{L}$ and $h_{R}$ and another operator $\mathcal{S}$ that swaps
bras and kets (or left and right indices in the vectorized notation)

$\displaystyle\mathcal{P}_{h_{L}h_{R}}$
$\displaystyle=\sum_{\left[i\right]\left[j\right]}\left|\left|i_{h_{R}^{-1}\left(1\right)},\ldots,i_{h_{R}^{-1}\left(Q\right)};j_{h_{L}^{-1}\left(1\right)},\ldots,j_{h_{L}^{-1}\left(Q\right)}\right\rangle\right\rangle\left\langle\left\langle
i_{1},\ldots,i_{Q};j_{1},\ldots,j_{Q}\right|\right|$ (S.32)
$\displaystyle\mathcal{S}$
$\displaystyle=\sum_{\left[i\right]\left[j\right]}\left|\left|j_{1},\ldots,j_{Q};i_{1},\ldots,i_{Q}\right\rangle\right\rangle\left\langle\left\langle
i_{1},\ldots,i_{Q};j_{1},\ldots,j_{Q}\right|\right|$ (S.33)

One may check that $\mathcal{P}$ acting on state
$\left|\left|g\right\rangle\right\rangle$ leads to

$\displaystyle\mathcal{P}_{h_{L}h_{R}}\left|\left|g\right\rangle\right\rangle$
$\displaystyle=\sum_{\left[i\right]\left[i^{\prime}\right]}\left|\left|i_{h_{R}^{-1}\left(1\right)},\ldots,i_{h_{R}^{-1}\left(Q\right)};i^{\prime}_{h_{L}^{-1}\left(1\right)},\ldots,i^{\prime}_{h_{L}^{-1}\left(Q\right)}\right\rangle\right\rangle\left\langle\left\langle
i_{1},\ldots,i_{Q}\middle\|i^{\prime}_{g\left(1\right)},\ldots,i^{\prime}_{g\left(Q\right)}\right\rangle\right\rangle$
$\displaystyle=\sum_{\left[i^{\prime}\right]}\left|\left|i^{\prime}_{gh_{R}^{-1}\left(1\right)},\ldots,i^{\prime}_{gh_{R}^{-1}\left(Q\right)};i^{\prime}_{h_{L}^{-1}\left(1\right)},\ldots,i^{\prime}_{h_{L}^{-1}\left(Q\right)}\right\rangle\right\rangle$
$\displaystyle=\sum_{\left[i\right]}\left|\left|i_{h_{L}gh_{R}^{-1}\left(1\right)},\ldots,i_{h_{L}gh_{R}^{-1}\left(Q\right)};i{}_{1},\ldots,i{}_{1}\right\rangle\right\rangle=\left|\left|h_{L}gh_{R}^{-1}\right\rangle\right\rangle,$
(S.34)

where in the last equality we perform the change of variables
$i^{\prime}_{h_{L}^{-1}\left(k\right)}=i_{k},i^{\prime}_{k}=i_{h_{L}\left(k\right)}$.

Similarly, one may look at the action of $\mathcal{S}$

$\displaystyle\mathcal{S}\left|\left|g\right\rangle\right\rangle$
$\displaystyle=\sum_{\left[i\right]}\left|\left|i_{1},\ldots,i_{Q},i_{g\left(1\right)},\ldots,i_{g\left(Q\right)}\right\rangle\right\rangle=\sum_{\left[i\right]}\left|\left|i_{g^{-1}\left(1\right)},\ldots,i_{g^{-1}\left(Q\right)},i_{1},\ldots,i_{Q}\right\rangle\right\rangle=\left|\left|g^{-1}\right\rangle\right\rangle.$
(S.35)

The matrix element of the projective measurement operator is

$\displaystyle\left\langle\left\langle
g\right|\right|\mathcal{M}\left|\left|g^{\prime}\right\rangle\right\rangle$
$\displaystyle=\left(1-p\right)^{Q}+p^{Q}d.$ (S.36)

This operator is also left-/right- permutation symmetric and also symmetric
under the swap $\mathcal{S}$

$\displaystyle\mathcal{P}_{h_{L}h_{R}}^{-1}\mathcal{M}\mathcal{P}_{h_{L}h_{R}}$
$\displaystyle=\mathcal{M},$ (S.37)
$\displaystyle\mathcal{S}^{-1}\mathcal{M}\mathcal{S}$
$\displaystyle=\mathcal{M}.$ (S.38)

Taken together with the average over unitaries it follows that the model in
the permutation variables has global symmetries $S_{Q}\times
S_{Q}\rtimes\mathbb{Z}_{2}$.

However, when we consider the un-monitored measurements we find

$\displaystyle\mathcal{P}_{h_{L}h_{R}}^{-1}\mathcal{K}\mathcal{P}_{h_{L}h_{R}}$
$\displaystyle\neq\mathcal{K}\text{ in general for }\ h_{L}\neq h_{R},$ (S.39)
$\displaystyle\mathcal{P}_{hh}^{-1}\mathcal{K}\mathcal{P}_{hh}$
$\displaystyle=\mathcal{K},$ (S.40)
$\displaystyle\mathcal{S}^{-1}\mathcal{K}\mathcal{S}$
$\displaystyle=\mathcal{K}$ (S.41)

so there is only one surviving permutation invariance $-$ the one where left-
and right- are locked to one another.

###  S.II.D The Un-Monitored Measurements

It remains to evaluate the matrix elements for the combined monitored and un-
monitored measurements.

The action of $\mathcal{M}$ on a permutation degree of freedom is $g^{\prime}$
is

$\displaystyle\mathcal{M}\left|\left|g^{\prime}\right\rangle\right\rangle$
$\displaystyle=\left[\left(1-p\right)^{Q}\left|\left|g^{\prime}\right\rangle\right\rangle+p^{Q}\sum_{i}\left|\left|i,\ldots,i;i,\ldots,i\right\rangle\right\rangle\right].$
(S.42)

We note that

$\displaystyle\mathcal{K}\left|\left|i,\ldots,i;i,\ldots,i\right\rangle\right\rangle$
$\displaystyle=\left|\left|i,\ldots,i;i,\ldots,i\right\rangle\right\rangle.$
(S.43)

Now acting with $\mathcal{K}$ leads to

$\displaystyle\left\langle\left\langle
g\right|\right|\mathcal{K}\mathcal{M}\left|\left|g^{\prime}\right\rangle\right\rangle$
$\displaystyle=\left\langle\left\langle
g\right|\right|\mathcal{K}\left[\left(1-p\right)^{Q}\left|\left|g^{\prime}\right\rangle\right\rangle+p^{Q}\sum_{i}\left|\left|i,\ldots,i;i,\ldots,i\right\rangle\right\rangle\right]$
$\displaystyle=\left[\left(1-p\right)^{Q}\left\langle\left\langle
g\right|\right|\mathcal{K}\left|\left|g^{\prime}\right\rangle\right\rangle+p^{Q}\sum_{i}\left\langle\left\langle
g\right|\right|\mathcal{K}\left|\left|i,\ldots,i;i,\ldots,i\right\rangle\right\rangle\right]$
$\displaystyle=\left(1-p\right)^{Q}\left\langle\left\langle
g\right|\right|\mathcal{K}\left|\left|g^{\prime}\right\rangle\right\rangle+p^{Q}d.$
(S.44)

Our goal now is to compute the matrix elements $\left\langle\left\langle
g\right|\right|\mathcal{K}\left|\left|g^{\prime}\right\rangle\right\rangle$
appearing in (S.44). The operator $\mathcal{K}$ is given by (S.27).

$\displaystyle\left\langle\left\langle
g\right|\right|\mathcal{K}\left|\left|g^{\prime}\right\rangle\right\rangle=$
$\displaystyle\left\langle\left\langle
g\right|\right|\left(\sum_{\left[i\right]\left[j\right]}\prod_{k=1}^{Q}\left[\left(1-q\right)+q\delta_{i_{k},j_{k}}\right]\left|\left|i_{1}...i_{Q};j_{1}...j_{Q}\right\rangle\right\rangle\left\langle\left\langle
i_{1}...i_{Q};j_{1}...j_{Q}\right|\right|\right)\left|\left|g^{\prime}\right\rangle\right\rangle$
(S.45) $\displaystyle=$
$\displaystyle\sum_{\left[i\right]\left[j\right]}\prod_{k=1}^{Q}\left[\left(1-q\right)+q\delta_{i_{k},j_{k}}\right]\left\langle\left\langle
j_{g\left(1\right)},...,j_{g\left(Q\right)}\middle\|i_{1}...i_{Q}\right\rangle\right\rangle\left\langle\left\langle
i_{1}...i_{Q}\middle\|j_{g^{\prime}\left(1\right)},...,j_{g^{\prime}\left(Q\right)}\right\rangle\right\rangle$
(S.46) $\displaystyle=$
$\displaystyle\left((1-q)^{Q}\sum_{\left[i\right]\left[j\right]}+\sum_{l=1}^{Q}q^{l}(1-q)^{Q-l}\sum_{\\{r_{1},\ldots,r_{l}\\}\in
B_{l,Q}}\sum_{\left[i\right]\left[j\right]}\delta_{i_{r_{1}},j_{r_{1}}}\ldots\delta_{i_{r_{l}},j_{r_{l}}}\right)$
$\displaystyle\left\langle\left\langle
j_{g\left(1\right)},...,j_{g\left(Q\right)}\middle\|i_{1}...i_{Q}\right\rangle\right\rangle\left\langle\left\langle
i_{1}...i_{Q}\middle\|j_{g^{\prime}\left(1\right)},...,j_{g^{\prime}\left(Q\right)}\right\rangle\right\rangle$
(S.47)

where $B_{l,Q}$ is the set of subsets of $\\{1,2,\ldots,Q-1,Q\\}$ with $l$
elements.

The first term corresponds to performing no un-monitored measurements. As seen
in (S.29), this yields

$\displaystyle\sum_{\left[i\right]\left[j\right]}\left\langle\left\langle
j_{g\left(1\right)},...,j_{g\left(Q\right)}\middle\|i_{1}...i_{Q}\right\rangle\right\rangle\left\langle\left\langle
i_{1}...i_{Q}\middle\|j_{g^{\prime}\left(1\right)},...,j_{g^{\prime}\left(Q\right)}\right\rangle\right\rangle$
$\displaystyle=\sum_{\left[j\right]}\left\langle\left\langle
j_{g\left(1\right)},...,j_{g\left(Q\right)}\middle\|j_{g^{\prime}\left(1\right)},...,j_{g^{\prime}\left(Q\right)}\right\rangle\right\rangle=\left\langle\left\langle
g\middle\|g^{\prime}\right\rangle\right\rangle=d^{\left|gg^{\prime-1}\right|}.$
(S.48)

The second term corresponds to measuring $l=1,\ldots,Q$ out of the $Q$
replicas. For a fixed $l$, we sum over the $\binom{Q}{l}$ ways of choosing
which $l$ copies to measure. The coefficient of the $q^{l}(1-q)^{Q-l}$ term is
given by

$\displaystyle\sum_{\left[i\right]\left[j\right]}\sum_{\\{r_{1},\ldots,r_{l}\\}\in
B_{l,Q}}\delta_{i_{r_{1}},j_{r_{1}}}\ldots\delta_{i_{r_{l}},j_{r_{l}}}\left\langle\left\langle
j_{g\left(1\right)},...,j_{g\left(Q\right)}\middle\|i_{1}...i_{Q}\right\rangle\right\rangle\left\langle\left\langle
i_{1}...i_{Q}\middle\|j_{g^{\prime}\left(1\right)},...,j_{g^{\prime}\left(Q\right)}\right\rangle\right\rangle=d^{|gg^{\prime-1}h_{r_{1}}^{t_{1}}\ldots
h_{r_{l}}^{t_{l}}|}$ (S.49)

where $B_{l,Q}$ is the set of subsets of ${1,2,\ldots,Q}$ with $l$ elements,

$\displaystyle h_{r}=(g^{-1}(r)\ r)$ (S.50)

is a two-cycle that permutes replica index $r$ and $g^{-1}(r)$ and

$\displaystyle
t_{k}=\frac{1+\operatorname{sign}(|gg^{\prime-1}|-|gg^{\prime-1}h_{r_{k}}|)}{2}$
(S.51)

is either 0 or 1. If in the permutation $gg^{\prime-1}$, the elements
$g^{-1}(r)$ and $r$ belong to different cycles, then
$gg^{\prime-1}h_{r_{k}}^{t_{k}}$ joins the cycles to which $g^{-1}(r)$ and $r$
belong and $\left|gg^{\prime-1}\right|-|gg^{\prime-1}h_{r_{k}}|=1$. If the
elements $g^{-1}(r)$ and $r$ already belong to the same cycle, then
$gg^{\prime-1}h_{r_{k}}$ separates it such that $g^{-1}(k)$ and $k$ belong to
different cycles and $\left|gg^{\prime-1}\right|-|gg^{\prime-1}h_{r_{k}}|=-1$.
In this case, $t_{k}=0$ and $gg^{\prime-1}h_{r_{k}}^{t_{k}}=gg^{\prime-1}$.
Thus, expression $|gg^{\prime-1}h_{r_{k}}^{t_{k}}|$ selects the permutation
$gg^{\prime-1}$or $gg^{\prime-1}h_{r_{k}}$ with fewer cycles, i.e.

$\displaystyle|gg^{\prime-1}h_{r_{k}}^{t_{k}}|=\begin{cases}\left|gg^{\prime-1}\right|&{\rm
if}\ \left|gg^{\prime-1}\right|=|gg^{\prime-1}h_{r_{k}}|-1\\\
|gg^{\prime-1}h_{r_{k}}|&{\rm if}\
\left|gg^{\prime-1}\right|=|gg^{\prime-1}h_{r_{k}}|+1\end{cases},$ (S.52)

where $\left|gg^{\prime-1}\right|=|gg^{\prime-1}h_{r_{k}}|\pm 1$ always. We
consider the null power of a cycle to be the identity cycle.

Finally,

$\displaystyle\left\langle\left\langle
g\right|\right|\mathcal{K}\left|\left|g^{\prime}\right\rangle\right\rangle=(1-q)^{Q}d^{\left|gg^{\prime-1}\right|}+\sum_{l=1}^{Q}q^{l}(1-q)^{Q-l}\sum_{\\{r_{1},\ldots,r_{l}\\}\in
B_{l,Q}}d^{|gg^{\prime-1}h_{r_{1}}^{t_{1}}\ldots h_{r_{l}}^{t_{l}}|}.$ (S.53)

Notice that, setting $q=0$, we recover the expression for monitored
measurements alone, given by Eq. 13 in Jian  _et al._ (2020).

###  S.II.E Bulk and Boundary contributions

The entanglement entropy is obtained as the analytic continuation of the
difference of factors $\mathcal{Z}_{A}$ and $\mathcal{Z}_{\emptyset}$ in Eq. 7
in the main text. For a set of sites in region $A$, $\mathcal{Z}_{A}$ can be
interpreted as a classical partition function with boundary conditions imposed
on the set of sites with $t=0$, $\partial_{0}$, and on the set of sites with
$t=T$, $\partial_{T}$. After applying the rules derived in the last sections,
the bulk degrees of freedom are found to be distributed on the anisotropic
honeycomb lattice depicted in Fig. S3. Vertical bonds (red), $\mathcal{E}_{\rm
V}$, correspond to Weingarten weights and the zigzag bonds (blue),
$\mathcal{E}_{\rm ZZ}$, to the matrix elements in Eq. S.44.

Assuming the starting state is the high-temperature state, i.e. proportional
to the identity, the contribution from the $t=0$ boundary is simply given by
$\prod_{i\in\partial_{0}}\left\langle\left\langle
g_{i}\middle\|1\right\rangle\right\rangle/d^{Q}$. As the protocol assumes a
steady-state is reached much before any of the observables are considered,
this boundary condition does not influence any of the following results and
may be safely ignored.

On the contrary, the contributions from the $t=T$ boundary are nontrivial and
differ for sites belonging to the set $A$ or to its complement, $B$. This
boundary contribution, given by Eq. S.17 can be most conveniently obtained by
rewriting Eq. S.14 as
$\left|\left|\Sigma_{{A}}^{\left(n,k\right)}\right\rangle\right\rangle=\otimes_{i\in
B}\left|\left|1\right\rangle\right\rangle\otimes_{i\in
A}\left|\left|g(n,k,1)\right\rangle\right\rangle$, with
$\left|\left|g(n,k,1)\right\rangle\right\rangle$ a double-ket state of the
from (S.25). Thus, sites in $\bar{A}$, contribute with
$\prod_{i\in\partial_{T}\cap B}\left\langle\left\langle
1\middle\|g_{i}\right\rangle\right\rangle$. A depiction, $g(n,k,1)$, acting on
$Q=kn+1$ replicas of a single site is given in Fig. S4. It is composed of $k$
cyclic permutations, $g_{\text{cyc}}^{n}$, of $n$ replica indices acting
identically on $k$ sets. The last index is left invariant. Thus, the
contribution of sites in $A$ is given by $\prod_{i\in\partial_{T}\cap
A}\left\langle\left\langle g(n,k,1)\middle\|g_{i}\right\rangle\right\rangle$.

The boundary conditions of the classical model are sketched in Fig. S5.

Figure S3:  Bulk couplings of the effective classical model defined in an
anisotropic honeycomb lattice.  Figure S4:  $t=T$ boundary permutation,
$g(n,k,1)$, acting the $Q=kn+1$ replica indices for sites in $A$. $g(n,k,1)$
is composed of $k$ identical cyclic permutations, $g_{\text{cyc}}^{n}$, acting
on $n$ replica indices. The last index is left invariant.  Figure S5:
Boundary conditions for the entanglement entropy on subsystem $A$.

###  S.II.F Classical Statistical Model

So far we have evaluated matrix elements for the measurements on a single
qubit and the average over unitaries on a pair of sites. We now use these
results to write down the partition function in Eq. S.14:

$\displaystyle\mathcal{Z}_{A}=\sum_{\left\\{g_{i}\in
S_{Q}\right\\}}\left[\prod_{\langle i,j\rangle\in\mathcal{E}_{\rm
V}}W(g_{i}g_{j}^{-1})\times\prod_{\langle i,j\rangle\in\mathcal{E}_{\rm
ZZ}}W_{KM}(g_{i},g_{j})\times\prod_{i\in\partial_{0}}d^{\left|g_{i}\right|}\times\prod_{i\in\partial_{T}\cap
B}d^{\left|g_{i}\right|}\times\prod_{i\in\partial_{T}\cap
A}d^{\left|g(n,k,1)^{-1}g_{i}\right|}\right]$ (S.54)

where we reproduce here for convenience the weights computed above

$\displaystyle
W_{KM}(g_{i},g_{j})=\left(1-p\right)^{Q}\left\langle\left\langle
g_{i}\right|\right|\mathcal{K}\left|\left|g_{j}\right\rangle\right\rangle+p^{Q}d,$
(S.55)

and

$\displaystyle\left\langle\left\langle
g_{i}\right|\right|\mathcal{K}\left|\left|g_{j}\right\rangle\right\rangle=(1-q)^{Q}d^{\left|g_{i}g_{j}^{-1}\right|}+\sum_{l=1}^{Q}q^{l}(1-q)^{Q-l}\sum_{\\{r_{1},\ldots,r_{l}\\}\in
B_{l,Q}}d^{|g_{i}g_{j}^{-1}h_{r_{1}}^{t_{1}}\ldots h_{r_{l}}^{t_{l}}|}.$
(S.56)

This reduces to the expression in Ref. Jian  _et al._ (2020) for $q=0$
whereupon $\left\langle\left\langle
g_{i}\right|\right|\mathcal{K}\left|\left|g_{j}\right\rangle\right\rangle=d^{\left|g_{i}g_{j}^{-1}\right|}$.
In that case the weights may be interpreted as follows: when $p$ is large the
weight is nearly invariant under changes to the states corresponding to the
paramagnetic regime and, for small $p$, the system tries to maximize the
number of cycles in $g_{i}g_{j}^{-1}$ corresponding to an identity permutation
where the permutation degrees of freedom are ferromagnetic spontaneously
breaking one permutation symmetry.

In the presence of $q\neq 0$, the symmetry that is spontaneously broken for
small $p$ is explicitly broken by $q$ analogous to a field applied to a
classical ferromagnet. This is consistent with the crossover observed
numerically.

###  S.II.G Limiting cases

We consider limiting cases that serve to illustrate some features of the
model. We first linearize in $q$:

$\displaystyle\left\langle\left\langle
g\right|\right|\mathcal{K}\left|\left|g^{\prime}\right\rangle\right\rangle=(1-q)d^{\left|gg^{\prime-1}\right|}+q\sum_{r=1}^{Q}d^{|gg^{\prime-1}h_{r}^{t}|}+\mathcal{O}(q^{2}).$
(S.57)

We then take the $d\rightarrow\infty$ limit. For that, let us take (S.57) up
to $\mathcal{O}(d^{Q-2})$. We have

$\displaystyle
d^{\left|gg^{\prime-1}\right|}=\sum_{k=1}^{Q}d^{k}\delta_{|gg^{\prime-1}|,k}=d^{Q}\delta_{g^{-1},g^{\prime-1}}+d^{Q-1}\delta_{|gg^{\prime-1}|,Q-1}+\mathcal{O}(d^{Q-2})$
(S.58)

and

$\displaystyle\sum_{r=1}^{Q}d^{|gg^{\prime-1}h_{r}^{t}|}$
$\displaystyle=|g|_{1}\delta_{g^{-1},g^{\prime-1}}d^{Q}+\left(\max(|g|_{1},|g^{\prime-1}|_{1})\,\delta_{|gg^{\prime-1}|,Q-1}+Q\delta_{|gg^{\prime-1}|,Q}\,\delta_{|g|_{1},0}\right)d^{Q-1}+\mathcal{O}(d^{Q-2})$
$\displaystyle=|g|_{1}\delta_{g^{-1},g^{\prime-1}}d^{Q}+\left(\max(|g|_{1},|g^{\prime-1}|_{1})\,\delta_{|gg^{\prime-1}|,Q-1}+Q\delta_{g^{-1},g^{\prime-1}}\,\delta_{|g|_{1},0}\right)d^{Q-1}+\mathcal{O}(d^{Q-2})$
(S.59)

where we used $\delta_{|gg^{\prime-1}|,Q}=\delta_{g^{-1},g^{\prime-1}}$ and
where $|g|_{1}$ denotes the number of 1-cycles in the permutation $g$. Thus,

$\displaystyle\left\langle\left\langle
g\right|\right|\mathcal{K}\left|\left|g^{\prime}\right\rangle\right\rangle$
$\displaystyle=\left((1-q)+q|g|_{1}\right)\delta_{g^{-1},g^{\prime-1}}d^{Q}$
$\displaystyle+\left([1+q\max(|g|_{1},|g^{\prime-1}|_{1})]\delta_{|gg^{\prime-1}|,Q-1}+qQ\delta_{g^{-1},g^{\prime-1}}\,\delta_{|g|_{1},0}\right)d^{Q-1}+\mathcal{O}(d^{Q-2})$
(S.60)

The leading order in $d$ result in (S.60) reveals that the full $S_{Q}\times
S_{Q}\rtimes\mathbb{Z}_{2}$ symmetry of the $q=0$ model is broken down to
$S_{Q}\rtimes\mathbb{Z}_{2}$.


# Lipschitz harmonic functions on vertex-transitive graphs

Gideon Amir<EMAIL_ADDRESS>Bar-Ilan University, Ramat Gan 52900, Israel
,  Guy Blachar<EMAIL_ADDRESS>Bar-Ilan University, Ramat Gan 52900,
Israel  ,  Maria Gerasimova<EMAIL_ADDRESS>Westälische Wilhelms-
Universität Münster, 48149 Münster, Germany  and  Gady Kozma
<EMAIL_ADDRESS>The Weizmann Institute of Science, Rehovot 76100,
Israel

###### Abstract.

We prove that every locally finite vertex-transitive graph $G$ admits a non-
constant Lipschitz harmonic function.

##  1\. Introduction

In this paper we are interested in the space of Lipschitz harmonic functions
on a graph (precise definitions will be given below). The structure of the
space of such functions played a crucial role in Kleiner’s proof of Gromov’s
theorem [4, 8, 10] and has thus attracted some attention [11, 5]. In
particular, Kleiner showed that any Cayley graph supports a non-trivial
Lipschitz harmonic function. Our purpose in this paper is to generalize this
fact to vertex-transitive graphs. Any Cayley graph is vertex-transitive, but
the opposite is not true. In fact, there exist vertex-transitive graphs which
are quite far from Cayley graphs in a precise sense [1]. Generalizing results
from Cayley graphs to vertex-transitive graphs is sometimes challenging, see
for example [12].

In this note we prove the following theorem, answering a problem of
Georgakopoulos and Wendland [2, Problem 1.1] (who also proved a partial
result, see [2, Proposition 3.1]). Another partial result was proved much
earlier by Trofimov [13], who showed that any infinite vertex-transitive graph
supports a non-constant harmonic function, but with weaker control on the
growth of the function.

######  Theorem 1.1.

Every infinite, locally finite vertex-transitive graph $G$ admits a non-
constant Lipschitz harmonic function.

##  2\. Proof of Theorem 1.1

We start with some standard definitions.

######  Definition 2.1.

For a function $f\colon V\to\mathbb{C}$ we define $\nabla f$ to be a function
on the directed edges of the graph $V$ by $\nabla f(v,w)=f(v)-f(w)$. We define
$\Delta f$ to be a function on $V$ by $\Delta f(v)=\sum_{w\sim v}(f(v)-f(w))$.
A function $f\colon V\to\mathbb{C}$ on a graph $G=(V,E)$ is called harmonic if
$\Delta f\equiv 0$. We will say that $f$ is Lipschitz if $\nabla
f\in\ell^{\infty}(E).$

With the theorem now completely defined we can start the proof, but, before
starting the proof, let us discuss shortly the issue of unimodularity. A
locally compact group is called unimodular if its left and right Haar measures
are identical, and a vertex-transitive graph is called unimodular if its
automorphism group, with the topology of pointwise convergence, is unimodular.
Unimodularity can play an important role in studying probability on vertex-
transitive graphs, see for example, [6, Chapter 12]. Contrariwise, non-
unimodular vertex-transitive graphs have the so-called modular function which
can also aid in their analysis, see e.g. [3]. What we will use below is the
fact, first proved in [9], that any amenable vertex-transitive graph is
unimodular.

######  Definition 2.2.

A graph $G=(V,E)$ is called amenable if there exists a sequence of subsets
$X_{n}\subseteq V$ such that

$\lim_{n\to\infty}\frac{|\partial X_{n}|}{|X_{n}|}=0,$

where $\partial X=\\{v\in V\setminus X:\exists\leavevmode\nobreak\ w\in
X,w\sim v\\}$ is the outer vertex boundary of $X$.

Note that outer vertex boundary in this definition can be changed to any other
type of boundary. The following fact is well-known, and we include its proof
for completeness of the exposition.

######  Lemma 2.3.

Any regular amenable graph $G=(V,E)$ admits a sequence of functions $f_{n}$
such that

$\|\nabla f_{n}\|_{\ell^{2}(E)}=1,\leavevmode\nobreak\ \leavevmode\nobreak\
\|\Delta f_{n}\|_{\ell^{2}(V)}\to 0.$

###### Proof.

We first show that the spectrum of the operator $\Delta$ contains 0. This is
well-known (sometimes called Buser’s inequality), but let us give the proof
nonetheless. We take $h_{n}:=\frac{1}{\sqrt{|X_{n}|}}\cdot\mathbbm{1}_{X_{n}}$
to be the normalized characteristic functions of the sets $X_{n}$ from
Definition 2.2. They satisfy

$\|h_{n}\|_{\ell^{2}(V)}=1,\quad\|\Delta
h_{n}\|_{\ell^{2}(V)}^{2}\leq\frac{|\partial
X_{n}|\cdot(\deg(G)+1)}{|X_{n}|}\to 0.$

Thus indeed $0$ is in the spectrum of $\Delta$ (as an operator on
$\ell^{2}(V)$). Further, by the maximum principle there is no zero
eigenfunction.

By the spectral theorem, the positive self-adjoint operator $\Delta$ is
unitary equivalent to a multiplication operator on $L^{2}(Y,\nu)$ that
multiplies by some non-negative function $F(y)$. The argument above shows that
$\nu(F^{-1}((0,\varepsilon]))>0$ for any $\varepsilon>0$. Define
$f_{\varepsilon}$ to be the map of $\mathbbm{1}_{F^{-1}((0,\varepsilon])}$
under the unitary equivalence. Then

$\displaystyle\langle\Delta f_{\varepsilon},\Delta f_{\varepsilon}\rangle$
$\displaystyle=\int_{F^{-1}((0,\varepsilon])}F^{2}(y)\,d\nu(y)\leq\varepsilon\int_{F^{-1}((0,\varepsilon])}F(y)\,d\nu(y)$
$\displaystyle=\varepsilon\langle f_{\varepsilon},\Delta
f_{\varepsilon}\rangle$

where the equalities follow from the unitary equivalence. Since $\langle
f,\Delta f\rangle\cdot 2\deg(G)=\|\nabla f\|_{\ell^{2}(E)}^{2}$, this gives us
a sequence of functions $f_{n}$ on $G$ such that

$\|\nabla f_{n}\|_{\ell^{2}(E)}=1,\leavevmode\nobreak\ \leavevmode\nobreak\
\|\Delta f_{n}\|_{\ell^{2}(V)}\to 0.\qed$

###### Proof of main theorem.

The non-amenable case follows from Piaggio and Lessa [7]. To be more precise,
they prove that any stationary random graph for which random walk has positive
entropy has an infinite dimensional space of bounded harmonic functions. Since
vertex transitive graphs are stationary random graphs and any bounded function
is Lipschitz, it remains to show that random walk on any non-amenable graph
has positive entropy. To see this, we may assume that the random walk is lazy,
and note that by Cheeger’s inequality [6, §7.2] non-amenability implies that
the spectral radius of the random walk is strictly smaller then $1$. It
follows that the transition probabilities decay exponentially in the number of
steps, and therefore the entropy of the random walk grows linearly with the
number of steps i.e. it has positive entropy. This finishes the non-amenable
case.

We therefore assume that the graph $G=(V,E)$ is amenable. Our proof will be
similar to the proof of Shalom and Tao [8, 10].

By a well-known theorem of Soardi and Woess [9, Corollary 1], a vertex-
transitive graph $G$ is amenable if and only if its automorphism group
$\operatorname{Aut}(G)$ is amenable and unimodular. We write $\mu$ for the
Haar measure on $\operatorname{Aut}(G)$, which is bi-invariant by
unimodularity, normalized so that $\mu(\operatorname{Stab}(v))=1$ for any
$v\in V$.

Let us fix some vertex $o\in V$. For any $a,b\in V$, denote by
$H_{a,b}\subseteq\operatorname{Aut}(G)$ the set of all automorphisms of $G$
that map $a$ to $b$. We will use similar notations for multiple pairs of
vertices / edges. Take automorphisms $f_{o,a},f_{b,o}\in\operatorname{Aut}(G)$
so that $f_{o,a}(o)=a$ and $f_{b,o}(b)=o$. Then
$\operatorname{Stab}(o)=H_{o,o}=f_{b,o}H_{a,b}f_{o,a}$, so
$\mu(H_{a,b})=\mu(\operatorname{Stab}(o))=1$ (since $\mu$ is bi-invariant).

Take $f_{n}$ from Lemma 2.3, note that

$\sum_{e_{0}=(o,v)\in E}\sum_{e\in E}|\nabla
f_{n}(e)|^{2}\cdot\mu(H_{e,e_{0}})=\|\nabla f_{n}\|_{\ell^{2}(E)}^{2}=1,$

so we may choose an edge $e_{0}$ with origin at $o$ such that

$\sum_{e\in E}|\nabla f_{n}(e)|^{2}\cdot\mu(H_{e,e_{0}})\geq\frac{1}{\deg(G)}$

for infinitely many $n$. After passing to a subsequence we can assume that it
holds for all $n$.

We define new functions $g_{n}$ by

$g_{n}(v)=\sum_{e\in
E}C_{e,n}\int_{H_{e,e_{0}}}f_{n}(T^{-1}v)\leavevmode\nobreak\ d\mu(T),$

where $C_{e,n}=\nabla f_{n}(e)$. By construction

$\nabla g_{n}(e_{0})=\sum_{e\in E}|\nabla
f_{n}(e)|^{2}\cdot\mu(H_{e,e_{0}})\geq\frac{1}{\deg(G)}.$

We want to estimate $\|\nabla g_{n}\|_{\ell^{2}(E)}$ and $\|\Delta
g_{n}\|_{\ell^{2}(V)}$. For this purpose define
$H(\begin{subarray}{c}e,e_{0}\\\ w,v\end{subarray})$ to be the set of
automorphisms that take the edge $e$ to $e_{0}$ and the vertex $w$ to $v$.
Note that $\mu(H(\begin{subarray}{c}e,e_{0}\\\
w,v\end{subarray}))\leq\mu(H_{e,e_{0}})\leq 1$. Therefore

$\displaystyle|\Delta g_{n}(v)|$ $\displaystyle\leq\sum_{e\in
E}|C_{e,n}|\sum_{w\in V}\int_{H(\begin{subarray}{c}e,e_{0}\\\
w,v\end{subarray})}|\Delta f_{n}(T^{-1}v)|\leavevmode\nobreak\ d\mu(T)$
$\displaystyle=\sum_{e\in E}\sum_{w\in
V}|C_{e,n}|\cdot\mu\left(H(\begin{subarray}{c}e,e_{0}\\\
w,v\end{subarray}))\right)\cdot|\Delta f_{n}(w)|$
$\displaystyle\leq\|(C_{e,n})_{e}\|_{\ell^{2}(E)}\cdot\left\|\left(\mu\left(H(\begin{subarray}{c}e,e_{0}\\\
w,v\end{subarray})\right)\right)_{e,w}\right\|_{\ell^{2}(V)\to\ell^{2}(E)}\cdot\|\Delta
f_{n}\|_{\ell^{2}(V)}$ $\displaystyle\leq\|\Delta f_{n}\|_{\ell^{2}(V)}\to 0.$

The second inequality follows by using Cauchy-Schwarz for the sequences
$(C_{e,n})_{e}$ and $\sum_{w\in V}\mu\left(H(\begin{subarray}{c}e,e_{0}\\\
w,v\end{subarray}))\right)\cdot|\Delta f_{n}(w)|$ (note that the second norm
is the operator norm). On the last step we used the Riesz-Thorin inequality
$\|A\|^{2}\leq\|A\|_{1}\cdot\|A\|_{\infty}$ and the fact that

$\sum_{e\in E}\mu\left(H(\begin{subarray}{c}e,e_{0}\\\
w,v\end{subarray})\right)=\mu(H_{w,v})=1,\quad\sum_{w\in
V}\mu\left(H(\begin{subarray}{c}e,e_{0}\\\
w,v\end{subarray})\right)=\mu(H_{e,e_{0}})\leq 1.$

Define $\widehat{\nabla}$ by

$\widehat{\nabla}f(v):=\sum_{w\sim v}|f(w)-f(v)|.$

Denoting by $e^{+}$ the origin of the edge $e$, the same reasoning gives us

$|\nabla
g_{n}(e)|\leq|\widehat{\nabla}g_{n}(e^{+})|\leq\|\widehat{\nabla}f_{n}\|_{\ell^{2}(V)}\leq\sqrt{\deg(G)}\cdot\|\nabla
f_{n}\|_{\ell^{2}(E)}=\sqrt{\deg(G)}.$

Let us sum everything up. We have $\|\nabla
g_{n}\|_{l^{\infty}(E)}\leq\sqrt{\deg(G)}$, $\|\Delta
g_{n}\|_{\ell^{\infty}(V)}\to 0$ and $\nabla
g_{n}(e_{0})\geq\nicefrac{{1}}{{\deg(G)}}$. After adding constant functions we
can assume that $g_{n}(o)=0$. Since $\nabla g_{n}$ is bounded, $g_{n}(v)$ is
bounded (with a bound that depends on $v$) and we can use compactness to pass
to a subsequence where $g_{n}$ converges pointwise to some function $g$. It
follows that $\|\nabla g\|_{\ell^{\infty}(E)}\leq\sqrt{\deg(G)}$ and $\Delta
g=0$. Finally, $|\nabla g(e_{0})|>\nicefrac{{1}}{{\deg G}}$ so $g$ is not
constant. This finishes the proof. ∎

## Acknowledgements

During this research G.A. and G.B. were supported by Israeli Science
Foundation grant #957/20. G.B. was also supported by the Bar-Ilan President’s
Doctoral Fellowships of Excellence. G.K. was supported by the Israel Science
Foundation grant #607/21 and by the Jesselson Foundation. M.G. was supported
by the DFG – Project-ID 427320536 – SFB 1442, and under Germany’s Excellence
Strategy EXC 2044 390685587, Mathematics Münster: Dynamics–Geometry–Structure.

## References

  * [1] Alex Eskin, David Fisher, and Kevin Whyte.  Coarse differentiation of quasi-isometries I: Spaces not quasi-isometric to Cayley graphs.  Annals of Mathematics, pages 221–260, 2012.
  * [2] Agelos Georgakopoulos and Alex Wendland.  A study of 2-ended graphs via harmonic functions.  arXiv preprint arXiv:2304.13317, 2023.
  * [3] Tom Hutchcroft.  Nonuniqueness and mean-field criticality for percolation on nonunimodular transitive graphs.  Journal of the American Mathematical Society, 33(4):1101–1165, 2020\.
  * [4] Bruce Kleiner.  A new proof of Gromov’s theorem on groups of polynomial growth.  Journal of the American Mathematical Society, 23(3):815–829, 2010\.
  * [5] Tom Meyerovitch and Ariel Yadin.  Harmonic functions of linear growth on solvable groups.  Israel Journal of Mathematics, 216(1):149–180, 2016.
  * [6] Gábor Pete.  Probability and geometry on groups.  Unpublished lecture notes. http://www.math.bme.hu/g̃abor/PGG.pdf, June 2023 version.
  * [7] Matías Carrasco Piaggio and Pablo Lessa.  Equivalence of zero entropy and the Liouville property for stationary random graphs.  Electron. J. Probab, 21(55):1–24, 2016.
  * [8] Yehuda Shalom and Terence Tao.  A finitary version of Gromov’s polynomial growth theorem.  Geometric and Functional Analysis, 20:1502–1547, 2010.
  * [9] Paolo Maurizio Soardi and Wolfgang Woess.  Amenability, unimodularity, and the spectral radius of random walks on infinite graphs.  Math. Z., 205(3):471–486, 1990.
  * [10] Terence Tao.  A proof of Gromov’s theorem.  Blog. Available at http://terrytao.wordpress.com/2010/02/18/a-proof-of-gromovs-theorem/.
  * [11] Matthew CH Tointon.  Characterisations of algebraic properties of groups in terms of harmonic functions.  Groups, Geometry, and Dynamics, 10(3):1007–1049, 2016.
  * [12] Vladimir Ivanovich Trofimov.  Graphs with polynomial growth.  Mathematics of the USSR-Sbornik, 51(2):405, 1985.
  * [13] Vladimir Ivanovich Trofimov.  The existence of nonconstant harmonic functions on infinite vertex-symmetric graphs.  European Journal of Combinatorics, 19(4):519–523, 1998.