# Disordered Lieb-Robinson bounds in one dimension

Christopher L. Baldwin  Joint Quantum Institute, University of Maryland,
College Park, MD 20742, USA  Adam Ehrenberg  Joint Quantum Institute,
University of Maryland, College Park, MD 20742, USA  Joint Center for Quantum
Information and Computer Science, NIST/University of Maryland, College Park,
MD 20742, USA  Andrew Y. Guo  Joint Quantum Institute, University of Maryland,
College Park, MD 20742, USA  Joint Center for Quantum Information and Computer
Science, NIST/University of Maryland, College Park, MD 20742, USA  Alexey V.
Gorshkov  Joint Quantum Institute, University of Maryland, College Park, MD
20742, USA  Joint Center for Quantum Information and Computer Science,
NIST/University of Maryland, College Park, MD 20742, USA  National Institute
of Standards and Technology, Gaithersburg, MD 20899, USA

###### Abstract

By tightening the conventional Lieb-Robinson bounds to better handle systems
which lack translation invariance, we determine the extent to which “weak
links” suppress operator growth in disordered one-dimensional spin chains. In
particular, we prove that ballistic growth is impossible when the distribution
of coupling strengths $\mu(J)$ has a sufficiently heavy tail at small $J$, and
identify the correct dynamical exponent to use instead. Furthermore, through a
detailed analysis of the special case in which the couplings are genuinely
random and independent, we find that the standard formulation of Lieb-Robinson
bounds is insufficient to capture the complexity of the dynamics — we must
distinguish between bounds which hold for all sites of the chain and bounds
which hold for a subsequence of sites, and we show by explicit example that
these two can have dramatically different behaviors. All the same, our result
for the dynamical exponent is tight, in that we prove by counterexample that
there cannot exist any Lieb-Robinson bound with a smaller exponent. We close
by discussing the implications of our results, both major and minor, for
numerous applications ranging from quench dynamics to the structure of ground
states.

##  I Introduction

Lieb-Robinson (LR) bounds, named after Ref. Lieb and Robinson (1972), have
proven to be a valuable mathematical tool for many-body physics and quantum
information theory Hastings (2004); Nachtergaele and Sims (2006); Hastings and
Koma (2006); Bravyi  _et al._ (2006); Osborne (2006); Schuch  _et al._ (2011);
Abanin  _et al._ (2015); Shiraishi and Tajima (2017); Eldredge  _et al._
(2017); Deshpande  _et al._ (2018); Haah  _et al._ (2018); Bentsen  _et al._
(2019); Nachtergaele  _et al._ (2019). Conceptually, they provide hard
constraints on the extent to which correlations of any type can spread through
a many-body lattice system (broadly termed “operator spreading”). Numerous
applications, from rigorous results on many-body ground states to lower bounds
on the runtime of quantum protocols, can be found in the above references.

Given their utility, LR bounds have been both generalized and specialized in
multiple ways: leveraging the commutativity and graph structure of
interactions Prémont-Schwarz  _et al._ (2010); Wang and Hazzard (2020); Chen
and Lucas (2021), allowing for long-range interactions Foss-Feig  _et al._
(2015); Tran  _et al._ (2019); Chen and Lucas (2019); Kuwahara and Saito
(2020); Tran  _et al._ (2021a), and considering open systems Poulin (2010);
Descamps (2013); Sweke  _et al._ (2019); Guo  _et al._ (2021), to name a few.
However, one ingredient that has been noticeably absent is disorder, or more
generally a lack of translation invariance. To be fair, the conventional
bounds do allow for non-translation-invariant interactions, but there have
been no studies assessing the tightness of the resulting bounds (and we shall
find that they are far from tight). Certain works have considered related
topics — Refs. Burrell  _et al._ (2009); Gebert  _et al._ (2022) study the
effects of disordered local terms (albeit with uniform interactions), and Ref.
Chen (2021) derives bounds for random Hamiltonians with statistical
translation invariance111Ref. Chen (2021) does in fact allow for non-
translation-invariant interactions, but in the same manner as do the
conventional bounds. It would be worthwhile to investigate whether the results
of Ref. Chen (2021) can be tightened much as we do here.. Others have
calculated bounds for specific (often free-fermion-integrable) systems Burrell
and Osborne (2007); Hamza  _et al._ (2012); Gebert and Lemm (2016); Elgart
_et al._ (2018). While interesting on their own merits, none of these quite
address the question with which we concern ourselves here — to what extent is
operator spreading (as constrained by LR bounds) necessarily suppressed by
non-translation-invariant interactions?

Non-translation-invariant systems are known to exhibit a variety of phenomena
not found in their translation-invariant counterparts. Examples include spin
glass phases (both static and dynamic) Fischer and Hertz (1991); Mezard and
Montanari (2009), localization Lee and Ramakrishnan (1985); Kramer and
MacKinnon (1993), and Griffiths effects Vojta (2010). Disordered fermionic
models have been used to help understand quantum dots and strongly correlated
metals as well Song  _et al._ (2017); Altland  _et al._ (2019a, b). Of
particular (and somewhat controversial) interest is the phenomenon of many-
body localization (MBL) Basko  _et al._ (2006); Huse  _et al._ (2014);
Nandkishore and Huse (2015); Abanin  _et al._ (2019), whose existence remains
under debate Imbrie (2016); Suntajs  _et al._ (2020); Abanin  _et al._ (2021);
Sels and Polkovnikov (2021); Crowley and Chandran (2020). Given the challenges
inherent in studying not only MBL but disordered quantum many-body systems in
general, it is all the more important to identify rigorous constraints such as
those which LR bounds supply (although to be clear, our results and LR bounds
in general are not strong enough to resolve the questions surrounding MBL, as
we explain in Sec. II).

In the present work, we initiate the study of non-translation-invariant LR
bounds by considering arguably the simplest (but still quite rich) situation:
one-dimensional chains with nearest-neighbor interactions. An essential
feature of such systems is the importance of “weak links”, i.e., atypically
weak interactions. We develop the machinery for analyzing these systems, prove
that the LR bounds thus obtained are in a certain sense optimal, and use the
results to place constraints on various physical properties and processes.

Sec. II summarizes our results in conceptual terms. We have aimed to make it
sufficiently self-contained so that readers primarily interested in our
conclusions and willing to forgo the derivations should be able to read Sec.
II on its own. Sec. III then gives precise definitions of all quantities
involved in our analysis. Sec. IV derives LR bounds for general non-
translation-invariant systems, and Sec. V specializes to the case of random
couplings. Sec. VI lastly discusses some implications of our results, in
particular related to: quench dynamics, topological order, heating rates,
ground state correlations, and machine learning of local observables.

##  II Summary of results

Figure 1: Geometry of the systems studied in the present work, i.e., 1D chains
with nearest-neighbor interactions. Sites are indicated by black squares,
labelled by $i$. Terms of the Hamiltonian are indicated by solid lines, with
$H_{l}(t)$ acting on the two sites connected by that link. Given a set
$\\{J_{l}\\}$, we require that $\lVert H_{l}(t)\rVert\leq J_{l}$. Figure 2:
The possibility of a Hamiltonian causing operator spreading at dynamical
exponent $z$, i.e., in a time growing asymptotically as $t(r)\propto r^{z}$ to
reach a large distance $r$. Horizontal axis is the exponent $\alpha$
characterizing the number of weak links in the couplings $\\{J_{l}\\}$ — the
fraction of links between sites 0 and $r$ having $J_{l}\leq J$ is assumed to
go as $J^{\alpha}$ at small $J$ and large $r$. Vertical axis is $z$. Blue
region is where no Hamiltonian with such $\alpha$ can reach any large-distance
site at such $z$. Red region is where a Hamiltonian exists with such $\alpha$
that reaches every large-distance site at (or faster than) such $z$. The
boundary between the two is given by $z_{c}(\alpha)=\max[1/\alpha,1]$. In the
special case of independent random couplings, the $\alpha>1$ portion of the
boundary is included in the red region, while the $\alpha<1$ portion (shown in
purple) is where a Hamiltonian exists that reaches a subsequence of sites
faster than $z$ but where no Hamiltonian can reach every site at such $z$.
Lastly, at point $(\alpha,z)=(1,1)$, no Hamiltonian can reach every site
ballistically but it is unknown whether any Hamiltonian can reach some sites
ballistically.

We determine the extent to which operator spreading in 1D nearest-neighbor
chains is suppressed by weak links. To be precise, we consider arbitrary
$d$-state degrees of freedom (“qudits”) interacting via any Hamiltonian of the
form $H(t)=\sum_{l}H_{l}(t)$, where the sum is over links of the chain and
$H_{l}(t)$ acts on the two sites connected by link $l$ (although our analysis
in fact allows for arbitrary local terms as well222Our results actually apply
to any Hamiltonian of the form
$H(t)=\sum_{l\in\Lambda}H_{l}(t)+\sum_{i\in\Omega}h_{i}(t)$, for arbitrary
local terms $h_{i}(t)$. The local terms can trivially be accounted for by
first passing to the interaction picture with respect to them — the terms
$H_{l}(t)$ in this new frame have both the same support and the same norm as
originally, hence our analysis applies equally well using them. That said, the
behavior of any specific system clearly can depend strongly on the local
terms.). See Fig. 1. Unlike previous works, we assume that $\lVert
H_{l}(t)\rVert\leq J_{l}$ where $J_{l}$ varies from link to link
($\lVert\,\cdot\,\rVert$ denotes the operator norm throughout). The “weak”
links are those on which $J_{l}$ is much smaller than the typical value.

For arbitrary local operators $A_{0}$ and $B_{r}$ supported on sites 0 and $r$
respectively, and with $A_{0}^{t}$ denoting the evolution of $A_{0}$ over time
$t$, our goal is to bound the quantity $\lVert[A_{0}^{t},B_{r}]\rVert$ as
tightly as possible, making use of the weak links in the set $\\{J_{l}\\}$. We
particularly focus on the asymptotic behavior at large $r$ and $t$. The
commutator $[A_{0}^{t},B_{r}]$ is a standard and useful measure of operator
spreading (as we describe in Sec. III.2), but it is by no means the only such
measure. In fact, most of our calculations will involve a different quantity
from which bounds on the commutator easily follow.

LR bounds are best viewed as applying to families of Hamiltonians. For each
set of couplings $\\{J_{l}\\}$, we use $\mathcal{H}_{J}$ to denote the set of
all Hamiltonians as described above consistent with $\\{J_{l}\\}$ (i.e.,
$\lVert H_{l}(t)\rVert\leq J_{l}$ for all links $l$ at all times $t$). Our
bounds are uniform among $H\in\mathcal{H}_{J}$, in the sense that they make no
reference to any property of the Hamiltonian beyond the couplings
$\\{J_{l}\\}$. Thus while the results are extremely general, they may not be
very tight for one specific system. The “tightness” of LR bounds referred to
in this paper is instead the existence of some $H\in\mathcal{H}_{J}$ which
saturates the bound.

As a consequence of their generality, LR bounds have little to say regarding,
e.g., the existence of MBL — the complete lack of operator spreading in
strongly disordered time-independent systems Basko  _et al._ (2006); Huse  _et
al._ (2014); Nandkishore and Huse (2015); Abanin  _et al._ (2019). The same
applies to other phenomena involving slow dynamics under a fixed Hamiltonian,
such as activated processes in spin glasses Chamon  _et al._ (2002); Bapst
_et al._ (2013); Baldwin and Laumann (2018). Those $H\in\mathcal{H}_{J}$ that
saturate our bounds will instead tend to be highly time-dependent
Hamiltonians, specifically designed to transmit information and better viewed
as quantum circuits. These are the types of systems for which LR bounds give a
reasonably full picture.

Our first result, which holds for any possible set of couplings $\\{J_{l}\\}$,
is an improvement on the conventional LR bound. Whereas the standard
analysis333We are certainly not the first to improve on Eq. (1) — see, e.g.,
Refs. Wang and Hazzard (2020); Chen and Lucas (2021) for modifications that
yield smaller LR velocities, sometimes even parametrically so. We have not
attempted to marry our approach with theirs, but we expect that it can be done
and leave this for future work. leads to the result

$\Big{\lVert}\big{[}A_{0}^{t},B_{r}\big{]}\Big{\rVert}\leq
C\big{\lVert}A_{0}\big{\rVert}\big{\lVert}B_{r}\big{\rVert}\left(\prod_{l=1}^{r}4J_{l}\right)\frac{t^{r}}{r!},$
(1)

we show that one further has

$\Big{\lVert}\big{[}A_{0}^{t},B_{r}\big{]}\Big{\rVert}\leq
C\big{\lVert}A_{0}\big{\rVert}\big{\lVert}B_{r}\big{\rVert}\min_{\lambda}\left[\left(\prod_{l\in\lambda}4J_{l}\right)\frac{t^{|\lambda|}}{|\lambda|!}\right],$
(2)

where the minimization is over all subsets $\lambda$ of the links between
sites 0 and $r$ ($|\lambda|$ denotes the size of the subset). Even though much
of what follows will be concerned with the asymptotic behavior, Eq. (2) holds
for all $r$ and $t$. In these equations and throughout the entire paper, we
use $C$ to denote any constant which does not depend on $r$ or $t$ and whose
precise value is irrelevant to our conclusions. Its value will often change
between expressions (and primes/subscripts will differentiate such constants
within the same expression).

Figure 3: Circuit diagram of a simple protocol that transfers the state on
site 0 to site $r$ (here sites are arranged vertically and solid lines
indicate the absence of any unitary). The definition of the SWAP gate acting
on sites $i$ and $i+1$ is given at the bottom of the figure — $a$ and $b$
label basis states of the local Hilbert space (each taking values in
$\\{1,\cdots,d\\}$).

We next derive more explicit bounds by considering the “empirical
distribution” $\mu_{r}(J)$, defined (for a given set $\\{J_{l}\\}$) as the
fraction of links between sites 0 and $r$ having $J_{l}\leq J$:

$\mu_{r}(J)\equiv\frac{1}{r}\sum_{l=1}^{r}\delta_{J_{l}\leq J},$ (3)

where $\delta_{J_{l}\leq J}\equiv 1$ if $J_{l}\leq J$ and 0 otherwise. We
assume that $\mu_{r}(J)$ converges as $r\rightarrow\infty$ (in a sense defined
in Sec. IV.3) to a function $\mu(J)$, and that the latter behaves as a power
law at small $J$: $\mu(J)\sim\mu_{0}J^{\alpha}$ with $\alpha>0$. The exponent
$\alpha$ characterizes the prevalence of weak links, with smaller $\alpha$
implying more weak links. Our analysis in fact applies for more general forms
of $\mu(J)$ (as we discuss in Sec. IV.3), but the power-law behavior is
particularly convenient and representative. Note that the convergence of
$\mu_{r}(J)$ to $\mu(J)$ does not assume anything regarding the arrangement of
weak links in space — many of our results will hold regardless of where the
weak links are located.

An essential feature of an LR bound is the shape of the “front”, i.e., the
spacetime curve $t(r)$ that separates the region in which the bound is small
from that in which the bound is large (and thus vacuous). The dynamical
exponent $z$ and generalized LR velocity $v$ are defined by the asymptotic
behavior $vt(r)\sim r^{z}$ at large $r$. Keep in mind that $v$ has units of a
genuine velocity only when $z=1$ — we will stick to the term “generalized
velocity”444An alternate quantity is
$v_{\textrm{LR}}(r)\equiv[\textrm{d}t(r)/\textrm{d}r]^{-1}$ Foss-Feig  _et
al._ (2015). Although distance-dependent, $v_{\textrm{LR}}(r)$ has the correct
units of velocity even when $z\neq 1$. for $z\neq 1$. Whereas the conventional
LR bound, Eq. (1), has a ballistic front ($z=1$) for all $\alpha>0$, we show
that the improved bound, Eq. (2), instead has

$z_{c}(\alpha)=\max\big{[}\alpha^{-1},1\big{]}.$ (4)

The curve $z_{c}(\alpha)$ is sketched in Fig. 2.

One consequence of the above is that there cannot exist any
$H\in\mathcal{H}_{J}$ for which the operator-spreading front grows with a
dynamical exponent $z<z_{c}(\alpha)$. In particular, it is impossible to have
a ballistic front if $\alpha<1$. We have shaded this region blue in Fig. 2 and
labelled it as “asymptotically unattainable on any site” — it is impossible to
construct a Hamiltonian having that value of $\alpha$ which, at large
distances, reaches any site at that value of $z$.

On the other hand, we also identify an $H\in\mathcal{H}_{J}$ whose front grows
faster than any $z>z_{c}(\alpha)$, again requiring only that
$\mu_{r}(J)\rightarrow\mu(J)$ in a suitably strong sense. The Hamiltonian is
rather straightforward, consisting simply of a sequential series of SWAP gates
as shown in Fig. 3. Once all gates have been applied, $A_{0}^{t}$ is supported
on site $r$ and thus will generically fail to commute (by an $r$-independent
amount) with $B_{r}$. In order to satisfy $\lVert H_{l}(t)\rVert\leq J_{l}$,
the total runtime of the circuit is proportional to $\sum_{l=1}^{r}1/J_{l}$ —
analysis of this sum gives the behavior of the front.

We have shaded the region $z>z_{c}(\alpha)$ red in Fig. 2 and labelled it as
“asymptotically attainable on all sites” — it is possible (and we do so) to
construct a Hamiltonian having that value of $\alpha$ which reaches every
large-distance site at that value of $z$. In this sense, Eq. (4) is the
dynamical exponent for a given $\alpha$, i.e., Eq. (4) is tight.

It is rather striking that our result for $z_{c}(\alpha)$ agrees exactly with
the value predicted on physical grounds in Ref. Nahum  _et al._ (2018). The
results of Ref. Nahum  _et al._ (2018) are based on a coarse-grained
description of 1D disordered systems, in which it is postulated that a region
$l$ can be characterized by an effective “growth rate” $\Gamma_{l}$ setting
the rate at which operators spread across the region. The authors assume that
$\Gamma_{l}$ is power-law-distributed with exponent $\alpha$ (although they
work with the probability density having exponent $\alpha-1$), and ultimately
deduce precisely Eq. (4). Our results are somewhat more limited in scope555In
a different sense, our results are actually more general than those of Ref.
Nahum  _et al._ (2018) — we derive bounds for an individual realization of
couplings, and thus are agnostic to its origin. For example, many of our
results (namely those in Sec. IV) hold equally well for quasiperiodic systems
as for those with quenched randomness., since we consider microscopic weak
links rather than effective weak links emerging at long wavelengths, but this
nonetheless provides a rigorous foundation for many of the concepts at work in
Ref. Nahum  _et al._ (2018). It would be of great interest to investigate
whether the other phenomena discussed in Ref. Nahum  _et al._ (2018), such as
entanglement growth and transport, can be placed on similar rigorous grounds.

