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

This paper establishes a canonical link between quantum random walks on graphs and Krylov complexity to analytically compute Lanczos coefficients for the SYK model and characterize hypercube complexity, revealing that while Krylov complexity mimics black hole growth patterns, it saturates faster than circuit complexity due to quantum speed-ups.

The Gist

Imagine you are trying to understand how "complicated" a system gets as time passes. In the world of quantum physics, this is a huge question, especially when trying to understand black holes. This paper by Dimitrios Patramanis and Watse Sybesma offers a new way to look at this problem by treating quantum systems like a game of "walks" on a map.

Here is a breakdown of their findings using simple analogies:

1. The Map and the Walker

Think of a complex quantum system (like a collection of interacting particles) as a giant, invisible map made of dots (vertices) connected by lines (edges).

• The Classical Walker: Imagine a drunk person stumbling randomly from dot to dot. They move slowly, get confused, and eventually settle into a pattern where they just wander around the middle of the map. This is like a classical random walk.
• The Quantum Walker: Now, imagine a ghostly, magical walker. Because of quantum rules, this walker doesn't just pick one path; it spreads out like a wave, exploring many paths at once. It moves much faster and more efficiently than the drunk walker. This is a quantum walk.

2. Turning the Map into a Ladder

The authors discovered a clever trick. No matter how messy or complex the map looks, if you start at a specific point and organize the dots by how far they are from the start, you can flatten the whole map into a simple straight ladder (or a chain).

• The Ladder Rungs: Each rung on the ladder represents a "neighborhood" of dots on the original map.
• The Complexity: As the quantum walker moves up this ladder, the "distance" it travels from the bottom rung becomes a measure of complexity.
  • If the walker stays at the bottom, the system is simple.
  • If the walker climbs high up the ladder, the system has become very complex.

This "ladder" is what physicists call a Krylov chain, and the distance the walker travels is Krylov complexity. The paper proves that this mathematical ladder isn't just a random invention; it naturally emerges from the geometry of the graph itself.

3. Two Key Examples

The authors tested this idea on two famous types of maps to see how complexity behaves:

A. The Hypercube (The High-Dimensional Cube)

• The Setup: Imagine a cube, but in many dimensions. It's a very structured map.
• The Result:
  • Classical Walker: The drunk walker moves up the ladder, but eventually gets stuck near the middle. The complexity grows, then stops (saturates). This matches what we expect from black holes in some theories.
  • Quantum Walker: The ghostly walker zooms up the ladder, but instead of stopping, it bounces back and forth like a pendulum. It never really "settles."
  • The Twist: If you take an "average" of the quantum walker's position over a long time, it looks like it settles, similar to the classical walker. However, the quantum walker gets to that "settled" state much faster. This is a "quantum speed-up."

B. The SYK Model (The Chaotic Soup)

• The Setup: This is a famous model for a chaotic system (often used to study black holes). The authors mapped this chaos onto a specific tree-like graph.
• The Result: They were able to calculate exactly how the complexity grows for this system for any number of particles. They found that the "ladder" for this system has a specific shape that matches the behavior of chaotic systems, confirming that their method works for real, difficult physics problems.

4. The Big Takeaway: Speed vs. Saturation

The most important finding is about time.

• In the past, scientists thought complexity grew linearly (like a straight line) and then stopped. This was based on models using classical randomness.
• The authors show that quantum systems behave differently. They grow, but they also oscillate (wiggle) and, crucially, they reach their maximum complexity much faster than classical models predict.
• Why? Because the quantum walker can "teleport" through the map using quantum interference, whereas the classical walker has to stumble through every step.

Summary

This paper connects two different ways of thinking about randomness:

1. Quantum Walks: How particles move on a graph.
2. Krylov Complexity: How complicated a system gets over time.

They found that these two concepts are actually the same thing viewed from different angles. By turning a complex graph into a simple ladder, they can calculate exactly how fast a system becomes complex. Their main discovery is that quantum systems become complex and "saturate" (stop growing) much faster than classical systems, thanks to the unique speed of quantum mechanics. This helps refine our understanding of how black holes and other complex quantum systems evolve.

Technical Summary

Technical Summary: Emergence of Krylov Complexity through Quantum Walks

Problem Statement
This work investigates the relationship between two distinct concepts in theoretical physics: continuous-time quantum walks (CTQWs) on graphs and Krylov (or spread) complexity. While quantum walks are established tools for studying quantum algorithms and transport, and Krylov complexity has emerged as a primary measure for operator growth and state complexity in quantum chaos and holography, their structural connection has remained underexplored. The authors aim to demonstrate that the definition of Krylov complexity naturally emerges from the dynamics of a quantum walk on a graph. Furthermore, the paper seeks to utilize this correspondence to compute complexity measures for specific physical systems (such as the SYK model and hypercubes) and to compare these quantum walk results with the circuit complexity derived from classical random walks, particularly in the context of black hole dynamics.

