eigenspace representatives. If $H$ does not have any degenerate eigenspace,
then $\mathcal{H}_{|\overline{\Omega}\rangle}=\mathcal{H}_{|\Omega\rangle}$.
Alternatively, if $U$ is a function of $H$, $U\equiv f(H)$, then it will not
change the direction of any eigenspace representatives, as it will just amount
to multiplying them by a factor $f(\widetilde{\lambda})$, where
$\widetilde{\lambda}$ is the eigenvalue associated to the given eigenspace,
not changing the direction of the Hilbert space such a representative spans:
In this simple case141414From the linear algebra perspective this is a
relatively simple statement, but it is still relevant to point it out at this
stage because of subsequent applications of the Lanczos algorithm in the realm
of quantum mechanics, where $H$ shall be the Hamiltonian or, more generally,
the time evolution generator for the Hilbert space of study: A corollary of
this property states the fact that a time translation of the seed state
$|\Omega\rangle\mapsto e^{-itH}|\Omega\rangle$ does not modify its Lanczos
coefficients or its Krylov space, only changing its Krylov basis by the
corresponding time-translated version. Quantities computed solely out of the
Lanczos coefficients will therefore be invariant under time translations of
the seed state. This will be the case of the Krylov complexity profile as a
function of time, as can be deduced from its definition in section 2.1. This
will not necessarily mean that Krylov complexity of a given, fixed seed is
invariant under time translations (i.e. constant): Rather, the profiles
followed by the K-complexities of the evolution of two initial conditions
related by a time translation will be identical., the Krylov spaces of both
seeds are also identical, despite the fact that the Krylov bases are a unitary
transformation of each other.

In view of the polynomial recursion (1.81), since the Lanczos coefficients in
(1.115) are invariant, so will be the Krylov polynomials, i.e.

$p_{n}(\lambda)\longmapsto\overline{p}_{n}(\lambda)=p_{n}(\lambda)$ (1.116)

and, therefore, their roots are the same for any $n=0,\,\dots,\,K$. This is in
agreement with the fact that both seeds $|\Omega\rangle$ and
$|\overline{\Omega}\rangle$ in (1.114) probe the same eigenspaces of $H$ (even
though they do so through potentially different eigenspace representatives).

  2. 2.

Translations of $H$: Instead of changing the seed, one may also envision
certain modifications of the Hermitian operator of study while keeping
$|\overline{\Omega}\rangle=|\Omega\rangle$. Let us consider a shift,

$H\longmapsto\overline{H}=H-\alpha\mathds{1},\qquad\alpha\in\mathds{R}~{}.$
(1.117)

In quantum mechanics, constant energy shifts are known not to have an impact
on observable quantities. It is therefore insightful to analyse the effect of
such a transformation on the Lanczos algorithm. It can be shown inductively to
only shift the $a$-coefficients, leaving everything else invariant:

$\begin{split}&\overline{K}=K~{},\\\
&\overline{a}_{n}=a_{n}-\alpha\qquad\forall\;n=0,\,\dots,\,K-1~{},\\\
&\overline{b_{n}}=b_{n}\qquad\forall\;n=1,\,\dots,\,K-1~{},\\\
&|\overline{K}_{n}\rangle=|K_{n}\rangle\qquad\forall\;n=0,\,\dots,\,K-1~{}.\end{split}$
(1.118)

As a corollary, since the Krylov basis remains invariant, so does the Krylov
space. The effect of (1.118) on the Krylov polynomials is a shift in their
domain, namely:

$\overline{p}_{n}(\lambda)=p_{n}(\lambda+\alpha)~{}.$ (1.119)

Denoting the roots of $p_{n}$ (resp., $\overline{p}_{n}$) as
$\widetilde{\lambda}_{j}^{(n)}$ (resp.
$\overline{\widetilde{\lambda}}_{j}^{(n)}$)151515The author apologises for the
convoluted notation. The tilde is still kept because these roots are related
to the spectrum of the restriction of $H$ to Krylov space,
$\widetilde{\lambda}_{j}=\widetilde{\lambda}_{j}^{(K)}$ for $j=0,\dots,K-1$,
which need not constitute the full spectrum of the hermitian operator under
consideration, but potentially only a subset of it., where $j=0,\dots,n-1$ for
fixed $n$, (1.119) implies that the roots are accordingly shifted:

$\overline{\widetilde{\lambda}}_{j}^{(n)}=\widetilde{\lambda}_{j}^{(n)}-\alpha~{}.$
(1.120)

In particular, the eigenvalues of $H$ represented in Krylov space, given by
the roots of the $K$-th Krylov polynomial, are shifted in the same way as the
operator itself is in (1.117), consistently.

  3. 3.

Rescalings of $H$: Let us also consider the effect of a rescaling in $H$,

$H\longmapsto\overline{H}=\kappa H~{},\qquad\kappa\in\mathds{R},$ (1.121)

while keeping the seed fixed. This transformation still does not change the
Krylov basis (nor the Krylov space), but rescales accordingly the Lanczos
coefficients:

$\begin{split}&\overline{K}=K~{},\\\ &\overline{a}_{n}=\kappa
a_{n}\qquad\forall\;n=0,\,\dots,\,K-1~{},\\\ &\overline{b_{n}}=\kappa
b_{n}\qquad\forall\;n=1,\,\dots,\,K-1~{},\\\
&|\overline{K}_{n}\rangle=|K_{n}\rangle\qquad\forall\;n=0,\,\dots,\,K-1~{}.\end{split}$
(1.122)

When (1.122) is plugged into (1.81), the Krylov polynomials get accordingly
rescaled:

$\overline{p}_{n}(\lambda)=p_{n}\left(\frac{\lambda}{\kappa}\right)~{},$
(1.123)

hence also rescaling their roots as

$\overline{\widetilde{\lambda}}_{j}^{(n)}=\kappa\widetilde{\lambda}_{j}^{(n)}~{},$
(1.124)

consistently with the fact that $\overline{H}=\kappa H$.

  4. 4.

Sign flip of $H$: Finally, let us study the effect of changing the sign of the
operator:

$H\longmapsto\overline{H}=-H~{}.$ (1.125)

Inductively, the effect of (1.125) is shown to be:

$\begin{split}&\overline{K}=K~{},\\\
&\overline{a}_{n}=-a_{n}\qquad\forall\;n=0,\,\dots,\,K-1~{},\\\
&\overline{b_{n}}=b_{n}\qquad\forall\;n=1,\,\dots,\,K-1~{},\\\
&|\overline{K}_{n}\rangle=(-1)^{n}|K_{n}\rangle\qquad\forall\;n=0,\,\dots,\,K-1~{},\\\
&\overline{p}_{n}(\lambda)=(-1)^{n}p_{n}(-\lambda)\qquad\forall\;n=0,\,\dots,\,K~{}.\end{split}$
(1.126)

And the last line of (1.126) implies, consistently, that the roots of the
Krylov polynomials change sign, namely

$\overline{\widetilde{\lambda}}_{j}^{(n)}=-\widetilde{\lambda}_{j}^{(n)}~{},$
(1.127)

for $j=0,\dots,n-1$ and $n=0,\dots,K$.

The roots of the last Krylov polynomial $p_{K}(\lambda)$ are the exact
eigenvalues of the restriction of $H$ to Krylov space. Therefore, the roots of
$p_{K}$ should transform in the same way as the eigenvalues of $H$ do under
the corresponding transformations. This is confirmed by equations (1.116),
(1.120), (1.124) and (1.127). Furthermore, these equations also show that the
roots of the lower-degree Krylov polynomials ($p_{n}$ with $n<K$) still
transform in the same way: This is insightful because, as we shall argue in
section 1.7, such roots can be understood as numerical approximations to the
eigenvalues of $H$ obtained via successive truncations of Krylov space.

The behavior of Lanczos coefficients and Krylov elements under the
transformations discussed here will also turn out to be useful in order to
understand the mechanism through which the Lanczos algorithm resolves
progressively the spectrum when it is used as an approximation method, as we
shall discuss in section 1.7.4.

####  1.7 The Lanczos algorithm as an approximation method

So far, we have presented the Lanczos algorithm and argued how it may be used
as an efficient method to solve exactly the eigenvalue problem of a certain
hermitian operator $H$, which has the additional advantage of reducing
potential numerical errors due to the amplification of the contribution of
eigenspaces corresponding to large eigenvalues, an effect that is avoided
thanks to the iterative orthogonalization of each new Krylov element against
the previous ones in the Lanczos algorithm. However, this algorithm can be
also used as an approximation method: Running only a subset of the Lanczos
steps allows to calculate a numerical approximation to a subset of the
spectrum of $H$ in the way that will be explained in this section.

Let us suppose that we run the Lanczos algorithm formulated at the end of
section 1.2 up to the step $n_{*}-1$, building successfully the first $n_{*}$
Krylov elements, $\left\\{|K_{m}\rangle\right\\}_{m=0}^{n_{*}-1}$, together
with the Lanczos coefficients $\left\\{a_{m}\right\\}_{m=0}^{n_{*}-1}$ and
$\left\\{b_{m}\right\\}_{m=1}^{n_{*}-1}$. The latter are sufficient, according
to the polynomial recursion (1.81), to build the $n_{*}$-th (non-normalized)
Krylov polynomial $p_{n_{*}}(\lambda)$. In the same way the roots of the last
Krylov polynomial $p_{K}(\lambda)$ yield the $K$ eigenvalues represented in
Krylov space, as discussed around (1.84), one may attempt to use the $n_{*}$
roots of $p_{n_{*}}(\lambda)$ as an approximation to $n_{*}$ of those
eigenvalues. There is a sense in which this is correct and, in order to
illustrate it, let us for now consider an ideal case in which the Krylov-space
spectrum features a very pronounced hierarchy:

$\widetilde{\lambda}_{0}\gg\widetilde{\lambda}_{1}\gg\dots\gg\widetilde{\lambda}_{K-1}>0~{}.$
(1.128)

Note that the requirement that all eigenvalues are positive is not invariant
under shifts of $H$, despite the fact that the Krylov elements are expected to
be invariant under such a shift according to (1.118). It is also not invariant
under a sign flip of $H$, while the Krylov elements only change by a phase in
such a case, as stated in (1.126). It will nevertheless be pedagogical, at
this stage, to particularize our discussion to the spectrum (1.128). The
treatment of the most generic case will be postponed to section 1.7.4. A
hierarchy like (1.128) can be achieved, for example, if there is a parametric
separation between the eigenvalues, e.g.

$\widetilde{\lambda}_{j}=\lambda^{K-j}~{},\qquad\text{for }j=0,\,...\,K-1$
(1.129)

and where $\lambda>1$ is some constant setting the scale.

In the process of the implementation of the Lanczos algorithm, each
application of the operator $H$ on a given vector amplifies the projection of
such a vector over the eigenspace corresponding to the largest eigenvalue and,
in order to avoid this, each Lanczos step effectively subtracts the eigenspace
(or eigenspaces) contributing the most to the norm of the previous Krylov
element. As a result of this, if the spectrum ideally features a very
pronounced eigenvalue hierarchy, the Krylov subspace spanned by
$\left\\{|K_{m}\rangle\right\\}_{m=0}^{n_{*}-1}$ effectively probes the
eigenspaces of the $n_{*}$ largest eigenvalues for which, therefore, the roots
of $p_{n_{*}}(\lambda)$ give a numerical approximation. Let us be more precise
about this: We shall probe Krylov space with a seed whose profile with respect
to the eigenspace representatives is given by

$|\Omega\rangle=\sum_{j=0}^{K-1}\widetilde{\Omega}_{j}|\widetilde{\lambda}_{j}\rangle~{}.$
(1.130)

Note that all $\widetilde{\Omega}_{j}\neq 0$ because we are already focusing
on Krylov space. We also assume (1.130) to be normalized, so that

$\sum_{j=0}^{K-1}{\lvert\widetilde{\Omega}_{j}\rvert}^{2}=1~{}.$ (1.131)

This vector already gives the zeroth Krylov element,
$|K_{0}\rangle=|\Omega\rangle$. Let us apply explicitly the first Lanczos step
to it. We begin by computing the coefficient $a_{0}$:

$a_{0}=\langle
K_{0}|H|K_{0}\rangle=\sum_{j=0}^{K-1}{\lvert\widetilde{\Omega}_{j}\rvert}^{2}\,\widetilde{\lambda}_{j}~{}.$
(1.132)

That is: $a_{0}$ is the weighted average of all the eigenvalues represented in
Krylov space. If we do not assume any special “fine-tuning” of the
coefficients $\widetilde{\Omega}_{j}$ that may compete with the hierarchy
(1.128), then it is natural to expect that $a_{0}$ will be numerically close
to the largest eigenvalue $\widetilde{\lambda}_{0}$. In the particular case of
a parametric scale separation between eigenvalues (1.129), as long as the
coefficients $\widetilde{\Omega}_{j}$ do not feature a similar or competing
parametric scaling with $j$ (which is usually not the case because the probe
vector is chosen independently from the spectrum), it is safe to claim that
$a_{0}$ and $\widetilde{\lambda}_{0}$ are of the same order,
$a_{0}\sim\widetilde{\lambda_{0}}\sim\lambda^{K}$. Hence, $a_{0}$ is already a
good approximation to the largest eigenvalue and, in fact, the first Krylov
polynomial, written in (1.81), is precisely $p_{1}(\lambda)=\lambda-a_{0}$,
which already justifies that the root of $p_{1}(\lambda)$ approximates the
largest eigenvalue.

Furthermore, we can complete the Lanczos step and construct the first, non-
normalized Krylov element:

$|A_{1}\rangle=(H-a_{0})|K_{0}\rangle=\sum_{j=0}^{K-1}\widetilde{\Omega}_{j}\Big{(}\widetilde{\lambda}_{j}-a_{0}\Big{)}|\widetilde{\lambda}_{j}\rangle~{}.$
(1.133)

Now, since $a_{0}\sim\widetilde{\lambda}_{0}$, the subtraction inside the
bracket in the last term of (1.133) has the effect of practically cancelling
out the contribution from $j=0$, so that we may approximate

$|A_{1}\rangle\approx\sum_{j=1}^{K-1}\widetilde{\Omega}_{j}\Big{(}\widetilde{\lambda}_{j}-a_{0}\Big{)}|\widetilde{\lambda}_{j}\rangle~{},$
(1.134)

and in this way this Krylov element does no longer have a contribution from
the eigenspace of the largest eigenvalue. This consideration will be
quantitatively more accurate the more peaked the seed vector is around
$|\widetilde{\lambda}_{0}\rangle$, as this will make $a_{0}$ numerically
closer to $\widetilde{\lambda}_{0}$ according to the weighted average (1.132).
A new application of $H$ will now amplify prominently the direction
$|\widetilde{\lambda}_{1}\rangle$, but at the same time the coefficient
$a_{1}$ will be numerically close to $\widetilde{\lambda}_{1}$, and therefore
the projection of $H|K_{1}\rangle$ over $|\widetilde{\lambda}_{1}\rangle$ will
be effectively removed in the $n=2$ Lanczos step161616If we had kept track of
the contribution along the direction of $|\widetilde{\lambda}_{0}\rangle$,
which had been neglected in (1.134), it would have equally gotten amplified by
the action of $H$; however, it would eventually be effectively removed by the
corresponding subtractions of the Lanczos step that ensure orthogonality of
the new Krylov elements with respect to the previously-constructed ones. Thus,
for the sake of this qualitative discussion, we may directly not consider this
direction at all., as a result of which the Krylov element $|K_{2}\rangle$
will effectively not probe the eigenspaces
$\left\\{|\widetilde{\lambda}_{j}\rangle\right\\}_{j=0}^{1}$. In general, this
may serve as a qualitative argument for the statement

$\langle\widetilde{\lambda}_{j}|A_{n}\rangle=\text{{small}}\qquad\text{for
}j=0,\,...,\,n-1~{}.$ (1.135)

This was Lanczos’ original motivation for developing the recursion method, as
announced. The above expression may now be compared to equation (1.99), whose
version in terms of the non-normalized Krylov elements and polynomials we
provide here:

$\langle\widetilde{\lambda}_{j}|A_{n}\rangle=\widetilde{\Omega}_{j}p_{n}(\widetilde{\lambda}_{j})~{}.$
(1.136)

From (1.135) and (1.136), assuming the coordinates $\widetilde{\Omega}_{j}$ do
not feature a pronounced hierarchy competing with that in the spectrum, we
conclude that

$p_{n}(\widetilde{\lambda}_{j})=\text{{small}}\qquad\text{for
}j=0,\,...,\,n-1~{}.$ (1.137)

