sets of Lanczos coefficients, $\left\\{a_{n}\right\\}_{n=0}^{K-1}$ and
$\left\\{b_{n}\right\\}_{n=1}^{K-1}$, all these objects being related by the
recursion

$b_{n}|K_{n}\rangle=\left(H-a_{n-1}\right)|K_{n-1}\rangle-
b_{n-1}|K_{n-2}\rangle~{},$ (2.32)

where it is understood that $|K_{-1}\rangle\equiv|K_{K}\rangle\equiv 0$, as
usual. Expressed in coordinates over the Krylov basis, the Hamiltonian takes,
once again, the form of a tight-binding Hamiltonian [126] where the
$b$-coefficients play the role of hopping amplitudes, while the
$a$-coefficients act as local potential energies on each site of the Kryvlov
chain. Explicitly, we have:

$H=\sum_{n=0}^{K-1}a_{n}|K_{n}\rangle\langle
K_{n}|+\sum_{n=0}^{K-2}b_{n+1}\Big{(}|K_{n}\rangle\langle
K_{n+1}|+|K_{n+1}\rangle\langle K_{n}|\Big{)}~{}.$ (2.33)

The time-evolving state may be decomposed in coordinates over the Krylov basis
as

$|\phi(t)\rangle=e^{-itH}|\phi\rangle=\sum_{n=0}^{K-1}\phi_{n}(t)|K_{n}\rangle~{},$
(2.34)

where this time the Krylov space wave function $\phi_{n}(t):=\langle
K_{n}|\phi(t)\rangle$ has been defined without modding out a a power of $i$ as
in (2.12) because the function would still be generically complex-valued even
after such a redefinition. The Schrödinger equation dictated by the
Hamiltonian (2.33) imposes a differential recurrence relation for the wave
function which has a diagonal term controlled by the $a$-coefficients:

$i\dot{\phi}_{n}(t)=a_{n}\phi_{n}(t)+b_{n+1}\phi_{n+1}(t)+b_{n}\phi_{n-1}(t)~{},$
(2.35)

with the boundary conditions $\phi_{-1}\equiv\phi_{K}\equiv 0$ and the initial
condition $\phi_{n}(0)=\delta_{n0}$, since the initial state is itself the
zeroth Krylov element131313As a consistency check for (2.35), one may redefine
$\phi_{n}(t)=i^{n}\varphi_{n}(t)$: Substituting this in the recursion and
setting $a_{n}=0$ recovers (2.16) but with the opposite sign on the left-hand
side. This is perfectly consistent with the fact that (2.35) was derived for a
state evolving in the Schrödinger picture, where the time evolution operator
is $e^{-itH}$, while (2.16) was obtained for operator evolution in the
Heisenberg picture, where the time-translation (super-)operator is
$e^{it\mathcal{L}}$..

Noting that unitarity preserves the norm of the Krylov space wave function,

$\sum_{n=0}^{K-1}{|\phi_{n}(t)|}^{2}=1~{},\qquad\forall t\in\mathds{R}~{},$
(2.36)

the state K-complexity and K-entropy can now be defined, analogously to (2.15)
and (2.18), as the expectation value of position on the Krylov chain and as
the Shannon entropy of the wave function, respectively:

$\begin{split}&C_{K}(t):=\sum_{n=0}^{K-1}n~{}{|\phi_{n}(t)|}^{2}~{},\\\
&S_{K}(t):=-\sum_{n=0}^{K-1}{|\phi_{n}(t)|}^{2}\log{|\phi_{n}(t)|}^{2}~{}.\end{split}$
(2.37)

Since the $a$-coefficients do not necessarily vanish for states, the moments
to which the Lanczos coefficients are in correspondence can have indistinctly
even or odd index:

$M_{n}:=\langle\phi|H^{n}|\phi\rangle=\langle K_{0}|H^{n}|K_{0}\rangle~{}.$
(2.38)

These are, in turn, the Taylor series coefficients of the survival amplitude
of the evolving state defined as:

$S(t):=\langle\phi|\phi(t)\rangle=\sum_{n=0}^{+\infty}\frac{{(-it)}^{n}}{n!}M_{n}~{},$
(2.39)

as one can see considering (2.31) and Taylor-expanding the time evolution
operator. Depending on the state $|\phi\rangle$ of interest, the survival
amplitude might be given by some relevant quantity with well-known properties.
As an example, the authors of [79], motivated by the usefulness of Krylov
complexity in holography, take the seed state to be the thermofield double
state, as we shall review in section 2.3, in which case the survival amplitude
is given by the analytic continuation of the system’s partition function. Even
more interestingly, in the latter case the survival probability equals the
spectral form factor [116, 122, 123, 124], which is itself a well-studied
object sensitive to the quantum-chaotic properties of systems.

Let us conclude this section by stating a useful property of K-complexity,
applicable to both state and operator complexity. Observing the most generic
form of the recursion relation (2.35) for the Krylov space wave function we
may note that, since the Lanczos coefficients are always real by construction,
complex conjugating the full expression yields the same new recursion as
sending $t\mapsto-t$, as long as $t\in\mathds{R}$, leaving the initial and
boundary conditions unchanged. Consequently, we have the relation

$\phi_{n}^{*}(t)=\phi_{n}(-t)\quad\text{for }t\in\mathds{R}~{}.$ (2.40)

We may now plug this result into the definition of Krylov complexity (2.37),
reaching:

$C_{K}(t)=\sum_{n=0}^{K-1}n~{}\phi_{n}(t)\phi_{n}(-t)\quad\text{for
}t\in\mathds{R}~{}.$ (2.41)

Since the right-hand side of expression (2.41) is manifestly invariant under
the replacement $t\mapsto-t$, we conclude that Krylov complexity is always an
even function of time, regardless of the details of the initial state, i.e.:

$C_{K}(t)=C_{K}(-t)~{},$ (2.42)

always for $t\in\mathds{R}$. In particular, this property applies to operator
Krylov complexity; we recall that the operator recursion (2.16) is, modulo a
wave function redefinition and an extra sign on the left-hand side coming from
the difference between the Heisenberg and the Schrödinger pictures, a
particular case of the more generic recursion (2.35) that applies whenever the
$a$-coefficients vanish. Finally, let us note that using (2.40) it is
immediate to show that K-entropy, as defined in (2.37), is also an even
function of time since, just like K-complexity, it only depends on the modulus
squared of the Krylov space wave function.

####  2.2 Two theorems

This section will present two theorems that appeared in [78] and [79]. These
independent results (the first one in the frame of operator Krylov complexity,
and the second in that of state K-complexity) put the notion of K-complexity
on a more solid footing by relating it to other generic complexity notions.
The theorem in [78] shows that $C_{K}(t)$ is an upper bound on a class of
generalized complexities to which familiar notions like size complexity [81]
or out-of-time-ordered correlators (OTOCs) [80] belong. On the other hand,
[79] argues that the Krylov basis is an optimal choice of basis for defining a
complexity in the sense that it minimizes the local rate of growth near $t=0$.
The statements and proofs of both theorems will be presented, together with an
eventual comparative discussion of the results which will provide some
clarifying remarks.

#####  2.2.1 Q-theorem

This first theorem, presented in [78], constructs a class of generalized
complexities, dubbed Q-complexities (hence the name we are using to refer to
this result), where the Q comes from the French word quelconque, and shows
that K-complexity is, up to a multiplicative factor, an upper bound of the
family. The theorem was originally formulated for operator complexities but,
as we shall see below, it can be immediately extrapolated to any other Hilbert
space, and in particular it applies to state complexity as well.

Let us start by introducing the family of Q-complexities for a given time-
evolving (super-)state
$\left|\mathcal{O}(t)\right)=e^{it\mathcal{L}}|\mathcal{O})\in\widehat{\mathcal{H}}$,
where each member is defined as the expectation value of some hermitian
(super-)operator $\mathcal{Q}$ in the state $|\mathcal{O}(t))$, i.e.

$Q(t):=\Big{(}\mathcal{O}(t)\Big{|}\mathcal{Q}\Big{|}\mathcal{O}(t)\Big{)}~{}.$
(2.43)

For it to define a Q-complexity, the operator $\mathcal{Q}$ must fulfill the
following properties:

  1. 1.

The operator is positive-semidefinite, so that $Q(t)$ is never negative.
Explicitly:

$\mathcal{Q}=\sum_{a\geq 0}q_{a}|q_{a})(q_{a}|~{},\qquad q_{a}\geq
0\quad\forall a\geq 0~{},$ (2.44)

where $q_{a}$ denote the Q-complexity eigenvalues and $|q_{a})$ are the
associated eigenstates. Note that, for the sake of generality, we have not
been specific about whether the space has finite of infinite dimension.
Additionally, note that the set $\left\\{q_{a}\right\\}_{a\geq 0}$ need not be
sorted.

  2. 2.

There exists a constant $M>0$ such that the two following properties hold
simultaneously:

    1. i)

The action of the time-evolution generator (the Liouvillian, in the current
formulation) on a Q-complexity eigenstate cannot increase arbitrarily the
Q-complexity:

$\left(q_{a}|\mathcal{L}|q_{b}\right)=0\qquad\text{if }|q_{a}-q_{b}|>M~{}.$
(2.45)

    2. ii)

The initial condition does not feature an arbitrarily high Q-complexity:

$\left(q|\mathcal{O}\right)=0\qquad\text{if }q>M~{}.$ (2.46)

We will later provide some examples of Q-complexities (specifically, operator
size and out-of-time-ordered correlation functions), but for now it shall
suffice to say that K-complexity is an element of this family, where the
$\mathcal{Q}$ operator is given by the K-complexity operator
$\widehat{\mathcal{C}_{K}}$ defined in (2.14), for which the $q$-values are
simply $q_{n}=n$ and the complexity eigenstates are the Krylov elements
$|\mathcal{O}_{n})$. K-complexity is, in fact, a special representative of the
family of Q-complexities because the eigenvalues are sorted and, by
construction, the initial state is the zeroth element of the Krylov basis and
the action of $\mathcal{L}$ on a basis element changes its K-complexity by at
most one unit; therefore, the constant $M$ in (2.45) and (2.46) can be chosen
to be $M=1$. The eigenbasis of the K-complexity operator is, by construction,
adapted to $\mathcal{L}$ and $\mathcal{O}$ so that $C_{K}(t)$ increases
progressively due to the hopping between nearest neighbours on the Krylov
chain. From this point of view, the eigenbasis of any other $\mathcal{Q}$
operator may be regarded as a dilated version of the Krylov basis, in the
sense that a given state $|q)$ may receive contributions from several Krylov
elements, so that larger jumps between different $|q)$ states may occur during
time evolution. We shall see that this implies that $Q(t)$ is, at most, a
multiple of $C_{K}(t)$, where the multiplicative coefficient is controlled by
the constant $M$.

The Q-theorem states that

$Q(t)\leq M~{}C_{K}(t)~{}.$ (2.47)

In order to prove it, let us begin by bounding the subset of $q$-eigenstates
with which a given Krylov element overlaps. We propose that

$\left(q|\mathcal{L}^{n}|\mathcal{O}\right)=0\qquad\text{if }q>M(n+1)~{}.$
(2.48)

This may be shown inductively. For $n=0$, (2.48) reduces to the assumption
(2.46), and it implies that $|\mathcal{O})$ belongs to the span of $|q_{a})$
with $a$ such that $q_{a}\leq M$, that is:

$|\mathcal{O})=\sum_{\begin{subarray}{c}a~{}\text{s.t.}\\\ q_{a}\leq
M\end{subarray}}c_{a}|q_{a})~{},$ (2.49)

for some coefficients $c_{a}$. Now, for the $n=1$ case of (2.48) we have:

$\left(q|\mathcal{L}|\mathcal{O}\right)=\sum_{\begin{subarray}{c}a~{}\text{s.t.}\\\
q_{a}\leq M\end{subarray}}c_{a}\left(q|\mathcal{L}|q_{a}\right)~{}.$ (2.50)

Applying (2.45) to the term of the sum with the highest value of $q_{a}$ we
reach that

$\left(q|\mathcal{L}|\mathcal{O}\right)=0\qquad\text{if }q>2M~{}.$ (2.51)

The induction step is completely analogous to the $n=1$ step that we have just
performed explicitly, resulting in (2.48). Since each Krylov element
$|\mathcal{O}_{n})$ is a linear combination of $\mathcal{L}^{m}|\mathcal{O})$
with $m=0,\dots,n$, it immediately follows that

$\left(q|\mathcal{O}_{n}\right)=0\qquad\text{if }q>M(n+1).$ (2.52)

Equation (2.52) may be understood as follows: For a fixed value of $q$, the
Krylov elements $|\mathcal{O}_{n})$ have zero overlap with $|q)$ (i.e. the
former do not reach that far in the $q$-basis) if $n$ is strictly smaller than
some critical value $n(q)$. The critical value suggested by (2.52) is

$n(q)=\frac{q}{M}-1~{}.$ (2.53)

The expectation value of $\mathcal{Q}$ in an arbitrary state
$|\mathcal{W})\in\widehat{\mathcal{H}}$ is

$\left(\mathcal{W}|\mathcal{Q}|\mathcal{W}\right)=\sum_{a\geq
0}q_{a}{\lvert\left(q_{a}|\mathcal{W}\right)\rvert}^{2}\equiv\int_{\mathds{R}^{+}}dq~{}q~{}w(q)~{},$
(2.54)

where in the last step we have introduced the probability distribution
function (pdf) $w(q)$, which may be thought of as a sum of delta functions in
order to match the discrete sum prior to the last equality sign. We may now
invoke a useful relation between the expectation value of a positive-
semidefinite variable $q$ with a pdf $w(q)$ and the integral of the
(reciprocal of the) cumulative distribution function (cdf), $W(q)$, defined as

$W(q):=\int_{q}^{+\infty}ds~{}w(s)~{}.$ (2.55)

The announced property is:

$\int_{\mathds{R}^{+}}dq~{}q~{}w(q)=\int_{\mathds{R}^{+}}dq~{}W(q)~{},$ (2.56)

relating the expectation value of $q$ to the sum of the cumulative
probabilities of large values of the variable141414Identity (2.56) may be
proved as follows:
$\int_{\mathds{R}^{+}}dq~{}W(q)=\int_{\mathds{R}^{+}}dq\int_{q}^{+\infty}ds~{}w(s)=\int_{\mathds{R}^{+}}ds\int_{0}^{s}dq~{}w(s)=\int_{\mathds{R}^{+}}ds~{}s~{}w(s)~{},$
and (2.56) is proved. Note that the argument did not involve potentially ill-
behaved tools such as derivatives and integration by parts, only an exchange
of the integration symbols, which is acceptable as long as Fubini’s theorem is
applicable. In particular, this proof allows to use the identity (2.56) for
the distributions $w(q)$ and $W(q)$ at hand even if they are sums of delta
functions, reflecting their original discrete nature.. The distribution $W(q)$
may be expressed in terms of projectors to eigenspaces of $\mathcal{Q}$ with
eigenvalues larger than or equal to $q$. For simplicity, we give their
discrete version:

$\begin{split}&P_{q}^{Q}:=\sum_{\begin{subarray}{c}a~{}\text{s.t.}\\\
q_{a}\geq q\end{subarray}}|q_{a})(q_{a}|~{},\\\ &P_{n}^{K}:=\sum_{m\geq
n}|\mathcal{O}_{m})(\mathcal{O}_{m}|~{},\end{split}$ (2.57)

where in the second line we have additionally defined the analogous object for
the Krylov basis, which shall be used later. $W(q)$ is given in terms of
$P_{q}^{Q}$ by

$W(q)=\left(\mathcal{W}|P_{q}^{Q}|\mathcal{W}\right)~{},$ (2.58)

and combining (2.54) with (2.56) and (2.58) we reach:

$\left(\mathcal{W}|\mathcal{Q}|\mathcal{W}\right)=\int_{\mathds{R}^{+}}dq~{}\left(\mathcal{W}|P_{q}^{Q}|\mathcal{W}\right)~{}.$
(2.59)

Having expressed the expectation value of $\mathcal{Q}$ in the state
$|\mathcal{W})$ in terms of the projector over large spectral values of $q$ is
useful because it allows to employ inequalities like (2.52), which state to
what extent Krylov elements probe high $Q$-complexity values. In order to
proceed further, we consider the identity

