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

• URL: http://arxiv.org/abs/2602.04949v1
• Date: Wed, 04 Feb 2026 19:00:00 GMT
• Title: Emergence of Krylov complexity through quantum walks: An exploration of the quantum origins of complexity
• Authors: Dimitrios Patramanis, Watse Sybesma,
• Abstract summary: We study the relationship between quantum random walks on graphs and Krylov/spread complexity.<n>We show that the latter's definition naturally emerges through a canonical method of reducing a graph to a chain.<n>We use this identification to construct families of graphs corresponding to special classes of systems with known complexity features.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Average-case quantum complexity from glassiness [45.57609001239456]
  Glassiness -- a phenomenon in physics characterized by a rough free-energy landscape -- implies hardness for stable classical algorithms.<n>We prove that the standard notion of quantum glassiness based on replica symmetry breaking obstructs stable quantum algorithms for Gibbs sampling.
  arXiv  Detail & Related papers  (2025-10-09T17:37:33Z)
• Direct probing of the simulation complexity of open quantum many-body dynamics [42.085941481155295]
  We study the role of dissipation in simulating open-system dynamics using both quantum and classical methods.<n>Our results show that dissipation affects correlation length and mixing time in distinct ways at intermediate and long timescales.
  arXiv  Detail & Related papers  (2025-08-27T15:14:36Z)
• Quantum complexity phase transition in fermionic quantum circuits [14.723621424225973]
  We develop a general scaling theory for Krylov complexity phase transitions on quantum percolation models.<n>For non-interacting systems across diverse lattices, our scaling theory reveals that the KCPT coincides with the classical percolation transition.<n>For interacting systems, we find the KCPT develops a generic separation from the percolation transition due to the highly complex quantum many-body effects.
  arXiv  Detail & Related papers  (2025-07-29T18:00:25Z)
• Krylov Complexity as a Probe for Chaos [0.7373617024876725]
  We show that the dynamics towards saturation precisely distinguish between chaotic and integrable systems.<n>For chaotic models, the saturation value of complexity reaches its infinite time average at a finite saturation time.<n>In integrable models, complexity approaches the infinite time average value from below at a much longer timescale.
  arXiv  Detail & Related papers  (2024-08-19T17:52:42Z)
• Krylov complexity of fermion chain in double-scaled SYK and power spectrum perspective [0.0]
  We investigate Krylov complexity of the fermion chain operator which consists of multiple Majorana fermions in the double-scaled SYK (DSSYK) model with finite temperature. Using the fact that Krylov complexity is computable from two-point functions, the analysis is performed in the limit where the two-point function becomes simple. We confirm the exponential growth of Krylov complexity in the very low temperature regime.
  arXiv  Detail & Related papers  (2024-07-18T08:47:05Z)
• KPZ scaling from the Krylov space [83.88591755871734]
  Recently, a superdiffusion exhibiting the Kardar-Parisi-Zhang scaling in late-time correlators and autocorrelators has been reported. Inspired by these results, we explore the KPZ scaling in correlation functions using their realization in the Krylov operator basis.
  arXiv  Detail & Related papers  (2024-06-04T20:57:59Z)
• Spread complexity and quantum chaos for periodically driven spin chains [0.0]
  We study the dynamics of spread complexity for quantum maps using the Arnoldi iterative procedure. We find distinctive behaviour of the Arnoldi coefficients and spread complexity for regular vs. chaotic dynamics.
  arXiv  Detail & Related papers  (2024-05-25T11:17:43Z)
• On the quantum time complexity of divide and conquer [42.7410400783548]
  We study the time complexity of quantum divide and conquer algorithms for classical problems. We apply these theorems to an array of problems involving strings, integers, and geometric objects.
  arXiv  Detail & Related papers  (2023-11-28T01:06:03Z)
• Krylov complexity and chaos in quantum mechanics [0.0]
  We numerically evaluate Krylov complexity for operators and states. We find a clear correlation between variances of Lanczos coefficients and classical Lyapunov exponents. Our work provides a firm bridge between Krylov complexity and classical/quantum chaos.
  arXiv  Detail & Related papers  (2023-05-26T06:32:45Z)
• Krylov complexity in quantum field theory, and beyond [41.99844472131922]
  We study Krylov complexity in various models of quantum field theory.<n>We find that the exponential growth of Krylov complexity satisfies the conjectural inequality, which generalizes the Maldacena-Shenker-Stanford bound on chaos.
  arXiv  Detail & Related papers  (2022-12-29T19:00:00Z)
• Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms [55.41644538483948]
  In particular, some steps of the implementation, as state preparation and readout processes, can surpass the complexity aspects of the algorithm itself. We present the complexity involved in the full implementation of quantum algorithms for solving linear systems of equations and linear system of differential equations.
  arXiv  Detail & Related papers  (2021-06-23T16:33:33Z)
• Operator complexity: a journey to the edge of Krylov space [0.0]
  Krylov complexity, or K-complexity', quantifies this growth with respect to a special basis. We study the evolution of K-complexity in finite-entropy systems for time scales greater than the scrambling time.
  arXiv  Detail & Related papers  (2020-09-03T18:10:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.