Квантовое блуждание похоже на пьяного человека, который на каждом перекрёстке сворачивает случайно. Только вместо улиц — узлы графа, а вместо шагов — квантовые переходы. Учёные выяснили, что у такого блуждания есть скрытая мера — сложность Крылова. Она показывает, насколько быстро состояние системы «расплывается» по доступным вариантам.
Чтобы эту меру посчитать, авторы предлагают трюк: любой граф можно сжать в простую цепочку, как если бы все перекрёстки выстроились в одну линию. На этой цепочке сложность Крылова считается стандартными методами. Такой подход позволил впервые точно вычислить коэффициенты Ланцоша для модели SYK — популярной модели чёрных дыр, где взаимодействует произвольное число фермионов. А ещё полностью описать сложность для гиперкуба — графа, где узлы соединены как углы многомерного куба.
Самое интересное — сравнение с другой мерой сложности, которая возникает в контексте чёрных дыр. Оказалось, что сложность Крылова на гиперкубе растёт и выходит на плато, как и предсказывают случайные квантовые схемы. Но время насыщения может быть короче. Причина — квантовое ускорение: квантовое блуждание распространяется быстрее классического случайного блуждания, как если бы пьяный человек иногда проходил два квартала за один шаг.
Эта работа связывает два мира: теорию графов и физику чёрных дыр. Она даёт новый инструмент для оценки сложности квантовых систем и может помочь понять, как информация ведёт себя внутри чёрных дыр.
как её написали авторы, на английском 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.
Квантовое блуждание на гиперкубе может достигать узла, который классическое случайное блуждание посещает лишь за экспоненциально большое время — это называют квантовым ускорением.
Идея квантового ускорения на графах перекликается с сюжетом фильма «Интерстеллар», где герои используют кротовую нору, чтобы сократить путь между далёкими точками пространства.