Returning to Fig. 2, the situation becomes much more complicated on the
boundary $z=z_{c}(\alpha)$, i.e., when considering dynamics on the scale set
by $z_{c}(\alpha)$, both for our LR bounds and for our example Hamiltonians.
We demonstrate this by a detailed analysis of the special case in which the
couplings are drawn independently from a literal probability distribution
$\mu(J)$. After proving that $\mu_{r}(J)\rightarrow\mu(J)$ in the required
sense with probability 1, and thus that the portion of Fig. 2 away from
$z_{c}(\alpha)$ does indeed hold, we find that the generic behavior on the
boundary cannot be described by a single bound — we must introduce (at least)
two types of LR bounds:

  * •

“Almost-always” (a.a.) bounds are those that hold for all sites $r$, excepting
at most a finite number of sites. In other words, there exists a distance $R$
such that the bound holds for all $r>R$.

  * •

“Infinitely-often” (i.o.) bounds are those that hold for an infinite
subsequence of sites $\\{r_{k}\\}$ but need not hold outside of those sites.
In other words, for any distance $R$ there exists some site $r>R$ which is
subject to the bound.

One can imagine situations in which either of the above two bounds is more
relevant. For example, suppose that Alice is manipulating one site of a spin
chain and wants to be confident that her actions do not disturb distant
regions in a certain amount of time. In this case, a.a. bounds provide the
desired guarantee. On the other hand, suppose that Bob intends to transmit a
signal along the spin chain. If it is important that his signal reach every
site faster than a certain rate, then i.o. bounds place the heaviest
restrictions on what can be achieved.

In our case (still at $z=z_{c}(\alpha)$ and still assuming independent random
couplings), we find different behaviors depending on how $\alpha$ compares to
1. If $\alpha>1$, the results are straightforward: our example Hamiltonian has
a ballistic front that spreads to every site with finite velocity (note that
$z_{c}(\alpha)=1$ for $\alpha>1$). We have included this portion of the
boundary with the red region in Fig. 2 to indicate that it is also
“asymptotically attainable on all sites” (albeit with a maximum allowed
velocity).

However, we show that if $\alpha<1$, then an i.o. bound having
$z=z_{c}(\alpha)$ and arbitrarily small (generalized) velocity holds, while
concurrently, our example Hamiltonian does reach a subsequence $\\{r_{k}\\}$
asymptotically faster than $z_{c}(\alpha)$ (hence no such a.a. bound can
hold). Both statements hold with probability 1. Thus it is impossible to have
a front which reaches every site at dynamical exponent $z_{c}(\alpha)$, but it
is possible (and we do so) to construct a Hamiltonian which reaches a
subsequence of sites at $z_{c}(\alpha)$. We have drawn this portion of the
boundary purple in Fig. 2 and accordingly labelled it “asymptotically
attainable on some but not all sites”. Keep in mind that we have proven this
final statement only for the special case of independent random couplings.
Nonetheless, it is a highly non-trivial example that makes clear the
importance of distinguishing between a.a. and i.o. bounds.

Interestingly, the lone point $(\alpha,z)=(1,1)$ is the only portion of Fig. 2
in which we have been unable to give a definite answer. An i.o. bound with
vanishing velocity still holds, but the front in our example Hamiltonian is
now sub-ballistic for every site. It may be that a more complicated
Hamiltonian exists which does reach a subsequence $\\{r_{k}\\}$ at finite
velocity, yet it may instead be that a more sophisticated mathematical
technique can produce an a.a. bound with vanishing velocity. Further
investigation is clearly warranted.

Lastly, we discuss the implications of our results for various applications.
The LR bounds themselves have physical content — the statement derived here
that ballistic spreading is impossible for $\alpha<1$ can be considered an
application in and of itself. That said, our results have broader consequences
as well. Applications can roughly be grouped into two classes: those that
follow from the existence of the front, and those that follow from the “tail”
(i.e., the rapid decay of the LR bound at large distances outside the front).
Since we obtain a significantly altered front for $\alpha<1$, our results have
a qualitative impact on the former class. However, while we do find a more
complicated tail than in the conventional bound, the behavior at the largest
distances turns out to be unmodified, and thus our results have only a minor
impact on the latter class.

In the remainder of the paper, we make precise and prove the above statements.
Sec. III establishes notation and the formalism within which we work. Sec. IV,
after reviewing the conventional LR bound, derives Eq. (2) for generic non-
translation-invariant systems, and then makes use of the empirical
distribution $\mu_{r}(J)$ to derive Fig. 2. Sec. V considers the case of
independent random couplings $\\{J_{l}\\}$ in more detail, first proving that
the requirements of the preceding section are met and then examining behavior
on the boundary $z_{c}(\alpha)$, with particular focus on the distinction
between a.a. and i.o. behavior. Sec. VI lastly discusses the consequences of
the above for various applications.

##  III Definitions & notation

###  III.1 Geometry

In this work, we consider an $N$-site lattice in 1D, where each site hosts a
$d$-state degree of freedom. In other words, the Hilbert space is a tensor
product of $N$ local $d$-dimensional Hilbert spaces. Let $\Omega$ denote the
set of all $N$ sites and $\Lambda$ denote the set of all $N-1$ links. Here we
consider only nearest-neighbor Hamiltonians on this lattice, i.e.,
Hamiltonians of the form $H(t)=\sum_{l\in\Lambda}H_{l}(t)$, where $H_{l}(t)$
is supported only on the sites connected by link $l$ (although as noted above
in footnote 2, our results hold for Hamiltonians with arbitrary local terms as
well). These features are illustrated in Fig. 1.

Given a set of couplings $\\{J_{l}\\}_{l\in\Lambda}$, let $\mathcal{H}_{J}$ be
the family of all nearest-neighbor Hamiltonians for which

$\big{\lVert}H_{l}(t)\big{\rVert}\leq J_{l}.$ (5)

We even allow for a non-vanishing fraction of $\\{J_{l}\\}$ to be infinite,
meaning that there is no restriction on the corresponding terms. Pick an
operator of interest $A_{0}$ supported only666In fact, it will be clear from
our proof technique that the support of $A_{0}$ need not be solely site 0 but
can include all sites to the left of 0. Similarly, the support of $B_{r}$ can
include all sites to the right of $r$. In other words, our bounds are “many-
to-many”. on site 0, and similarly $B_{r}$ on site $r$ (the sites can be
either well inside the chain or near the edges — our bounds apply regardless).
For any $H\in\mathcal{H}_{J}$, let $A_{0}^{t}$ be the time evolution of
$A_{0}$, i.e., the solution to777Strictly speaking, Eq. (6) is not the
Heisenberg equation of motion for an arbitrary time-dependent Hamiltonian
$H(t)$. The Heisenberg-picture operator $A_{0}^{t}$ is defined by the relation
$\langle\Psi|A_{0}^{t}|\Psi\rangle\equiv\langle\Psi^{t}|A_{0}|\Psi^{t}\rangle$,
where $|\Psi^{t}\rangle$ is the solution to the Schrodinger equation:
$i\partial_{t}|\Psi^{t}\rangle=H(t)|\Psi^{t}\rangle$ with
$|\Psi^{0}\rangle=|\Psi\rangle$. The solution can be written
$|\Psi^{t}\rangle=\mathcal{T}e^{-i\int\textrm{d}sH(s)}|\Psi\rangle$, where the
operator on the right-hand side is a time-ordered exponential — earlier times
appear to the right. Thus in the expression
$\langle\Psi^{t}|A_{0}|\Psi^{t}\rangle$ which defines $A_{0}^{t}$, earlier
times appear outside later times. The differential equation that correctly has
$A_{0}^{t}$ as its solution is $\partial_{s}A_{0}^{s}=i[H(t-s),A_{0}^{s}]$
with $A_{0}^{0}=A_{0}$ — the commutator must be applied with later times first
and earlier times last. Despite all of this, however, our analysis applies
equally well with $H(t-s)$ in place of $H(s)$. Since the latter is less
burdensome notation-wise, we shall use Eq. (6) without further comment.

$\partial_{t}A_{0}^{t}=i\big{[}H(t),A_{0}^{t}\big{]},\qquad A_{0}^{0}=A_{0}.$
(6)

Even though $A_{0}$ is supported on site 0, $A_{0}^{t}$ will (barring trivial
cases) be supported throughout the entire chain for any $t>0$. The purpose of
LR bounds is to place a bound on the quantity

$D(r,t)\equiv\Big{\lVert}\big{[}A_{0}^{t},B_{r}\big{]}\Big{\rVert},$ (7)

that holds uniformly for all $H\in\mathcal{H}_{J}$. Since only the “portion”
of $A_{0}^{t}$ which acts non-trivially on site $r$ can possibly fail to
commute with $B_{r}$ (see Eq. (13) below), LR bounds considered as functions
of $r$ and $t$ constrain the extent to which local operators “spread”
throughout the system.

It is important to note that the Hamiltonians in $\mathcal{H}_{J}$ can have
arbitrary time dependence, as long as Eq. (5) is obeyed at all times. Thus it
is perhaps more informative to refer to any individual $H\in\mathcal{H}_{J}$
as a “protocol”, since it can for example be a quantum circuit designed to
perform a specific task. As discussed in Sec. II, this distinction sheds light
on the limitations of LR bounds.

The choice to use the operator norm in Eq. (7) has long been standard, as it
enters naturally in many applications Lieb and Robinson (1972); Hastings and
Koma (2006); Bravyi  _et al._ (2006); Abanin  _et al._ (2015). There are
situations in which alternative norms, in particular the Frobenius norm
defined as $\lVert O\rVert_{2}\equiv[d^{-N}\textrm{Tr}O^{{\dagger}}O]^{1/2}$,
may be more relevant and might behave quite differently Tran  _et al._ (2020).
However, the operator norm is itself an upper bound on a wide family of norms
including Frobenius (see App. A). Furthermore, the transfer protocol shown in
Fig. 3 leads to a commutator $[A_{0}^{t},B_{r}]$ which is $O(1)$ using any of
these norms. Thus we shall exclusively consider the operator norm in this
work, and the bounds obtained are automatically tight (at least regarding the
dynamical exponent) for the other norms as well.

###  III.2 Basis strings

The set of Hermitian operators acting on the Hilbert space is itself a real
vector space, and thus we can express any operator as a linear combination of
certain basis operators. First consider a single site $i$ and pick a Hermitian
basis $\\{X_{i}^{(\nu_{i})}\\}$ ($\nu_{i}\in\\{0,1,\cdots,d^{2}-1\\}$). For
the entire chain, we use the tensor product basis $\\{X^{(\nu)}\\}$:

$X^{(\nu)}\equiv\bigotimes_{i=1}^{N}X_{i}^{(\nu_{i})},$ (8)

where $\nu\equiv(\nu_{1},\cdots,\nu_{N})$. We assume (without loss of
generality) that $\\{X_{i}^{(\nu_{i})}\\}$ is chosen to be orthonormal with
respect to the trace product, meaning that the tensor product basis is
orthonormal as well:

$\displaystyle d^{-N}\textrm{Tr}X^{(\nu)}X^{(\nu^{\prime})}$
$\displaystyle=\prod_{i=1}^{N}d^{-1}\textrm{Tr}X_{i}^{(\nu_{i})}X_{i}^{(\nu^{\prime}_{i})}$
(9)
$\displaystyle=\prod_{i=1}^{N}\delta_{\nu_{i}\nu^{\prime}_{i}}=\delta_{\nu\nu^{\prime}}.$

We also take $X_{i}^{(0)}$ to be the identity $I_{i}$. Beyond this, any choice
of basis will work equally well.

We shall often refer to the basis elements as “strings”, and define the
support of a string to be the set of sites on which it does not have the
identity:

$\textrm{supp}X^{(\nu)}\equiv\big{\\{}i:\nu_{i}\neq 0\big{\\}}.$ (10)

An important superoperator acting on the space of Hermitian operators is that
which projects onto basis strings whose supports contain site $i$, i.e.,
strings that act non-trivially on site $i$. We denote this superoperator by
$\mathcal{P}_{i}$:

$\mathcal{P}_{i}X^{(\nu)}\equiv\Big{(}1-\delta_{\nu_{i}0}\Big{)}X^{(\nu)}.$
(11)

Similarly, for any subset of sites $\omega\subseteq\Omega$, we define
$\mathcal{P}_{\omega}$ to project onto basis strings which act non-trivially
somewhere (not necessarily everywhere) within $\omega$. A useful inequality
(see App. A) is that for any $\omega$ and any operator $O$,

$\big{\lVert}\mathcal{P}_{\omega}O\big{\rVert}\leq
2\big{\lVert}O\big{\rVert}.$ (12)

Also note that $[A_{0}^{t},B_{r}]=[\mathcal{P}_{r}A_{0}^{t},B_{r}]$, and so
for $D(r,t)$ in Eq. (7), we have the trivial bound

$D(r,t)\leq
2\big{\lVert}\mathcal{P}_{r}A_{0}^{t}\big{\rVert}\big{\lVert}B_{r}\big{\rVert}.$
(13)

In what follows, we shall focus on bounding
$\lVert\mathcal{P}_{r}A_{0}^{t}\rVert$, with a bound on $D(r,t)$ following
automatically by Eq. (13).

The next important superoperator is the generator of time evolution under
$H(t)$:

$\mathcal{L}(t)O\equiv i\big{[}H(t),O\big{]},$ (14)

and so (Eq. (6))

$\partial_{t}A_{0}^{t}=\mathcal{L}(t)A_{0}^{t}.$ (15)

We will also need the generator corresponding to a subset of terms in the
Hamiltonian. For any subset of links $\lambda\subseteq\Lambda$, define

$\mathcal{L}_{\lambda}(t)O\equiv i\sum_{l\in\lambda}\big{[}H_{l}(t),O\big{]}.$
(16)

Clearly $\mathcal{L}(t)=\sum_{l\in\Lambda}\mathcal{L}_{l}(t)$.

Denote the evolution superoperator itself by $\mathcal{U}(t)$, i.e.,
$A_{0}^{t}\equiv\mathcal{U}(t)A_{0}$ (and define $\mathcal{U}_{\lambda}(t)$
analogously). We can express the action of $\mathcal{U}(t)$ (and
$\mathcal{U}_{\lambda}(t)$) in terms of a time-ordered exponential:

$\displaystyle\mathcal{U}(t)A_{0}$
$\displaystyle=\Big{(}\mathcal{T}e^{\int_{0}^{t}\textrm{d}s\mathcal{L}(s)}\Big{)}A_{0}$
(17)
$\displaystyle=\Big{(}\mathcal{T}e^{i\int_{0}^{t}\textrm{d}sH(s)}\Big{)}A_{0}\Big{(}\mathcal{T}e^{i\int_{0}^{t}\textrm{d}sH(s)}\Big{)}^{{\dagger}},$

where $\mathcal{T}$ denotes time-ordering (note the ordering in the bottom
line of Eq. (17) — earlier times appear inside later times). Note that
$\lVert\mathcal{U}(t)A_{0}\rVert=\lVert A_{0}\rVert$.

Figure 4: Visual interpretation of Eq. (18). $\omega$ consists of the sites in
red, $\Omega/\omega$ the sites in blue. $\lambda$ consists of the dashed
links, $\Lambda/\lambda$ the solid links. Evolution under only
$H_{\Lambda/\lambda}$ cannot transform a string having the identity on
$\omega$ into one with a non-identity element, nor vice-versa.

Lastly, suppose $\lambda\subseteq\Lambda$ contains every link which connects a
subset of sites $\omega$ to its complement $\Omega/\omega$ (see Fig. 4). It is
intuitively clear that evolution under $\mathcal{L}_{\Lambda/\lambda}(t)$
alone cannot transform a basis operator which acts trivially on $\omega$ into
one which acts non-trivially, or vice versa. Put precisely,

$\mathcal{P}_{\omega}\mathcal{U}_{\Lambda/\lambda}(t)=\mathcal{U}_{\Lambda/\lambda}(t)\mathcal{P}_{\omega}.$
(18)

We give a proof of Eq. (18) in App. B.

###  III.3 Types of Lieb-Robinson bounds

To reiterate, the purpose of LR bounds is to place an upper limit on
$\lVert\mathcal{P}_{r}A_{0}^{t}\rVert$ (and thus $D(r,t)$) which applies to
every $H\in\mathcal{H}_{J}$ simultaneously. The bounds we construct will be of
the form

$\big{\lVert}\mathcal{P}_{r}A_{0}^{t}\big{\rVert}\leq\big{\lVert}A_{0}\big{\rVert}f\left[r^{\gamma}\left(1-\frac{vt}{r^{z}}\right)\right],$
(19)

where $\gamma>0$ and the function $f(x)$ decays to zero as
$x\rightarrow\infty$ and remains finite (or even diverges) as
$x\rightarrow-\infty$. A simple and common example is $f(x)=\exp{[-\kappa x]}$
for some $\kappa>0$. Although we shall not indicate so explicitly, note that
all quantities here are functions of the couplings $\\{J_{l}\\}$ defining
$\mathcal{H}_{J}$.

In the large-$r$ and large-$t$ limit, one identifies two important features
from Eq. (19):

  * •

There is a “front” defined by $vt=r^{z}$. For $vt>r^{z}$, the right-hand side
of Eq. (19) is large (and thus the bound is vacuous), while for $vt<r^{z}$,
$\lVert\mathcal{P}_{r}A_{0}(t)\rVert$ must be small. Thus the spacetime curve
$vt=r^{z}$ constitutes an envelope that constrains the expansion of
$A_{0}^{t}$. We refer to $z$ as the “dynamical exponent” and $v$ as the
“generalized velocity” of the bound (only when $z=1$ will we speak simply of
the “velocity”). Of particular interest are the largest value of $z$ and
smallest value of $v$ for which a bound as in Eq. (19) holds.

  * •

At fixed $t$, there is the “tail” behavior as $r\rightarrow\infty$,
characterized by the exponent $\gamma$ and the large-$x$ behavior of $f(x)$
(e.g., exponential or power-law). Even though
$\lVert\mathcal{P}_{r}A_{0}^{t}\rVert$ need never be identically zero, the
tail describes how rapidly it must decay at large distances.

Figure 5: Sketch of a possible spatial profile $\lVert[A_{0}^{t},B_{r}]\rVert$
as a function of $r$, indicated by dots (black line merely connects the
points). Red dashed line shows an a.a. bound consistent with the profile — red
and blue dots indicate points contained within the bound. There are implied to
be only a finite number of black dots. Blue dashed line shows an i.o. bound —
blue dots indicate the subsequence $\\{r_{k}\\}$ to which the bound applies.

As mentioned in Sec. II, we shall find it necessary to distinguish between
different types of LR bounds, based on whether a statement such as Eq. (19)
holds for all sites or merely a subsequence of sites:

  * •