Since $p_{n}(\lambda)$ is a polynomial of degree $n$, which diverges when
$\lambda\to\pm\infty$, one may consider (1.137) as an indication that its
roots are “near” $\left\\{\widetilde{\lambda}_{j}\right\\}_{j=0}^{n-1}$. It is
in this sense that we can claim that the roots of $p_{n}(\lambda)$ give a
numerical approximation to the $n$ largest eigenvalues of $n$, at least in the
case of the positive spectrum with a well-defined hierarchy (1.128) that we
took in order to simplify the discussion, and given a seed whose profile over
the eigenbasis is not in competition with such a hierarchy. For the sake of
generality, however, we have not been quantitatively precise about the meaning
of “approximating” or about the notions of “smallness” or “being close to a
number”. The case of a parametric hierarchy between the eigenvalues (1.129)
provides nevertheless a clear example than can be tested numerically, as will
be done in section 1.8. In such a case, the suppression of objects like
(1.135) may be understood as a suppression in terms of powers of the scale
$\lambda$ controlling the parametric separation in (1.129).

#####  1.7.1 Krylov space truncations

The approximation scheme being considered here amounts to truncating Krylov
space to a dimension $n_{*}<K$. Recalling the discussion around (1.85), we
note that finding the numerical approximation to $n_{*}$ of the eigenvalues of
$H$ by solving the equation

$p_{n_{*}}(\lambda)=0$ (1.138)

amounts to having effectively pretended that $|A_{n_{*}}\rangle\equiv 0$, i.e.
placing the termination of the Lanczos algorithm at step $n_{*}$ rather than
at step $K$, providing a truncated Krylov basis
$\left\\{|K_{n}\rangle\right\\}_{n=0}^{n_{*}-1}$ that spans a truncated Krylov
subspace:

$\mathcal{H}_{|\Omega\rangle}^{(n_{*})}:=\text{span}\left\\{|K_{n}\rangle\right\\}_{n=0}^{n_{*}-1}<\mathcal{H}_{|\Omega\rangle}~{}.$
(1.139)

The “fake” termination $|A_{n_{*}}\rangle\equiv 0$ is equivalent to pretending
that the action of $H$ over the truncated Krylov subspace is closed, admitting
a well-defined restriction which could be diagonalized within this subspace.
The fact that the roots of (1.138) are not exactly a subset of the eigenvalues
of $H$, but a numerical approximation to them as argued below equation
(1.137), is a reflection of the fact that there does not exist such a well-
defined restriction of $H$ over $\mathcal{H}_{|\Omega\rangle}^{(n_{*})}$.
Nevertheless, in practical situations with a limited computational power
available, where only a subset of the spectrum is required, or in which the
Krylov dimension might be infinite (which is often the case for differential
operators171717The Lanczos algorithm can be applied to a differential operator
either by turning it into a finite matrix through some regularization scheme,
or by iteratively applying it analytically to some seed function for a finite
collection of Lanczos steps. This may result useful e.g. for computing the
exponential of such an operator, an object which is often required for the
solution of linear differential equations. An immediate example is the
computation of the time evolution operator in quantum mechanics, whenever the
Hamiltonian is given in the form of a differential operator.) the use of this
truncation protocol is very useful and often unavoidable.

The solutions of (1.138) give $n_{*}$ approximations to Krylov-space
eigenvalues of $H$, which we shall denote $\widetilde{\lambda}_{j}^{(n_{*})}$
with $j=0,\dots,n_{*}-1$. Using them, together with the truncated Krylov basis
that spans (1.139) and its associated Krylov polynomials, we can equally build
the corresponding approximate eigenvectors by the means of the truncated
version of expression (1.100):

$|\widetilde{\lambda}_{j}^{(n_{*})}\rangle=\widetilde{\Omega}_{j}^{*}\sum_{n=0}^{n_{*}-1}q_{n}\Big{(}\widetilde{\lambda}_{j}^{(n_{*})}\Big{)}|K_{n}\rangle~{}.$
(1.140)

This approximation scheme will be illustrated in the numerical examples of
section 1.8 for three models with different seed vectors and hermitian
operators $H$. We note that, if $n_{*}=K$, then the truncated Krylov subspace
becomes the full Krylov space, and hence the approximate eigenvalues and
eigenvectors become exact. Namely, for all $j=0,\dots,K-1$ we have:

$\widetilde{\lambda}_{j}^{(K)}=\widetilde{\lambda}_{j}~{},\qquad|\widetilde{\lambda}_{j}^{(K)}\rangle=|\widetilde{\lambda}_{j}\rangle~{}.$
(1.141)

#####  1.7.2 Successive characteristic polynomials

In order to understand more visually this approximation, in which successive
truncations of Krylov space yield numerical approximations to the largest
eigenvalues of the spectrum (1.128), we can show explicitly that the last
Krylov polynomial $p_{K}(\lambda)$ is proportional to the characteristic
polynomial of the tridiagonal matrix (1.79) and that, likewise, each Krylov
polynomial $p_{n}(\lambda)$ is proportional to the $n$-dimensional truncation
of such a matrix, denoted $T_{n}$, built out of the Lanczos coefficients
$\left\\{a_{m}\right\\}_{m=0}^{n-1}$ and $\left\\{b_{m}\right\\}_{m=1}^{n-1}$.
In order to prove this, we will establish a recursive relation between the
aforementioned characteristic polynomials and show that it maps to the Krylov
polynomial recursion (1.81) by rescaling the polynomials with the adequate
non-vanishing constant. Consider the following characteristic polynomial:

$\begin{split}&\qquad\qquad\qquad\qquad\quad
R_{n}(\lambda):=\det\left(\lambda\mathds{1}_{n}-T_{n}\right)\\\
&=\begin{vmatrix}\lambda-a_{0}&-b_{1}&0&\dots&0&0&0\\\ -b_{1}&\lambda-
a_{1}&-b_{2}&\dots&0&0&0\\\ 0&-b_{2}&\lambda-a_{2}&\dots&0&0&0\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\\ 0&0&0&\dots&\lambda-
a_{n-3}&-b_{n-2}&0\\\ 0&0&0&\dots&-b_{n-2}&\lambda-a_{n-2}&-b_{n-1}\\\
0&0&0&\dots&0&-b_{n-1}&\lambda-a_{n-1}\end{vmatrix}~{}.\end{split}$ (1.142)

Note that, for the present discussion, we have chosen a convention to define
the characteristic polynomial that differs from that in (1.1) by a power of
$-1$. This determinant will yield a polynomial of degree $n$, and we may
develop it along its rightmost column, obtaining:

$R_{n}(\lambda)=(\lambda-a_{n-1})R_{n-1}(\lambda)+b_{n-1}X_{n-2}(\lambda)~{},$
(1.143)

where $X_{n-2}(\lambda)$ is an intermediary polynomial of degree $n-2$ given
by the determinant

$X_{n-2}(\lambda):=\begin{vmatrix}\lambda-a_{0}&-b_{1}&0&\dots&0&0\\\
-b_{1}&\lambda-a_{1}&-b_{2}&\dots&0&0\\\ 0&-b_{2}&\lambda-a_{2}&\dots&0&0\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\ 0&0&0&\dots&\lambda-
a_{n-3}&-b_{n-2}\\\ 0&0&0&\dots&0&-b_{n-1}\end{vmatrix}~{},$ (1.144)

which can be immediately developed along its last line, yielding

$X_{n-2}(\lambda)=-b_{n-1}R_{n-2}(\lambda)~{}.$ (1.145)

Plugging (1.145) into (1.143) yields a recursion between the characteristic
polynomials:

$R_{n}(\lambda)=(\lambda-
a_{n-1})R_{n-1}(\lambda)-b_{n-1}^{2}R_{n-2}(\lambda)~{},$ (1.146)

whose seeds are $R_{0}(\lambda)=1$ and $R_{1}(\lambda)=\lambda-a_{0}$. We now
note that, using the convention $b_{0}\equiv 1$ and posing

$\begin{split}&R_{0}(\lambda)=p_{0}(\lambda)=1~{},\\\
&R_{n}(\lambda)=\Big{(}\prod_{m=0}^{n-1}b_{m}\Big{)}p_{n}(\lambda)~{},\qquad
1\leq n\leq K~{},\end{split}$ (1.147)

the recursion (1.146) gets mapped to (1.81), confirming that the Krylov
polynomials are the characteristic polynomials of the successive tridiagonal
matrices up to a non-zero proportionality constant181818The $b$-coefficients
are never zero because they are originally given by the norms of the non-
normalized Krylov elements in the Lanczos algorithm. As discussed at the end
of section 1.2, if one of those norms is zero, the algorithm terminates and
such a coefficient ($b_{K}=0$) is not stored.. The fact that their zeroes give
numerical approximations to the eigenvalues of $H$ probed by these successive
Krylov space truncations is now intuitively easier to understand.

#####  1.7.3 The reversed Lanczos algorithm

The recursion (1.146) was derived by the means of developing the determinant
(1.142) along its rightmost column. This immediately suggests the possibility
of proceeding differently, namely, developing the determinant for the full
characteristic polynomial $R_{K}(\lambda)$ along its leftmost column, yielding
a new polynomial recursion whose final element is still $R_{K}(\lambda)$, just
like with (1.146), but whose intermediary polynomials are different from the
Krylov polynomials $p_{n}(\lambda)$, still admitting an interpretation in the
framework of the Lanczos algorithm, as we shall see below.

We start by considering the following pattern of truncation of Krylov space:
Instead of keeping the first $n$ Krylov elements, we shall keep the subset
$\left\\{|K_{m}\rangle\right\\}_{m=n}^{K-1}$. The approximate restriction of
$H$ over this Krylov subspace191919Along the lines of the discussion in
section 1.7.1, it is approximate in the sense that the action of $H$ is not
really closed in this subspace, but we explicitly neglect the subspace of the
image that does not belong to the subspace spanned by the truncated basis. is
denoted as $\overline{T}_{K-n}$ and, in coordinates over the above-mentioned
restricted Krylov basis, it takes the following form:

$\overline{T}_{K-n}\overset{*}{=}\begin{pmatrix}a_{n}&b_{n+1}&0&\dots&0&0&0\\\
b_{n+1}&a_{n+1}&b_{n+2}&\dots&0&0&0\\\ 0&b_{n+2}&a_{n+2}&\dots&0&0&0\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\\
0&0&0&\dots&a_{K-3}&b_{K-2}&0\\\ 0&0&0&\dots&b_{K-2}&a_{K-2}&b_{K-1}\\\
0&0&0&\dots&0&b_{K-1}&a_{K-1}\end{pmatrix}~{},$ (1.148)

where the star over the equality sign denotes that the right-hand side is an
expression in coordinates over a particular basis (in this case, the truncated
Krylov basis described in the preceding paragraph). We define the
characteristic polynomial of this matrix as

$\overline{R}_{K-n}(\lambda):=\det(\lambda\mathds{1}-\overline{T}_{K-n})~{}.$
(1.149)

Notationally, both for the matrix and the polynomial, the indexing $K-n$ has
been preferred because in this way the subindex indicates their dimension and
degree, respectively. Proceeding similarly to the steps that led to (1.146),
but this time developing the determinant along its leftmost column, one
reaches the recursion

$\overline{R}_{K-n}(\lambda)=(\lambda-
a_{n})\overline{R}_{K-(n+1)}(\lambda)-b_{n+1}^{2}\overline{R}_{K-(n+2)}(\lambda)~{}.$
(1.150)

For $n=K-1,\dots,0$. Note that, for $n=0$, the truncated operator becomes the
full original hermitian operator restricted to Krylov space $T_{K}=T$, where
we recall that $T$ is given in coordinates over the full Krylov basis in
(1.79), and hence we consistently have that

$\overline{R}_{K}(\lambda)=R_{K}(\lambda)=\det(\lambda\mathds{1}-T)~{},$
(1.151)

where the determinant should be understood to be restricted to Krylov space
$\mathcal{H}_{|\Omega\rangle}$.

The recursion above uses the polynomials at levels $n+1$ and $n+2$ to
determine that at level $n$, so the seeds required are the polynomials
corresponding to $n=K$ and $n=K-1$, which are given by

$\overline{R}_{0}(\lambda)=1,\qquad\overline{R}_{1}(\lambda)=\lambda-
a_{K-1}~{}.$ (1.152)

In order to make the recursion (1.150) more readable, and to make contact with
the discussion on Krylov polynomials that we shall shortly take, it is
convenient to relabel the indices as $K-n\longmapsto n$, resulting in

$\overline{R}_{n}(\lambda)=(\lambda-
a_{K-n})\overline{R}_{n-1}(\lambda)-b_{K-(n-1)}^{2}\overline{R}_{n-2}(\lambda)~{},$
(1.153)

whose seed is still (1.152). The connection of these successive truncations
and their corresponding characteristic polynomials to the Lanczos algorithm is
immediate after noticing that they correspond to ordered truncations of Krylov
space starting from the last (rather than the zeroth) Krylov element. As we
shall now show, the polynomials $\overline{R}_{n}(\lambda)$ are related to the
Krylov polynomials obtained applying the Lanczos algorithm to the last Krylov
element $|K_{K-1}\rangle$, used now as the new seed of the iterative process.
This protocol gives a new Krylov basis
$\left\\{|\overline{K}_{n}\rangle\right\\}_{n=0}^{K-1}$ of the same length as
the original one, together with new sets of Lanczos coefficients
$\left\\{\overline{a}_{n}\right\\}_{n=0}^{K-1}$ and
$\left\\{\overline{b}_{n}\right\\}_{n=1}^{K-1}$. The new seed gives directly
the zeroth element of the basis,

$|\overline{K}_{0}\rangle=|K_{K-1}\rangle~{},$ (1.154)

from which $\overline{a}_{0}$ can be immediately computed:

$\overline{a}_{0}=\langle\overline{K}_{0}|H|\overline{K}_{0}\rangle=\langle
K_{K-1}|H|K_{K-1}\rangle=a_{K-1}~{}.$ (1.155)

The first Lanczos step can now be applied:

$|\overline{A}_{1}\rangle=(H-\overline{a}_{0})|\overline{K}_{0}\rangle=(H-a_{K-1})|K_{K-1}\rangle=b_{K-1}|K_{K-2}\rangle~{},$
(1.156)

where in the last step we made use of the termination condition (1.66)

$|A_{K}\rangle=(H-a_{K-1})|K_{K-1}\rangle-b_{K-1}|K_{K-2}\rangle=0~{}.$
(1.157)

The first new Lanczos coefficient is given by the norm of
$|\overline{A}_{1}\rangle$,

$\overline{b_{1}}=b_{K-1}~{},$ (1.158)

and the next Krylov element is the normalized version of
$|\overline{A}_{1}\rangle$, i.e.

$|\overline{K}_{1}\rangle=|K_{K-2}\rangle~{}.$ (1.159)

To conclude this Lanczos step, we can compute the next $a$-coefficient:

$\overline{a}_{1}=\langle\overline{K}_{1}|H|\overline{K}_{1}\rangle=\langle
K_{K-2}|H|K_{K-2}\rangle=a_{K-2}~{}.$ (1.160)

At this point, we are in conditions to propose the following relations:

$\begin{split}&\overline{a}_{n}=a_{K-1-n}~{},\qquad
n=0,\,1\,,\dots,\,K-1~{},\\\ &\overline{b}_{n}=b_{K-n}~{},\qquad
n=1,\,2,\,,\dots,\,K-1~{},\\\
&|\overline{K}_{n}\rangle=|K_{K-1-n}\rangle~{},\qquad
n=0,\,1,\,\dots,\,K-1~{}.\end{split}$ (1.161)

This proposal may be proved by induction. The starting seeds (steps $n=0,\,1$)
have already been provided above, and it is only left to show the induction
step. We assume that (1.161) holds up to the step $n$, and take a step
further:

$\begin{split}&|\overline{A}_{n+1}\rangle=(H-\overline{a}_{n})|\overline{K}_{n}\rangle-\overline{b}_{n}|\overline{K}_{n-1}\rangle=(H-a_{K-1-n})|K_{K-1-n}\rangle-
b_{K-n}|K_{K-n}\rangle\\\ &=b_{K-n}|K_{K-n}\rangle+b_{K-1-n}|K_{K-n-2}\rangle-
b_{K-n}|K_{K-n}\rangle=b_{K-1-n}|K_{K-n-2}\rangle~{},\end{split}$ (1.162)

where we made use of the generic Lanczos step (1.54). The norm of
$|\overline{A}_{n+1}\rangle$ gives the new $b$-coefficient,

$\overline{b}_{n+1}=b_{K-(n+1)}~{},$ (1.163)

and its normalized version yields the new Krylov element,

$|\overline{K}_{n+1}\rangle=|K_{K-1-(n+1)}\rangle~{}.$ (1.164)

Finally, the next $a$-coefficient reads:

$\overline{a}_{n+1}=\langle\overline{K}_{n+1}|H|\overline{K}_{n+1}\rangle=a_{K-1-(n+1)}~{},$
(1.165)

where (1.164) and the definition of $a_{K-1-(n+1)}$ have been used.
Expressions (1.163), (1.164) and (1.165) are consistent with (1.161), which is
therefore proved. The Krylov basis associated to $|K_{K-1}\rangle$ simply
sweeps backwards the original Krylov basis, and as such we shall refer to it
as the reversed Krylov basis. Likewise, its associated $\overline{a}_{n}$ and
$\overline{b}_{n}$ sequences shall be dubbed the reversed Lanczos
coefficients.