$P_{q}^{Q}(1-P^{K}_{n(q)})=\sum_{\begin{subarray}{c}a~{}\text{s.t.}\\\
q_{a}\geq
q\end{subarray}}\sum_{m<n(q)}|q_{a})\left(q_{a}|\mathcal{O}_{m}\right)(\mathcal{O}_{m}|=0~{}.$
(2.60)

Technically, (2.60) vanishes because, at fixed $q$, for any $m<n(q)$ the
overlap $\left(q_{a}|\mathcal{O}_{m}\right)$ is zero by definition of $n(q)$,
as discussed below equation (2.52). Equivalently, one may understand directly
the vanishing of the product $P_{q}^{Q}(1-P^{K}_{n(q)})$ because the term in
brackets is the projector onto the subspace of Krylov elements
$|\mathcal{O}_{m})$ with $m<n(q)$ which, by definition of $n(q)$, is
orthogonal to the span of the elements $|q_{a})$ with $q_{a}\geq q$, onto
which the first term of the product projects. Expression (2.60) implies that
the span of $\left\\{|q_{a})\right\\}_{q_{a}\geq q}$ is entirely contained in
the span of $\left\\{|\mathcal{O}_{m})\right\\}_{m\geq n(q)}$, and therefore
we have the identities:

$P_{q}^{Q}P_{n(q)}^{K}=P_{q}^{Q}\qquad\Longleftrightarrow\qquad
P_{n(q)}^{K}P_{q}^{Q}=P_{q}^{Q}~{},$ (2.61)

where the second expression is the hermitian adjoint of the first. With this,
we may manipulate the expectation value of the projector in (2.59) as follows:

$\left(\mathcal{W}\left|P_{q}^{Q}\right|\mathcal{W}\right)=\left(\mathcal{W}\left|P_{n(q)}^{K}P_{q}^{Q}P_{n(q)}^{K}\right|\mathcal{W}\right)\leq\left(\mathcal{W}\Big{|}{\left(P_{n(q)}^{K}\right)}^{2}\Big{|}\mathcal{W}\right)=\left(\mathcal{W}\left|P_{n(q)}^{K}\right|\mathcal{W}\right)~{}.$
(2.62)

For the first step we applied iteratively the identities (2.61), and the
inequality simply used the fact that $P_{q}^{Q}$ is a projector, so its
presence in the expectation value can only have the effect of reducing the
norm contributions. The last equality uses the fact that projectors are
idempotent. Plugging (2.62) into (2.59) we find:

$\begin{split}&\left(\mathcal{W}|\mathcal{Q}|\mathcal{W}\right)=\int_{\mathds{R}^{+}}dq~{}\left(\mathcal{W}\left|P_{q}^{Q}\right|\mathcal{W}\right)\leq\int_{\mathds{R}^{+}}dq~{}\left(\mathcal{W}\left|P_{n(q)}^{K}\right|\mathcal{W}\right)\\\
&=\int_{n(0)}^{n(+\infty)}\frac{dn}{\left.n^{\prime}\left(q\right)\right|_{q=q(n)}}\left(\mathcal{W}\left|P_{n}^{K}\right|\mathcal{W}\right)~{},\end{split}$
(2.63)

where in the last step we have noted explicitly the change of variables
$q\mapsto n(q)$. For $n(q)=\frac{q}{M}-1$, as given in (2.53), the Jacobian is
constant and equal to $M$, and the integration domain becomes
$n\in[-1,+\infty[$. However, the spectrum of the K-complexity operator has no
support over $n<0$, and therefore the final integral is equal to an integral
over $n\in\mathds{R}^{+}$. This gives:

$\left(\mathcal{W}|\mathcal{Q}|\mathcal{W}\right)\leq
M\int_{\mathds{R}^{+}}dn~{}\left(\mathcal{W}\left|P_{n}^{K}\right|\mathcal{W}\right)=M~{}\left(\mathcal{W}\left|\widehat{\mathcal{C}_{K}}\right|\mathcal{W}\right)~{}.$
(2.64)

As stated, expression (2.64) holds for any
$|\mathcal{W})\in\widehat{\mathcal{H}}$. Our interest, nevertheless, is for
the case $|\mathcal{W})=\left|\mathcal{O}(t)\right)$, in which case relation
(2.64) is the announced upper bound on the family of K-complexities:

$Q(t)\leq M~{}C_{K}(t)~{},$ (2.65)

which holds for all times, precisely because (2.64) holds for any element of
the Hilbert space $\widehat{\mathcal{H}}$. This concludes the proof151515The
original formulation of the theorem in [78] poses a more conservative bound,
$Q(t)\leq 2MC_{K}(t)$, which resulted from the use of a different critical
function $n(q)=\frac{q}{2M}$. Such a choice was not judged necessary for the
proof presented in this text. of the Q-theorem (2.47).

######  2.2.1.1 Some examples of Q-complexities

The Q-theorem (2.47) puts K-complexity in a prominent position within the
family of Q-complexities. Given this, showing that some members of this family
are familiar notions of quantum complexity that have been widely studied in
the context of operator growth, quantum chaos and holography serves to provide
a more solid justification to the study of Krylov complexity.

###### Size complexity

Operator size [81] measures the spatial extent over which an operator has a
non-trivial support. For the sake of illustration, we shall consider a system
of $N$ qudits, whose Hilbert space is the tensor product of the
$d$-dimensional spaces of each individual qudit, therefore having dimension
$D=d^{N}$, which implies that the dimension of operator space is
$\dim\widehat{\mathcal{H}}=D^{2}=d^{2N}$. The tensor product structure of the
total Hilbert space allows to define the size of an operator $\mathcal{O}$ as
the number of sites (i.e. the number of qudits) on which the operator acts
non-trivially (i.e. differently from the identity over that qudit space). If
$\mathcal{O}$ is simply a tensor product of operators, the definition just
given applies immediately, but if it is a linear combination of several
operators consisting on tensor products themselves, then the notion of size
needs to be modified to be the weighted average of the size of each individual
tensor product contributing to $\mathcal{O}$. Phrased in this manner, showing
that operator size is a $Q$-complexity is rather straightforward: We just need
to construct a basis of operator space consisting of tensor-product operators
of fixed size. For a given size $s$, there are $h(s)$ linearly independent
operator chains, where

$h(s)=\binom{N}{s}{(d^{2}-1)}^{s}~{},$ (2.66)

where $d^{2}-1$ is the dimension of the subspace of the operator space of a
single qudit that excludes the identity. We note that, consistently,

$\sum_{s=0}^{N}h(s)=d^{2N}=\dim\widehat{\mathcal{H}}~{}.$ (2.67)

Thus, one may form an orthonormal basis of operator space constructed out of
fixed-size chains $|s,j)$, with $j=1,\dots,h(s)$ and $s=0,\dots,N$, which can
be used to build the $\mathcal{Q}$ operator for size complexity through its
spectral resolution:

$\mathcal{Q}=\sum_{s=0}^{N}s\sum_{j=1}^{h(s)}|s,j)(s,j|~{}.$ (2.68)

The complexity eigenvalues are given by $s=0,\dots,N$, which are $h(s)$ times
degenerate. They are positive-semidefinite and therefore the assumption (2.44)
is satisfied. Furthermore, given a $k$-local Hamiltonian and an initial
operator $\mathcal{O}$ of size $r$, assumptions (2.45) and (2.46) are
satisfied with $M=\max(k,r)$. Thus, (2.68) defines correctly a $Q$-complexity.
The size of the time-evolving operator $|\mathcal{O}(t))$ may be computed as
the expectation value of $\mathcal{Q}$ in (2.68) and is subject to the bound
(2.47).

Given a system in the thermodynamic limit with a $k$-local Hamiltonian and an
initial operator of small size, each power of the Liouvillian in the Taylor
series of $e^{it\mathcal{L}}|\mathcal{O})$ has the effect of increasing the
size of the operator by a finite amount, and likewise it increases its
projection over the corresponding Krylov elements. As a result, for these
large-$N$ systems, K-complexity and size complexity may be expected to be
qualitatively similar [81, 1], at least for chaotic systems, where both
quantities may grow in time as fast as allowed (see section 2.3). However, for
finite size systems, the degeneracy in the size eigenvalues forbids size
complexity from growing further than $N$, the total length of the qudit chain
in the example above, while the Krylov complexity eigenvalues are completely
non-degenerate and increasing, as a result of which K-complexity has a further
scope of growth once size complexity has saturated. In the case of chaotic
systems, size complexity will typically grow exponentially [81] up to the
scrambling time [116] $t_{s}\sim\log N$, after which it saturates, while
K-complexity may continue growing up until the Heisenberg time $t\sim e^{N}$,
as argued in [109] and shown numerically for the first time in publication
[1], detailed in Chapter 3.

###### Out-of-time-ordered correlation functions

OTOCs are a standard probe of chaos (see e.g. [80, 91, 82]), as they measure
the capacity of a system to scramble information efficiently. Let us consider
two localized observables in a system (morally, one could think of the example
qudit system in the previous discussion), $\mathcal{V}$ and $\mathcal{O}$.
Assuming that they are localized on different sites, their commutator
vanishes, $[\mathcal{V},\mathcal{O}]=0$, implying that the measurements of
both observables are completely uncorrelated, they do not affect each other.
If we now evolve the operator $\mathcal{O}(t)$ with the system’s Hamiltonian,
it may start to grow, potentially developing some non-trivial support over the
sites on which $\mathcal{V}$ is localized. As a consequence, a measurement of
$\mathcal{V}$ at time zero and a measurement of $\mathcal{O}$ at time $t$
(i.e. a measurement of $\mathcal{O}(t)$) will be correlated, and this will be
reflected in the non-vanishing of the commutator
$[\mathcal{V},\mathcal{O}(t)]$. In order to measure the growth of such a
quantity, the OTOC is defined to be (the square of) its norm:

$\mathcal{F}(t):={\Big{\lVert}[\mathcal{V},\mathcal{O}(t)]\Big{\rVert}}^{2}=\Big{(}[\mathcal{V},\mathcal{O}(t)]\Big{|}[\mathcal{V},\mathcal{O}(t)]\Big{)}~{}.$
(2.69)

Given the inner product (2.7), expression (2.69) takes the familiar form

$\mathcal{F}(t)=\frac{-1}{Z(\beta)}\text{Tr}\left\\{e^{-\beta
H}{\left[\mathcal{V},\mathcal{O}(t)\right]}^{2}\right\\}~{},$ (2.70)

whose non-trivial [80] connected components are of the form
$\langle\mathcal{V}\mathcal{O}(t)\mathcal{V}\mathcal{O}(t)\rangle_{\beta}$,
hence the name out-of-time-ordered correlation function. The relevance of
OTOCs for the study of quantum chaos has peaked since [80] showed that these
functions grow at most exponentially, $\mathcal{F}(t)\sim e^{\lambda_{L}t}$,
with an exponent that is bounded from above by161616Strictly speaking, the so-
called MSS bound (2.71) was proved in [80] for a regulated version of the
thermal inner product. As of today, applying the same bound to OTOCs (2.70)
computed with the conventional thermal inner product remains a conjecture.:

$\lambda_{L}\leq\frac{2\pi}{\beta}~{}.$ (2.71)

Proving that OTOCs belong to the family of $Q$-complexities, bounded from
above by (a multiple of) K-complexity, is therefore an important result of
[78] which suggests the usefulness of the latter as a probe of quantum chaos.
Let us consider the superoperator defined by the adjoint action of
$\mathcal{V}$, $\mathcal{L}_{\mathcal{V}}\equiv[\mathcal{V},\cdot]$, verifying

$\mathcal{L}_{\mathcal{V}}|\mathcal{W})=\Big{|}\left[\mathcal{V},\mathcal{W}\right]\Big{)}$
(2.72)

for any $|\mathcal{W})\in\widehat{\mathcal{H}}$. With respect to the inner
products (2.10), this superoperator is hermitian,
$\mathcal{L}_{\mathcal{V}}=\mathcal{L}_{\mathcal{V}}^{\dagger}$, and as such
it satisfies

