Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2401.00526 · Physical Review A

Krylov spread complexity of quantum walks

Bhilahari Jeevanesan

Published Sep 6, 2024• 2 citations
arXivHTMLPDF

Abstract

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 $\overline{\mathcal{C}}$ complexity. This reveals an empirical upper bound for the $\overline{\mathcal{C}}$ complexity as a function of Hilbert-space dimension and an exact lower bound.

DOI
10.1103/physreva.110.032206

Related papers

Emergence of Krylov complexity through quantum walks: An exploration of the quantum origins of complexity

Dimitrios Patramanis, Watse Sybesma

In this work we study the relationship between quantum random walks on graphs and Krylov/spread complexity. We show that the latter's definition naturally emerges through a canonical method of reducing a graph to a chain, on which we can identify the usual Krylov structure. We use this identification to construct families of graphs corresponding to special classes of systems with known complexity features and conversely, to compute Krylov complexity for graphs of physical interest. The two main outcomes are the analytic computation of the Lanczos coefficients for the SYK model for an arbitrary number $q$ of interacting fermions and the complete characterization of Krylov complexity for the hypercube graph in any number of dimensions. The latter serves as the starting point for an in-depth comparison between Krylov and circuit complexities as they purportedly arise in the context of black holes. We find that while under certain conditions Krylov complexity follows the growth and saturation pattern ascribed to such systems, the timescale at which saturation happens can generally be shorter than what is predicted by random unitary circuits, due to the effects of quantum speed-ups commonly occurring when comparing quantum and classical random walks.

hep-thCross-listedarXiv:2602.04949•Journal of High Energy Physics•Feb 6, 2026•0 citations

Bounds on Entanglement Dynamics from Krylov-Space Spreading

Swati Choudhary, Sukrut Mondkar, Ujjwal Sen

A recently developed notion, known as spread complexity, captures how a quantum state spreads in Krylov space under unitary evolution. Related Krylov-space approaches are increasingly being investigated for applications in quantum control, simulation, and metrology, as well as are being considered for implementation in near-term quantum platforms. However, its connection to fundamental quantum resources such as entanglement and quantum coherence remains unclear. We show that the dynamics of entanglement is constrained by the extent of spreading in Krylov space. For multipartite systems, we relate state delocalization in the Krylov basis, quantified by the inverse participation ratio, to geometric measures of multipartite quantum correlations. Furthermore, we derive analytical relations between the quantum coherence of the initial state in the energy eigenbasis and spread complexity for qubit and qutrit systems. Our results make progress towards understanding the subtle interplay between the dynamical spreading in Krylov space and fundamental quantum resources.

quant-pharXiv:2603.26619•Mar 30, 2026•0 citations

Krylov complexity of density matrix operators

Paweł Caputa, Hyun-Sik Jeong, Sinong Liu +2 more

A bstract Quantifying complexity in quantum systems has witnessed a surge of interest in recent years, with Krylov-based measures such as Krylov complexity ( C K ) and Spread complexity ( C S ) gaining prominence. In this study, we investigate their interplay by considering the complexity of states represented by density matrix operators . After setting up the problem, we analyze a handful of analytical and numerical examples spanning generic two-dimensional Hilbert spaces, qubit states, quantum harmonic oscillators, and random matrix theories, uncovering insightful relationships. For generic pure states, our analysis reveals two key findings: (I) a correspondence between moment-generating functions (of Lanczos coefficients) and survival amplitudes, and (II) an early-time equivalence between C K and 2 C S . Furthermore, for maximally entangled pure states, we find that the moment-generating function of C K becomes the Spectral Form Factor and, at late-times, C K is simply related to NC S for N ≥ 2 within the N -dimensional Hilbert space. Notably, we confirm that C K = 2 C S holds across all times when N = 2. Through the lens of random matrix theories, we also discuss deviations between complexities at intermediate times and highlight subtleties in the averaging approach at the level of the survival amplitude.

arXiv:2402.09522•Journal of High Energy Physics•May 31, 2024•59 citations

On Minimizing Krylov Complexity Using Higher-Order Generators

Saud Čindrak, Kathy Lüdge