The termination of the reversed basis can be verified considering the $n=K$
Lanczos step:

$\begin{split}&|\overline{A}_{K}\rangle=(H-\overline{a}_{K-1})|\overline{K}_{K-1}\rangle-\overline{b}_{K-1}|\overline{K}_{K-2}\rangle\\\
&=(H-a_{0})|K_{0}\rangle-b_{1}|K_{1}\rangle=b_{1}|K_{1}\rangle-
b_{1}|K_{1}\rangle=0~{},\end{split}$ (1.166)

where, in the second-to-last equality, the $n=1$ Lanczos step of the original
basis, (1.35), which has one subtraction term less than the generic steps with
$n\geq 2$, has been applied.

With this, it is equally possible to build a family of reversed Krylov
polynomials, denoted $\overline{p}_{n}(\lambda)$ with $n=0,\,\dots,\,K$, by
noting that

$|\overline{A}_{n}\rangle=\overline{p}_{n}(H)|\overline{K}_{0}\rangle=\overline{p}_{n}(H)|K_{K-1}\rangle~{}.$
(1.167)

Using the Lanczos recursion satisfied by the reversed Krylov basis, given in
the first equality of (1.162), one can show that the reversed polynomials
satisfy a relation which is analogous to that in (1.81):

$\begin{split}&\overline{p}_{0}(\lambda)=1~{},\\\
&\overline{p}_{1}(\lambda)=\lambda-\overline{a}_{0}=\lambda-a_{K-1}~{},\\\
&\overline{p}_{n}(\lambda)=\frac{\lambda-\overline{a}_{n-1}}{\overline{b}_{n-1}}\overline{p}_{n-1}(\lambda)-\frac{\overline{b}_{n-1}}{\overline{b}_{n-2}}\overline{p}_{n-2}(\lambda)\\\
&\qquad\;\,=\frac{\lambda-
a_{K-n}}{b_{K-(n-1)}}\overline{p}_{n-1}(\lambda)-\frac{b_{K-(n-1)}}{b_{K-(n-2)}}\overline{p}_{n-2}(\lambda)~{},\qquad
n\geq 2~{}.\end{split}$ (1.168)

Now, in the same way that recursions (1.81) and (1.146) are mapped to each
other through (1.147), the recursions defining the reversed characteristic
polynomials (1.153) and the reversed Krylov polynomials (1.168) are mapped to
each other through202020This time, we prefer not to use the convention
“$\overline{b}_{0}\equiv 1$”, since a putative extension of the relation
between original and reversed Lanczos coefficients given in (1.161) to $n=0$
would suggest to associate $\overline{b}_{0}\equiv b_{K}=0$, which might
induce to confusion.:

$\begin{split}&\overline{R}_{0}(\lambda)=\overline{p}_{0}(\lambda)=1~{},\qquad\overline{R}_{1}(\lambda)=\overline{p}_{1}(\lambda)=\lambda-\overline{a}_{0}=\lambda-
a_{K-1}~{},\\\
&\overline{R}_{n}(\lambda)=\Big{(}\prod_{m=1}^{n-1}\overline{b}_{m}\Big{)}\,\overline{p}_{n}(\lambda)=\Big{(}\prod_{m=1}^{n-1}b_{K-m}\Big{)}\,\overline{p}_{n}(\lambda)~{},\qquad
2\leq n\leq K~{}.\end{split}$ (1.169)

In particular, setting $n=K$, we expect to obtain the full characteristic
polynomial of the restriction of $H$ to the Krylov space of the original seed
$|\Omega\rangle$, as stated in (1.151). Combining this with the recursion
(1.169) yields

$\Big{(}\prod_{m=1}^{K-1}b_{K-m}\Big{)}\,\overline{p}_{K}(\lambda)=\Big{(}\prod_{m=1}^{K-1}b_{m}\Big{)}\,p_{K}(\lambda)~{}.$
(1.170)

The products on sides of the equality involve the full sequence of
$b$-coefficients, which are all non-vanishing. This implies

$\overline{p}_{K}(\lambda)=p_{K}(\lambda)~{}.$ (1.171)

The interesting feature of these reversed families of Krylov basis elements
and polynomials is that, since they sweep backwards their original
counterparts, the vector $|\overline{K}_{n}\rangle$ will be mostly supported
over the eigenspaces over which $|K_{K-1-n}\rangle$ is supported, which in the
case of the discussion at the beginning of section 1.7 would be those
corresponding to the $n$ smallest eigenvalues of $H$ represented in Krylov
space. Therefore, the roots of the reversed Krylov polynomials
$\overline{p}_{n}(\lambda)$ will, this time, give numerical approximations to
increasingly larger eigenvalues, as we shall verify in the numerical
illustration presented in section 1.8.

This reversed Lanczos algorithm remains, nevertheless, an academic exercise,
and cannot be used as a resource-saving protocol to approximate the smallest
eigenvalues of the spectrum (instead of the largest), as in order to construct
this reversed Krylov basis one needs to have constructed in the first place
the full original Krylov basis of the seed $|\Omega\rangle$, since the seed of
the former is the last element of the latter. Rather, the discussion serves as
an illustration of the fact that, once the Krylov space associated to a given
vector $|\Omega\rangle$ has been constructed, it is not possible to exit it by
applying the Lanczos procedure to any vector contained within that Krylov
space, because the action of $H$ on such a space is closed, by construction.
As an alternative example, one may attempt to seed the Lanczos algorithm with
any other element of the Krylov basis, namely
$|\overline{K}_{0}\rangle=|K_{n_{0}}\rangle$ for some
$n_{0}\in[0,K-1]\bigcap\mathds{Z}$: In such a case, analytical expressions
rapidly become cumbersome, but one can verify that
$|\overline{K}_{n}\rangle\in\text{span}\left\\{|K_{m}\rangle\right\\}_{m=n_{0}-n}^{n_{0}+n}$,
i.e. the new Krylov basis explores symmetrically the original Krylov basis
around the new seed 212121Modulo eventual bounces of the terms in the linear
combination if it reaches the left or right edges of the original Krylov
basis, that is, if $m$ in a term $|K_{m}\rangle$ contributing to
$|\overline{K}_{n}\rangle$ reaches $0$ (left edge) or $K-1$ (right edge): When
this occurs, a new application of $H$ to the conflictive term will yield terms
proportional to $|K_{0}\rangle$ and $|K_{1}\rangle$ (resp. $|K_{K-1}\rangle$
and $|K_{K-2}\rangle$), which is what we mean by a bounce of the support of
the linear combination at the edge of Krylov space..

#####  1.7.4 Generic behavior of the Lanczos algorithm

The discussion below the example spectrum (1.128) stated that, for such a
particular instance of a positive spectrum with a marked hierarchy between the
eigenvalues, the profile of the vectors $|K_{n}\rangle$ in the eigenbasis of
$H$ is such that the first Krylov elements are peaked near eigenvectors
corresponding to the largest eigenvalues. For a generic, potentially not
positive-definite spectrum, inspection of expressions like (1.133) might
appear to suggest that the relevant eigenvalues for the initial Krylov
elements are those with the largest absolute value, as the phase of the
coordinates of a vector over an orthonormal basis is not relevant when it
comes to evaluating the contribution of a given direction to the total norm.
This, however, cannot be a generic statement about the behavior of the Lanczos
algorithm for any hermitian operator $H$ with an arbitrary spectrum, as can be
seen from the symmetry properties of the recursion method discussed in section
1.6: The Krylov elements are invariant under constant shifts of $H$ (1.117),
which also shift the spectrum but leave invariant the eigenvectors; therefore,
the profile of $|K_{n}\rangle$ in the eigenbasis is invariant under constant
shifts of the spectrum, but the identification of the eigenvalue with the
largest absolute value is not a shift-invariant statement, so this cannot be a
valid criterion to identify the dominant directions of a Krylov element.

As an example of the above discussion, we can take the spectrum in (1.128) and
a seed vector which is, for simplicity, initially peaked near the direction
with the largest eigenvalue $\widetilde{\lambda}_{0}$. The discussion at the
beginning of section 1.7 implied that the first Lanczos step would effectively
remove the direction of the largest eigenvalue,
$|\widetilde{\lambda}_{0}\rangle$, so that $|K_{1}\rangle$ is peaked near the
direction of $|\widetilde{\lambda}_{1}\rangle$, the second largest eigenvalue,
and so forth. We may now perform a shift of the full spectrum by the value of
the originally largest eigenvalue, i.e. a shift (1.117) with
$\alpha=\widetilde{\lambda}_{0}$:

$\overline{\widetilde{\lambda}}_{j}=\widetilde{\lambda}_{j}-\widetilde{\lambda}_{0}~{},$
(1.172)

which results in the sign-flipped hierarchy

$0=\overline{\widetilde{\lambda}}_{0}\gg\overline{\widetilde{\lambda}}_{1}\gg\dots\gg\overline{\widetilde{\lambda}}_{K-1}$
(1.173)

and, therefore, in the shifted spectrum the eigenvalue with the largest
absolute value is $\overline{\widetilde{\lambda}}_{K-1}$. However, since both
the Krylov elements and the eigenvectors are invariant under this shift, it
will still hold that $|\overline{K}_{0}\rangle$ is peaked near
$|\overline{\widetilde{\lambda}}_{0}\rangle$, $|\overline{K}_{1}\rangle$ near
$|\overline{\widetilde{\lambda}}_{1}\rangle$, etc, in apparent contradiction
with our earlier qualitative considerations.

The way out from this apparent paradox is to rephrase the practical effect of
a Lanczos step in terms that are explicitly invariant under sign flips and
constant shifts or rescalings of $H$, and which reduce to the identification
of the largest eigenvalues in the particular case of (1.128). For this, we
consider a generic Lanczos step with $n\geq 2$, which we restate here:

$|A_{n}\rangle=(H-a_{n-1})|K_{n-1}\rangle-b_{n-1}|K_{n-2}\rangle~{}.$ (1.174)

The new, non-normalized Krylov element is constructed in (1.174) by modifying
$H|K_{n-1}\rangle$ with two subtraction terms, whose effect we may describe
qualitatively:

  * •

The coefficient $a_{n-1}$ is given by

$a_{n-1}=\langle K_{n-1}|H|K_{n-1}\rangle~{},$ (1.175)

and as such it gives the (weighted) average value of the eigenvalues
effectively probed by $|K_{n-1}\rangle$. Thus, the effect of the term
$-a_{n-1}|K_{n-1}\rangle$ can be analyzed from the inspection of

$(H-a_{n-1})|K_{n-1}\rangle=\sum_{j=0}^{K-1}\mathcal{K}_{j}^{(n-1)}(\widetilde{\lambda}_{j}-a_{0})|\widetilde{\lambda}_{j}\rangle~{},$
(1.176)

where $\mathcal{K}_{j}^{(n-1)}$ are the coordinates of $|K_{n-1}\rangle$ over
the eigenbasis. Considering only those directions
$|\widetilde{\lambda}_{j}\rangle$ that contain most of the norm of this Krylov
element, the eigenvalues that will get more affected by the subtraction
$\widetilde{\lambda}_{j}-a_{0}$ will be those belonging to regions of the
spectrum where the eigenvalues accumulate, as $a_{0}$ will be numerically
close to them. Consequently, this subtraction will substantially reduce the
projection of the vector over the corresponding eigenspaces.

  * •

Broadly speaking, the subtraction term $-b_{n-1}|K_{n-2}\rangle$ in (1.174)
serves the purpose of avoiding the previous Krylov element from reemerging
when $H$ is applied to $|K_{n-1}\rangle$, in order to ensure orthogonality of
the Krylov basis. For instance, in the step $n=1$, given in (1.35), a term of
this sort is not required because there is no $|K_{-1}\rangle\equiv 0$ term
requiring to be subtracted.

Putting these two considerations together, the more correct (yet qualitative)
description of the net effect of the subtraction terms in the $n$-th Lanczos
step can now be stated. The projections more drastically reduced are those
along the directions of eigenvectors verifying that:

  * i)

$|K_{n-1}\rangle$ has a more significant overlap with them.

  * ii)

Their associated eigenvalues belong to a region of the spectrum effectively
probed by $|K_{n-1}\rangle$ where the eigenvalues accumulate more.

Furthermore, directions belonging to the linear span of the previous Krylov
elements do not reemerge in subsequent Lanczos steps.

Consequently, isolated eigenvalues are the first to be resolved efficiently in
the scheme of successive approximations using progressive Krylov space
truncations, as long as the seed state overlapped significantly with their
eigenspace, and small eigenvalue differences take longer to be resolved and
require more numerical accuracy. This statement is adequately invariant under
shifts or rescalings of $H$ in the sense that eigenvalues belonging to densely
or sparsely populated regions of the spectrum (relative to the total spectral
width, or to the average eigenvalue spacing) are mapped under a shift or a
rescaling to eigenvalues in the corresponding regions of the new spectrum
(defined relatively with respect to the new spectral width or spacing). The
statement is also invariant under a sign flip in the spectrum because this
transformation does not change the distance between eigenvalues. For instance,
in the shifted, negative semi-definite spectrum (1.172), the hierarchy of
absolute values is reversed with respect to that in (1.128), as can be seen in
(1.173), but it still holds that, in order, the more isolated eigenvalues are
those with $j=0,\,1,\,\dots,\,K-1$, both for $\widetilde{\lambda}_{j}$ and for
$\overline{\widetilde{\lambda}}_{j}$.

On can think of the Lanczos algorithm as an approximation method that resolves
eigenvalue differences. Given the mean eigenvalue spacing $\Delta$ in the
spectrum of $H$, we can define the normalized distances between consecutive
eigenvalues,

$s_{n}:=\frac{\lvert\lambda_{n}-\lambda_{n+1}\rvert}{\Delta}~{},$ (1.177)

where we have implicitly assumed that the eigenvalues $\lambda_{n}$ are sorted
so that $\lambda_{0}\geq\lambda_{1}\geq\dots\geq\lambda_{D-1}$. The quantity
$s_{n}$ is explicitly invariant under both shifts and rescalings of $H$, as
well as a sign flip of the spectrum. With this, we can generically say that,
assuming the use of a seed vector $|\Omega\rangle$ probing all eigenspaces
democratically, it will take fewer Lanczos steps to resolve eigenvalue pairs
$\left(\lambda_{n},\lambda_{n+1}\right)$ with a larger value of $s_{n}$, while
those featuring a smaller normalized difference will require finer
approximations where the Krylov truncation dimension $n_{*}$ is closer to $K$.

All these qualitative claims will be illustrated in next section, combining
different spectra and seed vectors with different starting profiles over the
eigenbasis.

For the eventual applications to physics, and particularly to gravity, of
interest in this Thesis, approximation methods based on the Lanczos algorithm
will not play a central role. We will in general assume the capability of
building the full Krylov basis and sequences of Lanczos coefficients (either
numerically or analytically) and use this information to arrange the Hilbert
space in a manner that will be useful for studying systematically the time
evolution of a given initial state or operator, as will be described in detail
in 2.1. Nevertheless, in the cases in which $H$ is the time evolution
generator (either the Hamiltonian for state evolution, or the
Liouvillian222222The Liouvillian, defined in equation (2.2), is an operator
acting over the space of operators, consisting on the adjoint action of the
Hamiltonian. This is the correct time evolution generator for operators in the
Heisenberg picture for operator evolution), the analysis provided throughout
the present Chapter may still be valuable in the sense that it sheds light on
how successive Krylov elements probe the different gravity microstates in the
available Hilbert space. The previous conclusion stating that the last Krylov
elements probe finer and finer level differences in the spectrum will, for
instance, turn out to be insightful in the context of state and operator
dynamics in quantum-chaotic systems.

####  1.8 Numerical examples

In this section we shall provide three numerical examples of the application
of the Lanczos algorithm, which serve to illustrate how Krylov elements probe
the different eigenvectors of $H$ depending on the seed vector and on the
structure of the spectrum itself, reinforcing the discussions in section 1.7,
especially those in its subsection 1.7.4. The three toy models considered are:

  1. 1.

An operator $H$ whose spectrum features the exponential hierarchy (1.129) with
$\lambda=2$ and a seed vector $|\Omega\rangle$ which is exponentially peaked
on the largest eigenvalue, reinforcing such a hierarchy:

$|\Omega\rangle=\frac{1}{N(\lambda)}\sum_{j=0}^{K-1}\lambda^{-j}|\widetilde{\lambda}_{j}\rangle~{},$
(1.178)

where the factor $N(\lambda)$ ensures normalization and is given by

$N(\lambda)=\sqrt{\sum_{j=0}^{K-1}\lambda^{-2j}}~{}.$ (1.179)

A simpler version of this model was presented in the original work by Lanczos
[19] in order to illustrate the exchange in dominance of the different
eigenvectors contributing to the successive Krylov elements.