Methodology
The authors employ a two-way approach, establishing a rigorous correspondence between graph theory and the Lanczos algorithm:

1. Graph Reduction to a Chain: The core methodology involves reducing the dynamics of a CTQW on an arbitrary graph to a one-dimensional chain. By selecting an initial state (a vertex or set of vertices), the authors define a "neighborhood partition" of the graph based on distance layers. They construct "neighborhood states" (superpositions of vertices within a specific distance layer) which form an orthonormal basis.
2. Identification of Krylov Structure: The authors demonstrate that the action of the graph's adjacency matrix (serving as the Hamiltonian) on these neighborhood states results in a tridiagonal matrix structure. The coefficients of this tridiagonal matrix are identified as the Lanczos coefficients ($a_n$ and $b_n$). Consequently, the average distance of the walker from the origin on this effective chain is identified as the Krylov/spread complexity ($C_K$).
3. Analytic Computation: Using this framework, the authors derive analytic expressions for Lanczos coefficients for specific graph families corresponding to physical systems. They analyze the SYK model by mapping operator growth to a graph of tree generations (related to Fuss-Catalan numbers) and analyze the hypercube graph using binomial coefficients for neighborhood sizes.
4. Comparison with Classical Walks: The paper compares the time-dependent Krylov complexity of quantum walks against the circuit complexity derived from classical random walks on the same graphs (specifically the hypercube). This involves analyzing time-averaged behaviors and saturation timescales.

Key Contributions and Results

• Formal Derivation of Krylov Complexity: The paper provides a constructive proof that for any graph supporting a CTQW, a "Krylov chain" exists. The neighborhood basis of the graph corresponds exactly to the Krylov basis, and the transition amplitudes between layers correspond to the Lanczos coefficients.
• SYK Model Complexity: The authors derive an analytic expression for the Lanczos coefficients of the SYK model for an arbitrary number of interacting fermions $q$. Unlike previous works that relied on large-$q$ limits or disorder averaging, this result is derived for a single instance of the Hamiltonian. The resulting coefficients differ slightly from the standard large-$q$ limit (involving a factor converging to $e^{-1/2}$), which the authors attribute to the coarse-graining effects of disorder averaging in previous derivations.
• Hypercube Characterization: The paper provides a complete characterization of Krylov complexity for the hypercube graph in any dimension $D$. The Lanczos coefficients are found to be $b_n = \frac{1}{D}\sqrt{n(D-n+1)}$, which corresponds to the $SU(2)$ symmetry algebra. The resulting complexity is $C_K(t) = D \sin^2(t/D)$.
• Quantum vs. Classical Saturation: A detailed comparison reveals that while classical random walks on the hypercube exhibit linear growth followed by saturation at $C \sim D/2$ with a timescale scaling as $D \log D$, the quantum walk exhibits oscillatory behavior. However, upon time-averaging, the quantum complexity also saturates at $D/2$. Crucially, the authors find that the saturation timescale for the quantum walk scales linearly with $D$ ($T_{sat} \sim \pi D$), which is significantly faster than the classical $D \log D$ scaling. This is attributed to quantum speed-ups inherent in quantum walks compared to classical diffusion.
• Graph Families and Symmetry: The authors classify graphs based on the growth of their Lanczos coefficients (e.g., constant, $\sqrt{n}$, $n$), linking these to specific symmetries (Heisenberg-Weyl, $SL(2,R)$) and dynamical properties (integrable vs. chaotic).

Significance and Claims
The paper claims to offer a "rediscovery" of Krylov complexity from the perspective of quantum walks, providing a unified framework that connects graph theory, quantum algorithms, and high-energy physics.

• Unification: It establishes that the "Krylov chain" is not merely an abstract mathematical construct but a physical reality arising from the symmetry of graph neighborhoods.
• Computational Utility: The framework allows for the analytic computation of complexity measures for systems where direct calculation is difficult, such as the SYK model for arbitrary $q$.
• Black Hole Physics Context: In the context of black holes (modeled via the Hayden-Preskill circuit and random unitary circuits), the paper suggests that while Krylov complexity and circuit complexity share similar growth and saturation patterns after time averaging, the underlying quantum dynamics (quantum walks) exhibit faster saturation timescales due to quantum speed-ups. This implies that the "scrambling" or thermalization timescales in quantum systems may be shorter than those predicted by classical random walk models often used in holographic conjectures.
• Limitations: The authors modestly note that the equivalence between the quantum walk reduction and the Krylov basis relies on the existence of an "equitable partition" (distance regularity) in the graph. For graphs lacking this symmetry, the reduction is not straightforward. Additionally, the paper acknowledges that the difference in early-time behavior (quadratic for quantum vs. linear for classical) remains an open question regarding the physical interpretation of these measures.

The work concludes that the interface between quantum walks and complexity theory offers a promising avenue for understanding the quantum origins of complexity, particularly in distinguishing between classical stochastic processes and genuine quantum dynamics in chaotic systems.