Krylov complexity provides a powerful framework for characterizing the dynamical evolution of quantum systems through the spreading of states in Krylov space. The motivation for this is rooted in the optimality of the Krylov basis for the analyzed cost function. In this work, we reinterpret the motivation for the Krylov basis from a dynamical perspective and show that it corresponds to a first-order approximation of the time-evolution operator. We extend this framework to higher-order generators and analytically disprove the optimality assumption by showing that an infinite-order generator can be constructed to exhibit smaller spread for arbitrary times. We propose a natural time scale for the construction of these higher-order generators and discuss results for matrices sampled from Gaussian Unitary Ensembles, demonstrating smaller Krylov complexity at all higher orders. These results extend the framework of Krylov complexity beyond the conventional Krylov basis by disproving the widely held assumption of optimality, extending the construction to higher-order generators, and introducing a physically motivated method for their construction. Our findings therefore suggest that previous statements and results concerning Krylov complexity may need to be reconsidered.

quant-pharXiv:2603.07183•Mar 10, 2026•0 citations

Krylov complexity and dynamical phase transition in the quenched Lipkin-Meshkov-Glick model

Pedro H. S. Bento, Adolfo del Campo, Lucas C. Céleri

Investigating the time evolution of complexity in quantum systems entails evaluating the spreading of the system's state across a defined basis in its corresponding Hilbert space. Recently, the Krylov basis has been identified as the one that minimizes this spreading. In this study, we develop a numerical exploration of the Krylov complexity in quantum states following a quench in the Lipkin-Meshkov-Glick model. Our results reveal that the long-term averaged Krylov complexity acts as an order parameter for this model. It effectively discriminates between the two dynamic phases induced by the quench, sharing a critical point with the conventional order parameter. Additionally, we examine the inverse participation ratio and the Shannon entropy in both the Krylov basis and the energy basis. A matching dynamic behavior is observed in both bases when the initial state possesses a specific symmetry. This behavior is analytically explained by establishing the equivalence between the Krylov basis and the prequench energy eigenbasis.

arXiv:2312.05321•Physical review. B./Physical review. B•Jun 11, 2024•25 citations

Statistics and complexity of wavefunction spreading in quantum dynamical systems

Y. W. Fu, Keun-young Kim A, Kunal Pal +1 more

A bstract We consider the statistics of the results of a measurement of the spreading operator in the Krylov basis generated by the Hamiltonian of a quantum system starting from a specified initial pure state. We first obtain the probability distribution of the results of measurements of this spreading operator at a certain instant of time, and compute the characteristic function of this distribution. We show that the moments of this characteristic function are related to the so-called generalised spread complexities, and obtain expressions for them in several cases when the Hamiltonian is an element of a Lie algebra. Furthermore, by considering a continuum limit of the Krylov basis, we show that the generalised spread complexities of higher orders have a peak in the time evolution for a random matrix Hamiltonian belonging to the Gaussian unitary ensemble. We also obtain an upper bound in the change in generalised spread complexity at an arbitrary time in terms of the operator norm of the Hamiltonian and discuss the significance of these results.