It is worth to note that, in the context of quantum mechanics and holography,
a state with an exponential profile over the energy basis like (1.178) is
reminiscent of a (non-factorizable) version of the thermofield double state
[86], which is the gravity microstate describing a two-sided black hole, and
can be also seen as the purification of the thermal state. However, for
$\lambda>1$, the vector (1.178) is peaked near the largest232323In this
section we use an indexing convention such that $\widetilde{\lambda}_{0}$ is
the largest, rather than the smallest, eigenvalue. This choice was sensible
for the discussion of interest, as in the examples considered
$\widetilde{\lambda}_{0}$ was amongst the first eigenvalues to be reproduced
in the scheme of successive approximations, being numerically comparable to
the first few Lanczos coefficients, as Figures A.2, A.6 and A.10 will
illustrate. In quantum-mechanical problems it is customary to reserve the
smallest index for the ground state of the Hamiltonian, and we shall stick to
that convention in the subsequent Chapters of this Thesis. eigenvalue
$\widetilde{\lambda}_{0}$, while the actual thermofield double state at finite
temperature is always peaked on the ground state.

  2. 2.

The same operator $H$ as in the previous case, but probed with a different
seed vector, this time with a strictly flat profile over the eigenbasis:

$|\Omega\rangle=\frac{1}{\sqrt{K}}\sum_{j=0}^{K-1}|\widetilde{\lambda}_{j}\rangle~{}.$
(1.180)

This might be thought of as a more realistic example, in which the seed
$|\Omega\rangle$ is not necessarily correlated with the eigenvectors of $H$
and thus probes all of them equally242424A vector whose coordinates over the
eigenbasis are randomly drawn from independent and identical distributions
might be a better generalization of this, but for the purpose of the intended
analysis the simpler instance with constant coefficients will be insightful
enough..

The vector (1.180) can be obtained as the $\lambda\to 1$ limit of (1.178), and
it can be thought of as a toy version of the infinite-temperature thermofield
double state.

  3. 3.

In this case, the seed kept a flat profile (1.180), but the spectrum of $H$ in
(1.129) was tweaked to feature a quasi-degeneracy near the largest eigenvalue:

$\begin{split}&\widetilde{\lambda}_{0}=\widetilde{\lambda}_{1}+\lambda~{},\\\
&\widetilde{\lambda}_{j}=\lambda^{K-j}~{},\qquad 1\leq j\leq
K-1~{},\end{split}$ (1.181)

still with $\lambda=2$.

Since all the seed vectors (1.178) and (1.180) have been written directly in
coordinates over the Krylov eigenspace representatives (projections over other
potential eigenspaces of $H$ being null by definition of an eigenspace
representative), constructing numerically these vectors amounts to
initializing column vectors in a space of dimension $D\equiv K$. In all the
analyses the Krylov dimension was taken to be $K=20$ and we worked in
coordinates over the eigenbasis of $H$, so that the coordinates of
$|\Omega\rangle$ could be directly read off from (1.178) and (1.180), and $H$
took the form of a diagonal matrix with entries given by the eigenvalues. This
fully defines the seed and operator in a given coordinate system, and no more
information is required in order to run the Lanczos algorithm.

Models 1 and 2 serve the purpose of illustrating the discussion at the
beginning of section 1.7 on a positive-definite spectrum with a parametrically
controlled hierarchy, where the successive Krylov space truncations serve to
gradually approximate numerically the eigenvalues of $H$ from the largest to
eventually the smallest. On the other hand, model 3 is an example of the more
general behavior announced in section 1.7.4: the largest eigenvalues of the
spectrum are very close to each other (much closer than the average eigenvalue
spacing), and consequently it takes various Lanczos steps to resolve them
accurately, despite being the biggest: This supports the claim that the
relevant feature determining how fast eigenvalues are resolved is not their
absolute value, but whether they are isolated or not (compared to the rest of
the eigenvalues probed by the seed).

For each model, a numerical analysis demonstrating the various aspects of the
Lanczos algorithm presented throughout this Chapter was performed.
Specifically, the steps of the analysis were the following:

  1. 1.

Application of the Lanczos algorithm for the construction of all the Krylov
elements $|K_{n}\rangle$ and Lanczos coefficients $a_{n}$, $b_{n}$. In order
to estimate quantitatively what eigenvectors are probed, and to what extent,
by each Krylov element, the following indicators describing the structure of a
vector $|\chi\rangle$ in coordinates over a given basis (in this case, the
basis of eigenspace representatives in Krylov space) were used:

     * •

Average position of a given vector $|\chi\rangle$ on the basis:

$P(|\chi\rangle):=\sum_{j=0}^{K-1}j\,{\lvert\langle\widetilde{\lambda}_{j}|\chi\rangle\rvert}^{2}~{}.$
(1.182)

     * •

Participation ratio (PR): It estimates the effective number of basis elements
contributing to the norm of a certain vector $|\chi\rangle$, hence its name.
It requires of the construction of an intermediary quantity, called the
Inverse Participation Ratio (IPR):

$IPR(|\chi\rangle):=\sum_{j=0}^{K-1}{\lvert\langle\widetilde{\lambda}_{j}|\chi\rangle\rvert}^{4}~{},$
(1.183)

from which the PR can be computed as

$PR(|\chi\rangle)=\frac{1}{IPR(|\chi\rangle)}~{}.$ (1.184)

If $|\chi\rangle$ has unit norm, this quantity satisfies $0\leq
PR(|\chi\rangle)\leq K$ [106].

  2. 2.

Using the Lanczos coefficients computed and the polynomial recursion (1.81),
the Krylov polynomials $\left\\{p_{n}(\lambda)\right\\}_{n=0}^{K}$ were
constructed explicitly. Next, the roots of each Krylov polynomial were
numerically determined; these give the successive numerical approximations to
the eigenvalues of $H$ that one obtains from the progressive Krylov space
truncations of dimension $n_{*}$, verifying $1\leq n_{*}\leq K$. For each
truncated Krylov subspace of dimension $n_{*}$, the roots of the polynomial
$p_{n_{*}}(\lambda)$ yield $n_{*}$ approximate eigenvalues,
$\left\\{\widetilde{\lambda}^{(n_{*})}_{j}\right\\}_{j=0}^{n_{*}-1}$. When
$n_{*}=K$, the truncated Krylov subspace becomes equal to the full Krylov
space, $p_{K}(\lambda)$ is proportional to the characteristic polynomial of
$H$, and its roots were verified to be equal (within the working numerical
precision) to the exact eigenvalues of $H$.

  3. 3.

Within each Krylov space truncation, the approximate eigenvectors associated
to the approximate eigenvalues obtained in the previous point were computed
via (1.140), where a-priori knowledge of $\widetilde{\Omega}_{j}^{*}$ is not
required252525Even if in these specific toy models we did have such a
knowledge, since the seed vector was directly constructed in coordinates over
the eigenbasis, which give the coefficients $\widetilde{\Omega}_{j}$. In a
practical situation, such coordinates are not known a priori because the goal
of the problem is precisely to construct the eigenbasis., since it amounts to
a normalization constant of the vector. These approximate eigenvectors were
compared to the exact ones computing their position (1.182) and participation
ratio (1.184) over the eigenbasis. Since all computations were performed in
coordinates over the latter basis, exact eigenvectors take the form of
Kronecker deltas, and it was verified that approximate eigenvectors reduced to
this shape in the last truncation $n_{*}=K$.

  4. 4.

As an “academic exercise”, we constructed the reversed Krylov polynomials
$\overline{p}_{n}(\lambda)$ implementing the recursion (1.168). Computing
their roots, we obtained approximations to the spectrum within the successive
Krylov space truncations of dimension $n_{*}$, spanned by
$\left\\{|\overline{K}_{n}\rangle=|K_{K-1-n}\rangle\right\\}_{n=0}^{n_{*}-1}$.
We verified that they reconstructed the spectrum of $H$ in the opposite order
to the ordinary Krylov space truncations in step 2, even though with a
slightly slower convergence.

  5. 5.

For the sake of completeness, the approximate eigenvectors corresponding to
the approximate eigenvalues in the previous step were constructed analogously
to the analysis in step 3 and compared to the exact eigenvectors, which are
still recovered when $n_{*}=K$.

The method by Lanczos proposes to solve the eigenvalue problem restricted to
Krylov space in terms of the basis
$\left\\{|K_{n}\rangle\right\\}_{n=0}^{K-1}$ rather than the (non orthonormal)
basis $\left\\{H^{n}|\Omega\rangle\right\\}_{n=0}^{K-1}$ because the
construction of the latter is numerically unreliable due to the uncontrolled
amplification of the largest eigenvalues every time $H$ acts on the vector.
However, the algorithm is still not exempt from numerical instabilities
inherent to its recursive nature: Finite-precision errors may build up accross
the successive Lanczos steps, resulting in the eventual loss of orthogonality
of the constructed Krylov elements. There exist re-orthogonalization
algorithms [6] that may be used to fix these issues, which were studied in
detail and implemented for the first time in the context of Krylov complexity
for quantum many-body systems in [1, 2, 3], works in which these algorithms
were combined with the use of high-performance computing facilities that
allowed the exploration of large Hilbert spaces using double-floating-point
precision. However, a deep discussion on re-orthogonalization techniques was
not required for the toy models that shall be presented here: In this case,
the original Lanczos algorithm was run using the software Mathematica [107] at
a sufficiently high numerical precision, whose important memory and time
requirements are at the origin of the smallness of the Krylov dimension $K=20$
chosen. Nevertheless, with this value of $K$, the parametric separation in the
spectrum (1.129) is sufficiently pronounced for the results to be instructive,
even if, as announced above, the scale parameter was set to $\lambda=2$: The
ratio between the largest and the smallest eigenvalue of the spectrum in
models 1 and 2 is $\lambda^{K-1}=2^{19}=524288$, and the use of high-precision
arithmetic is therefore required in order to prevent the eigenvector of the
largest eigenvalue from being spuriously amplified after it had been
effectively subtracted in the initial Lanczos steps.

The numerical results are depicted in Figures A.1 to A.12, which have been
collected in Appendix A. We shall discuss them in detail for each model next.

#####  1.8.1 Model 1. Exponentially peaked seed vector

Applying the Lanczos algorithm to the seed (1.178) yields a Krylov basis whose
properties with respect to the eigenbasis can be analyzed by the means of the
functions (1.182) and (1.184) defined previously. The results, depicted in
Figure A.1, confirm the expectation that each Lanczos step effectively removes
from the linear combination the eigenspace corresponding to the largest
eigenvalue dominating in the previous iteration. The effect is mainly due to
the fact that the seed vector is already very localized near
$|\widetilde{\lambda}_{0}\rangle$ and, as discussed in section 1.7, each
Lanczos step removes the dominant direction in the previous Krylov element.

Figure A.1 appears to suggest that the Krylov basis elements are already
almost eigenstates of $H$, since they are very localized near the
corresponding eigenvectors. This observation is in qualitative agreement with
the tridiagonal (hence, almost diagonal) form of $H$ when it is written in
coordinates over the Krylov basis (1.79). In fact, since the Lanczos
coefficients are the items of such a matrix representation, they already
provide an order-of-magnitude estimate of the eigenvalues of $H$, as
illustrated in Figure A.2.

In Figure A.3 we can observe the successive approximations to the spectrum of
$H$ and to the corresponding eigenvectors obtained in the scheme of
progressive truncations of Krylov space, as a function of the dimension of the
Krylov subspace considered, $n_{*}$. When $n_{*}=1$ only one eigenvalue is
obtained, numerically close to the largest eigenvalue of $H$. Progressively,
smaller and smaller eigenvalues start to appear as $n_{*}$ is increased.
Consistently, the approximate eigenvectors gradually converge to Kronecker
deltas in the eigenbasis, centered in the position of the exact eigenvector
they correspond to, and with a participation ratio equal to $1$ when
$n_{*}=K$.

Finally, Figure A.4 depicts the result of successive approximations to the
spectrum obtained from the family of reversed Krylov polynomials. Correctly,
they start approximating the smaller eigenvalues and their corresponding
eigenvectors, and yield the exact spectrum when the truncation is maximal,
$n_{*}=K$.

#####  1.8.2 Model 2. Flat seed vector

The result of the application of the Lanczos algorithm to the seed (1.180)
with an operator $H$ whose spectrum features the exponential hierarchy (1.129)
also illustrates the exchange of dominance of the different eigenvectors, in a
setup in which the seed is not correlated with the spectrum in the sense that
its profile over the eigenbasis does not reinforce or counter the spectral
hierarchy. The initial Krylov element $|K_{0}\rangle$, coinciding with the
seed vector, is a flat linear superposition of all eigenvectors and, in
agreement with (1.132), $a_{0}$ is the arithmetic average of the eigenvalues
of $H$, slightly numerically biased towards lower eigenvalues because, as a
result of the exponential hierarchy, they are closer to each other than the
larger ones, which are more isolated. Consequently, the subtraction
$\widetilde{\lambda}_{j}-a_{0}$ in (1.133) is maximal for $j=0$, implying that
the Krylov element $|K_{1}\rangle$ is sharply peaked near
$|\widetilde{\lambda}_{0}\rangle$. Similarly, subsequent Krylov elements are
peaked around the eigenvectors corresponding to smaller and smaller
eigenvalues, as illustrated in Figure A.5. Figure A.6 depicts the comparison
between the Lanczos coefficients and the eigenvalues of $H$, featuring a
somewhat significant discrepancy between $a_{0}$ and $\widetilde{\lambda}_{0}$
due to the fact that the former is the arithmetic spectral average. Figure A.7
depicts the convergence of the approximate eigenvalues and eigenvectors as a
function of the Krylov space truncation: In each Krylov subspace, the lowest
approximate eigenvalue is close to the arithmetic average of the eigenvalues
that are left out of the truncated subspace, as one can confirm by observing
that the corresponding approximate eigenvector receives contributions from the
exact eigenvectors of all such low-lying eigenvalues. Finally, Figure A.8
illustrates that the reconstruction of the spectrum of $H$ in the reverse
order is still achieved by the use of the reversed Krylov polynomials.

#####  1.8.3 Model 3. Flat seed vector, spectrum with a quasi-degeneracy

Probing the spectrum (1.181) with a flat seed (1.180) through the Lanczos
algorithm illustrates the fact that the recursion method takes longer to
resolve eigenvalues in areas where they accumulate, regardless of whether
their absolute value is large or small, since this is not a translationally-
invariant feature, as argued in section 1.7.4. Figure A.9 depicts the
structure of the Krylov elements: While $|K_{0}\rangle=|\Omega\rangle$ is a
flat superposition of all exact eigenvectors, $|K_{1}\rangle$ is a linear
combination that involves both $|\widetilde{\lambda}_{0}\rangle$ and
$|\widetilde{\lambda}_{1}\rangle$, the eigenvectors of the quasi-degenerate
eigenvalues, not being able to resolve them; eventually, $|K_{7}\rangle$ is
also some linear combination of $|\widetilde{\lambda}_{0}\rangle$ and
$|\widetilde{\lambda}_{1}\rangle$, so that the truncations with dimension
$n_{*}\geq 8$ start to show two approximate eigenvalues very close to each
other of the order of $\widetilde{\lambda}_{0}$, having therefore effectively
resolved the quasi-degeneracy. This can be observed in Figure A.11. For
completeness, Figures A.10 and A.12 depict, respectively, the comparison
between Lanczos coefficients and eigenvalues, and the convergence results upon
applying the reversed Lanczos algorithm.

####  1.9 Combinatorial relations and Lanczos coefficients

There exists [20, 108, 78] a bijective map between the set of Lanczos
coefficients $a_{n},b_{n}$ and the sequence moments of the operator $H$,
defined as:

$M_{k}:=\langle\Omega|H^{k}|\Omega\rangle~{}.$ (1.185)

The correspondence is of a combinatorial nature, which allows for some
analytical estimates and bounds, as we shall see for instance in section 2.3,
but which can also be systematically implemented on a computer. Let us study
each direction of the correspondence separately.

#####  1.9.1 From Lanczos coefficients to moments

This direction may appear to be the least interesting one, as in practice one
can often easily compute the moments $M_{k}$ and needs the Lanczos
coefficients. However, in section 2.3 it will reveal itself as a useful tool
to establish bounds on the growth of the $b_{n}$ coefficients as a function of
$n$.

The cleanest way to understand how to obtain moments from Lanczos coefficients
[20, 78, 109] is to consider the tridiagonal form of $H$ in coordinates over
the Krylov basis, given in (1.79). Such an expression can be written
algebraically as

$H=\widehat{a}+\widehat{a}^{\dagger}+\widehat{n}~{},$ (1.186)

where, borrowing the conventional notation from the simple quantum harmonic
oscillator, we have defined the ladder-like operators262626Notationally, the
hat in the definition of these operators is used to distinguish them from the
$a$-coefficients and the index $n$, symbols which have been used previously in
the text. $\widehat{a},~{}\widehat{a}^{\dagger}$ and the number-like operator
$\widehat{n}$:

$\widehat{a}:=\sum_{n=0}^{K-2}b_{n+1}\,|K_{n}\rangle\langle
K_{n+1}|~{},\qquad\widehat{n}:=\sum_{n=0}^{K-1}a_{n}\,|K_{n}\rangle\langle
K_{n}|~{}.$ (1.187)

These operators are reminiscent of the ladder and number operators of the
harmonic oscillator because $\widehat{a}$ and $\widehat{a}^{\dagger}$ decrease
(resp. increase) the position in the Krylov basis by one unit, while
$\widehat{n}$ preserves it. However, the algebra of the operators at hand is
determined by the specific value of the Lanczos coefficients, and in fact they
need not close an algebra in general.

Now, using that $|\Omega\rangle=|K_{0}\rangle$, we can rewrite the moments
(1.185) in a more suggestive manner:

$M_{k}=\langle
K_{0}|{\Big{(}\widehat{a}+\widehat{a}^{\dagger}+\widehat{n}\Big{)}}^{k}|K_{0}\rangle~{}.$
(1.188)

Expanding the power inside of the bra-ket we will obtain a sum of monomials of
degree $k$, consisting of powers of $\widehat{a},~{}\widehat{a}^{\dagger}$ and
$\widehat{n}$, sandwiched by $\langle K_{0}|$ and $|K_{0}\rangle$. It is
possible to understand intuitively how to compute in a diagrammatic fashion
the expectation value of each monomial in the zeroth state272727Since we are
borrowing terminology from the quantum harmonic oscillator, we shall also
refer to vectors as states, and to diagonal matrix elements of operators as
expectation values in the corresponding state. But we shall keep in mind that
the algebraic discussions throughout the present Chapter are applicable to
generic Hilbert spaces, potentially outside the realm of quantum mechanics. of
the Krylov basis: Starting from $|K_{0}\rangle$, we apply in an ordered
fashion the operators composing a given monomial, which have the following
effect:

  * •

$\widehat{a}$ sends $|K_{n}\rangle\longmapsto b_{n}~{}|K_{n-1}\rangle$.

  * •

$\widehat{a}^{\dagger}$ sends $|K_{n}\rangle\longmapsto
b_{n+1}~{}|K_{n+1}\rangle$.

  * •

$\widehat{n}$ performs the operation $|K_{n}\rangle\longmapsto
a_{n}~{}|K_{n}\rangle$.

Lastly, after having applied the full monomial to $|K_{0}\rangle$, the inner
product between the resulting state and $\langle K_{0}|$ is computed in order
to obtain the sought expectation value; if the former state is not itself
proportional to $|K_{0}\rangle$, the result will be zero. Additionally, the
action of the monomial on $|K_{0}\rangle$ will vanish if in an intermediary
step of the sequence of operations we encounter either
$\widehat{a}|K_{0}\rangle=0$ or $\widehat{a}^{\dagger}|K_{K-1}\rangle=0$.
Conceiving the positions over the Krylov basis as levels in a vertical
direction, and the power $k$ (giving the degree of the monomial) as a total
number of horizontal steps, the above protocol can be represented by Motzkin
paths [110]: These are paths of $k$ steps that depict concatenations of
positions $\left\\{P_{l}=(l,n_{l})\right\\}_{l=0}^{k}$ in a two-dimensional
grid starting from the point $P_{0}=(0,0)$ and ending in $P_{k}=(k,0)$ in
which $n_{l+1}$ is either $n_{l}+1$, $n_{l}-1$ or $n_{l}$, with the condition
that $n_{l}\geq 0$ (i.e. no path goes below the zero level). The contribution
of a full Motzkin path, giving the expectation value of a given monomial of
ladder operators, can be evaluated assigning to it a product of Lanczos
coefficients, where the index of each coefficient is dictated by each one of
the steps $P_{l}\longmapsto P_{l+1}$ according to a rule inherited from the
sequence of operations described above:

  * •

A descending step $(l,n_{l})\longmapsto(l+1,n_{l}-1)$ is evaluated as
$b_{n_{l}}$.

  * •

An ascending step $(l,n_{l})\longmapsto(l+1,n_{l}+1)$ is evaluated as
$b_{n_{l}+1}$.

  * •

A horizontal step $(l,n_{l})\longmapsto(l+1,n_{l})$ evaluates to $a_{n_{l}}$.

As announced, for finite $K$, the paths need to be satisfy the additional
requirement of not reaching higher than the level $K-1$, i.e. $n_{l}\leq K-1$.
These are called restricted Motzkin paths. In the discussion that follows we
will focus on unrestricted Motzkin paths, simply referred to as Motzkin paths.

These combinatorial objects admit a rather detailed analytical treatment,
presented in [110]. In particular, the number of (unrestricted) Motzkin paths
of length $k$ is given by the Motzkin number [111], $m_{k}$:

$m_{k}=\sum_{l=0}^{\lfloor k/2\rfloor}\binom{k}{2l}C_{l}~{},$ (1.189)

where $C_{l}$ denotes the Catalan numbers,

$C_{l}=\frac{1}{l+1}\binom{2l}{l}~{},$ (1.190)

which in turn count the number of Dyck282828Note the “y”. paths [112] of
length $2l$. A Dyck path of length $2l$ is a Motzkin path of the same length
with no horizontal steps (which is the reason why they can only have an even
length). For future reference, we may give the asymptotic behavior of both
numbers for large length [112, 113]:

$m_{k}\sim\frac{1}{2\sqrt{\pi}}{\left(\frac{3}{k}\right)}^{3/2}3^{k}~{},\qquad
C_{k}\sim\frac{2^{2k}}{k^{3/2}\sqrt{\pi}}~{},$ (1.191)

for large $k$.

As an example, let us show the explicit computation of the third moment
$M_{3}$, assuming no restriction on the height of the Motzkin path (or,
equivalently, assuming $K\geq 2$), depicted diagrammatically in Figure 1.1:

$\begin{split}M_{3}&=\langle K_{0}|\widehat{n}^{3}|K_{0}\rangle+\langle
K_{0}|\widehat{a}\widehat{n}\widehat{a}^{\dagger}|K_{0}\rangle+\langle
K_{0}|\widehat{n}\widehat{a}\widehat{a}^{\dagger}|K_{0}\rangle+\langle
K_{0}|\widehat{a}\widehat{a}^{\dagger}\widehat{n}|K_{0}\rangle\\\
&=a_{0}^{3}+b_{1}^{2}a_{1}+2b_{1}^{2}a_{0}~{}.\end{split}$ (1.192)

Figure 1.1: The four nonequivalent Motzkin paths contributing to $M_{3}$, with
their corresponding evaluation. Note that the third Motzkin number given by
(1.189) is indeed $m_{3}=4$.

At this point, we note that all odd moments $M_{2l+1}$ are given by Motzkin
paths of odd length, which must necessarily involve at least a horizontal
step, since the number of ascending steps must equal that of descending steps.
As each horizontal step is evaluated by an $a$-coefficient, this immediately
implies the following corollary:

$M_{2m+1}=0\qquad\forall~{}m=0,\dots,n\qquad\Longleftrightarrow\qquad
a_{m}=0\qquad\forall~{}m=0,\dots,n~{}.$ (1.193)

In particular, all $a$-coefficients will vanish if and only if all odd moments
are null292929This result is hard to prove inductively using the Lanczos
recursion (1.54), while it becomes self-evident when analyzed from the optics
of Motzkin paths.. In this case, only even moments $M_{2n}$ will remain being
generically non-null, and they will be exclusively given by Dyck paths of
length $2n$. This result applies in cases of particular relevance for the
subjects of study of this Thesis, such as the Lanczos coefficients associated
to quantum-mechanical observables evolving in the Heisenberg picture, as will
be detailed in Chapter 2, or the coefficients of the infinite-temperature
thermofield double state in the disorder-averaged and double-scaled SYK model,
analyzed in detail in Chapter 5 following publication [4].

#####  1.9.2 From moments to Lanczos coefficients

In most practical situations, the moments $M_{n}$ will either be available or
efficiently calculable, and the task will be to compute the Lanczos
coefficients out of them. In such a case, knowing that the relation between
moments and Lanczos coefficients is bijective, one may exploit the analytical
results in the previous section and guess Ansätze that may give at least
bounds on the profile of the Lanczos coefficients that are compatible with the
given moments. Sometimes this is sufficient to give the asymptotic behavior of
$a_{n}$ and $b_{n}$ at large $n$, as illustrated in [78, 109] and reviewed in
section 2.3. Alternatively, one can implement the direct transformation from
moments to Lanczos coefficients [20]. The main objects involved in this
transformation are Hankel matrices of moments, defined as

$H_{n}:=\begin{pmatrix}M_{0}&M_{1}&\dots&M_{n}\\\ M_{1}&M_{2}&\dots&M_{n+1}\\\
\vdots&\vdots&\ddots&\vdots\\\ M_{n}&M_{n+1}&\dots&M_{2n}\end{pmatrix}~{},$
(1.194)

whose determinant we denote as

$D_{n}:=\det H_{n}~{}.$ (1.195)

The Lanczos $a_{n}$ and $b_{n}$ coefficients can be written in terms of these
determinants as [108]:

$\begin{split}&a_{n}=\frac{\mathcal{C}_{n}^{n,~{}n-1}}{D_{n-1}}-\frac{\mathcal{C}_{n+1}^{n+1,n}}{D_{n}}~{},\\\
&b_{n}^{2}=\frac{D_{n-2}D_{n}}{D_{n-1}^{2}}~{},\end{split}$ (1.196)

where $\mathcal{C}_{n}^{i,j}$ denotes the cofactor associated to the $(i,j)$
element303030Note that $H_{n}$ is a $(n+1)\times(n+1)$ matrix, and we use an
indexing convention such that matrix elements $(H_{n})_{ij}$ are labelled by
$i,j=0,\dots,n$. of the matrix $H_{n}$ given in (1.194).

Operationally, the computational implementation of (1.196) can be made by the
means of a recursive algorithm [20]. If we have access to the moments
$\left\\{M_{n}\right\\}_{n=0}^{2n_{*}+1}$, we can compute
$\left\\{a_{n}\right\\}_{n=0}^{n_{*}}$ and
$\left\\{b_{n}\right\\}_{n=1}^{n_{*}}$. For this, we initialize the following
quantities:

$M_{k}^{(0)}=(-1)^{k}M_{k}~{},\qquad L_{k}^{(0)}=(-1)^{k+1}M_{k+1}~{},\qquad
k=0,1,\dots,2n_{*}~{}.$ (1.197)

Next, we can construct the successive lists
$\left\\{M^{(n)}_{k}\right\\}_{k=n}^{2n_{*}-n+1}$ and
$\left\\{L^{(n)}_{k}\right\\}_{k=n}^{2n_{*}-n}$, for $n=1,\dots,n_{*}$,
through the recursion:

$\begin{split}&M_{k}^{(n)}=L_{k}^{(n-1)}-\frac{L_{n-1}^{(n-1)}}{M_{n-1}^{(n-1)}}M_{k}^{(n-1)}~{},\\\
&L_{k}^{(n)}=\frac{M_{k+1}^{(n)}}{M_{n}^{(n)}}-\frac{M_{k}^{(n-1)}}{M_{n-1}^{(n-1)}}~{}.\end{split}$
(1.198)

In practice, this recursion may be implemented by nesting two loops, an outer
one for $n=0,\dots,n_{*}$ and an inner one for313131Note that the range of $k$
in $L_{k}^{(n)}$ is $k=n,\dots,2n_{*}-n$. The overlooking of this fact,
together with a wrong range for $n$ in the outer loop, constitute typos in the
reference [20]. $k=n,n+1,\dots,2n_{*}-n+1$. With this, the Lanczos
coefficients can be evaluated from:

$b_{n}^{2}=M_{n}^{(n)}~{},\qquad a_{n}=-L_{n}^{(n)}~{},$ (1.199)

for $n=0,\dots,n_{*}$ in both cases. We note that the range of $k$ for both
$M^{(n)}_{k}$ and $L^{(n)}_{k}$ at fixed $n$ is empty whenever $n\geq
n_{*}+1$, consistent with the fact that no more Lanczos coefficients $a_{n}$
or $b_{n}$ with $n>n_{*}$ can be computed out of the given finite collection
of moments $\left\\{M_{n}\right\\}_{n=0}^{2n_{*}+1}$. See [20] for more
details on this recursive algorithm and for the symbolic expression of the
first few Lanczos coefficients in terms of moments.

As argued around (1.193), whenever odd moments are zero all the $a_{n}$
coefficients vanish. In this case the transformation from moments to Lanczos
coefficients simplifies slightly: There are only $b_{n}$ coefficients, still
given by the second line of (1.196), and in order to evaluate the determinants
involved, one can implement another recursive algorithm [20], consisting on a
simplified version of (1.198). Assuming access to the even moments
$\left\\{M_{2n}\right\\}_{n=0}^{n_{*}}$, it is possible to compute
$\left\\{b_{n}\right\\}_{n=1}^{n_{*}}$ by initializing the list
$M^{(0)}_{2k}=M_{2k}$ for $k=0,\dots,n_{*}$ and progressively generating the
successive lists $\left\\{M^{(n)}_{2k}\right\\}_{k=n}^{n_{*}}$, with
$n=1,\dots,n_{*}$, by the means of the recursion:

$M^{(n)}_{2k}=\frac{M^{(n-1)}_{2k}}{b_{n-1}^{2}}-\frac{M^{(n-2)}_{2k-2}}{b_{n-2}^{2}}~{},$
(1.200)

with which the Lanczos coefficients can be evaluated from

$b_{n}^{2}=M^{(n)}_{2n}~{}.$ (1.201)

For consistency, we note that the recursion (1.200) needs to be complemented
with the boundary conditions

$b_{0}\equiv b_{-1}\equiv 1~{},\qquad M^{(-1)}_{2k}=0\quad\text{for any
}k~{}.$ (1.202)

There exist [20] recursive computational algorithms similar to (1.198) and
(1.200) for the evaluation of the moments out of the Lanczos coefficients
(i.e. the reverse transformation, which would belong to section 1.9.1), but we
shall not consider them here, as the problems of interest in this Thesis
involve the computation of Lanczos coefficients in contexts in which the
moments are known or easily computable. For the reverse direction, we shall
only consider the combinatorial relations described in section 1.9.1 because
they allow for some analytical grasp.

As a matter of fact, in computational implementations, not even the recursions
(1.198) and (1.200) shall be extensively used in our case, because they
require high precision arithmetics in order to compute reliably more than a
few Lanczos coefficients, the reason for this being that the moments in
(1.185) grow roughly exponentially in $k$, while the Lanczos coefficients are
of the order of the spectral width; hence, important numerical cancellations
between large numbers need to operate in order to yield smaller numbers (the
Lanczos coefficients) in the afore-mentioned recursions, making them difficult
to work with in practice. Due to this, in the case of the systems studied
numerically in Chapters 3 and 4, the preferable method was a direct
implementation of the Lanczos algorithm, which itself also suffers from some
numerical instabilities that are nevertheless controllable, as we shall review
in the next section.

####  1.10 Numerical instabilities of the Lanczos algorithm

As formulated in section 1.2, the Lanczos algorithm suffers from severe
numerical instabilities due to its inherent recursive nature: In a given
Lanczos step $n$, the Krylov element $|K_{n}\rangle$ is built out of
$|K_{n-1}\rangle$ and $|K_{n-2}\rangle$, as illustrated in (1.54), which are
themselves the outcomes of the two previous Lanczos steps, as a consequence of
which numerical errors due to the implementation of the algorithm with finite-
precision arithmetic accumulate through the Lanczos steps and result in the
eventual loss of orthogonality in the numerically constructed Krylov basis.

In his seminal article [19], Lanczos himself proposed to combine the recursion
method with full Gram-Schmidt (GS) steps in order to maintain orthogonality of
the basis. Nowadays, in the literature on numerical methods there exist more
systematic algorithms for curing this numerical instability (see e.g. [6, 114,
115]). The numerical works of [1, 2, 3], presented in Chapters 3 and 4 make
use of the Full Orthogonalization (FO) and Partial Re-Orthogonalization (PRO)
algorithms, which we shall describe generically in this section. Such
algorithms may allow to compute the full sequences of Lanczos coefficients and
Krylov elements at fixed, double-floating point precision for reasonably large
matrices, but they come at the cost requiring more execution time and more
memory in order to store all the Krylov basis elements323232From the point of
view of the numerical eigenvalue problem, the Krylov elements needed to be
stored anyway because they are used to obtain the eigenvectors. However, in
the physical applications of the Lanczos algorithm that we will introduce in
next Chapter (in particular, the computation of Krylov complexity), only the
Lanczos coefficients are needed, and hence this memory requirement may be
regarded as a drawback of the re-orthogonalization algorithms..

In what follows we will give a description of the FO and PRO algorithms,
providing their systematic formulation which can be readily implemented on a
computer. Within the framework of those presentations, objects like $a_{n}$,
$b_{n}$, $|A_{n}\rangle$ and $|K_{n}\rangle$ will stand for the numerically
computed coefficients or vectors, rather than their exact counterparts.