We call Eq. (19) an “almost-always” (a.a.) bound if there exists an $R$ such
that it holds for all $r>R$. This is the sense in which all past works (to our
knowledge) have derived and discussed LR bounds888Strictly speaking, past
works have derived bounds that hold for every single site (i.e., $R=0$). Here
we do not differentiate between “almost-always” and such “always” bounds
(although one arguably could), since our focus is on asymptotic behavior.
Given an a.a. bound with $R>0$, one simple way to extend it to all sites is to
use the trivial bound $\lVert[A_{0}^{t},B_{r}]\rVert\leq 2\lVert
A_{0}\rVert\lVert B_{r}\rVert$ for $r\leq R$. If the couplings $\\{J_{l}\\}$
are bounded by some $J_{\textrm{max}}$, another way is to use the conventional
LR bound corresponding to $J_{\textrm{max}}$ for $r\leq R$ (Eq. (31) below).
Since the number of sites which violate the a.a. bound is by definition
finite, neither prescription changes any of the asymptotic behavior..

  * •

We call Eq. (19) an “infinitely-often” (i.o.) bound if for every $R$, it holds
for some $r>R$. This is equivalent to saying that there exists a subsequence
$\\{r_{k}\\}_{k=1}^{\infty}$ on which the bound holds.

Fig. 5 illustrates the distinction between the two, showing a hypothetical
curve $\lVert[A_{0}^{t},B_{r}]\rVert$ versus $r$ alongside consistent a.a. and
i.o. bounds. Note that a.a. bounds are automatically i.o. bounds, but not
vice-versa. The distinction is likely unimportant for translation-invariant
systems (although we are not aware of any works that compare the two to begin
with), but it turns out to be essential in non-translation-invariant systems —
as mentioned in Sec. II, there will be situations in which we can derive i.o.
bounds but are unable to derive corresponding a.a. bounds (even proving that
no such a.a. bound can exist).

##  IV General bound for non-translation-invariant systems

###  IV.1 Review of the conventional bound

We first review the standard Lieb-Robinson bound. Start with a Hamiltonian
$H\in\mathcal{H}_{J}$:

$H(t)=\sum_{l\in\Lambda}H_{l}(t),\qquad\big{\lVert}H_{l}(t)\big{\rVert}\leq
J_{l}.$ (20)

For any link $l$, pass to the interaction picture with respect to all other
terms in the Hamiltonian by defining

$A_{0I}^{t}\equiv\mathcal{U}_{\Lambda/l}(t)^{{\dagger}}A_{0}^{t}.$ (21)

The equation of motion for $A_{0I}^{t}$ (see Eqs. (15) and (17)) is

$\displaystyle\partial_{t}A_{0I}^{t}$
$\displaystyle=-\mathcal{U}_{\Lambda/l}(t)^{{\dagger}}\mathcal{L}_{\Lambda/l}(t)A_{0}^{t}+\mathcal{U}_{\Lambda/l}(t)^{{\dagger}}\mathcal{L}(t)A_{0}^{t}$
(22)
$\displaystyle=\mathcal{U}_{\Lambda/l}(t)^{{\dagger}}\mathcal{L}_{l}(t)A_{0}^{t},$

from which it follows that

$A_{0I}^{t}=A_{0}+\int_{0}^{t}\textrm{d}s\,\mathcal{U}_{\Lambda/l}(s)^{{\dagger}}\mathcal{L}_{l}(s)A_{0}^{s}.$
(23)

Since we are considering a 1D chain, $l$ is the only link that connects the
sites on its right (denoted $>l$) to the sites on its left (denoted $<l$). We
thus use Eq. (18) to obtain

$\mathcal{P}_{>l}A_{0I}^{t}=\mathcal{P}_{>l}A_{0}+\int_{0}^{t}\textrm{d}s\,\mathcal{U}_{\Lambda/l}(s)^{{\dagger}}\mathcal{P}_{>l}\mathcal{L}_{l}(s)A_{0}^{s}.$
(24)

Furthermore,
$\mathcal{P}_{>l}A_{0I}^{t}=\mathcal{U}_{\Lambda/l}(t)^{{\dagger}}\mathcal{P}_{>l}A_{0}^{t}$.
Taking the norm then gives

$\big{\lVert}\mathcal{P}_{>l}A_{0}^{t}\big{\rVert}\leq\big{\lVert}\mathcal{P}_{>l}A_{0}\big{\rVert}+\int_{0}^{t}\textrm{d}s\big{\lVert}\mathcal{P}_{>l}\mathcal{L}_{l}(s)A_{0}^{s}\big{\rVert}.$
(25)

Recall that $\mathcal{L}_{l}(s)A_{0}^{s}\equiv i[H_{l}(s),A_{0}^{s}]$. Since
$H_{l}(s)$ is supported only on link $l$,

$\mathcal{L}_{l}(s)A_{0}^{s}=\mathcal{L}_{l}(s)\mathcal{P}_{>l-1}A_{0}^{s}.$
(26)

Together with Eq. (12), we thus have

$\displaystyle\big{\lVert}\mathcal{P}_{>l}\mathcal{L}_{l}(s)\mathcal{P}_{>l-1}A_{0}^{s}\big{\rVert}$
$\displaystyle\leq
2\big{\lVert}\mathcal{L}_{l}(s)\mathcal{P}_{>l-1}A_{0}^{s}\big{\rVert}$ (27)
$\displaystyle\leq 4J_{l}\big{\lVert}\mathcal{P}_{>l-1}A_{0}^{s}\big{\rVert},$

and Eq. (25) becomes

$\big{\lVert}\mathcal{P}_{>l}A_{0}^{t}\big{\rVert}\leq\big{\lVert}\mathcal{P}_{>l}A_{0}\big{\rVert}+4J_{l}\int_{0}^{t}\textrm{d}s\big{\lVert}\mathcal{P}_{>l-1}A_{0}^{s}\big{\rVert}.$
(28)

Taking $r>0$ for concreteness and supposing that $l$ lies between sites 0 and
$r$, $\lVert\mathcal{P}_{>l}A_{0}\rVert=0$ and we are left with

$\big{\lVert}\mathcal{P}_{>l}A_{0}^{t}\big{\rVert}\leq
4J_{l}\int_{0}^{t}\textrm{d}s\big{\lVert}\mathcal{P}_{>l-1}A_{0}^{s}\big{\rVert}.$
(29)

To obtain a closed-form bound on $\lVert\mathcal{P}_{r}A_{0}^{t}\rVert$, first
note that
$\lVert\mathcal{P}_{r}A_{0}^{t}\rVert=\lVert\mathcal{P}_{r}\mathcal{P}_{\geq
r}A_{0}^{t}\rVert\leq 2\lVert\mathcal{P}_{\geq r}A_{0}^{t}\rVert$ (Eq. (12)),
then use Eq. (29) iteratively: bound $\lVert\mathcal{P}_{\geq
r}A_{0}^{t}\rVert$ in terms of $\lVert\mathcal{P}_{\geq r-1}A_{0}^{s}\rVert$,
then bound the latter in terms of $\lVert\mathcal{P}_{\geq
r-2}A_{0}^{s^{\prime}}\rVert$, and so on until reaching the origin (at which
point do not introduce $\mathcal{P}_{\geq 0}$ — simply use that $\lVert
A_{0}^{s}\rVert=\lVert A_{0}\rVert$). The result is

$\big{\lVert}\mathcal{P}_{r}A_{0}^{t}\big{\rVert}\leq
2\big{\lVert}A_{0}\big{\rVert}\left(\prod_{l=1}^{r}4J_{l}\right)\frac{t^{r}}{r!}.$
(30)

From here, one usually takes all $J_{l}$ to equal a common value $J$. This
gives (using that $r!\geq(r/e)^{r}$)

$\displaystyle\big{\lVert}\mathcal{P}_{r}A_{0}^{t}\big{\rVert}$
$\displaystyle\leq
2\big{\lVert}A_{0}\big{\rVert}\exp{\left[r\log{\frac{4eJt}{r}}\right]}$ (31)
$\displaystyle\leq
2\big{\lVert}A_{0}\big{\rVert}\exp{\left[-r\left(1-\frac{4eJt}{r}\right)\right]}.$

Eq. (31) is of the form in Eq. (19), with $z=1$, $\gamma=1$, and $v=4eJ$: we
have a ballistic (a.a.) LR bound with exponential tail and velocity of order
$J$.

One can certainly use Eq. (30) for non-translation-invariant $\\{J_{l}\\}$ as
well. Yet it is easy to see that the result might be rather weak. Suppose that
at large $r$, the empirical distribution of couplings (Eq. (3)) approaches a
function $\mu(J)$ (in some sufficiently strong sense — we are only reasoning
schematically for the moment). Then

$\displaystyle\prod_{l=1}^{r}4J_{l}$
$\displaystyle=\exp{\left[\sum_{l=1}^{r}\log{4J_{l}}\right]}\sim\exp{\left[r\int\textrm{d}\mu(J)\log{4J}\right]}.$
(32)

As long as $\log{J}$ is integrable with respect to $\mu(J)$, we still obtain a
ballistic LR bound:

$\big{\lVert}\mathcal{P}_{r}A_{0}^{t}\big{\rVert}\leq
2\big{\lVert}A_{0}\big{\rVert}\exp{\left[-r\left(1-\frac{4e\overline{J}t}{r}\right)\right]},$
(33)

where $\log{4\overline{J}}\equiv\int\textrm{d}\mu(J)\log{4J}$. Yet the
requirement that $\log{J}$ be integrable is quite easy to satisfy: if
$\mu(J)\sim J^{\alpha}$ at small $J$ for any $\alpha>0$, however small, then
$\overline{J}$ is finite and Eq. (30) is ballistic. Clearly this is a much
weaker claim than that in Fig. 2. As we show in the following subsections,
taking the small-$J$ links more seriously allows us to prove that the actual
dynamics must be sub-ballistic for any $\alpha<1$.

###  IV.2 Improvements via integrating out links

Figure 6: Transformation from the original picture (top line) to the
interaction picture with respect to “large” terms (bottom line). The dashed
links (labelled $l_{1}$ through $l_{4}$) are those on which $\lVert
H_{l}(t)\rVert\leq\epsilon$, and the solid links those on which $\lVert
H_{l}(t)\rVert>\epsilon$. Squares on the top line represent individual sites,
but rectangles on the bottom line represent the collection of all
corresponding sites connected by solid links — the transformed interaction
$\widetilde{H}_{l_{i}}^{t}$ is supported on the entire neighboring rectangles
(but no farther by virtue of Eq. (18)).

In words, we improve on the conventional bound by passing to a further
interaction picture with respect to all “large” terms in the Hamiltonian,
namely all $H_{l}(t)$ whose norms exceed999It is interesting to note that this
same technique has been used to derive optimal LR bounds for power-law-
interacting systems, e.g., $H(t)=\sum_{ij}H_{ij}(t)$ with $\lVert
H_{ij}(t)\rVert\leq|i-j|^{-\alpha}$. To improve on the conventional bound,
which would predict a front growing exponentially in time, group the
interactions into short-range ($|i-j|\leq r^{*}$ for some $r^{*}$) and long-
range ($|i-j|>r^{*}$) and then pass to the interaction picture with respect to
short-range terms Foss-Feig  _et al._ (2015). It has recently been shown that
this procedure can be repeated for a hierarchy of length scales to obtain LR
bounds which are provably tight Tran  _et al._ (2021a). some threshold
$\epsilon$. On the one hand, the remaining terms have a larger support in this
interaction picture, and we do not try to describe their structure within that
support. Yet in return, every remaining term has norm less than $\epsilon$,
and so no dynamics can occur on any scale faster than $\epsilon^{-1}$. The
latter effect, which suppresses operator spreading, turns out to be the
dominant one when there is a sufficient number of weak links. We sketch the
situation in Fig. 6.

We now make this argument precise. Pick any subset of links
$\lambda\equiv\\{l_{1},\cdots,l_{n}\\}$ lying between 0 and $r$. Pass to the
interaction picture with respect to $H_{\Lambda/\lambda}$:

$\widetilde{A}_{0}^{t}\equiv\mathcal{U}_{\Lambda/\lambda}(t)^{{\dagger}}A_{0}^{t},\qquad\widetilde{H}_{l}(t)\equiv\mathcal{U}_{\Lambda/\lambda}(t)^{{\dagger}}H_{l}(t).$
(34)

As in Eq. (22), the equation of motion for $\widetilde{A}_{0}^{t}$ is

$\displaystyle\partial_{t}\widetilde{A}_{0}^{t}$
$\displaystyle=\mathcal{U}_{\Lambda/\lambda}(t)^{{\dagger}}\mathcal{L}_{\lambda}(t)\mathcal{U}_{\Lambda/\lambda}(t)\widetilde{A}_{0}^{t}$
(35)
$\displaystyle\equiv\widetilde{\mathcal{L}}_{\lambda}(t)\widetilde{A}_{0}^{t},$

where
$\widetilde{\mathcal{L}}_{\lambda}(t)\widetilde{A}_{0}^{t}=i[\widetilde{H}_{\lambda}(t),\widetilde{A}_{0}^{t}]$
and $\widetilde{H}_{\lambda}(t)=\sum_{i=1}^{n}\widetilde{H}_{l_{i}}(t)$.

The transformed operator $\widetilde{H}_{l_{i}}(t)$ is supported on
(potentially) all sites between $l_{i-1}$ and $l_{i+1}$, yet it has the same
norm as $H_{l_{i}}(t)$, namely bounded by $J_{l_{i}}$. Thus we can apply the
same procedure as in Sec. IV.1 to the operator $\widetilde{A}_{0}^{t}$, with
$\lambda$ in place of $\Lambda$ and with $\widetilde{H}_{\lambda}(t)$ as the
Hamiltonian. Following an identical derivation to that of Eq. (29), we obtain

$\big{\lVert}\mathcal{P}_{>l_{i}}\widetilde{A}_{0}^{t}\big{\rVert}\leq
4J_{l_{i}}\int_{0}^{t}\textrm{d}s\big{\lVert}\mathcal{P}_{>l_{i-1}}\widetilde{A}_{0}^{s}\big{\rVert}.$
(36)

Use that $\lVert\mathcal{P}_{r}A_{0}^{t}\rVert\leq
2\lVert\mathcal{P}_{>l_{n}}A_{0}^{t}\rVert=2\lVert\mathcal{P}_{>l_{n}}\widetilde{A}_{0}^{t}\rVert$
to start the iteration, and $\lVert\widetilde{A}_{0}^{s}\rVert=\lVert
A_{0}\rVert$ to terminate it. Thus

$\big{\lVert}\mathcal{P}_{r}A_{0}^{t}\big{\rVert}\leq
2\big{\lVert}A_{0}\big{\rVert}\left(\prod_{i=1}^{n}4J_{l_{i}}\right)\frac{t^{n}}{n!}.$
(37)

Since $\lambda$ is arbitrary, we are free to use the subset that gives the
tightest bound:

$\big{\lVert}\mathcal{P}_{r}A_{0}^{t}\big{\rVert}\leq
2\big{\lVert}A_{0}\big{\rVert}\min_{\lambda}\left[\left(\prod_{i=1}^{|\lambda|}4J_{l_{i}}\right)\frac{t^{|\lambda|}}{|\lambda|!}\right],$
(38)

where the minimum is over all subsets of links between 0 and $r$. Eq. (38) is
our improved LR bound.

Although the minimization in Eq. (38) may seem computationally expensive due
to the $2^{r}$ possible $\lambda$, it can be performed efficiently. For a
fixed size of $\lambda$, the optimal choice is clearly those links having the
$|\lambda|$ smallest values of $J_{l}$. Thus one need only sort
$\\{J_{l}\\}_{l=1}^{r}$ beforehand, and the minimization amounts to simply
checking the $r$ possible values of $|\lambda|$.

###  IV.3 An explicit bound in terms of the distribution of couplings

We now make use of Eq. (38) to prove general results in terms of the
“distribution” of couplings $\mu_{r}(J)$, by which we mean the fraction of
links between 0 and $r$ for which $J_{l}\leq J$. Reproducing Eq. (3) (recall
that $\delta_{J_{l}\leq J}\equiv 1$ if $J_{l}\leq J$ and 0 otherwise),

$\mu_{r}(J)\equiv\frac{1}{r}\sum_{l=1}^{r}\delta_{J_{l}\leq J}.$ (39)

From this definition, for any $\epsilon>0$ such that $\mu_{r}(\epsilon)\neq
0$, we can choose $\lambda$ to be the subset of links with $J_{l}\leq\epsilon$
and thus have the LR bound

$\displaystyle\big{\lVert}\mathcal{P}_{r}A_{0}^{t}\big{\rVert}$
$\displaystyle\leq 2\big{\lVert}A_{0}\big{\rVert}\frac{(4\epsilon
t)^{r\mu_{r}(\epsilon)}}{[r\mu_{r}(\epsilon)]!}$ (40) $\displaystyle\leq
2\big{\lVert}A_{0}\big{\rVert}\exp{\left[-r\mu_{r}(\epsilon)\left(1-\frac{4e\epsilon
t}{r\mu_{r}(\epsilon)}\right)\right]}.$

Now suppose that $\mu_{r}(J)$ converges101010One might be concerned by us
taking $r\rightarrow\infty$ since we are considering a finite chain of $N$
sites. However, note that all of the bounds derived in Secs. IV and V are
independent of $N$. Thus to be precise, we are supposing that we have an
infinite sequence of couplings $\\{J_{l}\\}$ which obeys Eqs. (42) and (43),
and we are considering the restriction of an infinite lattice to $N$ sites.
Any statement involving $r$ should be interpreted as applying when $N>r$. as
$r\rightarrow\infty$ to a function $\mu(J)$ defined on $[0,\infty)$, with the
small-$J$ (“tail”) behavior111111Throughout this paper, a statement such as
“$f(x)\sim g(x)$ as $x\rightarrow 0$” means that $\lim_{x\rightarrow
0}f(x)/g(x)=1$.

$\mu(J)\sim\mu_{0}J^{\alpha},$ (41)

for some $\mu_{0}>0$. The parameter $\alpha>0$ will play an essential role in
what follows. We do need to specify the precise sense in which $\mu_{r}(J)$
converges. It will not be sufficient to require merely that
$\lim_{r\rightarrow\infty}\mu_{r}(J)=\mu(J)$ at any fixed $J$, but also that
$\mu_{r}(J)$ behave as $\mu(J)$ on scales which decrease with increasing $r$.
This is expressed by the following conditions, which we assume to be met:

  * •

For any $\beta\in[0,1/\alpha)$ and $J>0$,

$\lim_{r\rightarrow\infty}\frac{\mu_{r}(Jr^{-\beta})}{\mu(Jr^{-\beta})}=1.$
(42)

  * •

For any $\beta>1/\alpha$,

$\lim_{r\rightarrow\infty}\frac{\min_{l=1}^{r}J_{l}}{r^{-\beta}}=\infty.$ (43)

As an example of why Eqs. (42) and (43) are necessary, rather than simply the
condition $\lim_{r\rightarrow\infty}\mu_{r}(J)=\mu(J)$ (which is contained in
Eq. (42) as the case $\beta=0$), suppose that there is a single link on which
$J_{l}=0$. Clearly there cannot be any operator spreading past link $l$ (note
that this is captured by the general bound in Eq. (38)). On the other hand,
the value of a single coupling does not affect the fraction which are less
than any value in the large-$r$ limit. Thus
$\lim_{r\rightarrow\infty}\mu_{r}(J)$ at any fixed value of $J$ does not
identify individual anomalously weak links, whereas Eq. (43) does. In other
words, Eqs. (42) and (43) are a precise way of stating that the weakest links
between sites 0 and $r$ are also distributed in a manner behaving as $\mu(J)$
at large $r$.