arXiv:2411.09390•Journal of High Energy Physics•Jun 13, 2025•10 citations
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‾\overline{\mathcal{C}}C complexity. This reveals an empirical upper bound for the C‾\overline{\mathcal{C}}C complexity as a function of Hilbert-space dimension and an exact lower bound.
In this work we study the relationship between quantum random walks on graphs and Krylov/spread complexity. We show that the latter's definition naturally emerges through a canonical method of reducing a graph to a chain, on which we can identify the usual Krylov structure. We use this identification to construct families of graphs corresponding to special classes of systems with known complexity features and conversely, to compute Krylov complexity for graphs of physical interest. The two main outcomes are the analytic computation of the Lanczos coefficients for the SYK model for an arbitrary number qqq of interacting fermions and the complete characterization of Krylov complexity for the hypercube graph in any number of dimensions. The latter serves as the starting point for an in-depth comparison between Krylov and circuit complexities as they purportedly arise in the context of black holes. We find that while under certain conditions Krylov complexity follows the growth and saturation pattern ascribed to such systems, the timescale at which saturation happens can generally be shorter than what is predicted by random unitary circuits, due to the effects of quantum speed-ups commonly occurring when comparing quantum and classical random walks.
A recently developed notion, known as spread complexity, captures how a quantum state spreads in Krylov space under unitary evolution. Related Krylov-space approaches are increasingly being investigated for applications in quantum control, simulation, and metrology, as well as are being considered for implementation in near-term quantum platforms. However, its connection to fundamental quantum resources such as entanglement and quantum coherence remains unclear. We show that the dynamics of entanglement is constrained by the extent of spreading in Krylov space. For multipartite systems, we relate state delocalization in the Krylov basis, quantified by the inverse participation ratio, to geometric measures of multipartite quantum correlations. Furthermore, we derive analytical relations between the quantum coherence of the initial state in the energy eigenbasis and spread complexity for qubit and qutrit systems. Our results make progress towards understanding the subtle interplay between the dynamical spreading in Krylov space and fundamental quantum resources.
A bstract Quantifying complexity in quantum systems has witnessed a surge of interest in recent years, with Krylov-based measures such as Krylov complexity ( C K ) and Spread complexity ( C S ) gaining prominence. In this study, we investigate their interplay by considering the complexity of states represented by density matrix operators . After setting up the problem, we analyze a handful of analytical and numerical examples spanning generic two-dimensional Hilbert spaces, qubit states, quantum harmonic oscillators, and random matrix theories, uncovering insightful relationships. For generic pure states, our analysis reveals two key findings: (I) a correspondence between moment-generating functions (of Lanczos coefficients) and survival amplitudes, and (II) an early-time equivalence between C K and 2 C S . Furthermore, for maximally entangled pure states, we find that the moment-generating function of C K becomes the Spectral Form Factor and, at late-times, C K is simply related to NC S for N ≥ 2 within the N -dimensional Hilbert space. Notably, we confirm that C K = 2 C S holds across all times when N = 2. Through the lens of random matrix theories, we also discuss deviations between complexities at intermediate times and highlight subtleties in the averaging approach at the level of the survival amplitude.
Krylov complexity provides a powerful framework for characterizing the dynamical evolution of quantum systems through the spreading of states in Krylov space. The motivation for this is rooted in the optimality of the Krylov basis for the analyzed cost function. In this work, we reinterpret the motivation for the Krylov basis from a dynamical perspective and show that it corresponds to a first-order approximation of the time-evolution operator. We extend this framework to higher-order generators and analytically disprove the optimality assumption by showing that an infinite-order generator can be constructed to exhibit smaller spread for arbitrary times. We propose a natural time scale for the construction of these higher-order generators and discuss results for matrices sampled from Gaussian Unitary Ensembles, demonstrating smaller Krylov complexity at all higher orders. These results extend the framework of Krylov complexity beyond the conventional Krylov basis by disproving the widely held assumption of optimality, extending the construction to higher-order generators, and introducing a physically motivated method for their construction. Our findings therefore suggest that previous statements and results concerning Krylov complexity may need to be reconsidered.
Investigating the time evolution of complexity in quantum systems entails evaluating the spreading of the system's state across a defined basis in its corresponding Hilbert space. Recently, the Krylov basis has been identified as the one that minimizes this spreading. In this study, we develop a numerical exploration of the Krylov complexity in quantum states following a quench in the Lipkin-Meshkov-Glick model. Our results reveal that the long-term averaged Krylov complexity acts as an order parameter for this model. It effectively discriminates between the two dynamic phases induced by the quench, sharing a critical point with the conventional order parameter. Additionally, we examine the inverse participation ratio and the Shannon entropy in both the Krylov basis and the energy basis. A matching dynamic behavior is observed in both bases when the initial state possesses a specific symmetry. This behavior is analytically explained by establishing the equivalence between the Krylov basis and the prequench energy eigenbasis.
A bstract We consider the statistics of the results of a measurement of the spreading operator in the Krylov basis generated by the Hamiltonian of a quantum system starting from a specified initial pure state. We first obtain the probability distribution of the results of measurements of this spreading operator at a certain instant of time, and compute the characteristic function of this distribution. We show that the moments of this characteristic function are related to the so-called generalised spread complexities, and obtain expressions for them in several cases when the Hamiltonian is an element of a Lie algebra. Furthermore, by considering a continuum limit of the Krylov basis, we show that the generalised spread complexities of higher orders have a peak in the time evolution for a random matrix Hamiltonian belonging to the Gaussian unitary ensemble. We also obtain an upper bound in the change in generalised spread complexity at an arbitrary time in terms of the operator norm of the Hamiltonian and discuss the significance of these results.