#####  1.10.1 Full Orthogonalization (FO)

This algorithm [6] systematizes the proposal by Lanczos [19] and amounts to
replacing each Lanczos step by a full GS step. That is, in every step the
operator $H$ is applied to the last Krylov element built, and the result is
explicitly orthogonalized against all of the previous basis elements computed,
eventually evaluating the Lanczos coefficients according to their original
definition. Conventionally [6], the Gram-Schmidt orthogonalization is
performed explicitly twice in order to reduce errors.

Altogether, the FO algorithm may be formulated as follows:

  * $n=0$:

    * $\bullet$

Set $|K_{0}\rangle=|\Omega\rangle$ (normalized by assumption).

    * $\bullet$

Assign $a_{0}=\langle K_{0}|H|K_{0}\rangle$.

  * $n\geq 1$:

    * $\bullet$

Set $|A_{n}\rangle=H|K_{n-1}\rangle$

    * $\bullet$

GS step: $|A_{n}\rangle\longmapsto|A_{n}\rangle-\sum_{m=0}^{n-1}\langle
K_{m}|A_{n}\rangle\,|K_{m}\rangle$.

    * $\bullet$

Repeat the previous subtraction.

    * $\bullet$

If $\sqrt{\langle A_{n}|A_{n}\rangle}=0$ break. Otherwise continue.

    * $\bullet$

Assign $b_{n}=\sqrt{\langle A_{n}|A_{n}\rangle}$.

    * $\bullet$

Set $|K_{n}\rangle=\frac{1}{b_{n}}|A_{n}\rangle$.

    * $\bullet$

Assign $a_{n}=\langle K_{n}|H|K_{n}\rangle$.

    * $\bullet$

Increase $n\longmapsto n+1$ and repeat the current step.

We remind that, just like for the original Lanczos algorithm formulated in
section 1.2, the termination condition checking whether the norm of
$|A_{n}\rangle$ is null is computationally implemented by comparing such a
quantity to a numerical threshold of choice, generically related to the
working precision.

#####  1.10.2 Partial Re-Orthogonalization (PRO)

The FO algorithm is somewhat inefficient because the Gram-Schmidt steps
increase significantly the execution time of the recursion: In every FO step
one needs to compute $n$ inner products and perform $2n$ subtractions, as
opposed to the computation of two coefficients and two subtractions per step
in the original Lanczos algorithm. Furthermore, it is an overkill method
because it always performs the explicit re-orthogonalization even in steps in
which it might not be required. Partial Re-Orthogonalization [114, 6, 115]
improves on this by running a new recursion, parallel to the Lanczos
recursion, which keeps track of how numerical errors build up in the Krylov
basis, and performs a full orthogonalization step only when such errors cross
a customizable threshold. This ensures orthogonality of the output Krylov
basis up to a controllable parameter.

We start by writing a generic Lanczos step where, as announced, the objects
written represent the numerically constructed vectors and coefficients;
because of this, we need to add an extra vector in the relation between the
computed Krylov elements that accounts for the accumulated numerical error,
which deviates them from their exact counterparts and makes them fail to
fulfill exactly (1.54):

$b_{n}|K_{n}\rangle=(H-a_{n-1})|K_{n-1}\rangle-
b_{n-1}|K_{n-2}\rangle+|\xi_{n-1}\rangle~{},$ (1.203)

where $|\xi_{n-1}\rangle$ is the promised extra vector accounting for
numerical error. Equation (1.203) can be turned into a recursion that
estimates the buildup of the spurious overlap between different Krylov
elements (which should be orthogonal). Defining the inner product

$W_{mn}:=\langle K_{m}|K_{n}\rangle$ (1.204)

and acting with $\langle K_{m}|$ on (1.203) yields

$b_{n}W_{mn}=T_{m,n-1}-a_{n-1}W_{m,n-1}-b_{n-1}W_{m,n-2}+\langle
K_{m}|\xi_{n-1}\rangle~{},$ (1.205)

where $T_{mn}:=\langle K_{m}|K_{n}\rangle$ is the matrix element of the
restriction of $H$ to Krylov space. It may not necessarily be real, symmetric
and tridiagonal as expected from (1.79) because of the accumulation of
numerical errors. We may now relabel the indices in (1.205) as
$m\leftrightarrow n-1$, obtaining the following equivalent expression:

$b_{m+1}W_{n-1,m+1}=T_{n-1,m}-a_{m}W_{n-1,m}-b_{m}W_{n-1,m-1}+\langle
K_{n-1}|\xi_{m}\rangle~{}.$ (1.206)

Subtracting (1.206) from (1.205) and using that $T_{mn}=T_{nm}$ up to
numerical errors that we loosely absorb into the contributions involving the
vectors $|\xi_{n}\rangle$, we find a recursion between the overlaps:

$\begin{split}W_{mn}=&\frac{1}{b_{n}}\Big{\\{}b_{m+1}W^{*}_{m+1,n-1}+a_{m}W^{*}_{m,n-1}+b_{m}W^{*}_{m-1,n-1}-a_{n-1}W_{m,n-1}-b_{n-1}W_{m,n-2}\Big{.}\\\
&\Big{.}+\langle K_{m}|\xi_{n-1}\rangle-\langle
K_{n-1}|\xi_{m}\rangle\Big{\\}}\equiv\frac{1}{b_{n}}\Big{\\{}\widetilde{W}_{mn}+\mathcal{E}_{m,n-1}\Big{\\}}~{},\end{split}$
(1.207)

where in the last step we have recast the recursion into a term
$\widetilde{W}_{mn}$ involving the computable overlaps, given in the first
line of the expression (1.207), plus an error contribution
$\mathcal{E}_{m,n-1}$ that can be read from the second line and which is in
principle unknown. Given a working machine precision $\varepsilon_{M}$, it may
be estimated as a quantity of order $\varepsilon_{M}\lVert H\rVert$, where
$\lVert H\rVert$ is the norm333333It should be thought of as the norm in
operator space inherited from the norm in the departing Hilbert space
$\mathcal{H}$. of the operator $H$:

$\mathcal{E}_{m,n-1}:=\langle K_{m}|\xi_{n-1}\rangle-\langle
K_{n-1}|\xi_{m}\rangle\approx\frac{\widetilde{W}_{mn}}{\lvert\widetilde{W}_{mn}\rvert}\cdot
2\varepsilon_{M}\lVert H\rVert~{}.$ (1.208)

Since $\mathcal{E}_{m,n-1}$ is in general a complex number, it needs to be
given a phase, and (1.208) proposes the conservative estimate of giving it the
same phase as that of $\widetilde{W}_{mn}$, so that its contribution is
maximally disruptive. Along the same lines, the factor of $2$ is introduced
because of the fact that the error contribution has been defined as the sum of
two terms, each of which are modelled to be of the same order.

The recursion (1.207) may be exploited to keep track of how spurious overlaps
between Krylov elements grow in the successive Lanczos steps. Specifically,
PRO proposes a modified Lanczos algorithm in which at every step $n$ one
computes not only the Krylov element $|K_{n}\rangle$, but also estimates the
spurious overlap with previously computed Krylov elements, $W_{mn}$ with $m<n$
by the means of (1.207).

Graphically, the algorithm computes iteratively the columns of the hermitian
matrix

$\Big{(}W_{mn}\Big{)}=\begin{pmatrix}W_{00}&W_{01}&W_{02}&\dots&W_{0,K-1}\\\
\cdot&W_{11}&W_{12}&\dots&W_{1,K-1}\\\ \cdot&\cdot&W_{22}&\dots&W_{2,K-1}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
\cdot&\cdot&\cdot&\dots&W_{K-1,K-1}\end{pmatrix}~{}.$ (1.209)

The matrix elements below the main diagonal can in principle be determined by
hermiticity; however, within a fixed column (i.e. fixed Lanczos step $n$),
they cannot be predicted in terms of the elements above the diagonal of the
previous columns (i.e. previous Lanczos steps), as they correspond to overlaps
$W_{mn}=\langle K_{m}|K_{n}\rangle$ with $m>n$, that is, overlaps with Krylov
elements that have not been generated yet. The PRO algorithm uses, at a given
Lanczos step $n$, the recursion (1.207) to estimate the spurious overlaps with
the previous basis elements, $W_{mn}$ with $m\leq n$ assuming knowledge of all
$\left\\{W_{ij},\;i=0,\dots,j,\;\forall j=0,\dots,n-1\right\\}$. It should be
noted, however, that the presence of the term $W^{*}_{m+1,n-1}$ in the cited
expression prevents it from being able to predict both $W_{n-1,n}$ and
$W_{nn}$ in terms of the above-mentioned set of inner products. The lack of
predictability of both quantities is not a problem because in the Lanczos step
(1.52) $|A_{n}\rangle$ is explicitly orthogonalized against $|K_{n-1}\rangle$
and subsequently renormalized so that $|K_{n}\rangle$ has unit norm, and hence
one can assign $W_{n-1,n}=\varepsilon_{M}$ and $W_{nn}=1$.

After computing all $W_{mn}$ with $m<n$, given a certain numerical threshold
$\varepsilon_{T}\geq\varepsilon_{M}$ of choice, the PRO algorithm will
implement a full Gram-Schmidt step whenever any of these quantities surpasses
the threshold, granting orthogonality of the output Krylov basis up to
$\varepsilon_{T}$.

All in all, the Lanczos algorithm incorporating PRO, sometimes denoted as
LanPRO [6], may be formulated as follows:

  * $n=0$:

    * $\bullet$

Set $|K_{0}\rangle=|\Omega\rangle$ (normalized by assumption).

    * $\bullet$

Assign $W_{00}=1$.

    * $\bullet$

Assign $a_{0}=\langle K_{0}|H|K_{0}\rangle$.

  * $n=1$:

    * $\bullet$

Lanczos step: $|A_{1}\rangle=(H-a_{0})|K_{0}\rangle$.

    * $\bullet$

Assign $b_{1}=\sqrt{\langle A_{1}|A_{1}\rangle}$. If $b_{1}<\varepsilon_{T}$,
break. Otherwise continue.

    * $\bullet$

Set $|K_{1}\rangle=\frac{1}{b_{1}}|A_{1}\rangle$.

    * $\bullet$

Assign $W_{01}=\varepsilon_{M}$ and $W_{11}=1$.

    * $\bullet$

Assign $a_{1}=\langle K_{1}|H|K_{1}\rangle$.

  * $n\geq 2$:

External loop for $n$:

    * $\bullet$

Lanczos step: $|A_{n}\rangle=(H-a_{n-1})|K_{n-1}\rangle-
b_{n-1}|K_{n-2}\rangle$.

    * $\bullet$

Compute a-priori b-coefficient: $b_{n}=\sqrt{\langle A_{n}|A_{n}\rangle}$. If
$b_{n}<\varepsilon_{T}$ break. Otherwise continue.

    * $\bullet$

Assign $W_{n-1,n}=\varepsilon_{M}$ and $W_{nn}=1$.

    * $\bullet$

Internal loop for $m=0,\dots,n-2$:

      * $-$

Assign, in order:

$\begin{split}&\widetilde{W}_{mn}=b_{m+1}W^{*}_{m+1,n-1}+a_{m}W^{*}_{m,n-1}+b_{m}W^{*}_{m-1,n-1}-a_{n-1}W_{m,n-1}-b_{n-1}W_{m,n-2}~{},\\\
&\mathcal{E}_{m,n-1}=\frac{\widetilde{W}_{mn}}{\lvert\widetilde{W}_{mn}\rvert}\cdot
2\varepsilon_{M}\lVert H\rVert~{},\\\
&W_{mn}=\frac{1}{b_{n}}\Big{\\{}\widetilde{W}_{mn}+\mathcal{E}_{m,n-1}\Big{\\}}~{}.\end{split}$
(1.210)

    * $\bullet$

If there is some $m\leq n-2$ such that $W_{mn}>\varepsilon_{T}$, do:

      * $-$

GS for $|A_{n-1}\rangle\longmapsto|A_{n-1}\rangle-\sum_{l=0}^{n-2}\langle
K_{l}|A_{n-1}\rangle~{}|K_{l}\rangle$.

      * $-$

Repeat the previous subtraction.

      * $-$

Recompute $b_{n-1}$. If $b_{n-1}<\varepsilon_{T}$ break. Otherwise recompute
$|K_{n-1}\rangle=\frac{1}{b_{n-1}}|A_{n-1}\rangle$, and recompute
$a_{n-1}=\langle K_{n-1}|H|K_{n-1}\rangle$.

      * $-$

GS for $|A_{n}\rangle\longmapsto|A_{n}\rangle-\sum_{l=0}^{n-1}\langle
K_{l}|A_{n}\rangle~{}|K_{l}\rangle$.

      * $-$

Repeat the previous subtraction.

      * $-$

Recompute $b_{n}$. If $b_{n}<\varepsilon_{T}$ break. Otherwise compute
$|K_{n}\rangle=\frac{1}{b_{n}}|A_{n}\rangle$, and assign $a_{n}=\langle
K_{n}|H|K_{n}\rangle$.

      * $-$

Assign $W_{l,n-1}=\delta_{l,n-1}+(1-\delta_{l,n-1})\varepsilon_{M}$ for all
$l=0,\dots,n-1$.

      * $-$

Assign $W_{l,n}=\delta_{l,n}+(1-\delta_{l,n})\varepsilon_{M}$ for all
$l=0,\dots,n$.

    * $\bullet$

Otherwise do:

      * $-$

Set $|K_{n}\rangle=\frac{1}{b_{n}}|A_{n}\rangle$.

      * $-$

Assign $a_{n}=\langle K_{n}|H|K_{n}\rangle$.

Let us make some clarifications at this point:

  * •

The numerical threshold for deciding whether a quantity is effectively zero,
$\varepsilon_{T}$, is a parameter of choice. It may be taken to be e.g.
$\varepsilon_{T}=\sqrt{\varepsilon_{M}}>\varepsilon_{M}$ (assuming
$\varepsilon_{M}<1$). The interpretation of the interplay between
$\varepsilon_{M}$ and $\varepsilon_{T}$ is that spurious overlaps are
initialized to be of the order of the working precision, $\varepsilon_{M}$,
and iteratively implementing the recursion (1.207) they are allowed to
gradually grow up to $\varepsilon_{T}$, when the GS step will be enforced.
That is, orthogonality of the output Krylov basis is granted up to errors of
order $\varepsilon_{T}$.

  * •

Since the spurious overlaps are initialized to quantities of order
$\varepsilon_{M}$ and grow from there, in cases in which the hermitian
operator $H$ is bounded so that its norm is of order one, the error term
$\mathcal{E}_{m,n-1}$ in (1.210) can be directly neglected as it will be at
least of the order of the rest of the terms in the recursion for
$\widetilde{W}_{mn}$, whose numerical implementation will anyway generate
automatically new errors of order $\varepsilon_{M}$ themselves. This
simplifying choice was made in the implementations of LanPRO for the projects
[1, 2, 3].

  * •

We note from (1.210) that, at a given step $n$, the overlaps
$\left\\{W_{mn}\right\\}_{m=0}^{n-2}$ are determined solely out of
$\left\\{W_{m,n-1}\right\\}_{m=0}^{n-1}$ and
$\left\\{W_{m,n-2}\right\\}_{m=0}^{n-2}$. That is, for the determination of
the items above the diagonal of a given column of the matrix (1.209) only the
items (above the diagonal) of the two previous columns are required. The
preceding ones do not need to be saved in the local memory. Likewise, because
of this reason, whenever the threshold $\varepsilon_{T}$ is crossed the
explicit GS step is performed both for $|A_{n-1}\rangle$ and $|A_{n}\rangle$,
since in this way both lists $\left\\{W_{m,n-1}\right\\}_{m=0}^{n-1}$ and
$\left\\{W_{m,n}\right\\}_{m=0}^{n}$ can be re-initialized to orthogonality up
to machine precision, so that the error recursion starts over in the next step
$n+1$.

### 2 Krylov complexity

Chapter 1 introduced the Lanczos algorithm and the algebraic structure of
Krylov space in an intentionally generic manner. There, $H$ denoted some
hermitian operator acting over some Hilbert space, probed with the combination
of the latter and a seed vector $|\Omega\rangle$. These tools were originally
developed as an efficient approach to the numerical eigenvalue problem, see
[6, 7, 8] for a review, but they have eventually found wide application in
physics for tasks that go far beyond the computation of the spectrum of some
operator of interest.