$(\mathcal{W}|\mathcal{L}_{\mathcal{V}}=\Big{(}\left[\mathcal{V},\mathcal{W}\right]\Big{|}~{},$
(2.73)

for any $(\mathcal{W}|$ belonging to the dual of operator space,
$\widehat{\mathcal{H}}^{*}$. With this, we can define the $\mathcal{Q}$
operator relevant to the OTOC (2.69) as:

$\mathcal{Q}=\mathcal{L}_{\mathcal{V}}^{2}~{}.$ (2.74)

And one can verify that

$\mathcal{F}(t)=\Big{(}\mathcal{O}(t)\Big{|}\mathcal{Q}\Big{|}\mathcal{O}(t)\Big{)}=\Big{(}\mathcal{O}(t)\Big{|}\mathcal{L}_{\mathcal{V}}^{2}\Big{|}\mathcal{O}(t)\Big{)}$
(2.75)

Because of the square, (2.74) is positive-semidefinite, automatically
fulfilling (2.44). Even though we do not have the explicit eigenbasis of
$\mathcal{L}_{\mathcal{V}}^{2}$, given a $k$-local Hamiltonian, assumptions
(2.45) and (2.46) are also satisfied thanks to the locality of $\mathcal{V}$
and $\mathcal{O}$. Even though OTOCs are often thought of as four-point
functions (which they are by definition), they are also a perfectly valid
$Q$-complexity. Their relation to K-complexity and the use of the latter to
improve the MSS bound (2.71) will be the subject of section 2.3.1.

#####  2.2.2 Optimal basis theorem

Let us now proceed to present the second theorem on Krylov complexity, which
appeared in [79]. It was originally formulated for state complexities defined
in the Hilbert space $\mathcal{H}$ of some physical system but, just like the
Q-theorem, it is applicable to any Hilbert space (such as operator space) for
which there may be a time evolution generator that can be used to define the
Krylov complexity of a certain time-evolving element of the space. The optimal
basis theorem proceeds very similarly to the Q-theorem: It establishes a class
of generalized complexities or cost functions, of which Krylov complexity (or
a very closely related notion) is a representative, and performs an
optimization procedure that will make the latter stand out from the rest. This
optimization, however, is of a different nature from that in section 2.2.1,
and as a result it will yield that K-complexity bounds any other element of
the family from below, but for a finite interval of time that will be
dependent on the latter. Let us present the theorem in its original
formulation.

Given a time-evolving state $|\phi(t)\rangle$, written in (2.31), in the
system’s $D$-dimensional Hilbert space $\mathcal{H}$, and given some
orthonormal basis for the space,

$\mathcal{B}:=\left\\{|\mathcal{B}_{n}\rangle\right\\}_{n=0}^{D-1}~{},$ (2.76)

one can define a generalized complexity or cost function associated to the
basis $\mathcal{B}$ as:

$C_{\mathcal{B}}(t):=\sum_{n=0}^{D-1}c_{n}{\left|\langle\mathcal{B}_{n}|\phi(t)\rangle\right|}^{2}\equiv\sum_{n=0}^{D-1}c_{n}~{}p_{\mathcal{B}}(n,t)~{},$
(2.77)

where the complexity eigenvalues $c_{n}$ form a sorted, strictly increasing
sequence $0\leq c_{0}<c_{1}<\dots<c_{D-1}$. The motivation of the argument is
to consider these coefficients as a fixed collection of values and to find a
basis that is optimal in some sense. In order to clarify the optimization
process, let us consider the Taylor series of the cost function (2.77) around
$t=0$:

$C_{\mathcal{B}}(t)=\sum_{m=0}^{+\infty}\frac{t^{m}}{m!}C_{\mathcal{B}}^{(m)}~{},$
(2.78)

where

$C_{\mathcal{B}}^{(m)}:=\sum_{n=0}^{D-1}c_{n}p_{\mathcal{B}}^{(m)}(n)~{},\qquad
p_{\mathcal{B}}^{(m)}(n):=\left.\frac{d^{m}}{dt^{m}}p_{\mathcal{B}}(n,t)\right|_{t=0}~{}.$
(2.79)

We now introduce a relational notion between sets of cost function Taylor
coefficients: Given two bases $\mathcal{B}$ and $\mathcal{B}^{\prime}$
defining the corresponding cost functions, we say that
$\left\\{C_{\mathcal{B}}^{(m)}\right\\}_{m\geq
0}<\left\\{C_{\mathcal{B}^{\prime}}^{(m)}\right\\}_{m\geq 0}$ if there exists
some $M\in\mathds{N}_{0}$ such that
$C_{\mathcal{B}}^{(m)}=C_{\mathcal{B}^{\prime}}^{(m)}$ for $m<M$ and
$C_{\mathcal{B}}^{(M)}<C_{\mathcal{B}^{\prime}}^{(M)}$. In words, one set is
said to be smaller than the other if the first differing Taylor coefficient is
smaller in the first set. This implies that there exists some time $t_{*}$
such that $\mathcal{C}_{\mathcal{B}}(t)<\mathcal{C}_{\mathcal{B}^{\prime}}(t)$
for $t\in[0,t_{*}[$. The particular value of $t_{*}$ is strongly dependent on
the subsequent Taylor coefficients of both series.

With this, we can now state the optimal basis theorem: For a fixed set of
complexity eigenvalues $c_{n}$, and given some orthonormal basis
$\mathcal{B}$, the Krylov basis (dubbed $\mathcal{K}$) is always optimal for
defining the cost function (2.77) in the sense that

$\left\\{C_{\mathcal{K}}^{(m)}\right\\}_{m\geq
0}<\left\\{C_{\mathcal{B}}^{(m)}\right\\}_{m\geq 0}\qquad\text{for any
}\mathcal{B}~{}.$ (2.80)

Again, this implies that, for any basis $\mathcal{B}$, there will always exist
some time interval around $t=0$ such that the cost function
$C_{\mathcal{B}}(t)$ is larger than K-complexity171717Strictly speaking,
$C_{\mathcal{K}}(t)$ matches our definition of Krylov complexity (2.15) if the
fixed complexity eigenvalues are $c_{n}=n$. Nevertheless, for any other choice
of increasing $c_{n}$, the Krylov basis remains being optimal. This is why,
within this section, we shall denote the cost function defined through the
Krylov basis as $C_{\mathcal{K}}(t)$ instead of $C_{K}(t)$, even though we may
still loosely refer to it as K-complexity..

In order to prove this theorem, we shall compute explicitly the moments of the
cost function of $\mathcal{B}$ and compare them to those of the cost function
associated to the Krylov basis. The only property of the Krylov basis that
will enter in the argument is the fact that it is an orthonormal basis
$\left\\{|K_{n}\rangle\right\\}_{n=0}^{K-1}$ where the $n$-th element is a
linear combination of $\left\\{H^{m}|\phi\rangle\right\\}_{m=0}^{n}$; it can
be inductively shown that this requirement defines uniquely the basis (up to
global phases), and hence the details of the Lanczos algorithm will not be
necessary.

The probability moments $p_{\mathcal{B}}^{(m)}(n)$ appearing in (2.79) can be
developed by using the definition (2.77), together with the explicit
expression of the time-evolving state (2.31). We find:

$p_{\mathcal{B}}^{(m)}(n)=i^{m}\sum_{k=0}^{m}(-1)^{k}\langle\phi|H^{m-k}|\mathcal{B}_{n}\rangle\langle\mathcal{B}_{n}|H^{k}|\phi\rangle~{}.$
(2.81)

To show (2.80), we may now proceed in an inductive fashion: We consider a
basis $\mathcal{B}$ such that its first $N$ elements are Krylov elements, i.e.
$|\mathcal{B}_{n}\rangle=|K_{n}\rangle$ for $n=0,\dots,N-1$, and we shall
analyse the difference between having the next basis element given by the next
Krylov element, i.e. $|\mathcal{B}_{N}\rangle=|K_{N}\rangle$, or by something
else. The conclusion will be that the former option minimises the cost
function Taylor coefficients, and proceeding iteratively one eventually
constructs the full Krylov basis181818If the Krylov dimension $K$ is smaller
than the full Hilbert space dimension $D$, then any basis whose first $K$
elements are the Krylov elements is optimal for (2.77), the subsequent basis
elements being irrelevant because they lie outside of the Krylov space and are
never probed by $|\phi(t)\rangle$.. As a seed for the inductive argument, we
note that the zeroth Krylov element is the initial condition itself,
$|K_{0}\rangle=|\phi(0)\rangle=|\phi\rangle$, and therefore
$C_{\mathcal{K}}^{(0)}=C_{\mathcal{K}}(0)=c_{0}$; if $|\mathcal{B}_{0}\rangle$
differs from $|\phi\rangle$ by more than a global phase, then
$C_{\mathcal{B}}^{(0)}=C_{\mathcal{B}}(0)$ will be some linear combination of
$\left\\{c_{n}\right\\}_{n=0}^{D-1}$ (where the coefficients of such a linear
combination add up to one because of normalization of the initial condition
and orthonormality of the basis $\mathcal{B}$), probing non-trivially
complexity eigenvalues higher than $c_{0}$. Since the $c_{n}$ are sorted and
increasing, it follows that $C_{\mathcal{K}}^{(0)}<C_{\mathcal{B}}^{(0)}$,
establishing (2.80) for this particular choice of $\mathcal{B}$ (which is in
fact a class of bases, as we have not been specific about the subsequent basis
elements $\left\\{|\mathcal{B}_{n}\rangle\right\\}_{n=1}^{D-1}$).

For a basis $\mathcal{B}$ that coincides by assumption with the Krylov basis
in its $N$ first elements, we can decompose the contributions to the
coefficients (2.79) into those coming from the Krylov basis, and those coming
from the remaining unspecified part of $\mathcal{B}$:

$C_{\mathcal{B}}^{(m)}=\sum_{n=0}^{N-1}c_{n}~{}p_{\mathcal{K}}^{(m)}(n)+\sum_{n\geq
N}c_{n}~{}p_{\mathcal{B}}^{(m)}(n)~{}.$ (2.82)

For the contributions with $n\geq N$, we can observe (2.81) and note that, by
assumption, the elements $|\mathcal{B}_{n}\rangle$ with $n\geq N$ are
orthogonal to $\left\\{|K_{n}\rangle\right\\}_{n<N}$ and, therefore, at least
one of the two bra-kets inside of the sum will vanish for $m<2N$, yielding a
vanishing result for the probability moment. That is:

$p_{\mathcal{B}}^{(m)}(n)=0\qquad\text{for }n\geq N\text{ and }m<2N~{}.$
(2.83)

Plugging (2.83) into (2.82) shows that

$C_{\mathcal{B}}^{(m)}=C_{\mathcal{K}}^{(m)}\qquad\text{for }m<2N~{}.$ (2.84)

Hence, the potentially differing Taylor coefficient is
$C_{\mathcal{B}}^{(2N)}$. Once again, using (2.81) and recalling that
$\mathcal{B}$ coincides with the Krylov basis in its first $N$ elements, we
have that

$C_{\mathcal{B}}^{(2N)}=\sum_{n=0}^{N-1}c_{n}~{}p_{\mathcal{K}}^{(2N)}(n)+\binom{2N}{N}\sum_{n\geq
N}c_{n}~{}\langle\phi|H^{N}|\mathcal{B}_{n}\rangle\langle\mathcal{B}_{n}|H^{N}|\phi\rangle~{}.$
(2.85)

At this point, it is useful to perform the orthogonal decomposition

$H^{N}|\phi\rangle=|\chi_{N}\rangle+|\xi_{N-1}\rangle~{},$ (2.86)

where

$|\xi_{N-1}\rangle\in\text{span}\left\\{|K_{n}\rangle\right\\}_{n=0}^{N-1}=\text{span}\left\\{|\mathcal{B}_{n}\rangle\right\\}_{n=0}^{N-1}$
(2.87)

and, by definition of the Krylov basis,
$|\chi_{N}\rangle\propto|K_{N}\rangle$. Its full norm must therefore be
contained in the span of all the $|\mathcal{B}_{n}\rangle$ with $n\geq N$, in
particular:

$\langle\chi_{N}|\chi_{N}\rangle=\sum_{n\geq
N}{\lvert\langle\mathcal{B}_{n}|\chi_{N}\rangle\rvert}^{2}.$ (2.88)

We therefore have that (2.85) equals to:

$\begin{split}C_{\mathcal{B}}^{(2N)}&=\sum_{n=0}^{N-1}c_{n}~{}p_{\mathcal{K}}^{(2N)}(n)+\binom{2N}{N}\sum_{n\geq
N}c_{n}~{}\langle\chi_{N}|\mathcal{B}_{n}\rangle\langle\mathcal{B}_{n}|\chi_{N}\rangle\\\
&\geq\sum_{n=0}^{N-1}c_{n}~{}p_{\mathcal{K}}^{(2N)}(n)+c_{N}~{}\binom{2N}{N}\sum_{n\geq
N}\langle\chi_{N}|\mathcal{B}_{n}\rangle\langle\mathcal{B}_{n}|\chi_{N}\rangle\\\
&=\sum_{n=0}^{N-1}c_{n}~{}p_{\mathcal{K}}^{(2N)}(n)+c_{N}~{}\binom{2N}{N}\langle\chi_{N}|\chi_{N}\rangle=C_{\mathcal{K}}^{(2N)}~{},\end{split}$
(2.89)

where the inequality has made use of the fact that
$\left\\{c_{n}\right\\}_{n\geq 0}$ is an increasing sequence. Equality holds
either if $|\chi_{N}\rangle=0$, in which case the Krylov basis terminates and
the basis $\mathcal{B}$ is already optimal (and equal to the $\mathcal{K}$
basis), or if $|\mathcal{B}_{N}\rangle=|K_{N}\rangle$, as in this case
$|\chi_{N}\rangle$ does not have overlap with the elements
$|\mathcal{B}_{n}\rangle$ with $n>N$. This shows that the optimal Taylor
coefficient is obtained if $|\mathcal{B}_{N}\rangle$ coincides with the next
Krylov element. As announced, the iterative application of this argument makes
us conclude that the Krylov basis optimizes the Taylor series coefficients of
the cost function, proving the theorem (2.80).

The authors of [79] present this theorem as a manner to obtain Krylov
complexity as an output of an optimization process. The caveats of this
optimization will nevertheless be discussed in section 2.2.3.

#####  2.2.3 Discussion and comparison of the theorems

The two theorems that have been discussed provide a solid motivation for the
study of Krylov complexity: The Q-theorem shows that it appears in the upper
bound of a large family of generalized complexities to which familiar notions
like operator size or OTOCs belong, while the optimal basis theorem proves
that the Krylov basis can be obtained as an output of an optimization process
that, roughly speaking, seeks the smallest growth rate of complexity in the
vicinity of $t=0$.

However, at first glance, it might appear that the two theorems are in
tension, since K-complexity is simultaneously appearing as an upper and as a
lower bound on the generalized complexities. Several subtleties need to be
discussed in order to understand how these results can hold simultaneously.
First, we have already pointed out that, even though the theorems were
originally formulated for different Hilbert spaces (one dealt with operator
complexity, and the other addressed state complexity), nothing in their proofs
prevents us from extending them to other Hilbert spaces. In particular, one
may attempt to apply both theorems simultaneously in the same space, but the
first caveat in such a situation is to note that their hypotheses are not
exactly identical:

  * •

The complexity eigenvalues in the Q-theorem are positive-semidefinite and not
necessarily sorted, according to (2.44), while those in the basis theorem,
introduced in (2.77), are positive-semidefinite and sorted. This is not a
major obstacle: The Q-theorem can be reformulated in terms of a sorted
sequence of $q$-values by re-arranging the eigenbasis of the $\mathcal{Q}$
operator. Additionally, the $q$-values in (2.44) are allowed to be degenerate,
while the sequence $c_{n}$ of cost-function coefficients was originally [79]
defined to be strictly increasing. Nevertheless, the proof of the basis
theorem can be extended to the case where the $c_{n}$ feature degeneracies,
since at the end of the day the inequality reached in (2.89) between the
Taylor series coefficients is not strict.

  * •

The Q-theorem has two additional assumptions, (2.45) and (2.46), which makes
it restrict to bases for which the complexity only increases gradually upon
the action of the time-evolution generator, and such that the initial
condition does not have an arbitrarily large complexity. Hence, having
accepted the previous point, it follows that all Q-complexities define
acceptable cost functions for the basis theorem, but the reverse is not true.

Taking the above considerations into account, we deduce that there exist some
generalized complexities that fulfill simultaneously the assumptions of both
theorems, and therefore both bounds apply simultaneously for them. However,
the bounds are of a different nature:

  * •

The Q-complexity bound (2.47) holds at arbitrary times and for any
Q-complexity, since it was derived as a bound on the expectation value of the
$\mathcal{Q}$ superoperator evaluated on an arbitrary state $|\mathcal{W})$,
which was eventually particularized to be $\big{|}\mathcal{O}(t)\big{)}$.

  * •

The bound in the time domain that one can deduce from the basis theorem
operates differently: Given a cost function $C_{\mathcal{B}}(t)$ for a certain
basis $\mathcal{B}$, the fact that its Taylor coefficients are bigger (in the
sense defined in section 2.2.2) than those of $C_{\mathcal{K}}(t)$ implies
that there exists some interval of time around $t=0$ for which
$C_{\mathcal{K}}(t)\leq C_{\mathcal{B}}(t)$, but the size of that interval is
completely dependent on $\mathcal{B}$. In other words, there does not exist a
finite time range for which Krylov complexity is smaller or equal than any
cost function191919As an example, for any time $t_{0}>0$, one can always
construct a basis $\mathcal{B}$ such that
$|\mathcal{B}_{0}\rangle=|\phi(t_{0})\rangle$, and as a result
$C_{\mathcal{B}}(t)$ will be minimal at $t=t_{0}$. In particular, $t_{0}$ can
be arbitrarily close to $t=0$.. The bound of this theorem acts pairwise, in
the sense that for any basis there is always an interval of time for which the
Krylov basis gives a smaller cost function, but such an interval is not
universal202020The authors of [79] refer to this statement as a functional
optimization, as opposed to an optimization in time.. The fact that the
$c_{n}$ values are left fixed in the optimization argument reflects the
aforementioned pairwise nature of the latter.

To summarise, there may exist a generalized complexity $C_{\mathcal{B}}(t)$
for which both theorems apply simultaneously, suggesting the hierarchy:

$\text{ `` }C_{\mathcal{K}}(t)\leq C_{\mathcal{B}}(t)\leq
MC_{K}(t)~{}\text{.'' }$ (2.90)

However, the first inequality holds for some $\mathcal{B}$-dependent time
interval around $t=0$, while the second one holds at arbitrary times and for
some $\mathcal{B}$-dependent constant $M$. Additionally, for the actual
K-complexity $C_{K}(t)$ to enter in the leftmost term of (2.90), the
complexity eigenvalues defining $C_{\mathcal{B}}(t)$ must be given by
$c_{n}=n$, since they are left fixed in the optimal basis theorem, which is
the one dictating the leftmost inequality212121Otherwise, the leftmost term of
(2.90) is given by a version of Krylov complexity constructed with the same
complexity eigenbasis (i.e. the Krylov basis), but whose complexity
eigenvalues are set to $c_{n}$ instead of $n$. Such a version was denoted as
$C_{\mathcal{K}}(t)$, instead of $C_{K}(t)$, in section 2.2.2. Nevertheless,
in such a situation the rightmost term of (2.90) will still be $MC_{K}(t)$
(i.e. $M$ times the actual Krylov complexity) because that inequality comes
from the Q-theorem, whose proof does not require the set of complexity
eigenvalues to be fixed..

####  2.3 K-complexity, chaos and holography

In this section we shall introduce the remaining ingredients motivating and
contextualizing the research conducted for the contributions [1, 2, 3, 4].

#####  2.3.1 K-complexity and chaos

Krylov complexity was introduced in [78] because of its usefulness for the
study of operator growth. Not only did the authors put this notion in relation
to other complexities through their Q-theorem, but they also proposed the so-
called universal operator growth hypothesis according to which the Lanczos
coefficients (and therefore K-complexity) grow as fast as possible in
maximally chaotic systems.

Before presenting the hypothesis in more detail, we shall elaborate on what we
mean by a quantum chaotic system. Classically, a system is said to be chaotic
if it features ergodic trajectories in phase space, as opposed to classically
integrable systems where orbits are confined to the Cartesian product of
invariant tori defined by the action-angle variables [128]. Typically,
trajectories in a classically chaotic system with slightly different initial
conditions will feature exponential departure as a function of time [129],
where the exponent controlling the separation is the (classical) Lyapunov
exponent. Extrapolating this notion of classical chaos to the quantum realm is
not entirely obvious, as the lack of periodicity in the phase space orbits of
classically chaotic systems does not allow for a semi-classical quantization
scheme à la Bohr-Sommerfeld [124], and therefore alternative approaches to
quantum chaos have been developed historically. Inspired by the study of heavy
atomic nuclei spectra (see [130, 131] for a wide survey), E. Wigner proposed
to model the spectral correlations in such systems by those of random
matrices: This boosted the study of random matrix theory in the context of
quantum chaos, pioneered by Wigner himself, as well as by F. Dyson and M.
Mehta [122, 124, 132]. Subsequently, based on numerical evidences, the BGS
conjecture by O. Bohigas, M. J. Giannoni, and C. Schmit [133] advocated for
the use of random matrix theory as a paradigm for the study of quantum chaos:
They proposed that classically chaotic systems feature, when quantized,
eigenvalue level repulsion, which is the imprint of random-matrix spectral
correlations, even if the system has an order-one number of degrees of freedom
(which was not the case of the nuclei of heavy atoms). On the other hand, the
Berry-Tabor conjecture [134] proposes that in integrable systems the amount of
symmetry is such that energy levels are effectively uncorrelated and the level
spacing probability distribution becomes Poissonian. The use of the spectral
statistics as a diagnose for quantum chaos or quantum integrability is
nowadays paradigmatic, see [122] for an extensive review.

There exists, however, a notion of quantum chaos that is in many cases related
to the one above, but potentially not mathematically equivalent, and it is
that of operator growth and out-of-time-ordered correlation functions. Roughly
speaking, chaotic systems may be regarded as efficient information scramblers
that rapidly spread initially localized perturbations, reflected in a fast
operator growth [81] and in the corresponding exponential increase of OTOCs
[80]. Often, many-body systems exhibiting spectral chaos also feature
scrambling dynamics in their four-point functions, as is the case of the
Sachdev-Ye-Kitaev (SYK) model [89, 88, 87], a paradigmatic instance of a
quantum-chaotic model in $0+1$ dimensions with a gravitational dual. The
article [78] proposing the universal operator growth hypothesis for
K-complexity focuses on this notion of chaos.

The starting point for the formulation of the hypothesis is to exploit the
combinatorial relations between the two-point function and the Lanczos
coefficients stated in section 2.1.1 in order to translate the behavior of the
high-frequency tails of the spectral function $\Phi(\omega)$ into the
asymptotic behavior of the Lanczos coefficients $b_{n}$ as a function of $n$
(so far we assume the system to be in the thermodynamic limit, allowing for
the Krylov dimension of the operator to be infinite). In [127] it is shown
that the two following behaviours are equivalent:

$b_{n}\sim bn^{\delta}\qquad\Longleftrightarrow\qquad\Phi(\omega)\sim
e^{-{\left|\frac{\omega}{\omega_{0}}\right|}^{1/\delta}}~{},$ (2.91)

where $b$ and $\omega_{0}$ are some dimensionful constants and $\delta>0$.
This can be combined with the bound on the spectral function proved in [135],
according to which the slowest possible decay rate of the spectral function at
large frequencies is the exponential, giving $\delta\leq 1$. More
specifically:

$b_{n}\lesssim\alpha n\qquad\Longleftrightarrow\qquad\Phi(\omega)\lesssim
e^{-\frac{|\omega|}{\omega_{0}}}~{}.$ (2.92)

Note that, because of its importance, for the case of an asymptotically
linearly growing Lanczos sequence ($\delta=1$) the constant $b$ in (2.91) has
been relabeled as $\alpha$. In systems with one spatial dimension, the bound
on $b_{n}$ acquires a logarithmic correction [78].

The translation between the behaviors (2.92) is relatively simple given the
exponential behavior of the spectral function: Since it comes from the Fourier
transform of the two-point function (2.23), this exponential tail implies that
the latter has a singularity along the imaginary axis at $t=\pm
i\omega_{0}^{-1}$, which in turn enforces a certain asymptotic behavior of the
moments $\mu_{2n}$ such that the convergence radius of the Taylor series of
the two-point function does not exceed the distance between such a singularity
and the origin. Finally, the relation between moments and Lanczos coefficients
through Dyck paths reviewed in section 1.9.1 can be used to show that this is
compatible with the linear growth of the Lanczos coefficients. The details are
worked out in [78], where the argument here described allows to additionally
show that

$\omega_{0}=\frac{2}{\pi}\alpha~{}.$ (2.93)

The proof of the theorem bounding the tails of the spectral function by an
exponential decay involves [78] the study of the asymptotic behavior of the
moments
$\mu_{2n}=\left(\mathcal{O}\left|\mathcal{L}^{2n}\right|\mathcal{O}\right)$,
which probes the growth of the operator upon successive applications of the
Liouvillian, leading to the proposal that the bound (2.92) is saturated by
maximally chaotic systems (in the sense of scrambling). This is the statement
of the universal222222The slope $\alpha$, or equivalently $\omega_{0}$, in the
bound (2.92) is system-dependent [135], but the fact that the asymptotic
growth of the Lanczos coefficients is at most linear is not: This is the
universal content of the hypothesis. operator growth hypothesis.

An analysis of the recurrence relation for the operator wave functions (2.16)
shows that a linearly increasing sequence of Lanczos coefficients
$b_{n}\sim\alpha n$ implies an exponential growth of Krylov complexity,
$C_{K}(t)\sim e^{2\alpha t}$. This is verified for some analytical toy models
in [78], but it may also be derived from a continuous approximation of the
discrete recurrence relation232323See Appendix D.4 for a detailed analysis of
such a continuous approximation.. The result is very useful in connection to
OTOCs: As shown in [80], the latter grow at most exponentially with a quantum
Lyapunov exponent $\lambda_{L}$ subject to the universal bound (2.71) and, at
the same time, they are subject to the Q-complexity bound (2.47), implying
that their growth rate cannot exceed that of K-complexity. This provides a new
bound for the Lyapunov exponent in terms of the Krylov complexity exponent:
For maximally chaotic systems, both the OTOC and $C_{K}(t)$ grow
exponentially, with exponents satisfying the relation

$\lambda_{L}\leq 2\alpha~{}.$ (2.94)

A clarification is in order at this point: Both the Lanczos coefficients and
the two-point function require the specification of an inner product for their
computation. Despite not having explicitly mentioned it, the bound (2.92) on
the tails of the spectral function is proved only at infinite-temperature
$\beta=0$, and hence the corresponding inner product (2.6) has been assumed
throughout. In the case of infinite temperature, the MSS bound (2.71) becomes
meaningless, while the bound (2.94) remains finite, even though it is system-
dependent due to the appearance of $\alpha$. This is an illustration of the
power of K-complexity as a probe of chaos.

For finite temperatures $\beta>0$, a choice of thermal inner product (2.10)
needs to be made. The MSS bound was proved in [80] for a specific choice of
regulated thermal inner product that spread evenly the Boltzmann factor across
the operator insertions. Hence, the authors of [78] propose that the
corresponding choice for the computation of K-complexity in order to make
contact with such a regulated OTOC is the Wightman inner product (2.9), which
leads them to conjecture that

$\lambda_{L}^{(T)}\leq 2\alpha_{T}^{(W)}~{},$ (2.95)

where the temperature dependence and the inner product choice have been
stressed for clarity. This conjecture is tested in [78] numerically for the
SYK model at various temperatures, and it is found to be much tighter than the
MSS bound in such a system.

The universal operator growth hypothesis triggered a full field of research on
the use of K-complexity as a probe of quantum chaos. A plethora of articles
(see section 2.4) have been produced in this context, including contributions
[1, 2, 3]. Nonetheless, the field is not exempt of debate: The universal
operator growth hypothesis has been strongly contested for finite temperature
where, as has been discussed, it is still conjectural. Let us give a brief
overview of such a debate, as some valuable lessons can be extracted from it
and it has influenced the research line of the contributions leading to this
Thesis.

The main criticism to the operator growth hypothesis expressed as (2.95) comes
from the realm of quantum field theory and CFT [85]. In cases in which the
operators of interest have positive energy dimension, contact singularities at
$t=0$ are expected [136] in the conventional thermal two-point function,
defined as

$C_{\beta}(t):=\big{(}\mathcal{O}|\mathcal{O}(t)\big{)}_{\beta}=\frac{1}{Z(\beta)}\text{Tr}\left[e^{-\beta
H}\mathcal{O}\mathcal{O}(t)\right]~{},$ (2.96)

and due to this non-analyticity, no moments $\mu_{2n}$ can be computed. In
order to compute K-complexity in these situations, one is forced to employ a
regulated version of $C_{\beta}(t)$, namely the Wightman correlator, obtained
from the corresponding Wightman inner product (2.9):

$C_{\beta}^{W}(t):=\big{(}\mathcal{O}|\mathcal{O}(t)\big{)}_{\beta}^{W}=C_{\beta}\left(t+\frac{i\beta}{2}\right)~{}.$
(2.97)

The argument in [85] proceeds as follows: If $C_{\beta}(t)$ is singular at
$t=0$, this implies immediately that $C_{\beta}^{W}(t)$ is singular at
$t=-\frac{i\beta}{2}$. This is sufficient to dictate the asymptotic behavior
of the moments $\mu_{2n}$ that leads to an asymptotically linear growth of the
Lanczos coefficients with slope $\alpha=\pi/\beta$, yielding an exponential
growth for K-complexity $C_{K}(t)\sim e^{2\alpha t}=e^{\frac{2\pi t}{\beta}}$.
In other words, the choice of the regularization scheme for the two-point
function automatically enforces exponential growth of Krylov complexity,
regardless of the details of the system. The authors of [85] compute
explicitly Lanczos coefficients242424In order to compute analytically the
Lanczos coefficients out of the moments in certain specific cases, the authors
of [85] use a connection, previously pointed out in [137], between the
recursion method defining the Lanczos coefficients and the recursion defining
integrable Toda hierarchies, for which there exist families of known
solutions. in two-dimensional CFT, as well as free and generalized free
theories [138] in $d$ spacetime dimensions, confirming their expectation. The
fact that for all these evidently non-chaotic systems the Lanczos coefficients
still feature linear growth because of the regularization scheme chosen for
the two-point function is presented in the article as a counterexample to the
universal operator growth hypothesis. Furthermore, given that in the case at
hand $\alpha=\pi/\beta$, the bound (2.95) reduces to the MSS bound (2.71).

This criticism can be addressed from various perspectives, which have led to
interesting avenues of research. Let us note some pertinent observations:

  * •

The slope of the Lanczos coefficients is dictated by the singularity of the
two-point function that is closest to the origin of the complex plane for $t$.
The fact that the Wightman regularization scheme imposes a singularity at
$t=-\frac{i\beta}{2}$ does not necessarily rule out the existence of other
system-specific singularities closer to the origin which would then dominate
the slope of the Lanczos coefficients. Nevertheless, the point that this
$\beta$-dependent singularity needs to be there regardless of the nature of
the system remains valid and is sufficient to ensure exponential growth of
Krylov complexity.

  * •

The conflictive singularity that appears to make K-complexity featureless (or,
in a sense, universal) in the context of field theory is a result of the inner
product choice. Hence, an immediate alternative that one may consider is to
choose a different scalar product. This approach was taken, in the context of
two-dimensional conformal field theory with a large central charge, by [139]:
The article proposes to take as an inner product the expectation value in a
primary state of the theory, that should be thought of as acting as a thermal
bath. With this, invoking the operator-state correspondence, the auto-
correlation function of a certain light operator becomes a four-point
function, carrying dynamical information. It is found in [139] that the
K-complexity of a light primary operator defined with this inner product
behaves either oscillatory or exponentially depending on whether the “thermal
bath” is generated by a light or a heavy primary, respectively. Heavy
primaries are those whose scaling dimension is above the black hole threshold,
$\Delta_{BH}=\frac{c}{12}$. It is in fact expected that the spectrum of the
CFT (and of its gravitational dual) is chaotic above such a threshold [82,
83], and hence this result illustrates that K-complexity is sensitive to
chaos252525In the article [139], the two-point function still needs to be
regulated in order to avoid singularities at $t=0$, but the authors show that
the regulator does not determine the asymptotic behavior of K-complexity..
Holographically, the dual interpretation of the black hole threshold in the
CFT2 spectrum is the Hawking-Page transition point in the AdS3 bulk [140]:
Above this point, the bulk features a black hole, which is expected to be a
chaotic system [84, 83, 82], while below it the emergent geometry
corresponding to the light states consists on empty AdS3 with a conical
defect. The fact that K-complexity is found to oscillate below the threshold
and to grow exponentially above it is consistent with the bulk picture.

  * •

Lastly, we may note that up to now all the results on K-complexity reviewed in
the current section have dealt with systems in the thermodynamic limit. Even
the formulation of the universal operator growth hypothesis is itself adapted
to infinite systems, since it addresses the asymptotic behavior of the Lanczos
coefficients $b_{n}$, hence implicitly assuming that the sequence does not
terminate. This leaves scope for the study of finite-size (and potentially
non-perturbative) effects in Krylov complexity, which may as well retain some
imprints of the chaotic or integrable nature of systems. Such imprints might
potentially cure the limitations of the universal operator growth hypothesis
pointed out previously, being invisible in the thermodynamic limit. Studying
(mostly numerically) the behavior of the Lanczos coefficients towards the edge
of the Krylov chain and the associated Krylov space dynamics that their
features imply was one of the main motivations of the projects [1, 2, 3],
together with the applicability of Krylov complexity to holography that will
be discussed in the next section, even though it has already been suggested in
this text.

#####  2.3.2 K-complexity and holography

As mentioned in the Introduction of this Thesis and at the beginning of the
present Chapter, it has been proposed that the growth of the Einstein-Rosen
bridge in a two-sided262626See [141] for a study of one-sided black holes
where the Tomita-Takesaki formalism allows for the partial reconstruction of
some “left side”, which probably does not asymptote to a left boundary because
of an unavoidable cutoff in space whose details are currently not well
understood. black hole should be captured by a notion of quantum complexity in
the boundary theory. To present day, such a proposal rests mostly on
conjectural grounds. The size of the wormhole throat, computed as the length
of space-like geodesics with anchoring points on opposite boundaries, or as
related quantities such as bulk volumes [65] or actions defined on a Wheeler-
DeWitt patch [66], follows a very specific profile as a function of time and,
most importantly, satisfies the so-called switchback effect, according to
which an initially small perturbation (a shock wave sent from the boundary)
disrupts the geometry exponentially fast, as we shall describe more precisely
below. The observation that quantum complexity, understood as circuit
complexity, follows a similar profile in time and is equally sensitive to
initially small perturbations led to the holographic complexity proposal,
which suffers from numerous ambiguities [74, 75] both on the boundary and on
the bulk side: On the boundary, extrinsic tolerance parameters and the choice
of sets of unitary gates or cost functions in the case of circuit complexity
make it unlikely to be an item of the holographic dictionary, since such
choices are not features of the theory; on the other hand, from the bulk
perspective, the authors of [74, 75] show that it is possible to build
families of observables defined in codimension-zero and one hypersurfaces
whose growth as a function of time in a black hole background is qualitatively
the same and controlled by the size of the wormhole throat.

Before moving on to analyzing why Krylov complexity is a good candidate to be
the complexity item in the holographic dictionary, let us give some further
details on the gravitational scenarios that one expects to capture via a
complexity computation on the boundary. This will allow to identify the
objects to focus on and the relevant time scales of the problem. In this
discussion we shall use as a guiding example the results in [64] on the length
of space-like geodesics in a BTZ black hole geometry in AdS3 [142].

Figure 2.1: Schematic depiction of the universal extension of a two-sided
black hole. Red lines represent the black hole and white hole singularities,
and the black diagonal lines are the black hole and white hole horizons.
Spacelike geodesics anchored at a regulated boundary at times $t_{R}=-t_{L}=t$
have been depicted in purple. The wormhole length is given by the length of
the portion of each geodesic contained behind the horizon, and it can be
measured by the difference between the geodesic length at time $t$ and the one
at $t=0$, since the latter features no wormhole at all.

The most immediate gravitational construction where one can study the growth
of the wormhole throat is that of an unperturbed two-sided black hole. Figure
2.1 depicts such a background, plus a family of space-like geodesics joining
the left and right boundaries272727In a specific computation, the anchoring
points of the geodesics should be placed on a regulated boundary, i.e. at some
finite distance in the radial direction, since otherwise the length would be
divergent. anchored at coincident times on the left and the right side. The
difference between the length at a time $t$ and that at time $t=0$ is
associated to the growth of the wormhole since, as one can see in the diagram,
there is a space-time region building up behind the horizon for $t>0$ that
cannot be accessed with the ordinary Schwarzschild coordinates. In [64] the
result for the geodesic length (upon subtracting constant terms so that it
vanishes at $t=0$) in the aforementioned BTZ background is:

$\frac{l(t)}{l_{AdS}}=2\log\left\\{\cosh\left(\frac{R}{l_{AdS}^{2}}t\right)\right\\}~{},$
(2.98)

where $l_{AdS}$ and $R$ denote the AdS length and the black hole horizon
radius, respectively. The horizon radius $R$ is related to the black hole’s
inverse temperature,

$R=\frac{2\pi l_{AdS}^{2}}{\beta}~{},$ (2.99)

and by inspection of (2.98) we note that $l(t)$ features early quadratic
growth before the thermal, or Rindler time [143],

$t_{\beta}:=\frac{\beta}{2\pi}~{},$ (2.100)

after which it exhibits linear growth. If we want to analyze the growth of the
ERB from the boundary perspective by computing the complexity of the
microstate dual to the emergent bulk geometry, we need to decide which time-
evolving state we should compute the complexity of. The state dual to the
$t=0$ slice depicted in Figure 2.1 is, as argued in [86], the thermofield
double state, which is a highly entangled state belonging to the tensor
product of the left and right Hilbert spaces and is equal to the purification
of the thermal density matrix:

$|TFD\rangle:=\frac{1}{\sqrt{Z(\beta)}}\sum_{n}e^{-\frac{\beta
E_{n}}{2}}\left(\mathcal{T}|E_{n}\rangle\right)\otimes|E_{n}\rangle~{},$
(2.101)

where $\left\\{E_{n}\right\\}$ denote the proper energies of the Hamiltonian
of a single side, and $\mathcal{T}$ stands for the time-reversal
operator282828The path-integral construction of the TFD state requires of an
anti-unitary operator in its definition, see for instance [86, 144]. It may be
taken to be some more generic operator, such as the CPT operator, but here for
simplicity we have chosen time reversal which, roughly speaking, enforces the
fact that asymptotic boundary times run differently in the left and right
boundaries, as depicted schematically in Figure 2.1.. Since the anchoring
points of a given geodesic run vertically upwards on both boundaries, i.e.
$t_{R}=-t_{L}=t$, the state whose complexity one should consider is the
evolution of the TFD state generated by both the left and right Hamiltonian,
with the same sign:

$|\Psi(t)\rangle=e^{-it(H_{L}+H_{R})}|TFD\rangle~{},$ (2.102)

where
$H_{L}\equiv\left(\mathcal{T}H\mathcal{T}^{\dagger}\right)\otimes\mathds{1}$
and $H_{R}\equiv\mathds{1}\otimes H$, the left and right spaces being
identical copies of each other292929By convention, all left operators are
constructed as the insertion in the left Hilbert space of time-reversed
versions of the “original” operators in the Hilbert space that has been
doubled in this two-sided construction. That is, for any operator
$\mathcal{A}\in\widehat{\mathcal{H}}$, we define
$\mathcal{A}_{L}:=\left(\mathcal{T}\mathcal{A}\mathcal{T}^{\dagger}\right)\otimes\mathds{1}$.
Importantly, the left time-evolution operator (which makes left time increase
downwards on the left side) satisfies
$U_{L}(t)=\left(\mathcal{T}U(t)\mathcal{T}^{\dagger}\right)\otimes\mathds{1}=\left(\mathcal{T}e^{-itH}\mathcal{T}^{\dagger}\right)\otimes\mathds{1}=e^{itH_{L}}$,
which explains why the relative plus sign in equation (2.102) is the correct
one for the protocol described in Figure 2.1, where both left and right times
are required to increase upwards..

Figure 2.2: Schematic depiction of a two-sided eternal black hole perturbed by
an almost null shock wave sourced at a point on the left (regulated) boundary
at time $t_{L}=t_{w}>0$ in the past. Its effect [64, 145, 146, 147] is to
produce a shift in the corresponding null coordinate. The resulting geometry
is not discontinuous [147]; rather, the diagram manifests a coordinate
singularity due to the gluing of different patches on the left and right of
the shock wave, which were adapted to the unperturbed geometry. Roughly
speaking, the effect of the shock wave is to “push” the singularity towards
the future for the spacetime on the right side of the shock. The purple line
represents a spacelike geodesic anchored on the left and right (regulated)
boundaries at $t_{L}=t_{R}=0$. In the absence of a shock wave, the $t=0$ slice
features no wormhole behind the horizon (see Figure 2.1), while the purple
geodesic in this case does have some non-vanishing portion behind it, as
illustrated in the diagram. Thus, the difference between the length of the
slice anchored at $t_{L}=t_{R}=0$ with a shock wave in the bulk, and that of
the $t=0$ slice in the unperturbed geometry, is a coordinate-invariant measure
of the growth of the wormhole length due exclusively to the shock wave, as a
function of the time $t_{w}$ at which it was sourced. See [64] for an explicit
computation in three-dimensional gravity, whose result is given in equation
(2.103).

A more interesting gravitational setup, which makes contact with operator
growth, is that of the switchback effect. Noting that in an unperturbed black
hole background the length of the Einstein-Rosen bridge behind the horizon is
zero at $t=0$, we consider a protocol in which the geometry of the $t=0$ slice
is disrupted by a shock wave sent from the left boundary at some time in the
past $t_{L}=t_{w}>0$ (we recall that the left time increases downwards, i.e.
towards the past): Always computing the length of the spacelike geodesic
anchored at $t_{L}=t_{R}=0$ on the boundaries as a function of the time
$t_{w}$ at which the shock wave was generated measures the growth of the
wormhole solely due to this perturbation. Figure 2.2 depicts the protocol. In
words, the manifestation of the switchback effect [77] is the fact that the
perturbation is essentially harmless for small values of $t_{w}$, until it
becomes disruptive, which is captured by an initial exponential behavior. Such
a behavior is indeed found in the AdS3 computation that we have been alluding
to throughout this discussion [64]:

$\frac{l(t_{w})}{l_{AdS}}=2\log\left\\{1+\frac{E}{8M}e^{\frac{R}{l_{AdS}^{2}}t_{w}}\right\\}~{},$
(2.103)

where $M$ is the black hole mass and $E$ is the shock wave energy. The
computation in [64] considered a spherically symmetric in-falling shell of
matter of energy $E$, whose trajectory is time-like: If $t_{w}$ is small
enough, the in-falling matter barely disrupts the geometry on the slice $t=0$,
but for $t_{w}$ sufficiently big, the blueshift of its proper energy when it
reaches the $t=0$ slice (as measured in the frame of the slice) is such that
the matter appears to follow an almost-null trajectory, for which the
backreaction on the metric can be computed using the AdS-Vaidya solution [145,
146, 147]. We now recall the relation between the horizon radius and the mass
$M$ of the BTZ black hole:

$R^{2}=8G_{N}Ml_{AdS}^{2}~{},$ (2.104)

where $G_{N}$ denotes Newton’s 3-dimensional constant. We also note the
expression for the Bekenstein entropy [69] of the black hole,

$S=\frac{A}{4G_{N}}~{},$ (2.105)

where $A$ is the horizon area, in this case given by $A=2\pi R$. With this
all, we can now re-express (2.103) changing the variables $(R,M)$ by the pair
$(S,\beta)$, as these will be the parameters controlling an eventual boundary
computation matching the bulk result. We have:

$\frac{l(t_{w})}{l_{AdS}^{2}}=2\log\left\\{1+\frac{E\beta}{4S}e^{\frac{2\pi}{\beta}t_{w}}\right\\}~{}.$
(2.106)

This expression features two different regimes in time, the transition between
them taking place around the scrambling time:

$t_{scr}:=\frac{\beta}{2\pi}\log\left\\{\frac{4S}{E\beta}\right\\}~{}.$
(2.107)

The most important feature of the scrambling time is its logarithmic growth
with the number of degrees of freedom, $S$; the denominator $E\beta$ is
specific to the setup considered, making the onset time $t_{scr}$ larger if
the energy of the in-falling quanta is small compared to the black hole
temperature, and vice-versa. Before scrambling, we have:

$\frac{l(t_{w})}{l_{AdS}}\approx\frac{E\beta}{2S}e^{\frac{2\pi}{\beta}t_{w}}~{},\qquad
t_{w}<t_{scr}~{},$ (2.108)

i.e. an exponential growth with an exponent that coincides with that of the
MSS bound (2.71). Well after scrambling, (2.106) behaves asymptotically
linearly in time:

$\frac{l(t_{w})}{l_{AdS}}\sim\frac{4\pi}{\beta}t_{w}+2\log\left(\frac{E\beta}{4S}\right)~{},\qquad
t\gg t_{scr}~{}.$ (2.109)

Because of the behavior of the exponential function, (2.108) does not become
relevant until times of order $t_{scr}$, justifying the common qualitative
description of the switchback effect, namely that the perturbation sent from
the past is not very disruptive if it was sent earlier than a scrambling time
in the past, effectively only kicking in if it is sent from a time in the past
well greater than $t_{scr}$.

The previous discussion highlights the profile in time and the relevant time
scales that one should expect from a boundary computation describing the
switchback effect. Let us now argue which is the state dual to the perturbed
geometry whose complexity should be computed in this scenario. The shock wave
in the bulk sent from the boundary can be seen [64, 77, 54, 59] as sourced by
an operator insertion $\mathcal{O}$ in the boundary theory at the
corresponding boundary time; thus, in order to prepare the microstate dual to
the backreacted $t=0$ slice depicted in Figure 2.2, we need to consider the
TFD state, dual to the unperturbed $t=0$ slice, evolve it to the past
$t_{L}=t_{w}$, insert the operator, and evolve forward back to $t_{L}=0$. That
is:

$|\Psi(t_{w})\rangle=e^{-it_{w}H_{L}}\mathcal{O}_{L}e^{it_{w}H_{L}}|TFD\rangle=\mathcal{O}_{L}(t_{w})|TFD\rangle~{},$
(2.110)

where
$\mathcal{O}_{L}=\left(\mathcal{T}\mathcal{O}\mathcal{T}^{\dagger}\right)\otimes\mathds{1}$
is the one-sided operator inserted in the left copy of the Hilbert space. We
recall that $e^{it_{w}H_{L}}$ evolves the left side to the past time
$t_{L}=t_{w}$, and therefore $\mathcal{O}_{L}(t_{w})$ is correctly in the past
if $t_{w}>0$. Any evolution involving the right Hamiltonian $H_{R}$ would
commute with $\mathcal{O}_{L}$ and be eventually cancelled out by the
subsequent reversed evolution, so it has been directly omitted in (2.110).
Furthermore, noting that $|TFD\rangle$ is annihilated by the Hamiltonian
$H_{L}-H_{R}$, being therefore stationary under the time evolution it
generates, we can see $|\Psi(t_{w})\rangle$ as a state that evolves regularly
in the Schrödinger picture with such a choice of total Hamiltonian:

$\begin{split}&e^{-it_{w}(H_{L}-H_{R})}|\Psi(0)\rangle=e^{-it_{w}(H_{L}-H_{R})}\mathcal{O}_{L}|TFD\rangle\\\
&=e^{-it_{w}(H_{L}-H_{R})}\mathcal{O}_{L}e^{it_{w}(H_{L}-H_{R})}|TFD\rangle=e^{-it_{w}H_{L}}\mathcal{O}_{L}e^{it_{w}H_{L}}|TFD\rangle=|\Psi(t_{w})\rangle~{},\end{split}$
(2.111)

where in the second equality we have inserted a time evolution operator at
will between the operator and the TFD state, using the fact that the latter is
stationary, and in the third equality we have used that
$[\mathcal{O}_{L},H_{R}]=0$. Equation (2.111) allows to give yet another
interpretation to the switchback effect: The state $|TFD\rangle$ was
originally stationary under the evolution generated by $H_{L}-H_{R}$;
perturbing it with a localized operator insertion and then letting it evolve
yields a state that remains being approximately stationary until times of
order of $t_{scr}$, after which the perturbation is seen to be disruptive in
the emergent bulk geometry of the microstate.

Summarizing, the switchback effect may be probed by computing the (state)
complexity of the TFD state with the insertion of the time-evolved operator
$\mathcal{O}_{L}(t_{w})$, and a good candidate of holographic complexity
should be expected to exhibit the profile in time described above, namely
exponential growth before the scrambling time, logarithmic in the entropy,
followed by a period of linear growth. If the candidate complexity is Krylov
complexity, the state complexity of (2.110) makes direct connection with
operator complexity, as we shall argue now. We showed in section 2.1.2 that
the Lanczos coefficients (and hence, K-complexity) are entirely determined
from the survival amplitude of the state. Using the definition of the TFD
state (2.101) and the fact that the operator $\mathcal{O}_{L}(t_{w})$ only has
support on the left copy of the Hilbert space, it is possible to show that the
survival amplitude of (2.110) is related to the operator two-point function
via

$S(t_{w})=\langle\Psi(0)|\Psi(t_{w})\rangle=\frac{1}{Z(\beta)}\text{Tr}\left[e^{-\beta
H}\mathcal{O}^{\dagger}\mathcal{O}(-t_{w})\right]=C_{\beta}(-t_{w})=C^{*}_{\beta}(t_{w})~{},$
(2.112)

where we note that the trace is over a single copy of the Hilbert space. That
is, the survival amplitude equals the (conventional) thermal two-point
function of the operator, whose moments, in turn, determine uniquely the
operator’s K-complexity as detailed in section 2.1.1. In particular, the
Taylor expansion of the conventional thermal operator two-point function is
given by

$C_{\beta}(t)=\sum_{n=0}^{+\infty}\frac{(it)^{n}}{n!}\mu_{n}~{},\qquad\mu_{n}=\left(\mathcal{O}\left|\mathcal{L}^{n}\right|\mathcal{O}\right)_{\beta}~{},$
(2.113)

potentially admitting non-zero odd moments (which in turn imply potentially
non-vanishing $a_{n}$ Lanczos coefficients), while the Taylor series of the
state survival amplitude is written in (2.39), where the moments should be
understood in the present context as:

$M_{n}=\Big{\langle}\Psi(0)\Big{|}{\big{(}H_{L}-H_{R}\big{)}}^{n}\Big{|}\Psi(0)\Big{\rangle}~{}.$
(2.114)

Expression (2.113) differs from (2.39) in a sign due to the difference between
the Heisenberg and Schrödinger representations. Such a sign is precisely
compensated by the minus sign in the argument of $C_{\beta}(-t_{w})$ appearing
in (2.112), allowing to conclude that the state moments of
$|\Psi(t_{w})\rangle$, $M_{n}$, are exactly equal to the operator moments of
$\mathcal{O}(t_{w})$, $\mu_{n}$, therefore yielding coincident Lanczos
coefficients after plugging such quantities as an input for the recursion
method (cf. section 1.9.2). Using these Lanczos coefficients to implement the
recursion (2.35) for the Krylov space wave function associated to the state
$|\Psi(t_{w})\rangle$, one will find that it differs from the corresponding
recursion of the operator wave function with the same Lanczos coefficients by
a minus sign on the left-hand side, again side due to the fact that
$|\Psi(t_{w})\rangle$ and $\mathcal{O}(t_{w})$ evolve in the Schrödinger and
in the Heisenberg picture, respectively, implying that the state wave function
equals the complex conjugate of the operator wave function. Finally, recalling
(2.40) and (2.41), one concludes that the Krylov complexities of both objects
coincide. Summarizing, the K-complexity of the perturbed state
$|\Psi(t_{w})\rangle$ given in (2.110) is equal to the operator K-complexity
of $\mathcal{O}(t_{w})$: The switchback effect is directly probed by operator
K-complexity. Let us now present an alternative proof of this fact by
constructing explicitly the Krylov basis for $|\Psi(t_{w})\rangle$,
$\left\\{|K_{n}\rangle\right\\}_{n=0}^{K-1}$ out of the one associated to
$\mathcal{O}(t_{w})$, $\left\\{\mathcal{O}_{n}\right\\}_{n=0}^{K-1}$. We
propose the identification:

$|K_{n}\rangle=\mathcal{O}_{n,L}|TFD\rangle=\frac{1}{\sqrt{Z(\beta)}}\sum_{a,b=0}^{D-1}e^{-\frac{\beta
E_{b}}{2}}\left(\mathcal{O}_{n}\right)_{ab}^{*}\left(\mathcal{T}|E_{a}\rangle\right)\otimes|E_{b}\rangle~{},$
(2.115)

where
$\mathcal{O}_{n,L}=\left(\mathcal{T}\mathcal{O}_{n}\mathcal{T}^{\dagger}\right)\otimes\mathds{1}$
and $\left(\mathcal{O}_{n}\right)_{ab}$ are the matrix elements of the
operator $\mathcal{O}$ in the eigenbasis of the one-sided Hamiltonian $H$. One
can prove inductively that the elements $|K_{n}\rangle$ satisfy the Lanczos
recursion for states (2.32), with the Hamiltonian $H_{L}-H_{R}$ and the
standard inner product in the Hilbert space of states, given that the
$\mathcal{O}_{n}$ satisfy the Lanczos recursion for operators, with the
Liouvillian $\mathcal{L}\equiv[H,\cdot]$ defined on a single copy of the
Hilbert space and given the conventional thermal inner product (2.7). Since
the conventional thermal inner product is a representative of the family
(2.10) for which the $g(\tau)$ function is not even in the thermal circle, the
Lanczos recursion for operators (2.11) in this case needs to be supplemented
with $a$-coefficients, which do not vanish in general for $\beta>0$. The only
non-trivial step in the proof mapping the Lanczos recursion for
$|K_{n}\rangle$ to that of $\mathcal{O}_{n}$ is turning the action of the
total Hamiltonian on $|K_{n}\rangle$ into the action of the Liouvillian (i.e.
the commutator) on $\mathcal{O}_{n}$, which can be done, again, using the fact
that the TFD state is annihilated by $H_{L}-H_{R}$:

$\begin{split}&(H_{L}-H_{R})|K_{n}\rangle=(H_{L}-H_{R})\mathcal{O}_{n,L}|TFD\rangle\\\
&=(H_{L}-H_{R})\mathcal{O}_{n,L}|TFD\rangle-\mathcal{O}_{n,L}(H_{L}-H_{R})|TFD\rangle\\\
&=[H_{L},\mathcal{O}_{n,L}]|TFD\rangle-[H_{R},\mathcal{O}_{n,L}]|TFD\rangle=[H_{L},\mathcal{O}_{n,L}]|TFD\rangle~{}.\end{split}$
(2.116)

With this, we have that, given the $a_{n}$ and $b_{n}$ coefficients of the
operator $\mathcal{O}$,

$\begin{split}&(H_{L}-H_{R}-a_{n})|K_{n}\rangle-b_{n}|K_{n-1}\rangle\\\
&=\Big{\\{}[H_{L},\mathcal{O}_{n,L}]-a_{n}\mathcal{O}_{n,L}-b_{n}\mathcal{O}_{n-1,L}\Big{\\}}|TFD\rangle\\\
&=b_{n+1}\mathcal{O}_{n+1,L}|TFD\rangle=b_{n+1}|K_{n+1}\rangle~{},\end{split}$
(2.117)

proving that the states (2.115) do satisfy the Lanczos recursion with the
Hamiltonian $H_{L}-H_{R}$, thus correctly being the Krylov elements of
$|\Psi(t_{w})\rangle$. Furthermore, the states $|K_{n}\rangle$ turn out to
form correctly an orthonormal set provided that the elements $\mathcal{O}_{n}$
form such a set according to the conventional thermal inner product (2.7),
thanks to the structure of the TFD state, reflected in the square root of the
Boltzmann factor entering in (2.115). We may even express the Krylov space
wave function of $|\Psi(t_{w})\rangle$,

$\phi_{n}^{(\Psi)}(t_{w}):=\langle K_{n}|\Psi(t_{w})\rangle~{},$ (2.118)

in terms of that of $\mathcal{O}(t_{w})$,

$\phi_{n}^{(\mathcal{O})}(t_{w}):=\big{(}\mathcal{O}_{n}\big{|}\mathcal{O}(t_{w})\big{)}_{\beta}=\frac{1}{Z(\beta)}\text{Tr}\left[e^{-\beta
H}\mathcal{O}_{n}^{\dagger}\mathcal{O}(t_{w})\right]~{},$ (2.119)

where we stress once again that the trace runs over a single copy of the
Hilbert space. It is worth to note that, in this case, since the operator’s
$a$-coefficients do not necessarily vanish, its Krylov elements need not have
alternating hermiticity properties and a definition of the wave function like
the one in (2.12), where a factor of $i^{n}$ is pulled out, will not be useful
as it will generically not make it become a real-valued function. We consider
the expansion of the time-evolved operator in terms of its Krylov space wave
function,

$\mathcal{O}(t_{w})=\sum_{n=0}^{K-1}\phi_{n}^{(\mathcal{O})}(t_{w})~{}\mathcal{O}_{n}~{}.$
(2.120)

Plugging (2.120) into (2.110) and recalling (2.115) we obtain:

$|\Psi(t_{w})\rangle=\sum_{n=0}^{K-1}\left[\phi_{n}^{(\mathcal{O})}(t_{w})\right]^{*}|K_{n}\rangle~{},$
(2.121)

where the complex conjugation arises as a consequence of the anti-linearity of
the time-reversal operator. Finally, combining (2.121) with the definition
(2.118) yields

$\phi_{n}^{(\Psi)}(t_{w})=\left[\phi_{n}^{(\mathcal{O})}(t_{w})\right]^{*}=\phi_{n}^{(\mathcal{O})}(-t_{w})$
(2.122)

and, in agreement with the discussion around (2.40) and (2.41), this
establishes explicitly that the operator’s K-complexity,
$C_{K}^{(\mathcal{O})}(t_{w})$, and the state’s one, $C_{K}^{(\Psi)}(t_{w})$,
are identical:

$C_{K}^{(\Psi)}(t_{w})=\sum_{n=0}^{K-1}n~{}{\lvert\phi_{n}^{(\Psi)}(t_{w})\rvert}^{2}=\sum_{n=0}^{K-1}n~{}{\lvert\phi_{n}^{(\mathcal{O})}(t_{w})\rvert}^{2}=C_{K}^{(\mathcal{O})}(t_{w})~{}.$
(2.123)

It is worth to stress that the Krylov space dimensions are equal. One is the
dimension of a Krylov subspace of the operator space $\widehat{\mathcal{H}}$
of a single copy of the Hilbert space, whose dimension is
$\dim(\widehat{\mathcal{H}})=D^{2}$, while the other is the dimension of a
Krylov subspace contained in the tensor product of two copies of the Hilbert
space of states, to which the state $|\Psi(t_{w})\rangle$ belongs, and whose
dimension is also $\dim\left(\mathcal{H}\otimes\mathcal{H}\right)=D^{2}$.
Hence, the equality of the Krylov space dimensions is not inconsistent.
Furthermore, since the Hamiltonian generating the evolution of
$|\Psi(t_{w})\rangle$ is $H_{L}-H_{R}$, its Krylov dimension is subject to the
same upper bound as the operator’s Krylov dimension, written in (2.5). In
order to understand this, one needs to refer to the details of the proof of
such a bound, which appeared in contribution [1] and is contained in Chapter
3, but the main reason is the fact that the zero eigenvalue is $D$-times
degenerate in the spectra of both the two-sided Hamiltonian $H_{L}-H_{R}$ and
the single-sided Liouvillian $\mathcal{L}\equiv[H,\cdot]$, regardless of the
specific features of the physical system at hand.

We have established rigorously that the Krylov complexity of a time-evolving
operator in the Heisenberg picture gives the complexity of the perturbed state
(2.110) discussed in the context of the switchback effect, a proof that had
not appeared in the literature so far. In order to argue whether K-complexity
is suitable for holographic applications, it is left to discuss whether the
profile of such an operator complexity as a function of time can be expected
to display the profile featured by the gravitational result (2.106) described
previously, matching the relevant time scales. This was the goal of [109], the
first article that pointed out the potential relevance of Krylov complexity in
gravity, whose main results we shall discuss now.

The aforementioned article [109] is conceived as a follow-up to the one in
which K-complexity was introduced [78]. The latter, where the universal
operator growth hypothesis and the Q-theorem were presented, focuses on
systems in the thermodynamic limit, where the number of degrees of freedom $S$
is infinite. For such infinite and chaotic systems, it was found that
K-complexity grows exponentially in time, which so far is not in contradiction
with gravitational expectations: In the large-$S$ limit, the scrambling time
gets pushed towards infinity and only early-time dynamics, expected to be
exponential in gravity as illustrated in (2.108), are accessible. In order to
assess whether operator Krylov complexity also features a linear growth phase
in chaotic systems, it is necessary to consider finite-size systems and to
study their post-scrambling dynamics. For this purpose, the starting point of
[109] is to consider a typical operator in a chaotic system, expected to
satisfy the eigenstate thermalization hypothesis (ETH) [117, 118, 119, 120,
121], which is the following Ansatz for the operator matrix elements in the
energy basis:

$\langle
E_{m}|\mathcal{O}|E_{n}\rangle=O(\varepsilon)\delta_{mn}+e^{-\frac{S(\varepsilon)}{2}}f(\varepsilon,\omega)r_{mn}~{},$
(2.124)

where for notational simplicity we have written
$\varepsilon\equiv\frac{E_{m}+E_{n}}{2}$ and $\omega\equiv E_{m}-E_{n}$.
$S(\varepsilon)$ denotes the microcanonical entropy, whose exponential is
proportional to the density of states in a given energy shell. In this
hypothesis, $O(\varepsilon)$ and $f(\varepsilon,\omega)$ are smooth functions
of their arguments and $r_{mn}$ are independent (modulo hermiticity
constraints) and identically distributed complex Gaussian random variables
with zero mean and unit variance.

The ETH ensures [119, 121] that, at sufficiently late times, the expectation
value of the observable measured in a pure microstate within an energy shell
is indistinguishable, up to terms suppressed by powers of
$e^{-S(\varepsilon)}$, from the microcanonical expectation value in the same
shell303030The hypothesis itself is not specific about the time scale after
which both expectation values become similar, as this depends on the
particular dynamical information of the system.. It is therefore a mechanism
for thermalization of typical operators in chaotic systems. In random matrix
theory [121, 124] it is possible to derive an Ansatz for operator matrix
elements similar to (2.124) but without energy dependence in the functions
$S$, $O$ and $f$; intuitively, this behavior of the matrix elements can be
understood as a manifestation of the lack of correlation between the
eigenbases of the Hamiltonian and of the operator. One can therefore
understand the ETH Ansatz as a generalization of the RMT operator Ansatz which
amounts to assuming that, within each energy shell, the system effectively
behaves like a random matrix theory and, in this sense, this notion of
thermalization is connected to spectral chaos. The non-trivial content of the
hypothesis is the Gaussian distribution for the $r_{mn}$ variables313131See
[148] for an analysis of an integrable, non-thermalizing system in which some
operators appear to satisfy an ETH-like Ansatz, with the caveat that the
distribution of the off-diagonal matrix elements is not Gaussian., together
with the suppression of the off-diagonal matrix elements and the fact that the
functions $O(\varepsilon)$ and $f(\varepsilon,\omega)$ are continuous and,
roughly speaking, smooth323232When the ETH Ansatz applies, $O(\varepsilon)$
and $f(\varepsilon,\omega)$ give, respectively, the microcanonical one- and
two-point functions of the operator. For non-Gaussian corrections to the
hypothesis that give access to higher n-point functions, see the recent work
[149]..

The strategy of [109] is to compute two different regimes of the moments
$\mu_{2n}$ for ETH operators and use them to identify the corresponding
regimes in the Lanczos coefficients, by the means of the following inequality:

$\prod_{m=1}^{n}b_{m}^{2}\leq\mu_{2n}\leq C_{n}\prod_{m=1}^{n}b_{m}^{2}~{},$
(2.125)

which is derived through the connection between moments and Lanczos
coefficients involving Dyck paths, reviewed in section 1.9.1. The lower bound
is one of the many Dyck paths contributing to $\mu_{2n}$, as each contribution
is always positive; in particular, it is the path with $n$ consecutive up
steps followed by $n$ consecutive descending steps. The upper bound assumes a
non-decreasing Lanczos sequence, such that the contribution of all individual
paths is smaller or equal than that of the aforementioned path; we recall that
the Catalan number $C_{n}$, given in (1.190), is the total number of Dyck
paths of length $2n$. If the assumption of a non-decreasing sequence cannot be
made, a different upper bound, used in [78], still applies:

$\mu_{2n}\leq
C_{n}\big{(}\max\left\\{b_{m}\right\\}_{m=1}^{n}\big{)}^{2n}~{}.$ (2.126)

In the thermodynamic limit, given the exponentially decaying spectral function
(2.91) expected in a maximally chaotic system,

$\Phi(\omega)=e^{-\frac{\pi|\omega|}{2\alpha}}~{},$ (2.127)

the moments $\mu_{2n}$ can be obtained via (2.24), which yields

$\mu_{2n}={\left(\frac{2\alpha}{\pi}\right)}^{2n}(2n)!~{}.$ (2.128)

Assuming an asymptotically linear growth of the Lanczos coefficients,
$b_{n}\sim\alpha n$, and plugging it into (2.125), one finds that both the
upper and the lower bound display the same asymptotic behavior at large-$n$,
equal to that of (2.128), so the Ansatz is consistent. This is the original
argument with which [78] arrived at the universal operator growth hypothesis.
In order to improve on this result for finite-size systems, the authors of
[109] note that finite systems must necessarily have a spectral function of
bounded support, since the spectrum of the system has a finite band width,
which we shall assume to be generically extensive in system size,
$E_{\text{max}}-E_{\text{min}}\sim\Lambda S$, where $\Lambda$ is some
intensive constant with energy dimensions. This, in turn, implies [20] that
the Lanczos coefficients asymptote to a constant $b_{\infty}$. There should
therefore exist some $S$-dependent transition value $n_{*}$ at which the
$b_{n}$ sequence transitions from initial linear growth to a plateau regime.
In order order to identify $n_{*}$, we begin by noting that the integral
(2.24) over the real line should be replaced by one over the interval
$[-\Lambda S,\Lambda S]$, which is the domain of the energy differences in the
spectrum:

$\mu_{2n}=\frac{1}{2\pi}\int_{-\Lambda S}^{\Lambda
S}d\omega~{}\omega^{2n}~{}\Phi(\omega)~{}.$ (2.129)

Assuming the behavior (2.127) for the spectral function, a saddle-point
approximation shows that the main contribution to the integral in (2.129)
comes from $\omega\sim\frac{4n\alpha}{\pi}$. Given that $\alpha$ has
dimensions of energy, just like the Lanczos coefficients, and that it is
intensive (since it remains finite in the thermodynamic limit), we shall pose,
for the sake of this approximate argument, that $\alpha\sim\Lambda$. Hence,
when $n\gg S$ we have that the saddle point sits outside of the integration
domain, and there is no obvious contour deformation that would justify
approximating the integral (2.129) by evaluating its integrand on the saddle
point. Therefore, we have identified the transition value $n_{*}\sim S$, such
that for $n>n_{*}$ one needs to compute the moments $\mu_{2n}$ out of their
discrete spectral resolution. Given the infinite-temperature inner product
(2.6), which is assumed throughout in this argument, the exact expression for
the moments (2.19) is:

$\mu_{2n}=\frac{1}{D}\sum_{a,b=0}^{D-1}\omega_{ab}^{2n}|O_{ab}|^{2}~{},$
(2.130)

where $\omega_{ab}\equiv E_{a}-E_{b}$ and $O_{ab}\equiv\langle
E_{a}|\mathcal{O}|E_{b}\rangle$. For $n>0$, which is implied by $n>n_{*}$,
only off-diagonal matrix elements contribute, which can be taken from the ETH
estimate (2.124):

$\mu_{2n}\sim\frac{1}{D^{2}}\sum_{a,b}\omega_{ab}^{2n}f^{2}(\varepsilon,\omega)~{},$
(2.131)

where the entropic suppression $e^{-S(\varepsilon)}$ has been loosely factored
out of the sum as $D^{-1}$ and the random variables $|r_{mn}|^{2}$ inside the
sum have been replaced by their average, equal to one. Accepting that the main
contributions to the sum (2.131) come from the largest energy differences, and
recalling that $f(\varepsilon,\omega)$ is a smoothly varying function in the
ETH Ansatz, one may approximate [109] the result by the average of the power
of energy differences $\omega^{2n}$ across the band $[-\Lambda S,\Lambda S]$,
ignoring the details of $f(\varepsilon,\omega)$. This yields a new asymptotic
behavior for the moments,

$\mu_{2n}\sim\frac{{(\Lambda S)}^{2n}}{2n}~{},$ (2.132)

which, when plugged into (2.125), is compatible [109] with an asymptotic
plateau in the Lanczos coefficients, $b_{n}\sim\Lambda S\equiv b_{\infty}$.
All in all, [109] predicts the following profile for the Lanczos sequence in
systems with finite (but large) entropy $S$:

$b_{n}\sim\left\\{\begin{aligned} \alpha n~{},\qquad n\lesssim S~{},\\\
b_{\infty}~{},\qquad n\gg S~{}.\end{aligned}\right.$ (2.133)

We note that, in our order-of-magnitude estimate, $b_{\infty}\sim\Lambda S$
but also $\alpha\sim\Lambda$, and therefore one may pose $b_{\infty}\sim\alpha
S$ [109].

The profile (2.133) has interesting implications for Krylov complexity. A
continuous approximation to the dynamics of the operator wave function in
Krylov space, proposed in [109] and discussed in detail in Appendix D.4,
results in the ballistic propagation of a point particle through a velocity
field $v(n)\equiv 2b_{n}$. Since the particle starts at position $n=0$, it
begins probing the regime of linearly increasing Lanczos coefficients, which
results in an exponential increase of its position as a function of time,
captured by K-complexity: $C_{K}(t)\approx n(t)\sim e^{\lambda_{K}t}$, where
we have defined $\lambda_{K}:=2\alpha$ for convenience. Note that this
retrieves the result for infinite systems discussed in section 2.3.1. The
particle will reach the region of constant Lanczos coefficients, $n>n_{*}\sim
S$, at a time $t_{*}$ such that $C_{K}(t_{*})\sim n_{*}$, which satisfactorily
gives a scrambling time scale:

$t_{*}\sim\frac{1}{\lambda_{K}}\log S~{}.$ (2.134)

For times larger than $t_{*}$ the particle propagates through a region of
constant velocity field, $v(n)=2b_{\infty}\sim 2\alpha S=\lambda_{K}S$,
implying a linear increase in K-complexity, $C_{K}(t)\sim\lambda_{K}St$ at
late times.

Summarizing, the expected K-complexity profile for typical operators
satisfying the ETH Ansatz in maximally chaotic systems is predicted by [109]
to be:

$C_{K}(t)\sim\left\\{\begin{aligned} e^{\lambda_{K}t}~{},\qquad t\lesssim
t_{*}~{},\\\ \lambda_{K}St~{},\qquad t\gg t_{*}~{},\end{aligned}\right.$
(2.135)

where $\lambda_{K}=2\alpha$, the K-complexity exponent that bounds the
Lyapunov exponent in (2.94), and $t_{*}=\frac{1}{\lambda_{K}}\log S$ is a
scrambling time scale. In view of this result, the fact that operator Krylov
complexity exhibits a transition from exponential to linear growth at the
scrambling time led the authors of [109] to propose that it is indeed a good
candidate for holographic complexity, which adds up to the considerations
discussed earlier in this text on its potential suitability to describe the
switchback effect.

The results on post-scrambling K-complexity dynamics that have just been
reviewed are, nevertheless, incomplete to some extent: They predict an
asymptotic behavior for the Lanczos coefficients at large $n$, given by a
plateau, and a Krylov complexity profile that grows linearly for an indefinite
amount of time after scrambling. However, for a finite system, where
$S<\infty$, the Hilbert space must be finite-dimensional, just like the Krylov
dimension. Therefore, the $b_{n}$ sequence should terminate at some point,
when $n=K\sim D^{2}\sim e^{2S}$ if the Krylov dimension bound (2.5) is
saturated, and consequently Krylov complexity should not grow linearly
indefinitely after the scrambling time, but should eventually saturate. By
definition of $t_{*}$, $C_{K}(t_{*})\sim S$ and, since the ulterior growth is
linear, K-complexity will reach the maximal value $C_{K}(t_{K})\sim e^{2S}$ at
a time scale of order

$t_{K}\sim\frac{1}{\lambda_{K}S}e^{2S}~{},$ (2.136)

an exponentially large time scale known as the Heisenberg time [150, 151]. For
times greater than the Heisenberg time, K-complexity should saturate, but the
mechanism for such a saturation is not evident from the argument that has been
presented, requiring further analysis. From the gravity perspective, one
should also expect an eventual saturation of the expectation value of the ERB
length: Considering the Bekenstein-Hawking entropy
$S_{\text{BH}}=\frac{A}{4G_{N}}$, the sector of the gravity Hilbert space
relevant to the black hole microstates has a finite dimension. During its time
evolution, the microstate describing the bulk geometry explores successive
orthogonal states in the Hilbert space, whose emergent geometry features
increasingly larger wormhole lengths [143], until eventually all linearly
independent states have been explored by the Heisenberg time scale333333The
argument for claiming that all independent gravity microstates should have
been explored by the Heisenberg time relies on the assumption that orthogonal
states are probed at a constant rate [143]., after which the microstate
explores nothing but linear recombinations of states previously visited, and
hence the length expectation value saturates rather than growing further. This
is the regime in which the geometrical description of gravity ceases to apply,
and therefore such a behavior cannot be retrieved from a classical
computation. Eventually, K-complexity should undergo a Poincaré recurrence at
times of order $t_{P}\sim\exp\left(e^{S}\right)$, going back arbitrarily close
to its initial values [150].

Probing the saturation mechanism of K-complexity in finite systems, together
with the analysis of the imprints of quantum chaos or integrability in finite-
size effects of Krylov space dynamics, was the main motivation behind the
contributions [1, 2, 3], which will be presented in Chapters 3 and 4.

Finally, it is worth to close this section noting that K-complexity is also a
useful candidate for the holographic protocol depicted in Figure 2.1, i.e. the
study of the growth of the wormhole length in the unperturbed geometry. As
argued around (2.102), the relevant state to be analyzed in this case is the
time evolution of the TFD state generated by the two-sided Hamiltonian under
which it is not stationary, $H_{R}+H_{L}$. In [79] it was shown that the
survival amplitude associated to such a state is given by the analytic
continuation of the thermal partition function,

$S(t)=\langle
TFD|e^{-it(H_{R}+H_{L})}|TFD\rangle=\frac{Z(\beta+2it)}{Z(\beta)}~{},$ (2.137)

the associated probability being:

${|S(t)|}^{2}=\frac{Z(\beta+2it)Z(\beta-2it)}{Z(\beta)^{2}}~{},$ (2.138)

which is nothing but the spectral form factor (SFF) [116, 122], a well studied
object in the context of quantum chaos. For chaotic systems, the SFF is known
to decay towards a plateau, whose value is suppressed by the Hilbert space
dimension (i.e. exponentially suppressed in the number of degrees of freedom)
at times exponentially large in $S$, preceded or not by a linear ramp
depending on the universality class of the system. This structure of the SFF,
together with the constraint of unitarity, allows the authors of [79] to
associate qualitatively some features of K-complexity to the SFF, as follows:
Since the modulus squared of the zeroth component of the Krylov wave function
entering in the computation of $C_{K}(t)$ in (2.37) coincides precisely with
the survival probability (2.138), $|\phi_{0}(t)|^{2}=|S(t)|^{2}$, unitarity of
time evolution imposes, through (2.36), that the probabilities
$|\phi_{n}(t)|^{2}$ with $n>0$ will not be allowed to grow significantly
before the SFF has effectively decayed towards its plateau value at
exponentially late times or, rather, that they gradually build up as the SFF
progressively decays. With this, one could expect a progressive growth of
state K-complexity for the state $|\Psi(t)\rangle$ in 2.102 up to time scales
exponentially large in $S$, after which it should saturate. This proposal is
backed up by some numerical checks in random matrix theory [79]. However, the
absence of universal results about the early-time features of the spectral
form factor do not allow, from this perspective, to evaluate whether the state
complexity profile in this case will be qualitatively similar to the gravity
computation (2.98).

The last contribution of this Thesis [4], gathered in Chapter 5, considers the
state complexity of the TFD state in the double-scaled SYK model [98, 99], a
system that has been shown to be dual to two-dimensional JT gravity [96, 97].
The article presents the first explicit proof of the correspondence between
Krylov complexity in the boundary theory and length expectation value in the
bulk theory, by using the map between the Hilbert spaces of both dual theories
to establish a correspondence between the K-complexity eigenstates and the
bulk length operator eigenstates.

####  2.4 Research on Krylov complexity

This section collects the main lines of research currently open in the area of
Krylov complexity, together with relevant references. Inevitably, the
compilation will be biased towards topics of interest in the high-energy
theory community343434This section contains references of works that appeared
before January 1st, 2024, the date on which this Thesis was submitted for
evaluation to the University of Geneva..

  * •

K-complexity as a probe of chaos and integrability: [78, 109, 85, 125, 152,
153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165], as well as
[1, 2, 3].

  * •

Localization on the Krylov chain: [2, 3], as well as [166].

  * •

Exact (numerical) results for the Lanczos algorithm: [167, 166, 168, 169, 170,
171, 172, 152, 153, 173, 155, 174, 175, 158, 162] and [1, 2, 3].

  * •

Krylov complexity in QFT and CFT: [85, 176, 125, 177, 178, 139].

  * •

Analytical tools to study K-complexity, e.g. orthogonal polynomials [179],
integrable structures [137], renormalization-group techniques [180] and
geometrical interpretation [181, 182, 183, 184].

  * •

Holography and bulk dual of K-complexity: [4, 167, 185, 180, 125].

  * •

Quantum speed limits: [186, 187, 188, 189, 190, 191, 192].

  * •

State Krylov complexity: [79, 193, 194, 168, 169, 195, 196].

  * •

Krylov complexity and topological phases of matter: [197, 198].

  * •

K-complexity in symmetry-dominated systems, generalized coherent states: [181,
199, 79, 200, 201].

  * •

K-complexity in systems with saddle-dominated scrambling: [202, 203].

  * •

Open and driven systems: [170, 171, 173, 174, 175, 204].

  * •

K-complexity and quantum scars: [169, 205].

  * •

K-complexity in tensor networks: [172].

##  Part II Contributions

### 3 Exact results on a chaotic model: SYK

This Chapter contains, up to minor editorial modifications, a reproduction of
the publication [1], where the full sequence of Lanczos coefficients of a
typical operator in a chaotic and finite (yet large) many-body system (the
complex SYK4 model) was computed numerically for the first time, a task for
which both the Full Orthogonalization and Partial Re-Orthogonalization
algorithms discussed in section 1.10 needed to be implemented in high-
performance computing clusters. The plateau in the Lanczos sequence (2.133)
predicted by [109] was found to receive a non-perturbative correction given by
a slow descent of the Lanczos coefficients $b_{n}$ towards zero, eventually
consistent with the finite dimensionality of Krylov space. The K-complexity
profile associated to this sequence was satisfactorily found in numerical
computations to transition from early exponential growth to linear growth
after the scrambling time, and it furthermore depicted K-complexity saturation
at times exponentially large in the number of degrees of freedom (in this
case, the number of fermions). Along the way, the algebraic structure of
Krylov space was explored, in developments which are at the seed of the
analyses given in Chapter 1, and an upper bound on the operator Krylov space
dimension was proved. The main technical achievement of this project was the
successful implementation of the Lanczos algorithm for systems with Krylov
spaces of dimension up to $K=63~{}253$.

####  3.1 Introduction

The concepts of state and operator complexity lie at the intersection of
quantum information, condensed matter physics, quantum field theory (QFT) and
black hole physics. One is thus faced with a diversity of concepts and methods
on how to precisely define and actually measure complexity. The identification
of very large time scales in black hole physics and corresponding phenomena in
QFT (via the AdS/CFT correspondence) [86, 150, 206, 65, 70, 151, 207, 208] has
motivated the search for a form of complexity whose time dependence has the
following distinctive characteristics: In fast-scrambling systems with finite
entropy $S$, complexity should grow exponentially in time until
$t_{s}\sim\log(S)$ (known as the scrambling time) when it reaches a value of
order ${\cal O}(S)$; it then switches to a linear-in-time behavior until times
of order $\exp({\cal O}(S))$ when it settles around a plateau of order
$\exp({\cal O}(S))$; finally, after times of order $\exp(\exp({\cal O}(S)))$
it is expected to start performing the Poincaré dance. The growth of the
Einstein-Rosen bridge was connected in [65] with complexity growth of the
quantum state in the dual CFT. A notion of complexity known as Krylov
complexity, or K-complexity, was introduced in [78] as a useful diagnostic of
quantum chaos in the thermodynamic limit. In [109] it was argued for the first
time that K-complexity of generic operators in finite-size systems exhibits
the profile of complexity described above. This work reports on a complete
numerical analysis of K-complexity for all time scales, including scrambling
and well beyond, in concrete models demonstrating the above-described time-
dependence. This is the first time that such large time scales are studied
with numerical methods, and in concrete models. We uncover non-perturbative
effects which were not initially anticipated. The study overcame known
numerical instabilities and employed powerful algorithms executed on large
computing clusters.

Roughly speaking the time evolution of complexity quantifies how quickly a
reference operator grows under Heisenberg evolution in a pre-defined basis.
K-complexity, denoted $C_{K}$, measures this growth with respect to the Krylov
basis which, as we shall see below, is well-adapted to capture Heisenberg
evolution efficiently. K-complexity depends on the Hamiltonian of the system
and a chosen reference operator. It has an advantage over other notions of
complexity: its definition does not require an arbitrary tolerance parameter.
For circuit complexity111Circuit complexity of the SYK4 model, the main work-
horse of this project, has previously been studied in [209, 210]., to cite but
one example, such a tolerance parameter must be introduced, and its presence
is crucial in establishing its boundedness [211, 68, 212], whereas
K-complexity is naturally bounded from above222Operator size complexity [213]
shares this advantage of not requiring a tolerance parameter, but differs from
$C_{K}$ in other crucial respects. For example, it is directly bounded by the
total system size, while the upper bound for K-complexity scales exponentially
with system size. [109]. It is known to be bounded by the dimension of the
Hilbert space of operators; below we prove a stronger bound.

$C_{K}$ provides a fine-grained notion of complexity, as it manifestly
distinguishes all linearly independent operators up to a given, fixed length.
These features make K-complexity a natural choice for quantifying the
evolution of operators at late times (see e.g. Sec. 2.1 in [116] for a careful
definition of chaotic time scales) which is this project’s focus.

In studying K-complexity at these time scales one should either explicitly
construct, or obtain bounds on, the full sequence of Lanczos coefficients,
$b_{n}$, which characterize the Krylov basis of an operator. These
coefficients arise in the process of orthonormalizing333The process of
orthonormalization requires a choice of inner product. In this work we use the
standard Frobenius inner-product (see section 3.4). For other choices of inner
product inherited from finite-temperature correlation functions see
discussions in [20, 78]. the Krylov basis [19, 20]. In [78] it was
hypothesized that in a chaotic quantum system in the thermodynamic limit, the
Lanczos coefficients grow at a linear rate. In [109] it was suggested that, in
finite chaotic systems, the Lanczos sequence could exhibit plateau-like
features over a certain range. The study of finite chaotic systems that is
going to be presented constructs the full Lanczos sequence to reveal a non-
perturbative decay of this plateau, making an initially small but eventually
persistent correction to the “cliff-ended plateau” conjectured in [109]. We
refer to the resulting profile as “the Descent”.

We study K-complexity in the maximally chaotic SYK4 model [89, 87, 88, 90],
which is by now well-established as a toy model displaying key chaotic
properties of black holes, including late-time spectral chaos [93, 207]. We
also study the quadratic SYK2 model, which is integrable, showing Poisson
statistics [214, 215, 216].

####  3.2 Time evolution of operators and physical properties of Krylov space

We begin by providing the definition of Krylov space and stressing its
relation to the structure of the spectrum of the system under consideration
(and hence to its integrable or chaotic character). Consider a Hilbert space
$\mathcal{H}$, of dimension $\dim\left(\mathcal{H}\right)=D$, with associated
Hilbert space of linear operators
${L}\left(\mathcal{H}\right)\equiv\widehat{\mathcal{H}}$, acting on
$\mathcal{H}$ and satisfying $\dim(\widehat{\mathcal{H}})=D^{2}$. Now consider
a system whose dynamics are described by a certain (hermitian) Hamiltonian
$H\in\widehat{\mathcal{H}}$, and an observable
$\mathcal{O}\in\widehat{\mathcal{H}}$.

The associated Krylov space [5] is defined as the minimal subspace of operator
space that contains the time evolution of $\mathcal{O}$ at all times.

The time evolution of $\mathcal{O}$ is given by

$\centering\mathcal{O}(t)=e^{iHt}\mathcal{O}e^{-iHt}=e^{i\mathcal{L}t}\mathcal{O}\@add@centering$
(3.1)

where the Liouvillian operator is defined as
$\mathcal{L}\equiv\left[H,\cdot\right]$. Thus the Krylov space is the linear
span of all nested commutators of the Hamiltonian with the operator:

$\centering\mathcal{H}_{\mathcal{O}}=\text{span}\left\\{\mathcal{L}^{n}\mathcal{O}\right\\}_{n=0}^{+\infty}=\text{span}\left\\{\mathcal{O},\,[H,\mathcal{O}],\,[H,[H,\mathcal{O}]],\dots\right\\}.\@add@centering$
(3.2)

Equivalently, $\mathcal{H}_{\mathcal{O}}$ is the minimal invariant subspace of
the Liouvillian that contains $\mathcal{O}$. We denote
$\dim\left(\mathcal{H}_{\mathcal{O}}\right)\equiv K$.

$K$ is determined by studying the cardinality of the maximal set of linearly
independent objects of the form $\mathcal{L}^{n}\mathcal{O}$, which can be
found by computing the rank of

$\left(\begin{matrix}\mathcal{O},&\mathcal{LO},&\mathcal{L}^{2}\mathcal{O},&\dots&\mathcal{L}^{n}\mathcal{O},&\dots\end{matrix}\right)^{T}\,,$
(3.3)

in a convenient matrix representation, which we now define. Let us choose the
basis $|\omega_{ab})\equiv\ket{E_{a}}\bra{E_{b}}$, on $\widehat{\cal H}$,
which is naturally induced by the eigenbasis of the Hamiltonian on ${\cal H}$.
Then each nested commutator takes the form:

$\centering\mathcal{L}^{n}\left|\mathcal{O}\right)=\delta_{n0}\sum_{a=1}^{D}O_{aa}|\omega_{aa})+\sum_{\begin{subarray}{c}a,b=1\\\
a\neq
b\end{subarray}}^{D}O_{ab}\,\omega_{ab}^{n}\,|\omega_{ab})\@add@centering$
(3.4)

where we have defined the phases444We shall refer to energy differences as
phases, since they appear as such in the moment expansion of the two-point
function of $\mathcal{O}$. $\omega_{ab}:=E_{a}-E_{b}$, which are eigenvalues
of the Liouvillian acting on $|\omega_{ab})$. Note that the $\omega$’s related
to pairs of the form $(a,a)$ are zero, $\omega_{aa}=0$ for all $a=1,...,D$.
Displaying the coordinates of (3.4) as rows one can construct a matrix
representation of (3.3), which turns out to be a Vandermonde matrix. The rank
of this matrix is at most $D^{2}$, as it has $D^{2}$ columns, so we shall keep
the same number of rows to make it a square Vandermonde matrix:

$\centering\begin{pmatrix}O_{11}&O_{22}&\dots&O_{DD}&O_{12}&O_{13}&\dots&O_{D-1,D}\\\
0&0&\dots&0&O_{12}\;\omega_{12}&O_{13}\;\omega_{13}&\dots&O_{D-1,D}\;\omega_{D-1,D}\\\
0&0&\dots&0&O_{12}\;\omega_{12}^{2}&O_{13}\;\omega_{13}^{2}&\dots&O_{D-1,D}\;\omega_{D-1,D}^{2}\\\
\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\ddots&\vdots\\\
0&0&\dots&0&O_{12}\;\omega_{12}^{D^{2}-1}&O_{13}\;\omega_{13}^{D^{2}-1}&\dots&O_{D-1,D}\;\omega_{D-1,D}^{D^{2}-1}\end{pmatrix}~{}.\@add@centering$
(3.5)

To find its actual rank, we can compute its determinant, which is given by:

$\centering\Delta\left(\left\\{\omega_{ab}\right\\}\right)\prod_{i,j=1}^{D}O_{ij}\,,\@add@centering$
(3.6)

where $\Delta\left(\left\\{\omega_{ab}\right\\}\right)$ is the Vandermonde
determinant of the phases in the matrix. The expression (3.6) will be zero if
any of the phases are degenerate, and also if any of the matrix elements in
the energy basis vanish, so the corresponding columns should be removed in
order to be left with a matrix of maximal rank. Hence, the Krylov dimension
$K$ can be estimated using the following algorithmic prescription: $K$ is
equal to the number of distinct phases corresponding to the indices of non-
zero matrix elements of the operator in the energy basis. The zero phase
$\omega_{aa}=0$ is always at least $D$ times degenerate and therefore, since
it can only be counted once, the Krylov dimension is bounded by:

$1\leq K\leq D^{2}-D+1$ (3.7)

for any non-vanishing operator.

In general, if the operator $\mathcal{O}$ has a non-vanishing projection over
several eigenstates of the Liouvillian that share the same degenerate
eigenvalue, then this phase only contributes one dimension to the Krylov
space. So a legitimate question is to wonder what particular linear
combination of those eigenstates is actually contained in the Krylov space. In
order to answer this, one can consider the form of the operator
$\mathcal{L}^{n}\left|\mathcal{O}\right)$ given in (3.4). Suppose that, for
some set $I$ of pairs of indices, the eigenvalue is degenerate:

$\centering\mathcal{L}\left|\omega_{ab}\right)=\omega\left|\omega_{ab}\right)\;\;\;\forall(a,b)\in
I\@add@centering$ (3.8)

i.e. $\omega_{ab}=\omega$ for all $(a,b)\in I$. Assume also that
$\omega_{ab}\neq\omega$ for any $(a,b)\notin I$. Inserting (3.8) in (3.4) one
finds:

$\centering\mathcal{L}^{n}\mathcal{O}=\omega^{n}\sum_{\left(a,b\right)\in
I}\,O_{ab}\left|\omega_{ab}\right)+\sum_{\left(a,b\right)\notin
I}O_{ab}\,\omega_{ab}^{n}\left|\omega_{ab}\right).\@add@centering$ (3.9)

