Given the recent advances in quantum technology, the complexity of quantum states is an important notion. The idea of the Krylov spread complexity has come into focus recently with the goal of capturing this in a quantitative way. The present paper sheds light on the Krylov complexity measure by exploring it in the context of continuous-time quantum walks on graphs. A close relationship between Krylov spread complexity and the concept of limiting distributions for quantum walks is established. Moreover, using a graph optimization algorithm, quantum-walk graphs are constructed that have vertex states with minimal and maximal (long-time average) Krylov
C complexity. This reveals an empirical upper bound for the
C complexity as a function of Hilbert-space dimension and an exact lower bound.
This Thesis explores the notion of Krylov complexity as a probe of quantum chaos and as a candidate for holographic complexity. The first Part is devoted to presenting the fundamental notions required to conduct research in this area. Namely, an extensive introduction to the Lanczos algorithm, its properties and associated algebraic structures, as well as technical details related to its practical implementation, is given. Subsequently, an overview of the seminal references and the main debates regarding Krylov complexity and its relation to chaos and holography is provided. The text throughout this first Part combines review material with original analyses which either intend to contextualize, compare and criticize results in the literature, or are the fruit of the investigations leading to the publications on which this Thesis is based. These research projects are the subject of the second Part of the manuscript. In them, methods for the efficient implementation of the Lanczos algorithm in finite many-body systems were developed, allowing to compute numerically the Krylov complexity of models like SYK or the XXZ spin chain up to time scales exponentially large in system size. It was observed that the operator Krylov complexity profile in SYK, a paradigmatic low-dimensional chaotic system with a holographic dual, agrees with holographic expectations, while in the case of integrable models like XXZ complexity is affected by a novel localization effect in the so-called Krylov space which hinders its growth. Finally, an exact, analytical, correspondence between the Krylov complexity of the infinite-temperature thermofield double state in the low-energy regime of the double-scaled SYK model and bulk length in the theory of JT gravity is established.
Krylov complexity, as a novel measure of operator complexity under Heisenberg evolution, exhibits many interesting universal behaviors and also bounds many other complexity measures. In this work, we study Krylov complexity
K(t) in Random Matrix Theory (RMT). In large
N limit: (1) For infinite temperature, we analytically show that the Lanczos coefficient
{bn} saturate to constant plateau
n→∞limbn=b, rendering a linear growing complexity
K(t)∼t, in contrast to the exponential-in-time growth in chaotic local systems in thermodynamic limit. After numerically comparing this plateau value
b to a large class of chaotic local quantum systems, we find that up to small fluctuations, it actually bounds the
{bn} in chaotic local quantum systems. Therefore we conjecture that in chaotic local quantum systems after scrambling time, the speed of linear growth of Krylov complexity cannot be larger than that in RMT. (2) For low temperature, we analytically show that
bn will first exhibit linear growth with
n, whose slope saturates the famous chaos bound. After hitting the same plateau
b,
bn will then remain constant. This indicates
K(t)∼e2πt/β before scrambling time
t∗∼O(βlogβ), and after that it will grow linearly in time, with the same speed as in infinite temperature. We finally remark on the effect of finite
N corrections.
A bstract Quantum complexity, suitably defined, has been suggested as an important probe of late-time dynamics of black holes, particularly in the context of AdS/CFT. A notion of quantum complexity can be effectively captured by quantifying the spread of an operator in Krylov space as a consequence of time evolution. Complexity is expected to behave differently in chaotic many-body systems, as compared to integrable ones. In this paper we investigate Krylov complexity for the case of interacting integrable models at finite size and find that complexity saturation is suppressed as compared to chaotic systems. We associate this behavior with a novel localization phenomenon on the Krylov chain by mapping the theory of complexity growth and spread to an Anderson localization hopping model with off-diagonal disorder, and find that localization is enhanced in the integrable case due to a stronger disorder in the hopping amplitudes, inducing an effective suppression of Krylov complexity. We demonstrate this behavior for an interacting integrable model, the XXZ spin chain, and show that the same behavior results from a phenomenological model that we define: this model captures the essential features of our analysis and is able to reproduce the behaviors we observe for chaotic and integrable systems via an adjustable disorder parameter.
Krylov state complexity, or spread complexity, has emerged as a sharp and versatile diagnostic of quantum chaos, information spreading, and many-body dynamics. Built from the Lanczos algorithm and grounded in the optimal-basis theorem, Krylov complexity thereby provides a robust spectroscopic window into quantum dynamics. A central theme is the characteristic overshoot observed in chaotic systems: a complexity peak in which chaotic evolution drives the state deeper into the Krylov chain than in integrable systems before relaxing to equilibrium. This behavior, tied to random-matrix universality classes of spectral statistics, is illustrated across a broad range of models, including quantum billiards, quantum spin chains, and variants of the SYK model. We also discuss proposed holographic descriptions of Krylov complexity in Einstein gravity, and conclude by outlining future directions and open problems, including time-dependent systems and quantum-field-theoretic formulations. A Mathematica notebook is provided for numerical exploration of Krylov complexity and spectral statistics across models.
A bstract We apply a notion of quantum complexity, called “Krylov complexity”, to study the evolution of systems from integrability to chaos. For this purpose we investigate the integrable XXZ spin chain, enriched with an integrability breaking deformation that allows one to interpolate between integrable and chaotic behavior. K-complexity can act as a probe of the integrable or chaotic nature of the underlying system via its late-time saturation value that is suppressed in the integrable phase and increases as the system is driven to the chaotic phase. We furthermore ascribe the (under-)saturation of the late-time bound to the amount of disorder present in the Lanczos sequence, by mapping the complexity evolution to an auxiliary off-diagonal Anderson hopping model. We compare the late-time saturation of K-complexity in the chaotic phase with that of random matrix ensembles and find that the chaotic system indeed approaches the RMT behavior in the appropriate symmetry class. We investigate the dependence of the results on the two key ingredients of K-complexity: the dynamics of the Hamiltonian and the character of the operator whose time dependence is followed.