An area in which the recursion method has provided new insights and has even
become a line of research of its own is many-body physics. For the analysis of
the dynamics of quantum systems, one can take the hermitian operator $H$ to be
the generator of time evolution: Either the quantum Hamiltonian (denoted as
$H_{\text{q}}$ only for the sake of this discussion) for the evolution of
states in the Schrödinger picture, or the Liouvillian if one focuses on
operator evolution in the Heisenberg picture, in which case the discussions in
the previous Chapter carry over upon the replacement
$H\mapsto\mathcal{L}\equiv[H_{\text{q}},\cdot]$ and
$|\Omega\rangle\longmapsto\mathcal{O}$, where $\mathcal{O}$ is the operator
whose evolution is of interest (at the end of the day, operator space is a
perfectly valid Hilbert space of which $\mathcal{O}$ is an element and on
which $\mathcal{L}$ acts as a hermitian operator). The application of the
Lanczos algorithm to the initial condition using the corresponding generator
of time translations yields, as we will see, a basis of the Hilbert space
adapted to time evolution and a set of Lanczos coefficients that governs the
dynamics in Krylov space. Crucially, these coefficients are intimately related
to observables such as the two-point function in the case of operator
evolution and its various cousins obtained through Laplace and Fourier
transforms, whose analytical structures encode information on the system’s
spectrum. These quantities can be reconstructed from the Lanczos coefficients,
and importantly they may also be approximated out of finite truncations of
such sequences. The reader interested in applications of the recursion method
to many-body physics as an efficient numerical (and analytical) method for
analyzing dynamical and spectral properties is encouraged to consult the
detailed review [20]111This review also contains some illustrations of the
application of the Lanczos algorithm to classical evolution, where the Hilbert
space is the space of functions over phase space, and the time evolution
generator is the action of the Poisson bracket involving the classical
Hamiltonian $H_{\text{cl}}$, where the role of the generic $H$ in the
discussion from Chapter 1 would be played by
$H\longmapsto\left\\{H_{\text{cl}},\cdot\right\\}$..

Building up on these applications of the recursion method in the context of
condensed matter, the article [78] proposed to use the Lanczos algorithm to
study operator growth and quantum chaos. The notion of Krylov complexity (or
K-complexity) was presented in that work as the position expectation value of
the evolving observable $\mathcal{O}(t)$ with respect to its own Krylov basis.
A higher value of K-complexity denotes the fact that the operator is further
within the time evolution that can be generated by the system’s Liouvillian.
At early times (that is before the scrambling time scale222See [116] for a
summary of quantum and classical chaotic time scales.), for systems with
$k$-local Hamiltonians, K-complexity is comparable to size complexity, defined
as the spatial extent over which the operator has a non-trivial support, but
it eventually surpasses it because the Krylov basis is a complete basis of
Krylov space, and therefore K-complexity still has scope of growth once size
complexity is saturated in a finite system [109]. A faster propagation through
the Krylov basis denotes that the time evolution generator is an efficient
scrambler, and [78] proposes to use this as a diagnostic of quantum chaos. In
particular, since the Krylov space dynamics are controlled by the Lanczos
coefficients, the universal operator growth hypothesis presented in that work
proposes that maximally chaotic systems in the thermodynamic limit will
exhibit a maximal growth of the $b_{n}$-sequence for simple operators (proved
to be linear at infinite temperature, and conjectured to be so at finite
temperature), implying the fastest possible Krylov complexity growth (namely,
exponential). Additional mathematical relations to other notions of complexity
presented by the authors and which we shall review in this Chapter put on more
solid footing the use of K-complexity as a probe of quantum chaos.

Bringing this notion of complexity to the context of holography and black hole
physics as a plausible candidate for being the item in the holographic
dictionary describing the size of the ERB from the boundary perspective was
proposed in [109]. The authors of this work complemented the study of [78] by
considering systems away from the thermodynamic limit. This allowed them to
make some predictions on the expected behavior of K-complexity in the post-
scrambling regime, which was found to be linear for thermalizing systems333We
define a thermalizing system as a system in which typical (local or non-
extensive) operators satisfy the eigenstate thermalization hypothesis (ETH),
which is generally fulfilled in quantum chaotic systems [117, 118, 119, 120,
121]. in agreement with gravitational expectations for holographic
complexities [70, 71, 72, 73]. The immediate next step was to verify
numerically this K-complexity profile for a specific instance of a finite
system with a holographic gravitational dual, in order to also access the
eventual complexity saturation at late times: This was done for the first time
in [1] studying the complex SYK model, in a work to which we shall devote
Chapter 3.

Complementing the work by [78] and given that, as explained, the Lanczos
algorithm can be applied to any hermitian operator and probe vector belonging
to any Hilbert space, the authors of [79] propose to use Krylov complexity to
describe the evolution (in the Scrödinger picture) of states (rather than
observables) in a system’s Hilbert space with respect to their Krylov basis.
In the case of the evolution of the thermofield double state (TFD) [86], a
state relevant for studies in holography, the Lanczos coefficients generating
this evolution happen to be in correspondence to the moments of the spectral
form factor [116, 122, 123, 124], which itself also contains imprints of the
chaotic nature of systems, as it is related to the two-point spectral
correlations. The first analytical study of the state Krylov complexity of the
TFD in a low-dimensional instance of holography, which resulted the
establishment of an exact correspondence between K-complexity and wormhole
length, was carried out in the project [4] on the double-scaled SYK system,
which will be treated in Chapter 5.

The area of Krylov complexity is very young and, as such, not exempt from
debate. For instance, it is not immediate how to generalize the Lanczos
algorithm to systems whose Hilbert space has a more intricate structure as
compared to quantum mechanical models whose space consists of a discrete
tensor product. This is the case of quantum field theory (QFT) in general and
conformal field theory (CFT) in particular. In this context, the works [85,
125] pointed out that the universal operator growth hypothesis is not
immediately correct at finite temperature in QFT. We will review in this
Chapter the interesting caveats raised by the authors of these works, on which
publications [1, 2, 3] also intend to shed light. In addition, providing
support for the holographic interpretation of Krylov complexity requires the
explicit computation of such a quantity in concrete models, which are often
low-dimensional, and an eventual generalization to high dimensions constitutes
an open area of research.

To summarize, the driving forces of the projects supporting this Thesis are
the use of K-complexity as a probe of quantum chaos and as an item in the
holographic dictionary, two proposals that are intimately related. Hence, the
present Chapter intends to provide the essential definitions and constructions
required for this task, taken from the seminal references in the area and
combined with some original analyses that will hopefully enrich them. Because
of this, the selection of topics is, even though relatively basic and generic,
oriented towards the above-mentioned goals. Nevertheless, the recent years
have seen an explosion of articles on K-complexity: As a guide for the reader,
a final section is devoted to list the main lines of research in the area up
to this Thesis’ submission date, together with the relevant references.

####  2.1 Definition of Krylov complexity

In the spirit of the wide applicability of the Lanczos algorithm that Chapter
1 emphasized, this section shall present separately the definition of Krylov
complexity for operators and states. The algebraic structures underlying both
constructions will be completely analogous but we shall see that, in a
concrete physical application, each one gives access to different types of
observables and, consequently, to different features of the system studied,
therefore constituting complementary approaches.

#####  2.1.1 Operator K-complexity

The notion of Krylov complexity was introduced by Parker et al. in [78], an
article that proposed to study operator growth building up on the applications
of the recursion method in the context of many-body physics. Applying the
Lanczos algorithm to an initial observable (seen as an element of the operator
Hilbert space) and the system’s Liouvillian (which is a hermitian operator
acting on operator Hilbert space444In the condensed matter literature, in
order to avoid confusion, the term superoperator is often used to refer to an
operator that acts over operator space. Similarly, elements of operator space
are often dubbed superstates in this context.) results in an ordered Krylov
basis that is well adapted to time evolution. Because of the importance of
this construction, even though it is a particularization of the general
algorithm described in section 1.2, let us define explicitly the main objects
and tools that arise in the framework of operator Krylov complexity.

Given a Hilbert space $\mathcal{H}$ of dimension $D$, we consider the space of
linear operators acting on it, $\widehat{\mathcal{H}}$, whose dimension is
$D^{2}$. The time evolution of an operator
$\mathcal{O}\in\widehat{\mathcal{H}}$ in the Heisenberg picture is given
by555Throughout this Thesis we shall use natural units, setting $\hbar\equiv
c\equiv 1$.:

$\mathcal{O}(t)=e^{itH}\mathcal{O}e^{-itH}=\sum_{n=0}^{+\infty}\frac{{(it)}^{n}}{n!}\overbrace{\Big{[}H,\big{[}\dots,}^{(n)}\mathcal{O}\big{]}\Big{]}~{},$
(2.1)

where the last step makes use of the Baker-Campbell-Hausdorff (BCH) formula.
For notational convenience, we shall label elements of operator space with
smooth kets, i.e. $\mathcal{O}$ es represented by $|\mathcal{O})$. Likewise,
we will make use of the Liouvillian superoperator $\mathcal{L}$ acting over
$\widehat{\mathcal{H}}$, defined through

$\mathcal{L}|\mathcal{O})=\Big{|}[H,\mathcal{O}]\Big{)}$ (2.2)

for any $|\mathcal{O})\in\widehat{\mathcal{H}}$. With this, expression (2.1)
can be written more compactly as:

$\big{|}\mathcal{O}(t)\big{)}=e^{it\mathcal{L}}|\mathcal{O})=\sum_{n=0}^{+\infty}\frac{{(it)}^{n}}{n!}\mathcal{L}^{n}|\mathcal{O})~{},$
(2.3)

i.e. the nested commutators of the Hamiltonian with the operator are
conveniently re-expressed as powers of the Liouvillian acting on the initial
condition. From (2.3), the definition of the Krylov space associated to the
observable $\mathcal{O}$ is direct:

$\widehat{\mathcal{H}}_{\mathcal{O}}:=\text{span}\left\\{\mathcal{L}^{n}|\mathcal{O})\right\\}_{n\geq
0}~{}.$ (2.4)

By construction, (2.4) is a subspace of $\widehat{\mathcal{H}}$, and therefore
the Krylov space dimension, denoted $K:=\dim\widehat{\mathcal{H}}$, must
satisfy $K\leq D^{2}$. In [1] a slightly stronger bound which is useful in
numerical applications was proved to be

$1\leq K\leq D^{2}-D+1~{},$ (2.5)

for any non-vanishing operator $\mathcal{O}$. However, the basic notions on
K-complexity that will be reported in this Chapter will mostly refer, unless
otherwise stated, to systems in the thermodynamic limit with an infinite
Krylov dimension for the operator of interest. The proof of (2.5) will be
presented in Chapter 3.

Also by construction, the Krylov space (2.4) is the smallest subspace of
$\widehat{\mathcal{H}}$ that contains the time-evolved superstate
$\big{|}\mathcal{O}(t)\big{)}$ for any time666Strictly speaking, given that
$t$ appears in the coefficients of the infinite linear combination (2.3), one
could say that $\widehat{\mathcal{H}}_{\mathcal{O}}$ is the minimal subspace
of operator space that contains $\big{|}\mathcal{O}(t)\big{)}$ for any
$t\in\mathds{C}$, as long as the Taylor expansion in (2.3) is convergent.. The
elements $\left\\{\mathcal{L}^{n}|\mathcal{O})\right\\}_{n\geq 0}$ are
gradually explored by the time-evolving observable, so one might think that
they are adequate for a systematic study of the progression of time evolution.
However, this set does not necessarily constitute an orthonormal basis for
Krylov space (and, furthermore, in the cases in which $K$ is finite it is an
overcomplete basis). The Lanczos algorithm is able to provide an orthonormal
basis (upon the specification of an inner product in $\widehat{\mathcal{H}}$)
that still retains some notion of ordering adapted to time evolution, in the
sense that the $n$-th Krylov element will consist of a linear combination of
up to $n$ powers of the Liouvillian acting on the initial condition or,
equivalently, up to $n$ nested commutators of $H$ with $O$.

As announced, the application of the Lanczos algorithm for the construction of
an orthonormal Krylov basis requires the specification of an inner product in
operator space. Mathematically, the most immediate choice is the Frobenius
inner product, as this is the one that is naturally inherited from the inner
product in the space of states:

$\left(\mathcal{A}|\mathcal{B}\right):=\frac{1}{D}\text{Tr}\left[\mathcal{A}^{\dagger}\mathcal{B}\right]$
(2.6)

for any two operators $\mathcal{A},\mathcal{B}\in\widehat{\mathcal{H}}$. Note
that the normalization factor $\frac{1}{D}$ ensures that the unit operator has
unit norm. However, one might choose other scalar products of some physical
relevance [20, 78], as is the case of the thermal inner product with inverse
temperature777Throughout this Thesis we shall also use the convention
$k_{B}\equiv 1$ for the Boltzmann constant, implying that temperatures have
units of energy. $\beta=\frac{1}{T}$. There are several ways in which this
inner product may be defined; the conventional thermal product in quantum
mechanics is just

$\left(\mathcal{A}|\mathcal{B}\right)_{\beta}:=\frac{1}{Z(\beta)}\text{Tr}\left[e^{-\beta
H}\mathcal{A}^{\dagger}\mathcal{B}\right]~{},$ (2.7)

where $Z(\beta)=\text{Tr}\left[e^{-\beta H}\right]$ is the thermal partition
function. In linear-response theory, it is more customary [20, 78] to use the
so-called standard thermal inner product:

$\left(\mathcal{A}|\mathcal{B}\right)_{\beta}^{S}:=\frac{1}{2Z(\beta)}\text{Tr}\left[e^{-\beta
H}\mathcal{A}^{\dagger}\mathcal{B}+\mathcal{A}^{\dagger}e^{-\beta
H}\mathcal{B}\right]~{}.$ (2.8)

On the other hand, in applications to quantum field theory in which
correlation functions display contact singularities it is often preferred to
use a regularized thermal inner product, dubbed the Wightman inner product
(see e.g. [78]). This product splits evenly the Boltzmann factor amongst the
operator insertions, which is equivalent to analytically continuing one of
them to imaginary times:

$\left(\mathcal{A}|\mathcal{B}\right)_{\beta}^{W}:=\frac{1}{Z(\beta)}\text{Tr}\left[e^{-\beta
H/2}\mathcal{A}^{\dagger}e^{-\beta
H/2}\mathcal{B}\right]=\left(\mathcal{A}\Bigg{|}\mathcal{B}\left(\frac{i\beta}{2}\right)\right)_{\beta}~{}.$
(2.9)

The three options above are particular cases of a more generic thermal inner
product [20], which can be defined by the means of some function $g(\tau)$ on
the thermal circle:

$\left(\mathcal{A}|\mathcal{B}\right)_{\beta}^{g}:=\frac{1}{Z(\beta)}\int_{0}^{\beta}d\tau
g(\tau)\text{Tr}\left[e^{-(\beta-\tau)H}\mathcal{A}^{\dagger}e^{-\tau
H}\mathcal{B}\right]=\int_{0}^{\beta}d\tau
g(\tau)\left(\mathcal{A}\Big{|}\mathcal{B}\left(i\tau\right)\right)_{\beta}~{}.$
(2.10)

This is an inner product as long as $g(\tau)$ is a positive-semidefinite
function on the thermal circle $[0,\beta]$ which integrates to some constant
in such a domain; the constant is chosen to be $1$ so that the unit operator
has unit norm. We note that (2.7), (2.8) and (2.9) can be retrieved from
(2.10) by setting $g(\tau)=\delta(\tau)$,
$g(\tau)=\frac{1}{2}\left(\delta(\tau)+\delta(\tau-\beta)\right)$ and
$g(\tau)=\delta(\tau-\beta/2)$, respectively. Likewise, the Frobenius product
(2.6) can be interpreted as an infinite-temperature scalar product, reachable
in the $\beta=0$ limit of any of the thermal products defined above. With
respect of any member of the family of inner products (2.10), the Liouvillian
$\mathcal{L}$ is a hermitian superoperator acting over operator space.

For a hermitian initial operator $\mathcal{O}=\mathcal{O}^{\dagger}$ (i.e. an
observable), the Lanczos algorithm formulated in section 1.2 can be applied
using the Liouvillian $\mathcal{L}$ in order to generate an orthogonal Krylov
basis $\left\\{|\mathcal{O}_{n})\right\\}_{n\geq 0}$ for Krylov space (2.4),
together with a set of Lanczos coefficients $\left\\{a_{n}\right\\}_{n\geq 0}$
and $\left\\{b_{n}\right\\}_{n\geq 1}$. Given the generic thermal inner
product (2.10), if the $g$-function additionally satisfies
$g(\tau)=g(\beta-\tau)$, i.e. it is even in the thermal circle888This
requirement is often demanded in linear-response theory because it allows
correlation functions, defined as the overlap
$\left(\mathcal{O}|\mathcal{O}(t)\right)_{\beta}^{g}$, to satisfy the usual
fluctuation-dissipation theorem [20]., which is the case of (2.8) and (2.9)
but not of (2.7), then the algorithm simplifies and it is possible to prove
inductively the two following results:

  * i)

The Krylov elements have alternating hermiticity properties:
$\mathcal{O}_{n}^{\dagger}=(-1)^{n}\mathcal{O}_{n}$. Equivalently,
$i^{n}\mathcal{O}_{n}$ is hermitian for any $n\geq 0$.

  * ii)

$a_{n}=0$ for all $n\geq 0$.

Hence, in this case the Lanczos algorithm applied to operators only yields one
sequence of $b$-coefficients. Krylov elements $\mathcal{O}_{n}$ with even
(resp. odd) index $n$ are a linear combination of terms containing an even
(resp. odd) number of nested commutators of $H$ with $\mathcal{O}$.