It is manifest now that the direction of the $\omega$-eigenspace that
contributes to the Krylov space is precisely the projection of the operator
$\mathcal{O}$ over such an eigenspace:

$\centering\left|\mathcal{K}_{\omega}\right):=\sum_{\left(a,b\right)\in
I}\,O_{ab}\left|\omega_{ab}\right)~{}.\@add@centering$ (3.10)

Let‘s call $\left|\mathcal{K}_{\omega}\right)$ the eigenspace representative
for the phase $\omega$. The structure of the Krylov space is now fully
understood: Each eigenspace of the Liouvillian over which the operator
$\mathcal{O}$ has a non-vanishing projection contributes one Krylov dimension,
through a linear combination of the basis of the eigenspace of the form
(3.10). We can thus redefine the Krylov space as:

$\centering\mathcal{H}_{\mathcal{O}}=\text{span}\left\\{\left|\mathcal{K}_{\omega}\right),\;\;\;\omega\in\sigma(\mathcal{L})\right\\}\@add@centering$
(3.11)

where $\sigma(\mathcal{L})$ denotes the spectrum of $\mathcal{L}$. Finally,
the Krylov dimension $K$ is simply equal to the number of non-zero eigenspace
representatives $\left|\mathcal{K}_{\omega}\right)$.

