Une marche quantique ressemble à un homme ivre qui tourne au hasard à chaque intersection. Mais au lieu de rues, il y a des nœuds de graphe, et au lieu de pas, des transitions quantiques. Les scientifiques ont découvert que cette marche possède une mesure cachée : la complexité de Krylov. Elle indique à quelle vitesse l'état du système « s'étale » parmi les options disponibles.
Pour calculer cette mesure, les auteurs proposent une astuce : n'importe quel graphe peut être compressé en une simple chaîne, comme si toutes les intersections s'alignaient sur une seule ligne. Sur cette chaîne, la complexité de Krylov se calcule par des méthodes standard. Cette approche a permis pour la première fois de calculer précisément les coefficients de Lanczos pour le modèle SYK — un modèle populaire de trous noirs où un nombre arbitraire de fermions interagit. Elle a aussi permis de décrire entièrement la complexité pour l'hypercube — un graphe où les nœuds sont connectés comme les sommets d'un cube multidimensionnel.
Le plus intéressant est la comparaison avec une autre mesure de complexité qui apparaît dans le contexte des trous noirs. Il s'avère que la complexité de Krylov sur l'hypercube croît et atteint un plateau, comme le prédisent les circuits quantiques aléatoires. Mais le temps de saturation peut être plus court. La raison en est l'accélération quantique : une marche quantique se propage plus vite qu'une marche aléatoire classique, comme si l'homme ivre parcourait parfois deux pâtés de maisons en un seul pas.
Ce travail relie deux mondes : la théorie des graphes et la physique des trous noirs. Il offre un nouvel outil pour évaluer la complexité des systèmes quantiques et pourrait aider à comprendre comment l'information se comporte à l'intérieur des trous noirs.
tel que rédigé par les auteurs, en anglais 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.
Une marche quantique sur un hypercube peut atteindre un nœud qu'une marche aléatoire classique ne visite qu'après un temps exponentiellement long — c'est ce qu'on appelle l'accélération quantique.
L'idée d'accélération quantique sur les graphes fait écho à l'intrigue du film « Interstellar », où les héros utilisent un trou de ver pour raccourcir le chemin entre des points éloignés de l'espace.