For now we shall focus on the infinite-temperature inner product (2.6), which
probes the full Hilbert space of the system democratically. Let us write the
explicit formulation of the Lanczos algorithm for this case999It can be
generalized to the family of inner products (2.10) by replacing the
occurrences of the $\beta=0$ scalar product by the corresponding one, and
including $a$-coefficients according to the prescription in section 1.2
whenever $g(\tau)$ is not even.:

  * $n=0$:

    * $\bullet$

$|\mathcal{O}_{0})=|\mathcal{O})$ (normalized by assumption).

  * $n=1$:

    * $\bullet$

$|\mathcal{A}_{1})=\mathcal{L}|\mathcal{O}_{0})$.

    * $\bullet$

$b_{1}=\sqrt{\left(\mathcal{A}_{1}|\mathcal{A}_{1}\right)}$.

    * $\bullet$

$|\mathcal{O}_{1})=\frac{1}{b_{1}}|\mathcal{A}_{1})$.

  * $n\geq 2$:

    * $\bullet$

$|\mathcal{A}_{n})=\mathcal{L}|\mathcal{O}_{n-1})-b_{n-1}|\mathcal{O}_{n-2})$.

    * $\bullet$

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

    * $\bullet$

$|\mathcal{O}_{n})=\frac{1}{b_{n}}|\mathcal{A}_{n})$.

The formulation above emphasizes on the exact analytical definition of the
objects involved. For the specific numerical implementation of the algorithm,
see Chapter 3. For now, it suffices to say that, in cases with a finite-
dimensional Krylov space, the algorithm shall terminate by hitting a zero at
$b_{K}=0$. We note that the Krylov elements satisfy:

$\begin{split}&b_{1}|\mathcal{O}_{1})=\mathcal{L}|\mathcal{O}_{0})~{},\\\
&b_{n}|\mathcal{O}_{n})=\mathcal{L}|\mathcal{O}_{n-1})-b_{n-1}|\mathcal{O}_{n-2})~{},\qquad
2\leq n\leq K-1~{},\\\
&0=\mathcal{L}|\mathcal{O}_{K-1})-b_{K-1}|\mathcal{O}_{K-2})~{},\end{split}$
(2.11)

where the last line only applies if $K$ is finite.

These Krylov elements are probed gradually by the time-evolving observable
$\left|\mathcal{O}(t)\right)$. It is thus useful to decompose it in terms of
them:

$\big{|}\mathcal{O}(t)\big{)}=e^{it\mathcal{L}}|\mathcal{O})=\sum_{n=0}^{K-1}i^{n}\varphi_{n}(t)|\mathcal{O}_{n})~{},$
(2.12)

where $\varphi_{n}(t):=i^{-n}\left(\mathcal{O}_{n}|\mathcal{O}(t)\right)$ is
dubbed the operator wave function, which is real101010This definition of the
wave function modding out some power of the imaginary unit $i$ is useful for
numerical applications, as it allows to store the values of this function in
exclusively real variables, granting some memory optimization. thanks to the
alternating hermiticity properties of the Krylov elements discussed
previously. We may think of the Krylov basis as some chain (the Krylov chain)
through which the evolving operator is spreading according to the wave
function $\varphi_{n}(t)$, where $n$ plays the role of the position coordinate
on the chain. This perspective can be pushed further by noting the tridiagonal
form taken by the Liouvillian in coordinates over the Krylov basis, which can
be deduced from (2.11):

$\mathcal{L}=\sum_{n=0}^{K-2}b_{n+1}\Big{(}|\mathcal{O}_{n})(\mathcal{O}_{n+1}|+|\mathcal{O}_{n+1})(\mathcal{O}_{n}|\Big{)}~{}.$
(2.13)

We observe that (2.13), which generates the time evolution of the initial
condition $|\mathcal{O})=|\mathcal{O}_{0})$ takes the form of the Hamiltonian
of a hopping model [126] where the Lanczos coefficients play the role of
hopping amplitudes on the Krylov chain. In other words, the Lanczos
construction allows to map the time evolution of a certain operator to a one-
dimensional quantum-mechanical hopping problem [78, 20]. The projects [2, 3],
presented in Chapter 4, exploit this fact and study the imprints of the
system’s properties on the hopping amplitudes governing Krylov space
propagation. As we have already announced, the article [78] proposed to use
the position on the Krylov chain as a notion of (operator) complexity, dubbed
Krylov complexity or K-complexity. Considering the position (super-)operator
over the Krylov basis, which may itself be referred to as the K-complexity
(super-)operator,

$\widehat{\mathcal{C}_{K}}:=\sum_{n=0}^{K-1}n~{}|\mathcal{O}_{n})(\mathcal{O}_{n}|~{},$
(2.14)

K-complexity is defined to be the expectation value of such a superoperator
for the time-evolving element $\big{|}\mathcal{O}(t)\big{)}$:

$C_{K}(t):=\Big{(}\mathcal{O}(t)\Big{|}\widehat{\mathcal{C}_{K}}\Big{|}\mathcal{O}(t)\Big{)}=\sum_{n=0}^{K-1}n~{}\varphi_{n}(t)^{2}~{},$
(2.15)

where the last step made use of (2.12), together with the fact that the
operator wave function is always real. By construction of the Krylov basis,
the operator wave function is initially localized at $n=0$, i.e.
$\varphi_{n}(0)=\delta_{n0}$, and from then on it spreads over the Krylov
chain according to the Schrödinger equation dictated by the Liouvillian
(2.13), which takes the form of a recursive equation:

$\dot{\varphi}_{n}(t)=b_{n}\varphi_{n-1}(t)-b_{n+1}\varphi_{n+1}(t)~{},$
(2.16)

whose initial condition is, as announced, $\varphi_{n}(0)=\delta_{n0}$ and
where we need some boundary conditions to account for the edges of Krylov
space, namely $\varphi_{-1}\equiv\varphi_{K}\equiv 0$. Equation (2.16)
manifests that the knowledge of the Lanczos coefficients uniquely determines
the operator wave function $\varphi_{n}(t)$, and is therefore sufficient for
the eventual computation of K-complexity (2.15). We note that the time-
evolution (super-) operator $e^{it\mathcal{L}}$ is unitary since $\mathcal{L}$
is hermitian, as has been discussed. Therefore, the norm of the operator
remains constant as a function of (real) time111111Note that imaginary-time
evolution does not preserve the norm. $\Big{|}\mathcal{O}(i\tau)\Big{)}$ still
belongs to Krylov space by construction, but it would need to be renormalized
to unity in order to compute its K-complexity for some arbitrary
$\tau\in[0,\beta]$.:

$\Big{(}\mathcal{O}(t)\Big{|}\mathcal{O}(t)\Big{)}=\sum_{n=0}^{K-1}\varphi_{n}(t)^{2}=1~{},\qquad\forall
t\in\mathds{R}~{}.$ (2.17)

The larger K-complexity is, the further $\Big{|}\mathcal{O}(t)\Big{)}$ is
within the time evolution that can be generated by $\mathcal{L}$, i.e. one
requires more applications of the Liovillian in order to reconstruct
$\Big{|}\mathcal{O}(t)\Big{)}$ out of the initial condition $|\mathcal{O})$.
In this sense, this notion may be understood as a generalization of circuit
complexity that does not require any human input designating what the
reference state or the set of unitary gates are, and which is well-defined and
finite without introducing a tolerance parameter. In fact, despite not being
frequently mentioned, the choice of unitary gates in the context of circuit
complexity does have some relation with the Hamiltonian generating time
evolution: The complexity computed out of $k$-local gates will only give a
sensible result for the study of the time evolution of an initially localized
state or operator if the Hamiltonian is itself $k$-local and if the reference
state (or operator) is not highly non-local; similarly, size-complexity [81]
of an initially localized operator will grow progressively in time only if the
Hamiltonian is built with $k$-local interactions. At the end of the day, the
gates out of which complexity is computed are often related to the building
blocks of the Hamiltonian generating time evolution, and K-complexity
generalizes this fact: The reference state is nothing but the initial
condition of time evolution, and “the only unitary gate” is the time evolution
operator itself. $C_{K}(t)$ is therefore fully specified once the initial
condition, the time evolution generator, and and inner product over the
Hilbert space of interest, are given. This comes at the cost of being a very
specific construction in the sense that the basis adapted to the time
evolution of a given initial condition $|\mathcal{O)}$ might be completely
unrelated to the Krylov basis of a different initial condition
$|\mathcal{O}^{\prime})$.

An object which will be useful to characterize the exploration of the Krylov
chain by the time-evolving operator is the Shannon entropy of its operator
wave function with respect to the Krylov basis, introduced in [109] and dubbed
Krylov entropy or K-entropy:

$S_{K}(t)=-\sum_{n=0}^{K-1}\varphi_{n}(t)^{2}~{}\log\varphi_{n}(t)^{2}~{}.$
(2.18)

At this point, we recall that section 1.9 illustrated how the Lanczos
coefficients are in correspondence to the moments of the generator. In the
case of operator K-complexity, the relevant moments are

$\mu_{2n}:=\left(\mathcal{O}|\mathcal{L}^{2n}|\mathcal{O}\right)~{},$ (2.19)

where we have explicitly omitted odd moments, which vanish identically for any
hermitian operator $\mathcal{O}$ given an inner product belonging to the
family (2.10) that has an even $g$ function, consistently with the fact that
the $a$-coefficients vanish in this case, as argued in the discussion leading
to (2.11). We thus have the following bijective relation:

$\left\\{b_{n}\right\\}_{n=1}^{K-1}\longleftrightarrow\left\\{\mu_{2n}\right\\}_{n=1}^{K-1}~{},$
(2.20)

where we note that $\mu_{0}=1$ identically because of the requirement of
normalization of the initial condition. In this physical context, the relation
(2.20) is in fact extremely useful because the moments $\mu_{2n}$ are very
intimately related to an observable of importance: The operator’s two point
function or auto-correlation function, given by

$C(t):=\left(\mathcal{O}|\mathcal{O}(t)\right)~{}.$ (2.21)

Note that, since the initial condition gives the zeroth Krylov element, the
quantity (2.21) is equal to the zeroth component of the operator wave
function, $C(t)=\varphi_{0}(t)$. For hermitian operators, the auto-correlation
function is even in the time domain, and one can see that the coefficients of
its Taylor series around $t=0$ are precisely the moments $\mu_{2n}$:

$C(t)=\left(\mathcal{O}|e^{it\mathcal{L}}|\mathcal{O}\right)=\sum_{n=0}^{+\infty}\frac{{(it)}^{2n}}{(2n)!}\mu_{2n}~{}.$
(2.22)

Operationally, when one does not have direct access to the concrete algebraic
description of the underlying Hilbert space of the system in order to apply
explicitly the Lanczos algorithm, or if such an application is costly and
limited (e.g. in the case of field theory, or systems of infinite size), it
may be preferred to compute analytically the two-point function (2.21), obtain
the moments from it and, numerically, transform them into Lanczos coefficients
using the algorithm described in section 1.9.2, at the cost of coping with its
high-precision requirements.

Additionally, the fact that the moments $\mu_{2n}$ are the Taylor coefficients
of the operator’s two-point function allows for some further analytical
understanding of the behavior of the Lanczos sequence by extrapolating
features of the sequence of moments that can in turn be obtained from known
results on the two-point function or its various cousins. This was exploited
in [78] in order to propose the operator growth hypothesis, which is the
central contribution of the article together with the introduction of the
notion of K-complexity. We shall review this hypothesis in section 2.3, but
for now let us just present the aforementioned cousins:

  * •

The spectral function: It is the Fourier transform of the two-point function
(2.21),

$\Phi(\omega):=\int_{\mathds{R}}dt~{}C(t)~{}e^{-i\omega t}~{},$ (2.23)

from which the moments $\mu_{2n}$ can be computed as

$\mu_{2n}=\frac{1}{2\pi}\int_{\mathds{R}}d\omega~{}\omega^{2n}~{}\Phi(\omega)~{}.$
(2.24)

  * •

The Green function, given by

$G(z):=\left(\mathcal{O}\Big{|}\frac{1}{z-\mathcal{L}}\Big{|}\mathcal{O}\right)~{}.$
(2.25)

This function has singularities along the real axis, such that the
discontinuity in the vertical direction gives a version of the density of
states of the Liouvillian, weighted by the operator $\mathcal{O}$ due to the
fact that (2.25) is an expectation value evaluated in the state
$|\mathcal{O})$ rather than a full trace over $\widehat{\mathcal{H}}$. We will
see that such a weighted density is nothing but the spectral function
$\Phi(\omega)$. The Green function $G(z)$ admits different integral
representations depending on whether its argument belongs to the upper or to
the lower half of the complex plane:

$G(z^{\pm})=\mp i\int_{\mathds{R}^{\mp}}dt~{}C(t)~{}e^{-itz^{\pm}}~{},$ (2.26)

where $z^{+}$ (resp. $z^{-}$) denotes that the imaginary part of $z$ is
positive (resp. negative). From (2.26) and (2.23) we obtain, as promised, the
spectral function in terms of the jump across the real-axis discontinuity of
$G(z)$:

$\Phi(\omega)=-i\lim_{\varepsilon\to
0^{+}}\Big{(}G\left(\omega-i\varepsilon\right)-G\left(\omega+i\varepsilon\right)\Big{)}$
(2.27)

for real $\omega$.

Importantly, the Green function $G(z)$ admits a continued fraction expansion
in terms of the Lanczos coefficients $b_{n}$. This can be seen considering the
operator wave functions $\varphi_{n}(t)$ defined in (2.12): Defining some
“generalized” Green functions $G_{n}(z)$ as

$G_{n}(z^{\pm})=\mp
i\int_{\mathds{R}^{\mp}}dt~{}\varphi_{n}(t)~{}e^{-itz^{\pm}}=i^{-n}\left(\mathcal{O}_{n}\Big{|}\frac{1}{z^{\pm}-\mathcal{L}}\Big{|}\mathcal{O}\right)~{},$
(2.28)

we may turn the differential recursion (2.16) for $\varphi_{n}(t)$ into an
algebraic recurrence relation for $G_{n}(z)$:

$izG_{n}(z)-i\delta_{n0}=b_{n}G_{n-1}(z)-b_{n+1}G_{n+1}(z)~{},$ (2.29)

supplemented with the boundary conditions $G_{-1}\equiv G_{K}\equiv 0$.
Iterating this recursion, it is possible to obtain the promised continued-
fraction expansion of $G_{0}(z)=G(z)$:

$G(z)=\frac{1}{z-\frac{b_{1}^{2}}{z-\frac{b_{2}^{2}}{z-\dots}}}~{}.$ (2.30)

This last equation illustrates how the Lanczos coefficients are intimately
related to the spectral function $\Phi(\omega)$, as they are directly
responsible for the singularity structure of the Green function through
(2.30). The reader interested in the use of truncated sequences of Lanczos
coefficients in order to reconstruct numerically the spectral function is
referred to the review [20], where the $b$-sequence is treated as a “genetic
code of spectral densities” since it encodes information on the features of
$\Phi(\omega)$. For example, a $b_{n}$ sequence that asymptotes to a constant
implies a spectral density of bounded support, while indefinitely growing
Lanczos coefficients correspond to a $\Phi(\omega)$ whose domain is unbounded.
For a compilation of properties and relations, see [20], and for a rigorous
mathematical analysis of some particular cases see [127].

#####  2.1.2 State K-complexity

Chronologically, operator Krylov complexity was introduced before state Krylov
complexity because the relation between the Lanczos coefficients and the
various observables related to the two-point function make the recursion
method a very useful tool to study operator growth. However, articles [109, 1]
proposed to consider Krylov complexity as an adequate candidate for
holographic complexity, a task for which the K-complexity of a time-evolving
state in the system’s Hilbert space may be equally insightful, as shall be
discussed in section 2.3. The work [79] was the first to study analytically
Krylov complexity of states for some symmetry-dominated systems, as well as
numerically in random matrix theory. For reference, we shall give in this
section the relevant definitions regarding state K-complexity.

Given a time-evolving state in the Schrödinger picture,

$|\phi(t)\rangle=e^{-itH}|\phi\rangle~{},$ (2.31)

the Lanczos algorithm can be applied just as it was described121212Throughout
Chapter 1, the probe vector was generically denoted by $|\Omega\rangle$,
representing the seed element in whichever Hilbert space where one envisions
to apply the Lanczos algorithm. Here, we prefer the use of $|\phi\rangle$
because the symbol $|\Omega\rangle$ is frequently reserved to the vacuum state
in theories where it can be defined, whereas we intend to refer to an
arbitrary state in the system’s Hilbert space. in section 1.2. The reader is
referred to that section for the details but, schematically, let us simply
recall that the algorithm produces an orthonormal Krylov basis
$\left\\{|K_{n}\rangle\right\\}_{n=0}^{K-1}$ and, this time, generically two