Strictly speaking, we only need (and will prove) Eqs. (42) and (43) to hold
for a dense subset of $\beta$, say all rational $\beta$. The exponent
$1/\alpha$ appears because $r\mu(Jr^{-1/\alpha})=O(1)$ — one expects to find
couplings with $\beta<1/\alpha$ but not with $\beta>1/\alpha$ between sites 0
and $r$.

We feel that these conditions are reasonable to expect in practice. We show in
Sec. V that if each $J_{l}$ is chosen independently from a literal probability
distribution $\mu(J)$ obeying Eq. (41), then Eqs. (42) and (43) are satisfied
with probability 1 — in this sense, any sufficiently disordered set of
couplings will meet our requirements. Whether Eqs. (42) and (43) hold in any
specific situation obviously depends on the system under consideration, but in
any case (and perhaps more importantly), one can always return to Eq. (38) if
needed.

Let us first consider $\alpha\geq 1$. From Eq. (41) and the assumption that
$\lim_{r\rightarrow\infty}\mu_{r}(J)=\mu(J)$, there exists121212Let us remind
the reader of the precise definition of the limit of a sequence: the statement
$\lim_{r\rightarrow\infty}x_{r}=x$ is the statement that for any $\eta>0$,
there exists $R(\eta)\in\mathbb{N}$ such that $|x_{r}-x|<\eta$ for all
$r>R(\eta)$. $R$ and $\epsilon>0$ such that for all $r>R$,
$\mu_{r}(\epsilon)>C\epsilon^{\alpha}$ (recall our convention that $C$ is any
$r$\- and $t$-independent constant whose value may change from line to line).
Thus Eq. (40) becomes (for $r>R$)

$\big{\lVert}\mathcal{P}_{r}A_{0}^{t}\big{\rVert}\leq
2\big{\lVert}A_{0}\big{\rVert}\exp{\left[-C\epsilon^{\alpha}r\left(1-\frac{4et}{C\epsilon^{\alpha-1}r}\right)\right]}.$
(44)

This is simply a conventional LR bound with ballistic front and exponential
tail (a.a. because it holds for all $r>R$), having velocity
$4e/C\epsilon^{\alpha-1}$.

Now consider $\alpha<1$. Pick any $\beta\in(0,1/\alpha)$, and then from Eqs.
(41) and (42), there exists $R$ such that for all $r>R$,
$\mu_{r}(r^{-\beta})>Cr^{-\beta\alpha}$. Taking $\epsilon=r^{-\beta}$ in Eq.
(40), we thus have that for all $r>R$,

$\big{\lVert}\mathcal{P}_{r}A_{0}^{t}\big{\rVert}\leq
2\big{\lVert}A_{0}\big{\rVert}\exp{\left[-Cr^{1-\beta\alpha}\left(1-\frac{4et}{Cr^{1+\beta-\beta\alpha}}\right)\right]}.$
(45)

This is an a.a. LR bound having exponents

$z=1+\beta-\beta\alpha,$ (46) $\gamma=1-\beta\alpha.$ (47)

Note that the front is sub-ballistic precisely for $\alpha<1$ (whereas it is
no tighter than Eq. (44) for $\alpha\geq 1$).

By taking $\beta\nearrow 1/\alpha$, we can make the dynamical exponent $z$
arbitrarily close to $1/\alpha$. This actually implies that for any
$z<1/\alpha$, we have an a.a. LR bound with arbitrarily small generalized
velocity. Fixing $z$ and for any $v>0$, setting $\beta\in(z,1/\alpha)$ and
taking $r$ sufficiently large (so that $4er^{-\beta}<Cvr^{1-\beta\alpha-z}$)
gives

$\displaystyle\big{\lVert}\mathcal{P}_{r}A_{0}^{t}\big{\rVert}$
$\displaystyle\leq
2\big{\lVert}A_{0}\big{\rVert}\exp{\left[-Cr^{1-\beta\alpha}\left(1-\frac{4et}{Cr^{1+\beta-\beta\alpha}}\right)\right]}$
(48) $\displaystyle\leq
2\big{\lVert}A_{0}\big{\rVert}\exp{\left[-Cr^{1-\beta\alpha}\left(1-\frac{vt}{r^{z}}\right)\right]}.$

Interestingly, the tightest tail corresponds to the opposite limit of $\beta$.
Setting $\beta=0$ gives the standard exponential tail (albeit only at
distances $r>vt$ for some $v$), whereas increasing $\beta$ gives an
increasingly stretched-exponential tail. The optimal choice of $\beta$ depends
on the specific application: one should take $\beta\nearrow 1/\alpha$ if
constraining the shape of the front is most important, but one should set
$\beta=0$ if constraining the tail is most important.

We can combine these results (Eq. (44) for $\alpha\geq 1$ and Eq. (48) for
$\alpha<1$) simply by saying that Eq. (48) holds for any
$z<z_{c}(\alpha)\equiv\max[1/\alpha,1]$. This accounts for the blue region in
Fig. 2, with the upper boundary being given by $z_{c}(\alpha)$.

Note that this analysis can straightforwardly be extended to limiting
distributions $\mu(J)$ which are not simple power laws, with the expected
results. First of all, if $\mu(J)$ decays to 0 at small $J$ faster than any
power law (e.g., $\mu(J)\sim\exp{[-1/J]}$), then a conventional LR bound as in
Eq. (44) still holds. If $\mu(J)$ decays slower than any power law (e.g.,
$\mu(J)\sim 1/\log{J^{-1}}$), and if Eq. (42) is obeyed for all $\beta>0$,
then $z=\infty$ in that an LR bound with infinitesimal $v$ holds for any
finite $z$. Lastly, our main result still applies if $\mu(J)$ scales not
solely as $J^{\alpha}$ but as $J^{\alpha}p(J)$ for some sub-power-law function
$p(J)$ — an LR bound with arbitrarily small generalized velocity holds for any
$z<z_{c}(\alpha)$, as in Eq. (48).

###  IV.4 Tightness of the bound

As discussed in Sec. II, LR bounds should be complemented by an understanding
of their tightness, ideally by constructing an explicit protocol
$H\in\mathcal{H}_{J}$ that saturates the bound. To that end, we consider the
simple transfer protocol shown in Fig. 3. Denoting the total runtime of the
circuit by $T_{r}$, clearly $\mathcal{P}_{r}A_{0}^{T_{r}}=A_{0}$, and so any
valid LR bound must have a front which encompasses the spacetime point
$(r,T_{r})$. We shall focus on the dynamical exponent — if $T_{r}=O(r^{z})$,
then no LR bound can have a dynamical exponent larger than $z$.

Effecting a SWAP gate for arbitrary $d$-dimensional local Hilbert spaces is
not entirely trivial131313As pointed out to us by P. J. D. Crowley and C. R.
Laumann, it is not necessary to give an explicit construction of the SWAP
gate. From the definition of SWAP, the quantity $H_{l}\equiv
i\pi^{-1}J_{l}\log{\textrm{SWAP}_{l}}$ is a Hermitian operator supported on
link $l$ with norm $J_{l}$. The Hamiltonian that applies $H_{l}$ sequentially
as in Fig. 3 for time $\pi J_{l}^{-1}$, although not given in a completely
constructive form, is a legitimate member of $\mathcal{H}_{J}$., but a
construction is given in Ref. Garcia-Escartin and Chamorro-Posada (2013). For
completeness, we give the relevant details in App. C. The only interactions
needed (per SWAP gate) are a finite number of controlled-$Z$ gates. In our
case, since Eq. (5) must be respected, the time per controlled-$Z$ gate across
link $l$ is $O(1/J_{l})$. Thus the total runtime is

$T_{r}=C\sum_{l=1}^{r}\frac{1}{J_{l}}.$ (49)

We again assume that the distribution of couplings $\mu_{r}(J)$ satisfies Eqs.
(42) and (43). As we demonstrate below, it then follows that for any
$z>\max[1/\alpha,1]$,

$\lim_{r\rightarrow\infty}\frac{T_{r}}{r^{z}}=0.$ (50)

Let us first note that it is the same threshold exponent
$z_{c}(\alpha)\equiv\max[1/\alpha,1]$ which enters into both Eq. (50) and
(48). We can thus say that the dynamical exponent is $z_{c}(\alpha)$ in the
following sense:

  * •

For any $z<z_{c}(\alpha)$, there is no $H\in\mathcal{H}_{J}$ that can generate
correlations at any sufficiently large distance $r$ in a time of order
$r^{z}$.

  * •

For any $z>z_{c}(\alpha)$, we know of an explicit protocol
$H\in\mathcal{H}_{J}$ that can generate correlations at every sufficiently
large distance $r$ in a time vanishing compared to $r^{z}$.

However, the behavior precisely at $z=z_{c}(\alpha)$ is far more complicated
and system-dependent. In particular, the distinction between a.a. and i.o.
bounds becomes essential, as we demonstrate explicitly in Sec. V.

Now we turn to the proof of Eq. (50). It will be convenient to define
$Y_{l}\equiv 1/J_{l}$, so that $T_{r}=\sum_{l=1}^{r}Y_{l}$. Note that
$\mu_{r}(J)$, the fraction of links with $J_{l}\leq J$, is equivalently the
fraction with $Y_{l}\geq 1/J$. Fix $\gamma>0$ and define $a_{0}\equiv 0$,
$a_{k}\equiv r^{(k-1)\gamma}$ for $k\geq 1$ (writing $a_{k}$ instead of
$a_{k}(r)$ for conciseness). Also define $p_{k}$ to be the fraction of links
with $Y_{l}\in[a_{k},a_{k+1})$, equivalently

$p_{k}\equiv\mu_{r}\big{(}a_{k}^{-1}\big{)}-\mu_{r}\big{(}a_{k+1}^{-1}\big{)}.$
(51)

By definition, we have the bound

$T_{r}\leq r\sum_{k=0}^{\infty}p_{k}a_{k+1}.$ (52)

For $p_{0}$ and $p_{1}$, we shall simply use that $p_{0}\leq 1$, $p_{1}\leq
1$. For $p_{k}$ with $k\geq 2$, first note that the second term in Eq. (51)
can be neglected relative to the first at large $r$. Thus it follows from Eqs.
(41) and (42) that for any $\eta>0$, there exists $R_{k}$ such that for all
$r>R_{k}$,

$p_{k}\in\big{(}(1-\eta)Cr^{-(k-1)\alpha\gamma},(1+\eta)Cr^{-(k-1)\alpha\gamma}\big{)}.$
(53)

Furthermore, Eq. (43) implies that if we take $K$ to be the smallest integer
greater than $1/\alpha\gamma$, then there exists $R_{\infty}$ such that for
all $r>R_{\infty}$, $\min_{l=1}^{r}J_{l}>r^{-K\gamma}=a_{K+1}^{-1}$ and
therefore $p_{k}=0$ for all $k\geq K+1$. All together, we have that for
$r>\max[R_{2},\cdots,R_{K},R_{\infty}]$,

$p_{k}\leq\begin{cases}1,\quad&k\leq 1\\\
(1+\eta)Cr^{-(k-1)\alpha\gamma},\quad&2\leq k\leq K\\\ 0,\quad&K+1\leq
k\end{cases}.$ (54)

Eq. (52) becomes

$T_{r}\leq
r+r^{1+\gamma}+(1+\eta)Cr^{1+\alpha\gamma}\sum_{k=2}^{K}r^{k(1-\alpha)\gamma}.$
(55)

First consider $\alpha>1$. The sum in Eq. (55) is then $O(1)$ with respect to
$r$. Since $\gamma$ is arbitrary, Eq. (50) follows for any $z>1$ (namely
choose $\gamma<(z-1)/\alpha$). Note that this conclusion also applies when
$\mu(J)$ decays faster than a power law — in such a case, $p_{k}$ (for $k\geq
2$) is even smaller than for any finite $\alpha$ and thus Eq. (55) remains a
valid bound.

Next suppose $\alpha\leq 1$. The sum now grows no faster than
$O(r^{K(1-\alpha)\gamma})$, and thus

$T_{r}\leq Cr^{1+\alpha\gamma+K(1-\alpha)\gamma}\leq
Cr^{\frac{1}{\alpha}+\gamma}.$ (56)

The latter inequality follows because, by definition, $1/\alpha\gamma<K\leq
1+1/\alpha\gamma$. Again, since $\gamma$ is arbitrary, Eq. (50) follows.

Incidentally, this line of reasoning puts our discussion regarding the failure
of the conventional LR bound (Eq. (32) in particular) on firmer ground. As
noted above, the couplings enter into the conventional bound via the sum
$\sum_{l=1}^{r}\log{J_{l}}$. We have that

$r\sum_{k=0}^{\infty}p_{k}\log{a_{k+1}^{-1}}\leq\sum_{l=1}^{r}\log{J_{l}}\leq
r\sum_{k=0}^{\infty}p_{k}\log{a_{k}^{-1}}.$ (57)

The sums over $k$ again terminate at $K$, but now the summands go as
$r^{-k\alpha\gamma}\log{r^{-k\gamma}}$ and are dominated by small $k$
regardless of $\alpha$. More precisely, using Eq. (54) and the analogous lower
bound on $p_{k}$ gives

$Cr\log{r^{-\gamma}}\leq\sum_{l=1}^{r}\log{J_{l}}\leq C^{\prime}r.$ (58)

Since $\gamma$ can be arbitrarily small, inserting into Eq. (30) gives an LR
bound whose front, while not necessarily quite ballistic, cannot have a
dynamical exponent larger than 1. As we have now established, that bound is
far from tight.

##  V Disordered Lieb-Robinson bounds

As a non-trivial example of a situation in which the above results apply, here
we suppose that each $J_{l}$ is drawn i.i.d. from a probability distribution
$\mu(J)$ whose small-$J$ behavior is given by Eq. (41). We first prove Eqs.
(42) and (43), not merely in some average sense but with probability 1, using
standard techniques. The results in Secs. IV.3 and IV.4 then follow.

We next consider the threshold case $z=\max[1/\alpha,1]$ in more detail. For
$\alpha>1$, it follows immediately from the strong law of large numbers (see
Refs. Rosenthal (2006); Durrett (2019) for an introduction) that the transfer
protocol in Sec. IV.4 reaches all sites ballistically. For $\alpha<1$, on the
other hand, the distinction between a.a. and i.o. bounds becomes important —
we derive an i.o. bound with arbitrarily small generalized velocity, implying
that no protocol can reach every site in time $T_{r}=O(r^{1/\alpha})$, but
also show that the above transfer protocol does reach an infinite subsequence
of sites in time $T_{r}=O(r^{1/\alpha})$ (again with probability 1).
Interestingly, $\alpha=1$ is the only point at which we cannot give a definite
answer. Our i.o. bound still applies, but the transfer protocol now fails to
reach any site in time $T_{r}=O(r)$. It could be that an a.a. bound with
arbitrarily small velocity holds for $\alpha=1$, but we have not succeeded in
proving so.

Finally, we discuss some straightforward extensions of the above results.

###  V.1 Convergence of the distribution

We first prove Eq. (42). This requires some tools from probability theory
which can be found in textbooks on the subject Rosenthal (2006); Durrett
(2019) but are likely not common knowledge among physicists. Here we apply
these tools without further comment for ease of presentation, but include a
description of them in App. D for completeness.

To prove Eq. (42), pick any $\epsilon>0$ and $\beta\in[0,1/\alpha)$, then
define the event $E_{r}$ to be

$E_{r}\equiv\Big{\\{}\frac{\mu_{r}(Jr^{-\beta})}{\mu(Jr^{-\beta})}\not\in\big{(}1-\epsilon,1+\epsilon\big{)}\Big{\\}}.$
(59)

Abbreviating $\mu(Jr^{-\beta})$ by $\mu$ for conciseness, Eq. (59) is
equivalently the event that the number of couplings less than $Jr^{-\beta}$ is
not between $(1-\epsilon)r\mu$ and $(1+\epsilon)r\mu$. We can evaluate the
latter directly:

$\displaystyle\textrm{Pr}\big{[}E_{r}\big{]}$
$\displaystyle=\sum_{n\not\in((1-\epsilon)r\mu,(1+\epsilon)r\mu)}\binom{r}{n}\mu^{n}(1-\mu)^{r-n}$
(60)
$\displaystyle\leq\sum_{n\not\in((1-\epsilon)r\mu,(1+\epsilon)r\mu)}\exp{\left[n\log{\frac{r\mu}{n}}+(r-n)\log{\frac{r(1-\mu)}{r-n}}\right]}$
$\displaystyle\leq
r\exp{\left[-(1+\epsilon)r\mu\log{(1+\epsilon)}-\left(1-\frac{\mu}{1-\mu}\epsilon\right)(1-\mu)r\log{\left(1-\frac{\mu}{1-\mu}\epsilon\right)}\right]},$

where the final inequality follows because the summand is maximized at
$n=(1+\epsilon)r\mu$. One can confirm that the right-hand side goes as
$r\exp{[-Cr^{1-\beta\alpha}]}$ at large $r$, with $C$ positive. Since
$1-\beta\alpha>0$, $\textrm{Pr}[E_{r}]$ is therefore summable and the
probability of $E_{r}$ occurring infinitely often is zero (see App. D). The
probability that this occurs for any rational $\epsilon$ or $\beta$, i.e.,
that $\mu_{r}(Jr^{-\beta})/\mu(Jr^{-\beta})$ does not converge to 1 for any
$\beta<1/\alpha$, is likewise zero.

We now prove Eq. (43). Pick any $M>0$ and $\beta>1/\alpha$, and consider the
event

$E_{r}\equiv\Big{\\{}\min_{l=1}^{r}J_{l}\leq Mr^{-\beta}\Big{\\}}.$ (61)

We have (see App. D for the definition of “$E_{r}$ i.o.”)

$\textrm{Pr}\big{[}E_{r}\textrm{
i.o.}\big{]}=\lim_{R\rightarrow\infty}\textrm{Pr}\left[\exists
r>R:\min_{l=1}^{r}J_{l}\leq
Mr^{-\beta}\right]=1-\lim_{R\rightarrow\infty}\textrm{Pr}\left[\forall
r>R:\min_{l=1}^{r}J_{l}>Mr^{-\beta}\right].$ (62)

Clearly if $J_{l}>Mr^{-\beta}$, then $J_{l}>Ms^{-\beta}$ for all $s>r$. Thus
the following events are equivalent:

