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.