For instance, if one considers a system whose Liouvillian has a spectrum with
no degeneracies (other than the unavoidable null phases) and an operator that
is dense in the energy basis, the Krylov dimension will be maximal,
$K=D^{2}-D+1$. The only source of degeneracy in the phases will be the
universal one due to diagonal phases $\omega_{aa}=0$. We can now note
explicitly that the part of the operator algebra that is left out of the
Krylov space belongs to the space subtended by the projectors on the energy
eigenstates, since those correspond to zero phases, and the only combination
of them that contributes to $\mathcal{H}_{\mathcal{O}}$ is the representative
of the $\omega=0$ eigenspace, in this case:

$\centering\left|\mathcal{K}_{0}\right)=\sum_{a=1}^{D}O_{aa}\left|\omega_{aa}\right)=\sum_{a=1}^{D}O_{aa}\ket{E_{a}}\bra{E_{a}}\equiv\sum_{a=1}^{D}O_{aa}\mathcal{P}_{a}.\@add@centering$
(3.12)

To summarize, $K$ is determined by exploiting the advantages of the basis in
operator space induced by the eigenbasis of the Hamiltonian; crucially, the
determinant of a suitable matrix containing the representation of these nested
commutators in the given basis reduces to a Vandermonde determinant of energy
differences. The following algorithmic prescription is derived: $K$ is equal
to the number of eigenspaces of the Liouvillian over which $\mathcal{O}$ has
non-zero projection. The eigenvalues of the Liouvillian are precisely all
possible energy differences, $\omega_{ab}=E_{a}-E_{b}$. The zero phase is
always at least $D$ times degenerate, thus the Krylov dimension is bounded by
(3.7), for any non-zero operator. The more degeneracies there are in the
spectrum of the Liouvillian, the lower will be the Krylov dimension. The
expectation is that the spectrum of a chaotic system will not feature
degeneracies apart from those induced by the presence of extra symmetries; we
therefore conjecture that typical555Along the lines of ETH [117, 118, 119,
121], we expect typical observables in chaotic systems to be dense in the
energy basis (as is the case of localized operators in local chaotic systems).
Regardless of the structure of the spectrum, one can always choose a fine-
tuned operator having a sparse matrix representation in the energy basis, e.g.
an eigenspace projector $\ket{E}\bra{E}$; such a candidate will indeed have a
very small associated Krylov space, but will not generally fulfil the
requirements to be considered a typical operator. Conserved charges are also
special operators, since they commute with the Hamiltonian, and therefore
their Krylov space is always one-dimensional. operators in chaotic systems
saturate the upper bound in (3.7); for integrable systems we expect $K$ to be
significantly smaller than the bound. We have confirmed both expectations by
studying the chaotic SYK4 model (see numerics below) as well as RMT (see
Appendix B.1), and the integrable SYK2 model, see section 3.3 below.