$\displaystyle\Big{\\{}\forall r>R:\min_{l=1}^{r}J_{l}>Mr^{-\beta}\Big{\\}}$
$\displaystyle=\Big{\\{}J_{1}>M(R+1)^{-\beta}\Big{\\}}\bigcap\Big{\\{}J_{2}>M(R+1)^{-\beta}\Big{\\}}\bigcap\cdots\bigcap\Big{\\{}J_{R+1}>M(R+1)^{-\beta}\Big{\\}}$
(63)
$\displaystyle\qquad\qquad\bigcap\Big{\\{}J_{R+2}>M(R+2)^{-\beta}\Big{\\}}\bigcap\Big{\\{}J_{R+3}>M(R+3)^{-\beta}\Big{\\}}\bigcap\cdots.$

Since the couplings $\\{J_{l}\\}$ are independent, the probability of the
right-hand side is straightforward to evaluate:

$\displaystyle\textrm{Pr}\left[\forall
r>R:\min_{l=1}^{r}J_{l}>Mr^{-\beta}\right]$
$\displaystyle=\Big{(}1-\mu\big{(}M(R+1)^{-\beta}\big{)}\Big{)}^{R+1}\lim_{R^{\prime}\rightarrow\infty}\prod_{r=R+2}^{R^{\prime}}\Big{(}1-\mu\big{(}Mr^{-\beta}\big{)}\Big{)}$
(64)
$\displaystyle\sim\Big{(}1-C(R+1)^{-\beta\alpha}\Big{)}^{R+1}\exp{\left[\sum_{r=R+2}^{\infty}\log{\Big{(}1-Cr^{-\beta\alpha}\Big{)}}\right]},$

where the sum in the lower line is convergent because $\beta\alpha>1$.
Therefore

$\lim_{R\rightarrow\infty}\textrm{Pr}\left[\forall
r>R:\min_{l=1}^{r}J_{l}>Mr^{-\beta}\right]=1,$ (65)

and $\textrm{Pr}[\min_{l=1}^{r}J_{l}\leq Mr^{-\beta}\textrm{ i.o.}]=0$. The
probability for any $M\in\mathbb{N}$ or rational $\beta$, i.e., the
probability that $\min_{l=1}^{r}J_{l}/r^{-\beta}$ does not diverge, is
likewise zero. This completes the proof of Eq. (43).

###  V.2 Fluctuations at the threshold exponent

We now take the dynamical exponent $z$ to be the threshold value
$\max[1/\alpha,1]$, still for the model in which all couplings $\\{J_{l}\\}$
are chosen i.i.d. from $\mu(J)$. We determine whether an LR bound with
arbitrarily small $v$ holds, both in the a.a. and i.o. sense. In the
situations where we can provide a decisive answer (which will be all
$\alpha\neq 1$), this completes the diagram in Fig. 2.

First suppose $\alpha>1$. Then $\int\textrm{d}\mu(J)J^{-1}$ is finite (note
that $\textrm{d}\mu(J)\sim CJ^{\alpha-1}\textrm{d}J$ at small $J$), and recall
that we identified a specific protocol for which the runtime is
$T_{r}=C\sum_{l=1}^{r}1/J_{l}$. Since the couplings are i.i.d., the strong law
of large numbers (SLLN) Rosenthal (2006); Durrett (2019) gives that with
probability 1,

$\lim_{r\rightarrow\infty}\frac{T_{r}}{r}=\int\textrm{d}\mu(J)J^{-1}<\infty.$
(66)

Thus the above transfer protocol reaches every sufficiently large-distance
site with a non-zero velocity (namely $[\int\textrm{d}\mu(J)J^{-1}]^{-1}$).

Now suppose $\alpha<1$. Return to Eq. (38), and take the subset $\lambda$ to
be solely the link connecting $r-1$ and $r$:

$\big{\lVert}\mathcal{P}_{r}A_{0}^{t}\big{\rVert}\leq
8\big{\lVert}A_{0}\big{\rVert}J_{r}t.$ (67)

Although a rather loose bound, the probability that even the right-hand side
of Eq. (67) exceeds $vtr^{-1/\alpha}$ for all large $r$ vanishes, for any
$v>0$. In other words, we have an i.o. bound with arbitrarily small
generalized velocity: with probability 1, there exists a subsequence
$\\{r_{i}\\}$ for which

$\big{\lVert}\mathcal{P}_{r_{i}}A_{0}^{t}\big{\rVert}\leq\big{\lVert}A_{0}\big{\rVert}\frac{vt}{r_{i}^{1/\alpha}}.$
(68)

To prove Eq. (68), simply compute the probability that for all $r>R$,
$J_{r}>vr^{-1/\alpha}$:

$\displaystyle\textrm{Pr}\Big{[}\forall r>R:J_{r}>vr^{-1/\alpha}\Big{]}$ (69)
$\displaystyle\qquad\qquad\qquad=\lim_{R^{\prime}\rightarrow\infty}\prod_{r=R+1}^{R^{\prime}}\Big{(}1-\mu\big{(}vr^{-1/\alpha}\big{)}\Big{)}$
$\displaystyle\qquad\qquad\qquad\sim\lim_{R^{\prime}\rightarrow\infty}\prod_{r=R+1}^{R^{\prime}}\Big{(}1-Cr^{-1}\Big{)}=0.$

This establishes an i.o. bound with arbitrarily small $v$, but let us consider
again the previous transfer protocol. One can show that with probability 1,

$\liminf_{r\rightarrow\infty}\frac{T_{r}}{r^{1/\alpha}}=0,$ (70)

meaning that this protocol does reach a subsequence of sites $\\{r_{i}\\}$ in
time of order (and in fact asymptotically smaller than) $r_{i}^{1/\alpha}$.
The proof of Eq. (70), which we have adapted from Ref. lim , begins by noting
that $T_{r}r^{-1/\alpha}$ converges in distribution to a non-negative random
variable $S$ whose support includes 0 (a fact which is well-established but by
no means trivial, e.g., see Ref. Durrett (2019)). Thus pick any $\epsilon>0$.
We have that $\textrm{Pr}[S\geq\epsilon]<1$, and at the same time, we can
always choose a sequence of numbers $\\{C_{k}\\}$ such that $\textrm{Pr}[S\geq
C_{k}]<1/k^{2}\rightarrow 0$.

The convergence in distribution of $T_{r}r^{-1/\alpha}$ to $S$ implies that we
can construct a subsequence $\\{r_{k}\\}$ with the following properties:

  * •

$r_{k+1}-r_{k}\rightarrow\infty$ as $k\rightarrow\infty$;

  * •

For sufficiently large $k$,

$\bigg{|}\textrm{Pr}\Big{[}T_{r_{k}}r_{k}^{-1/\alpha}\geq
C_{k}\Big{]}-\textrm{Pr}\Big{[}S\geq C_{k}\Big{]}\bigg{|}<\frac{1}{k^{2}};$
(71)

  * •

$\epsilon_{k}>\epsilon$, where we define (for later convenience)

$\epsilon_{k}\equiv\frac{2\epsilon
r_{k+1}^{1/\alpha}-C_{k}r_{k}^{1/\alpha}}{(r_{k+1}-r_{k})^{1/\alpha}}.$ (72)

From Eq. (71), it follows that $\textrm{Pr}[T_{r_{k}}r_{k}^{-1/\alpha}\geq
C_{k}]<2/k^{2}$, and thus with probability 1, there is some $K$ such that
$T_{r_{k}}r_{k}^{-1/\alpha}<C_{k}$ for all $k>K$.

Consider, for $k>K$, the event

$E_{k}\equiv\Big{\\{}\forall k^{\prime}\geq k:T_{r_{k^{\prime}}}\geq 2\epsilon
r_{k^{\prime}}^{1/\alpha}\Big{\\}}.$ (73)

Since $T_{r_{k^{\prime}}}<C_{k^{\prime}}r_{k^{\prime}}^{1/\alpha}$ with
probability 1, we have that

$\displaystyle\textrm{Pr}\left[\forall k^{\prime}\geq k:T_{r_{k^{\prime}}}\geq
2\epsilon r_{k^{\prime}}^{1/\alpha}\right]$ (74)
$\displaystyle\;=\textrm{Pr}\left[\forall k^{\prime}\geq
k:T_{r_{k^{\prime}}}\geq 2\epsilon r_{k^{\prime}}^{1/\alpha}\bigcap
T_{r_{k^{\prime}}}<C_{k^{\prime}}r_{k^{\prime}}^{1/\alpha}\right]$
$\displaystyle\;\leq\textrm{Pr}\left[\forall k^{\prime}\geq
k:T_{r_{k^{\prime}+1}}-T_{r_{k^{\prime}}}>2\epsilon
r_{k^{\prime}+1}^{1/\alpha}-C_{k^{\prime}}r_{k^{\prime}}^{1/\alpha}\right]$
$\displaystyle\;=\textrm{Pr}\left[\forall k^{\prime}\geq
k:\frac{T_{r_{k^{\prime}+1}}-T_{r_{k^{\prime}}}}{(r_{k^{\prime}+1}-r_{k^{\prime}})^{1/\alpha}}>\epsilon_{k^{\prime}}\right]$
$\displaystyle\;\leq\textrm{Pr}\left[\forall k^{\prime}\geq
k:\frac{T_{r_{k^{\prime}+1}}-T_{r_{k^{\prime}}}}{(r_{k^{\prime}+1}-r_{k^{\prime}})^{1/\alpha}}>\epsilon\right],$

using Eq. (72). Note that the differences
$T_{r_{k^{\prime}+1}}-T_{r_{k^{\prime}}}$ are mutually independent, and thus
the probability on the right-hand side factors:

$\textrm{Pr}\big{[}E_{k}\big{]}\leq\lim_{K^{\prime}\rightarrow\infty}\prod_{k^{\prime}=k}^{K^{\prime}}\textrm{Pr}\left[\frac{T_{r_{k^{\prime}+1}}-T_{r_{k^{\prime}}}}{(r_{k^{\prime}+1}-r_{k^{\prime}})^{1/\alpha}}>\epsilon\right].$
(75)

Furthermore, since $r_{k+1}-r_{k}\rightarrow\infty$, the random variable
$(T_{r_{k+1}}-T_{r_{k}})/(r_{k+1}-r_{k})^{1/\alpha}$ itself converges in
distribution to $S$, and so for sufficiently large $k$,

$\textrm{Pr}\left[\frac{T_{r_{k+1}}-T_{r_{k}}}{(r_{k+1}-r_{k})^{1/\alpha}}>\epsilon\right]<\frac{1+\textrm{Pr}[S\geq\epsilon]}{2}.$
(76)

The right-hand side is strictly less than one, meaning the infinite product in
Eq. (75) evaluates to zero. Thus $\textrm{Pr}[E_{k}]=0$ and therefore

$\textrm{Pr}\left[T_{r_{k}}<2\epsilon r_{k}^{1/\alpha}\textrm{
i.o.}\right]=1-\lim_{k\rightarrow\infty}\textrm{Pr}\big{[}E_{k}\big{]}=1.$
(77)

In other words, Eq. (70) holds with probability 1.

It remains only to consider $\alpha=1$. The calculation in Eq. (69) still
holds, and thus an i.o. bound with arbitrarily small velocity exists with
probability 1. Yet for the transfer protocol, we now have

$\liminf_{r\rightarrow\infty}\frac{T_{r}}{r}=\infty,$ (78)

i.e., no site is reached ballistically. Compare to Eq. (70). It may be that a
more sophisticated protocol is able to reach a subsequence ballistically, or
it may be that no such protocol exists. We have been unable to rule out either
possibility.

To prove Eq. (78), following Ref. Durrett (2019), pick any $M>0$ and define
truncated random variables $Y_{l}^{\prime}\equiv\min[Y_{l},M]$ (recall that
$Y_{l}\equiv 1/J_{l}$). The expectation value of $Y_{l}^{\prime}$, denoted
$\overline{Y}(M)$, is finite and therefore the SLLN applies. Thus with
probability 1,

$\liminf_{r\rightarrow\infty}\frac{T_{r}}{r}=\liminf_{r\rightarrow\infty}\frac{1}{r}\sum_{l=1}^{r}Y_{l}\geq\liminf_{r\rightarrow\infty}\frac{1}{r}\sum_{l=1}^{r}Y_{l}^{\prime}=\overline{Y}(M).$
(79)

Since $\overline{Y}(M)\rightarrow\infty$ as $M\rightarrow\infty$, Eq. (78)
follows.

###  V.3 Extensions

Lastly, we discuss some straightforward extensions of the above results. These
are not meant to be exhaustive, nor do we expect them to be particularly tight
bounds — we only wish to point out some generalizations that can be obtained
with little additional work.

Couplings with finite-range correlations: As a first example, suppose that the
couplings $\\{J_{l}\\}$ are correlated, but that correlations exist only
within a finite range $\xi$. By the latter, we mean that joint distributions
$\mu^{(n)}$ factor only if all couplings involved are separated by at least
$\xi$ sites, e.g.,

$\displaystyle\mu^{(n+1)}\big{(}J_{l},J_{l+\xi},\cdots,J_{l+n\xi}\big{)}$ (80)
$\displaystyle\qquad\qquad\qquad=\mu^{(1)}(J_{l})\mu^{(1)}(J_{l+\xi})\cdots\mu^{(1)}(J_{l+n\xi}).$

Such correlations present no difficulties — simply first pass to the
interaction picture with respect to all but every $\xi$’th link, and then the
previous analysis applies. All lengths are reduced by a factor of $\xi$, and
thus the generalized LR velocity is increased by a factor of $\xi^{z}$ (which
we again do not claim to be a particularly accurate estimate), but the diagram
in Fig. 2 remains unmodified.

Bounds for multiple energy scales: Returning to a strictly 1D chain, suppose
that $J_{l}$ can only take the values $J$ and $\epsilon J$, where
$0<\epsilon\ll 1$. The couplings are still chosen independently, and the
probability of $J_{l}=\epsilon J$ is $\epsilon^{\alpha}$. This is a discrete
analogue to the situation from the previous subsections, for which $J_{l}$
could take any value greater than zero. Here, any LR bound will clearly have a
ballistic front, but one can still ask how the LR velocity $v$ compares to the
two scales $J$ and $\epsilon J$. By taking $\lambda$ in Eq. (38) to be those
links with $J_{l}=\epsilon J$ (the fraction of which approaches
$\epsilon^{\alpha}$ at large $r$ with probability 1), and comparing to the
conventional LR bound, we find that

$v=4e\epsilon^{\max[1-\alpha,0]}J.$ (81)

Analogous to the previous results, $v\ll J$ for $\alpha<1$. Furthermore, the
dependence of $v$ on $\epsilon$ in Eq. (81) is tight — the average of
$1/J_{l}$ is finite for all $\alpha$, namely given by
$(1-\epsilon^{\alpha}+\epsilon^{\alpha-1})/J$, and so the SLLN again applies,
as in Eq. (66). Taking $\epsilon\ll 1$, the velocity of the transfer protocol
is therefore Eq. (81) up to prefactors.

We can easily generalize to there being an arbitrary (finite) number of widely
separated energy scales. Suppose that $J_{l}=\epsilon^{\gamma_{k}}J$ with
probability $\epsilon^{\alpha_{k}}$ for $k\in\\{1,\cdots,K\\}$, and $J_{l}=J$
otherwise. Assume $0<\gamma_{1}<\cdots<\gamma_{K}$ and
$0<\alpha_{1}<\cdots<\alpha_{K}$. The optimal LR velocity is now

$\begin{gathered}v=4e\epsilon^{\zeta}J,\\\
\zeta\equiv\max[\gamma_{K}-\alpha_{K},\cdots,\gamma_{1}-\alpha_{1},0].\end{gathered}$
(82)

The dependence on $\epsilon$ is again tight. While simple, this result does
highlight that in general, neither the largest nor the smallest energy scale
necessarily determines the relevant velocity for operator growth on its own.

Figure 7: Example of a “ladder”, with $M=3$ sites per rung. To apply our
analysis, simply treat all $M$ sites connected vertically as a single “site”,
indicated by the red shading.

Bounds for ladders: Consider a system such as in Fig. 7, in which sites are
labelled by $(i,j)$ with $i\in\\{\cdots,-1,0,1,\cdots\\}$ and
$j\in\\{1,\cdots,M\\}$. The Hamiltonian is still given by a sum of terms for
each link of the lattice. Interactions along vertical links are arbitrary, and
interactions along horizontal links (denoted $H_{ij}(t)$ for the link between
$(i-1,j)$ and $(i,j)$) obey $\lVert H_{ij}(t)\rVert\leq J_{ij}$. Each $J_{ij}$
is again drawn independently from $\mu(J)$.

Since our analysis does not make any assumptions regarding the nature of the
local Hilbert space, we can simply identify each set of sites connected
vertically — $\\{(i,j)\\}_{j=1}^{M}$ for fixed $i$ — as comprising a single
“local” Hilbert space. However, the interaction between neighboring $i$ is
then $\sum_{j}H_{ij}(t)$, meaning that the coefficient $J_{l}$ entering into
bounds such as Eq. (38) should be $\sum_{j}J_{lj}$. The probability of
$\sum_{j}J_{lj}\leq J$ is bounded by

$\mu\big{(}J/M\big{)}^{M}\leq\textrm{Pr}\left[\sum_{j}J_{lj}\leq
J\right]\leq\mu\big{(}J\big{)}^{M}.$ (83)

Thus the correct exponent to use in our analysis is now $M\alpha$, and in
particular, $z_{c}(\alpha)=\max[1/M\alpha,1]$. Obtaining an improvement over
the conventional LR bound now requires $\alpha<1/M$, but nonetheless, we still
have that $z_{c}\rightarrow\infty$ as $\alpha\rightarrow 0$.

In fact, we can adapt the construction of Ref. Tran  _et al._ (2021b) to show
that this result for $z_{c}(\alpha)$ is tight. We discuss this assuming two
states per site ($d=2$) labelled by $|0\rangle$ and $|1\rangle$ — the same
protocol extends to arbitrary $d$ simply by acting as the identity in the
subspace orthogonal to $|0\rangle$ and $|1\rangle$, and it still produces an
$O(1)$ commutator for generic operators $A_{0}$ and $B_{r}$ which act non-
trivially on $|0\rangle$ and $|1\rangle$.

Taking cues from Ref. Tran  _et al._ (2021b), consider starting in the product
state with $a|0\rangle+b|1\rangle$ on site $(i-1,j)$ and $|0\rangle$ on all
other sites of rungs $i-1$ and $i$. Since arbitrary vertical interactions are
allowed, we can construct a unitary that takes this state to
$(a|\overline{0}\rangle_{i-1}+b|\overline{1}\rangle_{i-1})\otimes(|\overline{0}\rangle_{i}+|\overline{1}\rangle_{i})/\sqrt{2}$
in arbitrarily short time, where $|\overline{0}\rangle_{i}$ and
$|\overline{1}\rangle_{i}$ denote the states on rung $i$ with all sites in
$|0\rangle$ and $|1\rangle$ respectively. Defining
$H_{i}\equiv\sum_{j=1}^{M}J_{ij}|1\rangle\langle
1|_{(i-1,j)}\otimes|1\rangle\langle 1|_{(i,j)}$, we have

