A quantum walk is like a drunk person who turns randomly at every intersection. Except instead of streets, there are graph nodes, and instead of steps, there are quantum transitions. Scientists have discovered that such a walk has a hidden measure — Krylov complexity. It shows how quickly a system's state 'spreads out' over the available options.
To compute this measure, the authors propose a trick: any graph can be compressed into a simple chain, as if all intersections were lined up in a single row. On this chain, Krylov complexity is calculated using standard methods. This approach allowed them to compute, for the first time, the exact Lanczos coefficients for the SYK model — a popular model of black holes where an arbitrary number of fermions interact. They also fully described the complexity for the hypercube — a graph where nodes are connected like the corners of a multidimensional cube.
The most interesting part is the comparison with another measure of complexity that arises in the context of black holes. It turns out that Krylov complexity on the hypercube grows and reaches a plateau, just as random quantum circuits predict. But the saturation time can be shorter. The reason is quantum speedup: a quantum walk spreads faster than a classical random walk, as if the drunk person sometimes covered two blocks in a single step.
This work bridges two worlds: graph theory and black hole physics. It provides a new tool for assessing the complexity of quantum systems and may help understand how information behaves inside black holes.
as written by the authors arXiv:2602.04949
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.
A quantum walk on a hypercube can reach a node that a classical random walk would only visit after exponentially long time: this is called quantum speedup.
The idea of quantum speedup on graphs echoes the plot of the movie 'Interstellar', where heroes use a wormhole to shorten the path between distant points in space.