Квантовое блуждание похоже на пьяного человека, который на каждом перекрёстке сворачивает случайно. Только вместо улиц — узлы графа, а вместо шагов — квантовые переходы. Учёные выяснили, что у такого блуждания есть скрытая мера — сложность Крылова. Она показывает, насколько быстро состояние системы «расплывается» по доступным вариантам.

Чтобы эту меру посчитать, авторы предлагают трюк: любой граф можно сжать в простую цепочку, как если бы все перекрёстки выстроились в одну линию. На этой цепочке сложность Крылова считается стандартными методами. Такой подход позволил впервые точно вычислить коэффициенты Ланцоша для модели SYK — популярной модели чёрных дыр, где взаимодействует произвольное число фермионов. А ещё полностью описать сложность для гиперкуба — графа, где узлы соединены как углы многомерного куба.

Самое интересное — сравнение с другой мерой сложности, которая возникает в контексте чёрных дыр. Оказалось, что сложность Крылова на гиперкубе растёт и выходит на плато, как и предсказывают случайные квантовые схемы. Но время насыщения может быть короче. Причина — квантовое ускорение: квантовое блуждание распространяется быстрее классического случайного блуждания, как если бы пьяный человек иногда проходил два квартала за один шаг.

Эта работа связывает два мира: теорию графов и физику чёрных дыр. Она даёт новый инструмент для оценки сложности квантовых систем и может помочь понять, как информация ведёт себя внутри чёрных дыр.