$\displaystyle e^{i\pi
H_{i}/\sum_{j}J_{ij}}\Big{(}a\big{|}\overline{0}\big{>}_{i-1}+b\big{|}\overline{1}\big{>}_{i-1}\Big{)}\otimes\frac{\big{|}\overline{0}\big{>}_{i}+\big{|}\overline{1}\big{>}_{i}}{\sqrt{2}}$
(84)
$\displaystyle\;=a\big{|}\overline{0}\big{>}_{i-1}\otimes\frac{\big{|}\overline{0}\big{>}_{i}+\big{|}\overline{1}\big{>}_{i}}{\sqrt{2}}+b\big{|}\overline{1}\big{>}_{i-1}\otimes\frac{\big{|}\overline{0}\big{>}_{i}-\big{|}\overline{1}\big{>}_{i}}{\sqrt{2}}.$

The states $(|\overline{0}\rangle_{i}+|\overline{1}\rangle_{i})/\sqrt{2}$ and
$(|\overline{0}\rangle_{i}-|\overline{1}\rangle_{i})/\sqrt{2}$ can then be
converted into $|\overline{0}\rangle_{i}$ and $|\overline{1}\rangle_{i}$
respectively, again in arbitrarily short time, using interactions solely on
rung $i$. This procedure thus transforms the product state having
$a|0\rangle+b|1\rangle$ on site $(i-1,j)$ and $|0\rangle$ otherwise into the
generalized GHZ state
$a|\overline{0}\rangle_{i-1}\otimes|\overline{0}\rangle_{i}+b|\overline{1}\rangle_{i-1}\otimes|\overline{1}\rangle_{i}$.
Subsequently applying the procedure in reverse, albeit with the roles of rungs
$i-1$ and $i$ exchanged, then takes this generalized GHZ state into the
product state having $a|0\rangle+b|1\rangle$ on site $(i,j)$ and $|0\rangle$
otherwise. The net effect is that the state on site $(i-1,j)$ has been
transferred to site $(i,j)$ in a time $2\pi/\sum_{j}J_{ij}$ (coming from Eq.
(84)). Repeating the transfer sequentially from rung 0 to $r$, we have a
protocol analogous to Fig. 3 with runtime
$T_{r}=\sum_{l=1}^{r}2\pi/\sum_{j}J_{ij}$.

Thus not only does our LR bound apply to the ladder of Fig. 7, with
$\sum_{j}J_{lj}$ in place of $J_{l}$, but so does our analysis of the 1D
transfer protocol, again using $\sum_{j}J_{lj}$ as an effective horizontal
coupling. The result derived above that $z_{c}(\alpha)=\max[1/M\alpha,1]$ is
therefore tight. Note that if we restrict ourselves to bounded-strength
vertical interactions, but with bounds that are spatially uniform, then the
dynamical exponent remains unaffected even once the time required to effect
all single-rung transformations is incorporated. We leave the more complicated
situation in which the vertical interactions themselves have weak links as a
direction for future work.

The fact that $z_{c}(\alpha)\rightarrow 1$ as $M\rightarrow\infty$ for any
$\alpha>0$ suggests that our conclusions may not extrapolate to higher
dimensions (and analogously to longer-range interactions). There are far more
paths connecting any two sites in higher dimensions, and it may be that
transport remains ballistic for any power-law distribution of weak links. Of
course, the analysis of the ladder presented here only accounts for weak links
in one direction, and so the behavior of truly multi-dimensional disordered
systems remains an important open question.

##  VI Applications

In Sec. IV, we derived a modified LR bound for non-translation-invariant
systems — Eq. (45) — requiring only that the empirical distribution
$\mu_{r}(J)$ converge to a function $\mu(J)\sim CJ^{\alpha}$ (as formalized by
Eqs. (42) and (43)). For $\alpha<1$, the modified bound gives a significant
improvement over the conventional bound, and even guarantees that operator
spreading is sub-ballistic. Here we consider the consequences of this result
for various applications (assume $\alpha<1$ throughout).

On the one hand, the manner in which LR bounds are used in the following is
quite similar from case to case. Yet we shall see that different contexts come
with different caveats, some more than others, and we discuss the many open
directions for future work.

Note as well that we are working with the general bound of Sec. IV rather than
the more detailed results of Sec. V. In particular, implications of the
“a.a.”-“i.o.” distinction for the following applications warrant further
investigation.

###  VI.1 Growth of correlations

LR bounds directly place limitations on the extent to which correlations can
develop following a quench. Consider the correlation function

$G(t)\equiv\big{<}A^{t}B^{t}\big{>}-\big{<}A^{t}\big{>}\big{<}B^{t}\big{>},$
(85)

where the expectation value is in a product state $|\Psi\rangle$, time
evolution is under a Hamiltonian $H(t)\in\mathcal{H}_{J}$, and the operators
$A^{0}$ and $B^{0}$ are supported on sites to the left of 0 and to the right
of $r$ respectively (note that our analysis in Sec. IV applies equally well to
such operators even if they are not strictly local). Thus $G(0)=0$, and one
would like to understand how $G(t)$ grows in time.

The authors of Ref. Bravyi  _et al._ (2006) show that one can bound (assuming
$\lVert A\rVert=\lVert B\rVert=1$ for simplicity)

$\big{|}G(t)\big{|}\leq 4\big{\lVert}\mathcal{P}_{\geq
r/2}A^{t}\big{\rVert}+4\big{\lVert}\mathcal{P}_{\leq r/2}B^{t}\big{\rVert}.$
(86)

Supposing that $r$ is sufficiently large, we can immediately apply Eq. (45):

$\big{|}G(t)\big{|}\leq\exp{\left[-Cr^{1-\beta\alpha}+\frac{C^{\prime}t}{r^{\beta}}\right]},$
(87)

where $\beta$ can take any value in $(0,1/\alpha)$. The fact that one can
choose an optimal $\beta$ depending on $t$ makes Eq. (87) slightly more
interesting than the conventional bound.

Figure 8: Plot of Eq. (88), using $\alpha=2/3$ for concreteness. Dashed red
line corresponds to $n=2$ with $\beta_{i}\in\\{0,3/4,3/2\\}$ (each of the
individual curves being minimized among in Eq. (88) is shown as a dotted black
line). Solid red line corresponds to $n=30$ and $\beta_{i}$ equally spaced by
$1/20$, which closely approximates the curve at large $n$. Blue line is the
conventional LR bound for comparison. To reproduce the exact numbers in the
plot, set $r=25$ and $C=C^{\prime}=1$.

However, care must be taken in varying $\beta$. We have shown that for any
$\beta\in(0,1/\alpha)$, there exists $R(\beta)$ such that the bound holds for
$r>R(\beta)$, but we have not shown that the convergence is uniform in $\beta$
(i.e., that $R(\beta)$ can be made independent of $\beta$). Rather than impose
an additional requirement on the convergence of $\mu_{r}(J)$ and attempt to
verify it in non-trivial situations, here we shall simply choose a finite set
$\\{\beta_{i}\\}_{i=0}^{n}$ with $0\equiv\beta_{0}<\cdots<\beta_{n}<1/\alpha$
(note that $\beta=0$ simply recovers the conventional LR bound). The precise
statement of Eq. (87) is that for
$r/2>\max[R(\beta_{0}),\cdots,R(\beta_{n})]$,

$\big{|}G(t)\big{|}\leq\exp{\Bigg{[}\min_{i=0}^{n}\left[-Cr^{1-\beta_{i}\alpha}+\frac{C^{\prime}t}{r^{\beta_{i}}}\right]\Bigg{]}}.$
(88)

The behavior of Eq. (88) is shown in the dashed red line of Fig. 8. At large
$r$, it is given by $\exp{[-Cr+C^{\prime}t]}$ until $t=O(r)$, then by
$\exp{[-Cr^{1-\beta_{1}\alpha}+C^{\prime}t/r^{\beta_{1}}]}$ until
$t=O(r^{1+\beta_{1}(1-\alpha)})$, and in general,

$\displaystyle\big{|}G(t)\big{|}$
$\displaystyle\leq\exp{\left[-Cr^{1-\beta_{i}\alpha}+\frac{C^{\prime}t}{r^{\beta_{i}}}\right]},$
(89) $\displaystyle\qquad\qquad\qquad\quad r^{1+\beta_{i-1}(1-\alpha)}\ll t\ll
r^{1+\beta_{i}(1-\alpha)}.$

Of course, we are free to choose as large a set $\\{\beta_{i}\\}$ as we like
(although this may increase the distance required for the bound to hold). One
should heuristically think of Eq. (88) as minimizing over all
$\beta\in(0,1/\alpha)$ for any value of $r$, shown as the solid red line in
Fig. 8.

###  VI.2 Creation of topological order

A related application is lower bounds on the time needed to create topological
order. Again following Ref. Bravyi  _et al._ (2006), we say that two states
$|\Psi_{1}\rangle$ and $|\Psi_{2}\rangle$ in a 1D system of size $N$ are
“topologically ordered” (relative to each other) if there exist constants
$c_{1}\in(0,1)$ and $c_{2}>0$ such that, for every observable $O$ supported on
a set with diameter $c_{1}N$ or less,

$\begin{gathered}\Big{|}\big{<}\Psi_{1}\big{|}O\big{|}\Psi_{1}\big{>}-\big{<}\Psi_{2}\big{|}O\big{|}\Psi_{2}\big{>}\Big{|}<2e^{-c_{2}N},\\\
\Big{|}\big{<}\Psi_{1}\big{|}O\big{|}\Psi_{2}\big{>}\Big{|}<e^{-c_{2}N}.\end{gathered}$
(90)

In words, no “local” operator (even one supported on a non-vanishing fraction
of the system) can distinguish between or couple such states.

Suppose that $|\Psi_{1}\rangle$ and $|\Psi_{2}\rangle$ are topologically
ordered and have been prepared from states $|\Phi_{1}\rangle$ and
$|\Phi_{2}\rangle$ via time evolution under a Hamiltonian
$H(t)\in\mathcal{H}_{J}$:

$\big{|}\Psi_{i}\big{>}=\mathcal{T}e^{-i\int_{0}^{t}\textrm{d}sH(s)}\big{|}\Phi_{i}\big{>}.$
(91)

Ref. Bravyi  _et al._ (2006) shows that, for any operator $O$ with diameter
less than $c_{1}N/2$,

$\Big{|}\big{<}\Phi_{1}\big{|}O\big{|}\Phi_{1}\big{>}-\big{<}\Phi_{2}\big{|}O\big{|}\Phi_{2}\big{>}\Big{|}\leq
2e^{-c_{2}N}+2\big{\lVert}\mathcal{P}_{\geq c_{1}N}O^{t}\big{\rVert},$ (92)

and analogously for the off-diagonal matrix elements. We again use that

$\big{\lVert}\mathcal{P}_{\geq
c_{1}N}O^{t}\big{\rVert}\leq\exp{\Bigg{[}\min_{i=0}^{n}\left[-CN^{1-\beta_{i}\alpha}+\frac{C^{\prime}t}{N^{\beta_{i}}}\right]\Bigg{]}}.$
(93)

Note that for $t\ll N$, Eq. (93) is exponentially small in $N$. Returning to
Eq. (92), $|\Phi_{1}\rangle$ and $|\Phi_{2}\rangle$ then satisfy the
definition of topological order. In other words, for times less than $O(N)$,
it is impossible to prepare topologically ordered states ($|\Psi_{1}\rangle$
and $|\Psi_{2}\rangle$) from any states which are not themselves topologically
ordered ($|\Phi_{1}\rangle$ and $|\Phi_{2}\rangle$).

The above conclusion is identical to that of the conventional case, but note
that Eq. (93) in fact remains small for much longer times, until
$t=O(N^{1/\alpha})$. The bound is no longer exponential (rather stretched-
exponential), and so the definition in Eq. (90) is not strictly met, but
$|\Phi_{1}\rangle$ and $|\Phi_{2}\rangle$ exhibit a slightly looser sense of
topological order nonetheless. In this sense, we have that for non-
translation-invariant systems with $\alpha<1$, it is impossible to prepare
ordered states from unordered in times less than $O(N^{1/\alpha})$.

###  VI.3 Heating in periodically driven systems

The authors of Ref. Abanin  _et al._ (2015) consider energy absorption in
weakly driven systems, for which the Hamiltonian is of the form

$H(t)=\sum_{l\in\Lambda}H_{l}-g\cos{\omega t}\sum_{i}O_{i}.$ (94)

We shall limit ourselves to 1D, although Ref. Abanin  _et al._ (2015) treats a
general dimension. Within linear response theory Chaikin and Lubensky (1995),
i.e., to leading order at small $g$, the energy absorption rate is
proportional to $\sigma(\omega)\equiv\sum_{ij}\sigma_{ij}(\omega)$, where

$\sigma_{ij}(\omega)=\frac{1}{2}\int_{-\infty}^{\infty}\textrm{d}te^{i\omega
t}\Big{<}\big{[}O_{i}^{t},O_{j}^{0}\big{]}\Big{>}.$ (95)

The expectation value denoted by $\langle\,\cdot\,\rangle$ is taken in the
initial (potentially mixed) state of the system. Strictly speaking,
$\sigma_{ij}(\omega)$ is a distribution and should be integrated against test
functions to obtain meaningful results.

The authors first derive a bound

$\big{|}\sigma_{ij}(\omega)\big{|}\leq Ce^{-\kappa|\omega|},$ (96)

assuming a translation-invariant constraint $\lVert H_{l}\rVert\leq J$. There
is already the potential for tightening Eq. (96) in non-translation-invariant
systems, since the constants $C$ and $\kappa$ involve sums over connected
paths with factors of $J_{l}$, much as in Sec. IV.1. However, we suspect that
a more careful analysis of the path sum would not yield a significant
improvement (see Eq. (32)), and so we continue to use Eq. (96).

LR bounds enter into the analysis of Ref. Abanin  _et al._ (2015) as a means
of bounding $|\sigma(\omega)|$ by $O(N)$ ($N$ being the number of sites in the
system — note that naively bounding
$|\sigma(\omega)|\leq\sum_{ij}|\sigma_{ij}(\omega)|$ would give a bound
$O(N^{2})$). In particular, consider two sites $i$ and $j$ separated by a
distance $r>r^{*}$, with $r^{*}$ to be chosen later. Assuming a conventional
LR bound with velocity $v$, Eq. (95) can be bounded by two contributions:

$\displaystyle\big{|}\sigma_{ij}(\omega)\big{|}$ $\displaystyle\leq
C\int_{0}^{r/v}\textrm{d}te^{-\frac{t^{2}}{\delta
t^{2}}}e^{-a(r-vt)}+C^{\prime}\int_{r/v}^{\infty}\textrm{d}te^{-\frac{t^{2}}{\delta
t^{2}}}$ (97) $\displaystyle\leq
Ce^{-ar}+C^{\prime}e^{-\frac{r^{2}}{v^{2}\delta t^{2}}}.$

See Ref. Abanin  _et al._ (2015) for details, including the appearance of the
Gaussian factor. Since the terms of Eq. (97) decay exponentially with $r$ or
faster, the sum over all $i$ and $j$ with $|i-j|>r^{*}$ is indeed $O(N)$ and
scales as $\exp{[-ar^{*}]}$. For summing over $|i-j|<r^{*}$, simply use Eq.
(96). Thus by setting $r^{*}=O(|\omega|)$, both contributions decay
exponentially with $|\omega|$, and therefore

$\big{|}\sigma(\omega)\big{|}\leq CNe^{-\kappa^{\prime}|\omega|}.$ (98)

The exponential decay with $|\omega|$ is the main result of Ref. Abanin  _et
al._ (2015).

Let us consider whether this conclusion is altered in non-translation-
invariant systems by the use of our modified LR bound. As in the preceding
subsections, we choose a set $\\{\beta_{i}\\}_{i=0}^{n}$ and minimize Eq. (45)
over $\beta_{i}$. The integral over $t$ in Eq. (95) splits into multiple terms
(compare to Eq. (97)):

$\displaystyle\big{|}\sigma_{ij}(\omega)\big{|}$ $\displaystyle\leq
C_{0}\int_{0}^{r/v_{0}}\textrm{d}te^{-\frac{t^{2}}{\delta
t^{2}}}e^{-a_{0}(r-v_{0}t)}$ (99)
$\displaystyle+C_{1}\int_{r/v_{0}}^{r^{1+\beta_{1}(1-\alpha)}/v_{1}}\textrm{d}te^{-\frac{t^{2}}{\delta
t^{2}}}e^{-a_{1}(r^{1-\beta_{1}\alpha}-v_{1}tr^{-\beta_{1}})}$
$\displaystyle+C_{2}\int_{r^{1+\beta_{1}(1-\alpha)}/v_{1}}^{r^{1+\beta_{2}(1-\alpha)}/v_{2}}\textrm{d}te^{-\frac{t^{2}}{\delta
t^{2}}}e^{-a_{2}(r^{1-\beta_{2}\alpha}-v_{2}tr^{-\beta_{2}})}$
$\displaystyle+\cdots+C_{n}\int_{r^{1+\beta_{n}(1-\alpha)}/v_{n}}^{\infty}\textrm{d}te^{-\frac{t^{2}}{\delta
t^{2}}}.$

Although the latter terms are indeed much smaller than in the translation-
invariant case, note that the first term is unaffected. Thus
$|\sigma_{ij}(\omega)|$ still scales as $\exp{[-ar]}$ at large $r$, we are
still led to take $r^{*}=O(|\omega|)$, and the final result in Eq. (98) is
unchanged.

The lack of any significant reduction in the heating rate can be traced back
to the fact that it is the tail of the LR bound which constrains
$|\sigma(\omega)|$, and the tail of the non-translation-invariant LR bound is
no tighter than that of the translation-invariant case. Of course, this is
only a statement about the bounds — the physics involved in any specific
system very well may imply a dramatically slower heating rate.

Strictly speaking, the above comments only apply within linear response
theory. To go beyond linear response, one could perform a Magnus-like
expansion along the lines of Refs. Abanin  _et al._ (2017); Tran  _et al._
(2019). However, higher-order terms in the expansion involve higher-body
interactions (i.e., terms supported on more than two sites), and so the
results of this paper do not immediately apply. While we expect that our
results could be generalized to higher-body interactions, we have not
attempted to do so and leave this for future work.

###  VI.4 Ground state correlations

One of the most well-known applications of LR bounds is for the proof that
gapped ground states have exponentially decaying correlations. Considering a
1D nearest-neighbor Hamiltonian $H$ for concreteness (although this result
holds much more generally), the statement is that if there is a non-vanishing
gap $\Delta E$ between the ground state and first excited state energies, then
for any local observables $A_{0}$ and $B_{r}$,

$G(r)\equiv\big{<}A_{0}B_{r}\big{>}-\big{<}A_{0}\big{>}\big{<}B_{r}\big{>}\leq
Ce^{-\kappa r},$ (100)

where expectation values are in the ground state of $H$. See Refs. Hastings
(2004); Hastings and Koma (2006) for full details of the proof. Here we only
discuss the steps at which LR bounds enter.

