A Quantum Computational Perspective on Spread Complexity

This paper establishes a direct link between spread complexity and quantum circuit complexity by demonstrating that the former emerges as a limiting case of a synthesis framework involving time-evolution and superposition, offering a physical interpretation and computational advantages over traditional methods like the Lanczos algorithm.

The Gist

Imagine you are trying to build a specific, complex sculpture out of clay. In the world of quantum physics, this "sculpture" is a specific state of a system, and the "clay" is the information that makes up that system.

For a long time, physicists have had two different ways of measuring how "hard" it is to build these sculptures.

1. The "Circuit" Way: This counts how many specific tools (gates) you need to use to turn a simple lump of clay into your target sculpture. It's like counting the number of steps in a recipe.
2. The "Spread" Way: This measures how much the clay has "spread out" or scattered as it evolves over time. It's like measuring how far the clay has rolled away from its original spot.

The problem is that these two ways of measuring have lived in separate worlds. The "Spread" way is great for understanding chaotic systems (like black holes or turbulent fluids), but it's often abstract and hard to calculate. If the math gets too wild (divergent), the standard tools break down.

The Big Idea of This Paper
The authors of this paper have built a bridge between these two worlds. They propose a new way to think about the "Spread" measurement by treating it as a specific type of "Circuit" measurement.

Here is the analogy they use:

The Quantum "Beam Splitter" Setup

Imagine you have a single beam of light (your starting state). You want to turn it into a complex pattern (your target state). To do this, you are allowed to use only two types of tools:

1. The Time-Traveler (Unitary Gate): This tool moves the light forward in time. It's like pressing "Next" on a video player. This costs money (computational effort).
2. The Magic Splitter (Beam Splitter): This tool takes one beam of light and splits it into two, or combines two beams into one. Crucially, in this specific model, this tool is free. It costs nothing.

How They Connect the Dots

The authors asked: "What is the cheapest way to build our target sculpture using these tools?"

They found that if you use the free "Magic Splitter" to create superpositions (mixing beams) and the paid "Time-Traveler" to evolve the system, the most efficient path to build the target state naturally creates a specific set of building blocks.

These building blocks turn out to be exactly the same ones used in the "Spread" measurement (called the Krylov basis).

The "Infinitesimal" Trick
The magic happens when you make the "Time-Traveler" move in tiny, tiny steps (infinitesimal time steps).

• If you take big steps, you get a complex circuit.
• If you shrink the steps down to almost zero, the cost of building the sculpture using this new "splitter" method converges perfectly to the old "Spread" complexity number.

Why This Matters (According to the Paper)

The paper claims this new perspective offers two main benefits:

1. It Gives a Physical Meaning: It explains what the "Spread" complexity actually is. It's not just an abstract math formula; it's the minimum cost of building a state using time-evolution and free superpositions.
2. It Fixes Broken Math: The traditional way to calculate "Spread" complexity (using something called the Lanczos algorithm) often fails if the system gets too crazy or if the numbers get too big (divergent).
   • The Paper's Solution: Their new method only requires you to check the "return amplitude" (a simple measurement of how much the system looks like it started) at specific points in time. It doesn't need derivatives or high-order math that might blow up. It works even when the old methods crash.

A Concrete Example

To prove this works, the authors tested it on a specific mathematical system called SU(2) (which is related to how particles spin).

• They calculated the complexity using their new "circuit" method with different step sizes.
• As they made the time steps smaller and smaller, their new calculation smoothly turned into the known "Spread" complexity result.
• They also showed that for certain tricky scenarios, their method remains stable while traditional methods would fail.

Summary

In short, this paper says: "Spread Complexity" is just "Circuit Complexity" in disguise. If you build a quantum state using time-evolution and free mixing, and you take tiny steps, the cost you pay is exactly the "Spread" complexity. This gives us a new, more robust tool to measure complexity in systems where the old tools break down.

Technical Summary

Technical Summary: A Quantum Computational Perspective on Spread Complexity

Problem Statement
Quantum complexity has developed along two largely parallel tracks: dynamical complexity in physical systems (e.g., operator growth, black hole dynamics) and operational circuit complexity in quantum information. While "spread complexity" has emerged as a powerful diagnostic for quantum chaos, integrability breaking, and phase transitions, its physical interpretation remains abstract. Furthermore, its standard computation relies on the Lanczos algorithm, which requires high-order moments of the Hamiltonian or derivatives of the return amplitude. This approach fails or becomes ill-defined in systems with divergent moments, non-perturbative dynamics, or where the return amplitude is not analytic. This paper seeks to bridge the gap between spread complexity and circuit complexity, providing a physical interpretation for the former and a robust computational method that avoids the limitations of the Lanczos algorithm.

Methodology
The authors propose a computational framework where target states are synthesized using three fundamental operations acting on a system distributed across $n$ "beams":

