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.
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.