The authors of Refs. Hastings (2004); Hastings and Koma (2006) show that one
can bound $G(r)$ by (assuming $\lVert A_{0}\rVert=\lVert B_{r}\rVert=1$ for
simplicity)

$\big{|}G(r)\big{|}\leq\int_{-\infty}^{\infty}\textrm{d}t\frac{1}{|t|}e^{-\frac{t^{2}\Delta
E^{2}}{2q}}\Big{\lVert}\big{[}A_{0}^{t},B_{r}\big{]}\Big{\rVert}+2e^{-\frac{q}{2}},$
(101)

with $q$ to be chosen later. Much as we described in the previous subsection,
assuming a conventional LR bound with velocity $v$, split the integral into
one over $|t|<r/2v$ and one over $|t|>r/2v$. Using the LR bound in the former
and the trivial bound $\lVert[A_{0}^{t},B_{r}]\rVert\leq 2$ in the latter, we
find141414Note that $[A_{0}^{0},B_{r}]=0$ for any $r\neq 0$, and even more,
one can show that $[A_{0}^{t},B_{r}]=O(t)$ at small $t$. Thus the integrand of
Eq. (101) does not diverge as $|t|\rightarrow 0$ and the integral is finite.
The LR bound as presented in this paper, however, does not share the property
of vanishing as $|t|\rightarrow 0$, but this can easily be remedied by
combining the LR bound with the above observation that
$\lVert[A_{0}^{t},B_{r}]\rVert\leq C|t|$: use the former for $|t|\geq C^{-1}$
and the latter for $|t|<C^{-1}$ (see Refs. Hastings (2004); Hastings and Koma
(2006)).

$\displaystyle\big{|}G(r)\big{|}$ $\displaystyle\leq
Ce^{-\frac{ar}{2}}+C^{\prime}e^{-\frac{r^{2}\Delta
E^{2}}{8v^{2}q}}+2e^{-\frac{q}{2}}.$ (102)

Thus if $\Delta E>0$, setting $q=O(r)$ gives Eq. (100).

For non-translation-invariant systems, using our modified LR bound, we split
the integral over $t$ into additional terms as in the previous subsection (see
Eq. (99)). Yet we again do not obtain any significant improvement over Eq.
(102), since we still have a term scaling as $\exp{[-ar/2]}$.

In fact, it is unclear whether Eq. (102) itself applies to the systems
considered here — Ref. Movassagh (2017) proves that ensembles of Hamiltonians
are generically gapless if the norms of the interactions have continuous
distributions extending to zero. However, the lack of a gap in this case is
due to the existence with high probability of nearly-disconnected local
regions hosting low-energy excitations Movassagh (2017). Since those
excitations are decoupled from the larger system, one does not expect them to
give rise to long-range correlations on physical grounds. To our knowledge, it
remains a significant open question whether (and under what conditions) the
ground states of such disordered systems have rapidly decaying correlations.

###  VI.5 Predicting properties of gapped ground states

An interesting recent application in which LR bounds enter is classical
machine-learning algorithms for predicting properties of quantum many-body
ground states. The authors of Ref. Huang  _et al._ (2021) consider a family of
time-independent Hamiltonians $H(x)$ parametrized by a continuous (potentially
multi-dimensional) variable $x$, with corresponding ground states $\rho(x)$.
They obtain rigorous results on the ability to predict $\textrm{Tr}\rho(x)O$
for a certain $x$ from knowledge of $\\{\textrm{Tr}\rho(x_{i})O\\}_{i=1}^{n}$
for other parameter values $\\{x_{i}\\}_{i=1}^{n}$, where $O$ is any
observable that can be written as a sum of local terms.

A central ingredient is the result that if $H(x)$ has a non-zero spectral gap
uniformly in $x$, then one can bound the size of the gradient
$\nabla_{x}\textrm{Tr}\rho(x)O$. Specializing to 1D chains with
$H(x)=\sum_{l}H_{l}(x)$ and $O=\sum_{i}O_{i}$ (although Ref. Huang  _et al._
(2021) treats more general systems), the authors show that

$\big{\lVert}\nabla_{x}\textrm{Tr}\rho(x)O\big{\rVert}\leq\int_{-\infty}^{\infty}\textrm{d}tW(t)\sum_{il}\Big{\lVert}\big{[}O_{i},\hat{u}\cdot\nabla_{x}H_{l}^{t}(x)\big{]}\Big{\rVert},$
(103)

where $\hat{u}$ is an arbitrary unit vector in the parameter space, and $W(t)$
is a filter function which decays faster than any polynomial as
$|t|\rightarrow\infty$.

Much as before, the conventional LR bound enters by dividing the terms on the
right-hand side into two groups, one in which $i$ and $l$ are separated by a
distance less than $vt$ and the other in which they are separated by greater
than $vt$. Use the trivial bound on the commutator for the former and the LR
bound for the latter. Since there are $O(|t|)$ terms in the former and the sum
over the latter is $O(1)$, Eq. (103) reduces to

$\big{\lVert}\nabla_{x}\textrm{Tr}\rho(x)O\big{\rVert}\leq
C\int_{-\infty}^{\infty}\textrm{d}tW(t)|t|.$ (104)

The remaining integral is finite (since $W(t)$ decays sufficiently fast), and
thus the gradient is bounded. This property is then used in Ref. Huang  _et
al._ (2021) to establish the efficiency of algorithms capable of predicting
$\textrm{Tr}\rho(x)O$.

In a certain sense, our modified LR bound for non-translation-invariant
systems provides an improvement, since it allows us to replace the factor of
$|t|$ in Eq. (104) by $|t|^{\alpha}$. However, the important feature is merely
that the resulting integral over $t$ is finite. Thus while our modified bound
does tighten the numerical value of the gradient, it does not seem to give any
dramatic changes. Furthermore, since the analysis of Ref. Huang  _et al._
(2021) requires that the Hamiltonians $H(x)$ be gapped, the caveats from our
discussion of ground state correlations apply here as well. The more
substantive question is whether the conclusions of Ref. Huang  _et al._ (2021)
apply to disordered systems at all.

##  VII Acknowledgements

It is a pleasure to acknowledge valuable and stimulating discussions with
several colleagues: A. Chandran, P. J. D. Crowley, A. Deshpande, C. R.
Laumann, D. M. Long, A. Polkovnikov, and M. C. Tran in particular. We would
also like to thank MathOverflow users “Iosif Pinelis” and “mike” for guiding
us through a proof of Eq. (70). We acknowledge funding by the DoE ASCR Quantum
Testbed Pathfinder program (award No. DE-SC0019040), ARO MURI, AFOSR, DoE QSA,
NSF QLCI (award No. OMA-2120757), DoE ASCR Accelerated Research in Quantum
Computing program (award No. DE-SC0020312), NSF PFCQC program, AFOSR MURI,
DARPA SAVaNT ADVENT, and the Minta Martin and Simons Foundations.

## References

  * Lieb and Robinson (1972) E. H. Lieb and D. W. Robinson, “The finite group velocity of quantum spin systems,” Comm. Math. Phys. 28, 251 (1972).
  * Hastings (2004) M. B. Hastings, “Lieb-Schultz-Mattis in higher dimensions,” Phys. Rev. B 69, 104431 (2004).
  * Nachtergaele and Sims (2006) Bruno Nachtergaele and Robert Sims, “Lieb-Robinson bounds and the exponential clustering theorem,” Comm. Math. Phys. 265, 119–130 (2006).
  * Hastings and Koma (2006) M. B. Hastings and T. Koma, “Spectral gap and exponential decay of correlations,” Comm. Math. Phys. 265, 781–804 (2006).
  * Bravyi  _et al._ (2006) S. Bravyi, M. B. Hastings, and F. Verstraete, “Lieb-Robinson bounds and the generation of correlations and topological quantum order,” Phys. Rev. Lett. 97, 050401 (2006).
  * Osborne (2006) Tobias J. Osborne, “Efficient approximation of the dynamics of one-dimensional quantum spin systems,” Phys. Rev. Lett. 97, 157202 (2006).
  * Schuch  _et al._ (2011) Norbert Schuch, Sarah K. Harrison, Tobias J. Osborne, and Jens Eisert, “Information propagation for interacting-particle systems,” Phys. Rev. A 84, 032309 (2011).
  * Abanin  _et al._ (2015) D. A. Abanin, W. De Roeck, and F. Huveneers, “Exponentially slow heating in periodically driven many-body systems,” Phys. Rev. Lett. 115, 256803 (2015).
  * Shiraishi and Tajima (2017) Naoto Shiraishi and Hiroyasu Tajima, “Efficiency versus speed in quantum heat engines: Rigorous constraint from Lieb-Robinson bound,” Phys. Rev. E 96, 022138 (2017).
  * Eldredge  _et al._ (2017) Z. Eldredge, Z.-X. Gong, J. T. Young, A. H. Moosavian, M. Foss-Feig, and A. V. Gorshkov, “Fast quantum state transfer and entanglement renormalization using long-range interactions,” Phys. Rev. Lett. 119, 170503 (2017).
  * Deshpande  _et al._ (2018) Abhinav Deshpande, Bill Fefferman, Minh C. Tran, Michael Foss-Feig, and Alexey V. Gorshkov, “Dynamical phase transitions in sampling complexity,” Phys. Rev. Lett. 121, 030501 (2018).
  * Haah  _et al._ (2018) J. Haah, M. Hastings, R. Kothari, and G. H. Low, “Quantum algorithm for simulating real time evolution of lattice Hamiltonians,” in  _2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)_ (2018) pp. 350–360.
  * Bentsen  _et al._ (2019) G. Bentsen, Y. Gu, and A. Lucas, “Fast scrambling on sparse graphs,” PNAS 116, 6689 (2019).
  * Nachtergaele  _et al._ (2019) Bruno Nachtergaele, Robert Sims, and Amanda Young, “Quasi-locality bounds for quantum lattice systems. i. Lieb-Robinson bounds, quasi-local maps, and spectral flow automorphisms,” J. Math. Phys. 60, 061101 (2019).
  * Prémont-Schwarz  _et al._ (2010) I. Prémont-Schwarz, A. Hamma, I. Klich, and F. Markopoulou-Kalamara, “Lieb-Robinson bounds for commutator-bounded operators,” Phys. Rev. A 81, 040102 (2010).
  * Wang and Hazzard (2020) Zhiyuan Wang and Kaden R.A. Hazzard, “Tightening the Lieb-Robinson bound in locally interacting systems,” PRX Quantum 1, 010303 (2020).
  * Chen and Lucas (2021) C.-F. Chen and A. Lucas, “Operator growth bounds from graph theory,” Comm. Math. Phys. 385, 1273–1323 (2021).
  * Foss-Feig  _et al._ (2015) M. Foss-Feig, Z.-X. Gong, C. W. Clark, and A. V. Gorshkov, “Nearly linear light cones in long-range interacting quantum systems,” Phys. Rev. Lett. 114, 157201 (2015).
  * Tran  _et al._ (2019) M. C. Tran, A. Ehrenberg, A. Y. Guo, P. Titum, D. A. Abanin, and A. V. Gorshkov, “Locality and heating in periodically driven, power-law-interacting systems,” Phys. Rev. A 100, 052103 (2019).
  * Chen and Lucas (2019) C.-F. Chen and A. Lucas, “Finite speed of quantum scrambling with long range interactions,” Phys. Rev. Lett. 123, 250605 (2019).
  * Kuwahara and Saito (2020) T. Kuwahara and K. Saito, “Strictly linear light cones in long-range interacting systems of arbitrary dimensions,” Phys. Rev. X 10, 031010 (2020).
  * Tran  _et al._ (2021a) M. C. Tran, A. Y. Guo, C. L. Baldwin, A. Ehrenberg, A. V. Gorshkov, and A. Lucas, “Lieb-Robinson light cone for power-law interactions,” Phys. Rev. Lett. 127, 160401 (2021a).
  * Poulin (2010) D. Poulin, “Lieb-Robinson bound and locality for general Markovian quantum dynamics,” Phys. Rev. Lett. 104, 190401 (2010).
  * Descamps (2013) B. Descamps, “Asymptotically decreasing Lieb-Robinson velocity for a class of dissipative quantum dynamics,” Journal of Mathematical Physics 54, 092202 (2013).
  * Sweke  _et al._ (2019) R. Sweke, J. Eisert, and M. Kastner, “Lieb-Robinson bounds for open quantum systems with long-ranged interactions,” J. Phys. A 52, 424003 (2019).
  * Guo  _et al._ (2021) A. Y. Guo, S. Lieu, M. C. Tran, and A. V. Gorshkov, “Clustering of steady-state correlations in open systems with long-range interactions,” arXiv:2110.15368 (2021).
  * Burrell  _et al._ (2009) C. K. Burrell, J. Eisert, and T. J. Osborne, “Information propagation through quantum chains with fluctuating disorder,” Phys. Rev. A 80, 052319 (2009).
  * Gebert  _et al._ (2022) M. Gebert, A. Moon, and B. Nachtergaele, “A Lieb-Robinson bound for quantum spin chains with strong on-site impurities,” Rev. Math. Phys. 34, 2250007 (2022).
  * Chen (2021) C.-F. Chen, “Concentration of OTOC and Lieb-Robinson velocity in random Hamiltonians,” arXiv:2103.09186 (2021).
  * Burrell and Osborne (2007) C. K. Burrell and T. J. Osborne, “Bounds on the speed of information propagation in disordered quantum spin chains,” Phys. Rev. Lett. 99, 167201 (2007).
  * Hamza  _et al._ (2012) E. Hamza, R. Sims, and G. Stolz, “Dynamical localization in disordered quantum spin systems,” Comm. Math. Phys. 315, 215–239 (2012).
  * Gebert and Lemm (2016) M. Gebert and M. Lemm, “On polynomial Lieb–Robinson bounds for the XY chain in a decaying random field,” J. Stat. Phys. 164, 667–679 (2016).
  * Elgart  _et al._ (2018) A. Elgart, A. Klein, and G. Stolz, “Manifestations of dynamical localization in the disordered XXZ spin chain,” Comm. Math. Phys. 361, 1083–1113 (2018).
  * Fischer and Hertz (1991) K. H. Fischer and J. A. Hertz,  _Spin Glasses_ (CUP, 1991).
  * Mezard and Montanari (2009) M. Mezard and A. Montanari,  _Information, Physics, and Computation_ (OUP, 2009).
  * Lee and Ramakrishnan (1985) P. A. Lee and T. V. Ramakrishnan, “Disordered electronic systems,” Rev. Mod. Phys. 57, 287–337 (1985).
  * Kramer and MacKinnon (1993) B. Kramer and A. MacKinnon, “Localization: theory and experiment,” Rep. Prog. Phys. 56, 1469–1564 (1993).
  * Vojta (2010) T. Vojta, “Quantum Griffiths effects and smeared phase transitions in metals: Theory and experiment,” J. Low. Temp. Phys. 161, 299–323 (2010).
  * Song  _et al._ (2017) X.-Y. Song, C.-M. Jian, and L. Balents, “Strongly correlated metal built from Sachdev-Ye-Kitaev models,” Phys. Rev. Lett. 119, 216601 (2017).
  * Altland  _et al._ (2019a) A. Altland, D. Bagrets, and A. Kamenev, “Quantum criticality of granular Sachdev-Ye-Kitaev matter,” Phys. Rev. Lett. 123, 106601 (2019a).
  * Altland  _et al._ (2019b) A. Altland, D. Bagrets, and A. Kamenev, “Sachdev-Ye-Kitaev non-Fermi-liquid correlations in nanoscopic quantum transport,” Phys. Rev. Lett. 123, 226801 (2019b).
  * Basko  _et al._ (2006) D.M. Basko, I.L. Aleiner, and B.L. Altshuler, “Metal–insulator transition in a weakly interacting many-electron system with localized single-particle states,” Annals of Physics 321, 1126 – 1205 (2006).
  * Huse  _et al._ (2014) David A. Huse, Rahul Nandkishore, and Vadim Oganesyan, “Phenomenology of fully many-body-localized systems,” Phys. Rev. B 90, 174202 (2014).
  * Nandkishore and Huse (2015) Rahul Nandkishore and David A. Huse, “Many-body localization and thermalization in quantum statistical mechanics,” Annual Review of Condensed Matter Physics 6, 15–38 (2015).
  * Abanin  _et al._ (2019) Dmitry A. Abanin, Ehud Altman, Immanuel Bloch, and Maksym Serbyn, “Colloquium: Many-body localization, thermalization, and entanglement,” Rev. Mod. Phys. 91, 021001 (2019).
  * Imbrie (2016) J. Z. Imbrie, “On many-body localization for quantum spin chains,” J. Stat. Phys. 163, 998–1048 (2016).
  * Suntajs  _et al._ (2020) J. Suntajs, J. Bonca, T. Prosen, and L. Vidmar, “Quantum chaos challenges many-body localization,” Phys. Rev. E 102, 062144 (2020).
  * Abanin  _et al._ (2021) D. A. Abanin, J. H. Bardarson, G. De Tomasi, S. Gopalakrishnan, V. Khemani, S. A. Parameswaran, F. Pollmann, A. C. Potter, M. Serbyn, and R. Vasseur, “Distinguishing localization from chaos: Challenges in finite-size systems,” Annals of Physics 427, 168415 (2021).
  * Sels and Polkovnikov (2021) D. Sels and A. Polkovnikov, “Dynamical obstruction to localization in a disordered spin chain,” Phys. Rev. E 104, 054105 (2021).
  * Crowley and Chandran (2020) P. J. D. Crowley and A. Chandran, “A constructive theory of the numerically accessible many-body localized to thermal crossover,” arXiv:2012.14393 (2020).
  * Chamon  _et al._ (2002) Claudio Chamon, Malcolm P. Kennett, Horacio E. Castillo, and Leticia F. Cugliandolo, “Separation of time scales and reparametrization invariance for aging systems,” Phys. Rev. Lett. 89, 217201 (2002).
  * Bapst  _et al._ (2013) V. Bapst, L. Foini, F. Krzakala, G. Semerjian, and F. Zamponi, “The quantum adiabatic algorithm applied to random optimization problems: The quantum spin glass perspective,” Physics Reports 523, 127 – 205 (2013).
  * Baldwin and Laumann (2018) C. L. Baldwin and C. R. Laumann, “Quantum algorithm for energy matching in hard optimization problems,” Phys. Rev. B 97, 224201 (2018).
  * Nahum  _et al._ (2018) Adam Nahum, Jonathan Ruhman, and David A. Huse, “Dynamics of entanglement and transport in one-dimensional systems with quenched randomness,” Phys. Rev. B 98, 035118 (2018).
  * Tran  _et al._ (2020) M. C. Tran, C.-F. Chen, A. Ehrenberg, A. Y. Guo, A. Deshpande, Y. Hong, Z.-X. Gong, A. V. Gorshkov, and A. Lucas, “Hierarchy of linear light cones with long-range interactions,” Phys. Rev. X 10, 031009 (2020).
  * Garcia-Escartin and Chamorro-Posada (2013) Juan Carlos Garcia-Escartin and Pedro Chamorro-Posada, “A SWAP gate for qudits,” Quantum Inf. Process. 12, 3625–3631 (2013).
  * Rosenthal (2006) J. S. Rosenthal,  _A First Look at Rigorous Probability Theory_ (World Scientific, 2006).
  * Durrett (2019) R. Durrett,  _Probability: Theory and Examples_ (CUP, 2019).
  * (59) https://mathoverflow.net/questions/418111/what-is-the-liminf-of-a-sum-of-i-i-d-random-variables-with-heavy-tails.
  * Tran  _et al._ (2021b) Minh C. Tran, Andrew Y. Guo, Abhinav Deshpande, Andrew Lucas, and Alexey V. Gorshkov, “Optimal state transfer and entanglement generation in power-law interacting systems,” Phys. Rev. X 11, 031016 (2021b).
  * Chaikin and Lubensky (1995) P. M. Chaikin and T. C. Lubensky,  _Principles of Condensed Matter Physics_ (CUP, 1995).
  * Abanin  _et al._ (2017) Dmitry A. Abanin, Wojciech De Roeck, Wen Wei Ho, and Francois Huveneers, “Effective Hamiltonians, prethermalization, and slow energy absorption in periodically driven many-body systems,” Phys. Rev. B 95, 014112 (2017).
  * Movassagh (2017) Ramis Movassagh, “Generic local Hamiltonians are gapless,” Phys. Rev. Lett. 119, 220504 (2017).
  * Huang  _et al._ (2021) H.-Y. Huang, R. Kueng, G. Torlai, V. V. Albert, and J. Preskill, “Provably efficient machine learning for quantum many-body problems,” arXiv:2106.12627 (2021).