1. Beam Splitting ($Q$): A unitary operation that maps an $n$-beam vector to an $(n+1)$-beam vector, effectively creating a superposition.
2. Beam Recombination ($S$): A superposition operation that maps an $(n+1)$-beam vector back to an $n$-beam vector, preserving total probability.
3. Unitary Gate ($A$): A standard unitary operation acting on a single beam.

The authors assign computational costs to these operations with specific constraints:

• Beam splitting ($Q$) and recombination ($S$) are assigned zero cost.
• The unitary gate ($A$) is assigned a cost of 1.
• The cost of a channel synthesizing a state is defined by the number of applications of $A$ (circuit depth).

The complexity of a target state $|\psi\rangle$ is defined as the minimal cost required to synthesize it. The authors formulate a cost function based on the probability that the state preparation passes through a channel of depth $k$, weighted by $k$. By minimizing this cost over channel design parameters, they derive an optimal set of mutually orthogonal states $\{|\kappa_n\rangle\}$ generated by the unitary $A$ and zero-cost superpositions.

Key Contributions and Results

1. Derivation of the Orthogonal Basis:
   The authors demonstrate that the optimal synthesis channels produce a basis $\{|\kappa_n\rangle\}$ where each state $|\kappa_n\rangle$ is a linear combination of $\{A^m|\kappa_0\rangle\}_{m=0}^n$. The complexity of a state $|\psi\rangle$ is shown to be the expectation value $\langle \psi | \hat{K} | \psi \rangle$, where $\hat{K} = \sum n |\kappa_n\rangle\langle\kappa_n|$.

2. Connection to Spread Complexity:
   The central result is the demonstration that spread complexity emerges as a limiting case of this circuit complexity framework. When the unitary gate $A$ is identified with an infinitesimal time-evolution operator $A = e^{-i\Delta H}$ and the limit $\Delta \to 0$ is taken:

   • The basis $\{|\kappa_n\rangle\}$ converges to the standard Krylov basis $\{|K_n\rangle\}$ generated by the Hamiltonian $H$.
   • The cost operator $\hat{K}$ converges to the standard spread complexity operator.
   • The circuit complexity converges to the known spread complexity.

3. Computational Advantages:
   Unlike the Lanczos algorithm, which requires derivatives of the return amplitude or high-order moments (which may diverge), the proposed method relies solely on discrete evaluations of the return amplitude $R(\tau) = \langle \kappa_0 | e^{-i\tau H} | \kappa_0 \rangle$.

   • The method utilizes a matrix $S$ constructed from $R(\tau)$ at discrete time steps.
   • The orthogonal basis coefficients are derived via Cholesky (or LU) decomposition of $S$.
   • This approach remains robust in non-perturbative regimes where the return amplitude is well-defined but its Taylor expansion diverges.

4. Explicit $SU(2)$ Example:
   The framework is tested on an $SU(2)$ system with Hamiltonian $H = \alpha(J_+ + J_-)$.

   • For finite time steps $\Delta$, the circuit complexity is calculated explicitly.
   • As $\Delta \to 0$, the results converge to the known analytical expression for spread complexity.
   • The authors note that for finite $\Delta$, the complexity is periodic but not time-reversal symmetric, a feature attributed to the unidirectional nature of the discrete time-step gate $A$.

5. Relation to Nielsen Complexity:
   The paper discusses a connection between this circuit complexity and geometric (Nielsen) complexity. For systems governed by Lie algebras, the Krylov complexity (and by extension, the derived circuit complexity) is shown to be proportional to the geometric Nielsen complexity computed with the $F_1$ cost function, linking operator growth to geodesic motion in the space of unitaries.

Significance and Claims
The authors claim that this work provides a concrete physical interpretation of spread complexity, identifying it as the minimal cost of synthesizing a state using time-evolution and superposition operations. This perspective demystifies spread complexity by anchoring it in a quantum circuit model.

Furthermore, the paper offers a practical computational tool. By bypassing the need for derivatives and high-order moments, the method allows for the calculation of complexity in scenarios where traditional methods fail (e.g., divergent moments or non-perturbative dynamics). The authors emphasize that this framework situates spread complexity within the broader landscape of quantum information, potentially facilitating cross-pollination between high-energy physics and quantum computing, such as designing quantum algorithms for complex dynamics or optimizing circuits using physical intuition.

The paper explicitly notes that this construction does not contradict no-go theorems regarding Krylov complexity as a metric on the space of states, as their circuit model fixes a specific reference state as the input, thereby avoiding the definition of a distance between arbitrary intermediate states. Finally, the authors suggest that their discrete gate approach differs from and complements previous continuous manifold approaches to circuit complexity, particularly in that it does not require the existence of dynamical symmetries.