####  3.3 Integrable systems and SYK2

We have conjectured that the Krylov space for the time evolution of a typical
operator for integrable systems will be significantly smaller than the upper
bound in (3.7). Before verifying this conjecture in the case of SYK2, we
verify it in the simpler example of the quantum harmonic oscillator
$H=\omega(a^{\dagger}a+1/2)$ with the position operator
$\hat{x}=\sqrt{\frac{1}{2\omega}}(a+a^{\dagger})$, for which the Krylov space
dimension is $K=2$, even though the Hilbert space is infinite666Accordingly,
the Lanczos sequence contains a single element $b_{1}=\omega$ (see next
section for the definition of the Lanczos sequence in this specific
framework).. In this case, the smallness of the Krylov space is due to the
fact that the position operator has a non-vanishing projection over only two
eigenspaces of the Liouvillian (those corresponding to the energy differences
$\omega$ and $-\omega$).

Let us now test the conjecture in SYK2, an integrable system with more
structure than the harmonic oscillator. For simplicity, let us use the
Majorana (real) version of the model [87, 90]:

$\centering H=i\sum_{1\leq i<j\leq L}m_{ij}\,\chi_{i}\chi_{j}\@add@centering$
(3.13)

where the coupling strength $m_{ij}\in\mathds{R}$ is antisymmetric,
$m_{ij}=-m_{ji}$, and each independent matrix element is drawn from a Gaussian
distribution with zero mean and variance $\mathds{E}(m_{ij}^{2})=m^{2}/L$. The
number of sites is even, $L=2M$, and the Majorana fermions satisfy the
relations

$\left\\{\chi_{i},\chi_{j}\right\\}=\delta_{ij},\;\;\;\chi_{i}=\chi_{i}^{\dagger}~{}.$
(3.14)

The key point in the SYK2 case is the fact that operators do not grow after
commutation with the Hamiltonian, as also observed by [213, 217]. Hence the
subspace containing their time evolution will be, at most, that subtended by
operators of fixed equal size. For example if the operator of study is a
Majorana on some site with index $A$, $\mathcal{O}\equiv\chi_{A}$, commutation
with the Hamiltonian will give
$\left[\chi_{i}\chi_{j},\chi_{A}\right]=\delta_{Aj}\chi_{i}-\delta_{Ai}\chi_{j}$,
which is again a single-site operator (more details on the construction of the
Krylov space in this case are given in Appendix B.2). For one-site operators,
this implies an upper bound on $K$:

$\centering K\leq L\sim\log D\ll D^{2}-D+1~{}.\@add@centering$ (3.15)

It should be possible to reach this conclusion by studying the degeneracy
structure of the spectrum of SYK2, which features Poisson level spacing
statistics, and it is natural to expect other integrable systems to have a
small Krylov space, due to the expected degeneracies in the spectrum of the
Liouvillian and to the sparseness of simple operators in the energy basis. In
general, interacting integrable systems feature Poisson level spacing
statistics, implying, at least, the existence of quasi-degenerate levels in
the spectrum of the Hamiltonian, and therefore also in that of the
Liouvillian. We expect these systems to behave as if the degeneracies were
exact to a good degree of approximation, hence admitting a description in
terms of an effectively smaller Krylov space. This argument applies, and
accounts for a significant effective reduction of Krylov space, even if the
operator is not sparse in the energy basis, as long as the invariant subspace
of the Liouvillian over which it has a non-trivial projection contains
degenerate or quasi-degenerate levels. All this leads us to suggest that
integrable systems have a lower effective Krylov dimension compared with
chaotic ones. As a first step in trying to elevate this conjecture based on a
few concrete examples as well as qualitative ones, we estimate the minimal
length of time for which the difference in the dimension of the explored
Krylov space is large. Since quasi-degenerate energy levels are separated by
less than the mean level spacing $\Delta\sim\Gamma e^{-S}$, where $\Gamma$ is
a relevant energy scale of the system such as the total spectral width, we can
estimate the lowest time scale until which the Krylov dimensions of chaotic
vs. integrable (with quasi-degeneracies) systems remain significantly
different, to be of order of the Heisenberg time, i.e of order $e^{O(S)}$. For
infinite systems this lasts forever, while for large finite systems this is
way above the thermalization or scrambling time scales. The question of what
ultimately generically happens between the Heisenberg time scale and the
Poincaré time scale requires further research. Bounds like (3.7) and (3.15)
have not been noted previously in the literature.

####  3.4 Lanczos algorithm

Once the Krylov space adapted to time evolution of an operator with a constant
Hamiltonian is identified, one would like to construct an orthonormal basis
for it, given a certain scalar product $\left(\cdot|\cdot\right)$ on operator
space. This is achieved with the Lanczos algorithm, which is a
particularization of the Gram-Schmidt procedure:

  1. 1.

set $b_{0}\equiv 1$ and $\left|\mathcal{O}_{-1}\right)\equiv 0$

  2. 2.

$\left|\mathcal{O}_{0}\right)=\frac{1}{\sqrt{\left(\mathcal{O}|\mathcal{O}\right)}}\left|\mathcal{O}\right)$

  3. 3.

for $n\geq 1$:
$\left|\mathcal{A}_{n}\right)=\mathcal{L}\left|\mathcal{O}_{n-1}\right)-b_{n-1}\left|\mathcal{O}_{n-2}\right)$

  4. 4.

set $b_{n}=\sqrt{\left(\mathcal{A}_{n}|\mathcal{A}_{n}\right)}$

  5. 5.

if $b_{n}=0$ stop; otherwise set
$\left|\mathcal{O}_{n}\right)=\frac{1}{b_{n}}\left|\mathcal{A}_{n}\right)$ and
go to step 3.

In this work we make use of the Frobenius product
$\left(A|B\right)=\frac{1}{D}\text{Tr}\left[A^{\dagger}B\right]$. The
algorithm will construct an orthonormal set
$\left\\{\mathcal{O}_{n}\right\\}_{n=0}^{K-1}$, the Krylov basis, and the
Lanczos coefficients $\left\\{b_{n}\right\\}_{n=1}^{K-1}$.

Each Lanczos step produces an element $\left|\mathcal{A}_{n}\right)$
orthogonal to all previous $\left|\mathcal{O}_{m}\right)$ with $m<n$, so it is
either zero or a new direction in Krylov space. For $n<K$,
$\left|\mathcal{A}_{n}\right)\neq 0$ because the set that is being
orthogonalized with this procedure has rank $K$ (in particular,
$\left|\mathcal{A}_{n}\right)$ contains terms with up to $n$ nested
commutators of $H$ with $\mathcal{O}$). However,
$\left|\mathcal{A}_{K}\right)$ is orthogonal to
$\left\\{\mathcal{O}_{n}\right\\}_{n=0}^{K-1}$, which is already a complete
orthonormal basis of $\mathcal{H}_{\mathcal{O}}$, so it must therefore vanish,
just as $b_{K}=\sqrt{\left(\mathcal{A}_{K}|\mathcal{A}_{K}\right)}=0$. We
conclude that the Lanczos algorithm must terminate by hitting a zero once all
directions in Krylov space have been exhausted. This is accounted for in Step
5 above.

The representation of the Liouvillian over the Krylov space in such a basis
simplifies to a tridiagonal matrix
$\left(\mathcal{O}_{m}\right|\mathcal{L}\left|\mathcal{O}_{n}\right)=T_{mn}$,
whose entries are given by the Lanczos coefficients:

$\centering T\overset{*}{=}\begin{pmatrix}0&b_{1}&0&0&\dots&0\\\
b_{1}&0&b_{2}&0&\dots&0\\\ 0&b_{2}&0&b_{3}&\dots&0\\\
\vdots&&\ddots&&\ddots&\vdots\\\ &&&&\ddots&b_{K-1}\\\
0&0&0&\dots&b_{K-1}&0\end{pmatrix}.\@add@centering$ (3.16)

The eigenvalues of this matrix are all non-degenerate, and given precisely by
the phases corresponding to the eigenspaces of the Liouvillian that span the
Krylov space (see section 3.2).