##  Appendix A Some properties of matrix norms

In this paper, we use $\lVert\,\cdot\,\rVert$ to denote the operator norm,
i.e., the largest eigenvalue of the operator in question (technically the
largest singular value, but we shall only apply the norm to Hermitian
operators). It is equivalently the $p\rightarrow\infty$ limit of the Schatten
$p$-norm, defined for a generic $M\times M$ matrix $O$ as

$\big{\lVert}O\big{\rVert}_{p}\equiv\left(\frac{1}{M}\textrm{Tr}\big{|}O\big{|}^{p}\right)^{\frac{1}{p}}=\left(\frac{1}{M}\sum_{i=1}^{M}\big{|}\lambda_{i}\big{|}^{p}\right)^{\frac{1}{p}}.$
(105)

The Frobenius ($p=2$) norm is often of independent interest (e.g., see Ref.
Tran  _et al._ (2020)). Let us first note that $\lVert O\rVert_{p}$ is a non-
decreasing function of $p$, and thus the bounds on $\lVert O\rVert$ obtained
in this work are automatically bounds on $\lVert O\rVert_{p}$ for all
$p\in(0,\infty)$. This follows from the fact that for $p<q$, the function
$f(x)=x^{q/p}$ is convex on $[0,\infty)$. Thus

$\left(\frac{1}{M}\sum_{i=1}^{M}\big{|}\lambda_{i}\big{|}^{p}\right)^{\frac{q}{p}}\leq\frac{1}{M}\sum_{i=1}^{M}\big{|}\lambda_{i}\big{|}^{q},$
(106)

and exponentiating both sides by $1/q$ gives $\lVert O\rVert_{p}\leq\lVert
O\rVert_{q}$.

Now restrict ourselves to the operator norm and to tensor product Hilbert
spaces, i.e., $M=d^{N}$. A useful inequality is Eq. (12) in the main text: for
any Hermitian operator $O$ and any subset $\omega$ of the sites,
$\lVert\mathcal{P}_{\omega}O\rVert\leq 2\lVert O\rVert$, where
$\mathcal{P}_{\omega}$ projects onto basis strings which act non-trivially
somewhere in $\omega$.

To prove this, define $\mathcal{Q}_{\omega}\equiv I-\mathcal{P}_{\omega}$ to
be the projector onto strings which do act trivially throughout $\omega$. We
have that

$\big{\lVert}\mathcal{P}_{\omega}O\big{\rVert}\leq\big{\lVert}O\big{\rVert}+\big{\lVert}\mathcal{Q}_{\omega}O\big{\rVert}.$
(107)

Note that $\mathcal{Q}_{\omega}O$ is a tensor product between $\omega$ and its
complement: $\mathcal{Q}_{\omega}O=I_{\omega}\otimes O_{\Omega/\omega}$ for a
certain operator $O_{\Omega/\omega}$ acting on $\Omega/\omega$. Furthermore,
$\lVert\mathcal{Q}_{\omega}O\rVert=\lVert O_{\Omega/\omega}\rVert$. Pick a
state $|\psi\rangle$ such that
$|\langle\psi|O_{\Omega/\omega}|\psi\rangle|=\lVert O_{\Omega/\omega}\rVert$,
and define the normalized density matrix

$\rho\equiv
d^{-|\omega|}I_{\omega}\otimes\big{|}\psi\big{>}\big{<}\psi\big{|},$ (108)

so that
$|\textrm{Tr}\rho\mathcal{Q}_{\omega}O|=\lVert\mathcal{Q}_{\omega}O\rVert$.
Also note that $\textrm{Tr}\rho\mathcal{P}_{\omega}O=0$ (since
$\mathcal{P}_{\omega}O$ by definition consists only of basis strings
orthogonal to the identity on $\omega$), thus
$\lVert\mathcal{Q}_{\omega}O\rVert=|\textrm{Tr}\rho O|$. Lastly, by the
variational principle for density matrices, $|\textrm{Tr}\rho O|\leq\lVert
O\rVert$. Returning to Eq. (107), we have Eq. (12) from the main text.

##  Appendix B Proof that projection commutes with decoupled evolution

Recall the notation of Eq. (18) in the main text: $\omega$ denotes any subset
of sites, and $\lambda$ denotes a subset of links such that $\omega$ and
$\Omega/\omega$ are disconnected under $\Lambda/\lambda$. In words, removing
$\lambda$ from the lattice disconnects $\omega$ from everything else. Eq.
(18), reproduced here:

$\mathcal{P}_{\omega}\mathcal{U}_{\Lambda/\lambda}(t)=\mathcal{U}_{\Lambda/\lambda}(t)\mathcal{P}_{\omega},$
(109)

is the statement that interactions on $\Lambda/\lambda$ alone cannot convert
an operator supported outside $\omega$ into one whose support intersects
$\omega$, or vice versa. While obvious on physical grounds, it is worth
confirming that this follows from the formal definitions in Sec. III.2.

We need only make the following observations, all of which are clear from the
explicit expression for $\mathcal{U}_{\Lambda/\lambda}(t)$ given by Eq. (17):

  * •

$\mathcal{U}_{\Lambda/\lambda}(t)$ factors into
$\mathcal{U}_{\omega}(t)\otimes\mathcal{U}_{\Omega/\omega}(t)$, where the
first factor involves only the interactions within $\omega$ and the second
only those outside $\omega$.

  * •

For any product operator $O\equiv O_{\omega}\otimes O_{\Omega/\omega}$,

$\mathcal{U}_{\Lambda/\lambda}(t)O=\mathcal{U}_{\omega}(t)O_{\omega}\otimes\mathcal{U}_{\Omega/\omega}(t)O_{\Omega/\omega}.$
(110)

  * •

The action of $\mathcal{U}(t)$ takes the identity string to itself and does
not take any other basis string onto the identity (this statement is always
true for any system).

Consider an arbitrary operator $O$, which can always be decomposed as

$O=\sum_{\nu_{\omega}}X_{\omega}^{(\nu_{\omega})}\otimes
O_{\Omega/\omega}^{(\nu_{\omega})},$ (111)

where $\nu_{\omega}$ denotes a set of basis indices on $\omega$ and
$O_{\Omega/\omega}^{(\nu_{\omega})}$ denotes the partial projection of $O$
onto basis string $X_{\omega}^{(\nu_{\omega})}$. As a result of the above, we
have that

$\displaystyle\mathcal{P}_{\omega}\mathcal{U}_{\Lambda/\lambda}(t)O$
$\displaystyle=\mathcal{P}_{\omega}\sum_{\nu_{\omega}}\mathcal{U}_{\omega}(t)X_{\omega}^{(\nu_{\omega})}\otimes\mathcal{U}_{\Omega/\omega}(t)O_{\Omega/\omega}^{(\nu_{\omega})}$
(112) $\displaystyle=\sum_{\nu_{\omega}\neq
0}\mathcal{U}_{\omega}(t)X_{\omega}^{(\nu_{\omega})}\otimes\mathcal{U}_{\Omega/\omega}(t)O_{\Omega/\omega}^{(\nu_{\omega})}$
$\displaystyle=\mathcal{U}_{\Lambda/\lambda}(t)\sum_{\nu_{\omega}\neq
0}X_{\omega}^{(\nu_{\omega})}\otimes
O_{\Omega/\omega}^{(\nu_{\omega})}=\mathcal{U}_{\Lambda/\lambda}(t)\mathcal{P}_{\omega}O.$

##  Appendix C An explicit state transfer protocol

The transfer protocol $H(t)\in\mathcal{H}_{J}$ illustrated in Fig. 3, which we
use to assess the tightness of our LR bounds in the main text, is given there
in terms of SWAP gates. While perfectly sufficient on its own (see footnote 13
of Sec. IV), it is satisfying to see that $H(t)$ can be represented entirely
in terms of “standard” interactions, even for arbitrary $d$-state degrees of
freedom. This was demonstrated in Ref. Garcia-Escartin and Chamorro-Posada
(2013), and we summarize their construction here for the sake of completeness.

The circuit diagram for a single SWAP gate is shown in Fig. 9. The central
element is the add-invert gate $\widetilde{X}_{ij}$ (subscripts indicating the
two sites involved), defined as

$\widetilde{X}_{ij}\big{|}q_{i},q_{j}\big{>}\equiv\big{|}q_{i},-q_{j}-q_{i}\big{>},$
(113)

where $q_{i},q_{j}\in\\{0,1,\cdots,d-1\\}$ label single-site basis states. All
arithmetic here is to be interpreted mod $d$. Then
$\textrm{SWAP}_{ij}=\widetilde{X}_{ij}\widetilde{X}_{ji}\widetilde{X}_{ij}$:

$\big{|}q_{i},q_{j}\big{>}\stackrel{{\scriptstyle\widetilde{X}_{ij}}}{{\longrightarrow}}\big{|}q_{i},-q_{j}-q_{i}\big{>}\stackrel{{\scriptstyle\widetilde{X}_{ji}}}{{\longrightarrow}}\big{|}q_{j},-q_{j}-q_{i}\big{>}\stackrel{{\scriptstyle\widetilde{X}_{ij}}}{{\longrightarrow}}\big{|}q_{j},q_{i}\big{>}.$
(114)

The construction of the add-invert gate involves the single-site Fourier
Transform gate,

$\textrm{FT}_{j}\big{|}q_{j}\big{>}\equiv\frac{1}{\sqrt{d}}\sum_{p_{j}=0}^{d-1}e^{2\pi
iq_{j}p_{j}/d}\big{|}p_{j}\big{>},$ (115)

and the controlled-Z gate,

$\textrm{CZ}_{ij}\big{|}q_{i},q_{j}\big{>}\equiv e^{2\pi
iq_{i}q_{j}/d}\big{|}q_{i},q_{j}\big{>}.$ (116)

One can directly confirm that
$\widetilde{X}_{ij}=\textrm{FT}_{j}\textrm{CZ}_{ij}\textrm{FT}_{j}$ Garcia-
Escartin and Chamorro-Posada (2013).

Figure 9: Implementation of a SWAP gate between sites $i$ and $j$. The
$\widetilde{X}_{ij}$ gate is given in Eq. (113), the $\textrm{FT}_{j}$ gate is
given in Eq. (115), and the $\textrm{CZ}_{ij}$ gate is given in Eq. (116).

We need to express this procedure in terms of a Hamiltonian
$H(t)\in\mathcal{H}_{J}$. The only interaction required is for implementation
of the controlled-Z gate. Defining the local operator
$Z_{j}\equiv\textrm{diag}(0,1,\cdots,d-1)$, it is simply a $Z_{i}Z_{j}$
interaction. In order to respect the constraint on link $l$ that $\lVert
H_{l}\rVert\leq J_{l}$ (note that $\lVert Z_{j}\rVert=d-1$), we set

$H_{l}=-\frac{J_{l}}{(d-1)^{2}}Z_{l-1}Z_{l}.$ (117)

The controlled-Z gate on link $l$ then amounts to applying interaction $H_{l}$
for time $2\pi(d-1)^{2}/dJ_{l}$ (and three such gates are needed per SWAP
gate). As for the FT gates, since arbitrary local terms are allowed in the
family $\mathcal{H}_{J}$ (see footnote 2 of Sec. II), each amounts to applying
a local field for some fixed time. The total runtime required to effect state
transfer from site 0 to $r$ is therefore (not including the $O(r)$ runtime
from all FT gates)

$T_{r}=\frac{6\pi(d-1)^{2}}{d}\sum_{l=1}^{r}\frac{1}{J_{l}}.$ (118)

##  Appendix D Some probabilistic tools

Here we summarize some of the mathematical tools from probability theory
needed in Sec. V of the main text. Far more detail can be found in textbooks
on the subject, such as Refs. Rosenthal (2006); Durrett (2019) (including
derivations of the following, which we shall not present here).

To begin, keep in mind that the fundamental objects in probability theory are
subsets of the set of all possible outcomes, called “events”, together with a
function Pr that maps such subsets to the interval $[0,1]$. Oftentimes not all
subsets can be included in the domain of Pr, and Pr must obey certain natural
properties, but we will not dwell on these here. The important thing to note
is simply that we can perform all of the usual set-theoretic operations on
events, such as the union or intersection, and many of the basic tools in
probability theory involve relating the values of Pr with respect to those
operations.

Our first tool is “countable subadditivity” (also known as the “union bound”):
for any countable (potentially infinite) collection of events $\\{E_{r}\\}$,

$\textrm{Pr}\left[\bigcup_{r}E_{r}\right]\leq\sum_{r}\textrm{Pr}\big{[}E_{r}\big{]}.$
(119)

We will primarily use Eq. (119) after establishing that $\textrm{Pr}[E_{r}]=0$
for all $r$ — it then follows that $\textrm{Pr}[\cup_{r}E_{r}]=0$. In words,
if each event $E_{r}$ separately has probability zero, then the probability
that any of them occur (even if there are a countably infinite number) is also
zero.

The next tool is the “continuity” of probabilities. Suppose that $\\{A_{r}\\}$
is an “increasing” set of events, in that $A_{1}\subseteq
A_{2}\subseteq\cdots$, and similarly that $\\{B_{r}\\}$ is a “decreasing” set
of events, in that $B_{1}\supseteq B_{2}\supseteq\cdots$. We then have that

$\textrm{Pr}\left[\bigcup_{r}A_{r}\right]=\lim_{r\rightarrow\infty}\textrm{Pr}\big{[}A_{r}\big{]},\qquad\textrm{Pr}\left[\bigcap_{r}B_{r}\right]=\lim_{r\rightarrow\infty}\textrm{Pr}\big{[}B_{r}\big{]}.$
(120)

For our purposes, we will have events either of the form $A_{r}=$ “the event
that $E_{r^{\prime}}$ occurs for all $r^{\prime}>r$” or $B_{r}=$ “the event
that $E_{r^{\prime}}$ occurs for some $r^{\prime}>r$”. In terms of set-
theoretic operations, these are given by

$A_{r}\equiv\bigcap_{r^{\prime}>r}E_{r^{\prime}},\qquad
B_{r}\equiv\bigcup_{r^{\prime}>r}E_{r^{\prime}}.$ (121)

Note that $\\{A_{r}\\}$ is an increasing set of events and $\\{B_{r}\\}$ is a
decreasing set. We will specifically want to determine the probability that
some $A_{r}$ occurs and the probability that all $B_{r}$ occur. The former
event is denoted “$E_{r^{\prime}}$ a.a.” with a.a. abbreviating “almost
always”, and the latter event is denoted “$E_{r^{\prime}}$ i.o.” with i.o.
abbreviating “infinitely often”. These events are given by

$E_{r^{\prime}}\textrm{
a.a.}\equiv\bigcup_{r}\bigcap_{r^{\prime}>r}E_{r^{\prime}},\qquad
E_{r^{\prime}}\textrm{
i.o.}\equiv\bigcap_{r}\bigcup_{r^{\prime}>r}E_{r^{\prime}}.$ (122)

Note that $E_{r^{\prime}}$ a.a. and $E_{r^{\prime}}$ i.o. can be described in
words as “there exists an $r$ past which all $E_{r^{\prime}}$ occur” and “past
every $r$ there is some $E_{r^{\prime}}$ that occurs”, i.e., “$E_{r^{\prime}}$
occurs almost always” and “$E_{r^{\prime}}$ occurs infinitely often”
respectively, in exactly the same manner as we have used in discussing LR
bounds. Continuity — Eq. (120) — allows us to express the probabilities of
these events as

$\textrm{Pr}\big{[}E_{r^{\prime}}\textrm{
a.a.}\big{]}=\lim_{r\rightarrow\infty}\textrm{Pr}\left[\bigcap_{r^{\prime}>r}E_{r^{\prime}}\right],\qquad\textrm{Pr}\big{[}E_{r^{\prime}}\textrm{
i.o.}\big{]}=\lim_{r\rightarrow\infty}\textrm{Pr}\left[\bigcup_{r^{\prime}>r}E_{r^{\prime}}\right].$
(123)

We lastly need the “first Borel-Cantelli lemma”, which says that if a
collection of events $\\{E_{r}\\}$ has probabilities such that
$\sum_{r}\textrm{Pr}[E_{r}]$ is finite, then the probability is 1 that only a
finite number of the events occur:

$\sum_{r}\textrm{Pr}\big{[}E_{r}\big{]}<\infty\quad\longrightarrow\quad\textrm{Pr}\big{[}E_{r}\textrm{
i.o.}\big{]}=0.$ (124)

In particular, suppose we have a sequence of random variables $\\{X_{r}\\}$
and want to prove that it converges to zero with probability 1. The definition
of $\\{X_{r}\\}$ not converging to zero is that there exist some $\epsilon>0$
such that for every $R$, $|X_{r}|>\epsilon$ for some $r>R$. In other words,
$|X_{r}|>\epsilon$ i.o. for all $\epsilon>0$. It suffices to consider only
rational $\epsilon>0$, and thus by countable subadditivity, we only need to
prove that $\textrm{Pr}[|X_{r}|>\epsilon\textrm{ i.o.}]=0$ for each individual
$\epsilon$. By the Borel-Cantelli lemma, it further suffices (but need not be
necessary) to prove that $\sum_{r}\textrm{Pr}[|X_{r}|>\epsilon]$ is finite. If
each individual term $\textrm{Pr}[|X_{r}|>\epsilon]$ can be calculated or at
least bounded directly, this is a very useful line of attack.