Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Complexity growth in integrable and chaotic models

Vijay Balasubramanian

Published Jul 4, 2023• 63 citations
Publisher

Abstract

We use the SYK family of models with N Majorana fermions to study the complexity of time evolution, formulated as the shortest geodesic length on the unitary group manifold between the identity and the time evolution operator, in free, integrable, and chaotic systems. Initially, the shortest geodesic follows the time evolution trajectory, and hence complexity grows linearly in time. We study how this linear growth is eventually truncated by the appearance and accumulation of conjugate points, which signal the presence of shorter geodesics intersecting the time evolution trajectory. By explicitly locating such “shortcuts” through analytical and numerical methods, we demonstrate that: (a) in the free theory, time evolution encounters conjugate points at a polynomial time; consequently complexity growth truncates at O($\sqrt{N}$), and we find an explicit operator which “fast-forwards” the free N-fermion time evolution with this complexity, (b) in a class of interacting integrable theories, the complexity is upper bounded by O(poly(N)), and (c) in chaotic theories, we argue that conjugate points do not occur until exponential times O(eN), after which it becomes possible to find infinitesimally nearby geodesics which approximate the time evolution operator. Finally, we explore the notion of eigenstate complexity in free, integrable, and chaotic models.

DOI
10.1007/jhep07%282021%29011

Related papers

Complexity growth in integrable and chaotic models

Vijay Balasubramanian, Matthew P. DeCross, Arjun Kar +2 more

A bstract We use the SYK family of models with N Majorana fermions to study the complexity of time evolution, formulated as the shortest geodesic length on the unitary group manifold between the identity and the time evolution operator, in free, integrable, and chaotic systems. Initially, the shortest geodesic follows the time evolution trajectory, and hence complexity grows linearly in time. We study how this linear growth is eventually truncated by the appearance and accumulation of conjugate points, which signal the presence of shorter geodesics intersecting the time evolution trajectory. By explicitly locating such “shortcuts” through analytical and numerical methods, we demonstrate that: (a) in the free theory, time evolution encounters conjugate points at a polynomial time; consequently complexity growth truncates at O ( $$ \sqrt{N} $$ N ), and we find an explicit operator which “fast-forwards” the free N -fermion time evolution with this complexity, (b) in a class of interacting integrable theories, the complexity is upper bounded by O (poly( N )), and (c) in chaotic theories, we argue that conjugate points do not occur until exponential times O ( e N ), after which it becomes possible to find infinitesimally nearby geodesics which approximate the time evolution operator. Finally, we explore the notion of eigenstate complexity in free, integrable, and chaotic models.

arXiv:2101.02209•Journal of High Energy Physics•Jul 1, 2021•65 citations

Quantum complexity of time evolution with chaotic Hamiltonians

Vijay Balasubramanian

We study the quantum complexity of time evolution in large-N chaotic systems, with the SYK model as our main example. This complexity is expected to increase linearly for exponential time prior to saturating at its maximum value, and is related to the length of minimal geodesics on the manifold of unitary operators that act on Hilbert space. Using the Euler-Arnold formalism, we demonstrate that there is always a geodesic between the identity and the time evolution operator e -iHt whose length grows linearly with time. This geodesic is minimal until there is an obstruction to its minimality, after which it can fail to be a minimum either locally or globally. We identify a criterion — the Eigenstate Complexity Hypothesis (ECH) — which bounds the overlap between offdiagonal energy eigenstate projectors and the k-local operators of the theory, and use it to argue that the linear geodesic will at least be a local minimum for exponential time. We show numerically that the large-N SYK model (which is chaotic) satisfies ECH and thus has no local obstructions to linear growth of complexity for exponential time, as expected from holographic duality. In contrast, we also study the case with N = 2 fermions (which is integrable) and find short-time linear complexity growth followed by oscillations. Our analysis relates complexity to familiar properties of physical theories like their spectra and the structure of energy eigenstates and has implications for the hypothesized computational complexity class separations PSPACE * BQP/poly and PSPACE * BQSUBEXP/subexp, and the “fast-forwarding” of quantum Hamiltonians.

•Jul 4, 2023•104 citations

Quantum complexity of time evolution with chaotic Hamiltonians

Vijay Balasubramanian, Matthew P. DeCross, Arjun Kar +1 more

A bstract We study the quantum complexity of time evolution in large- N chaotic systems, with the SYK model as our main example. This complexity is expected to increase linearly for exponential time prior to saturating at its maximum value, and is related to the length of minimal geodesics on the manifold of unitary operators that act on Hilbert space. Using the Euler-Arnold formalism, we demonstrate that there is always a geodesic between the identity and the time evolution operator e −iHt whose length grows linearly with time. This geodesic is minimal until there is an obstruction to its minimality, after which it can fail to be a minimum either locally or globally. We identify a criterion — the Eigenstate Complexity Hypothesis (ECH) — which bounds the overlap between off- diagonal energy eigenstate projectors and the k -local operators of the theory, and use it to argue that the linear geodesic will at least be a local minimum for exponential time. We show numerically that the large- N SYK model (which is chaotic) satisfies ECH and thus has no local obstructions to linear growth of complexity for exponential time, as expected from holographic duality. In contrast, we also study the case with N = 2 fermions (which is integrable) and find short-time linear complexity growth followed by oscillations. Our analysis relates complexity to familiar properties of physical theories like their spectra and the structure of energy eigenstates and has implications for the hypothesized computational complexity class separations PSPACE "Image missing" BQP/poly and PSPACE "Image missing" BQSUBEXP/subexp, and the “fast-forwarding” of quantum Hamiltonians.

arXiv:1905.05765•Journal of High Energy Physics•Jan 21, 2020•113 citations

Time evolution of the complexity in chaotic systems: a concrete example

Run-Qiu Yang, Keun-young Kim A

Abstract We investigate the time evolution of the complexity of the operator by the Sachdev-Ye-Kitaev (SYK) model with N Majorana fermions. We follow Nielsen’s idea of complexity geometry and geodesics thereof. We show that it is possible that the bi- invariant complexity geometry can exhibit the conjectured time evolution of the complexity in chaotic systems: i) linear growth until t ∼ e N , ii) saturation and small fluctuations after then. We also show that the Lloyd’s bound is realized in this model. Interestingly, these characteristic features appear only if the complexity geometry is the most natural “non-Riemannian” Finsler geometry. This serves as a concrete example showing that the bi-invariant complexity may be a competitive candidate for the complexity in quantum mechanics/field theory (QM/QFT). We provide another argument showing a naturalness of bi-invariant complexity in QM/QFT. That is that the bi-invariance naturally implies the equivalence of the right-invariant complexity and left-invariant complexity, either of which may correspond to the complexity of a given operator. Without bi-invariance, one needs to answer why only right (left) invariant complexity corresponds to the “complexity”, instead of only left (right) invariant complexity.

arXiv:1906.02052•Journal of High Energy Physics•May 11, 2020•36 citations

Bounds on quantum evolution complexity via lattice cryptography

Ben Craps, Marine De Clerck, Oleg Evnin +2 more

We address the difference between integrable and chaotic motion in quantum theory as manifested by the complexity of the corresponding evolution operators. Complexity is understood here as the shortest geodesic distance between the time-dependent evolution operator and the origin within the group of unitaries. (An appropriate 'complexity metric' must be used that takes into account the relative difficulty of performing 'nonlocal’ operations that act on many degrees of freedom at once.) While simply formulated and geometrically attractive, this notion of complexity is numerically intractable save for toy models with Hilbert spaces of very low dimensions. To bypass this difficulty, we trade the exact definition in terms of geodesics for an upper bound on complexity, obtained by minimizing the distance over an explicitly prescribed infinite set of curves, rather than over all possible curves. Identifying this upper bound turns out equivalent to the closest vector problem (CVP) previously studied in integer optimization theory, in particular, in relation to lattice-based cryptography. Effective approximate algorithms are hence provided by the existing mathematical considerations, and they can be utilized in our analysis of the upper bounds on quantum evolution complexity. The resulting algorithmically implemented complexity bound systematically assigns lower values to integrable than to chaotic systems, as we demonstrate by explicit numerical work for Hilbert spaces of dimensions up to \sim 10^4 ∼ 10 4 .

arXiv:2202.13924•SciPost Physics•Oct 11, 2022•28 citations

Operator complexity: a journey to the edge of Krylov space

Eliezer Rabinovici, Adrián Sánchez-Garrido, Ruth Shir +1 more

A bstract Heisenberg time evolution under a chaotic many-body Hamiltonian H transforms an initially simple operator into an increasingly complex one, as it spreads over Hilbert space. Krylov complexity, or ‘K-complexity’, quantifies this growth with respect to a special basis, generated by H by successive nested commutators with the operator. In this work we study the evolution of K-complexity in finite-entropy systems for time scales greater than the scrambling time t s > log( S ). We prove rigorous bounds on K-complexity as well as the associated Lanczos sequence and, using refined parallelized algorithms, we undertake a detailed numerical study of these quantities in the SYK 4 model, which is maximally chaotic, and compare the results with the SYK 2 model, which is integrable. While the former saturates the bound, the latter stays exponentially below it. We discuss to what extent this is a generic feature distinguishing between chaotic vs. integrable systems.

arXiv:2009.01862•Journal of High Energy Physics•Jun 1, 2021•185 citations
We use the SYK family of models with N Majorana fermions to study the complexity of time evolution, formulated as the shortest geodesic length on the unitary group manifold between the identity and the time evolution operator, in free, integrable, and chaotic systems. Initially, the shortest geodesic follows the time evolution trajectory, and hence complexity grows linearly in time. We study how this linear growth is eventually truncated by the appearance and accumulation of conjugate points, which signal the presence of shorter geodesics intersecting the time evolution trajectory. By explicitly locating such “shortcuts” through analytical and numerical methods, we demonstrate that: (a) in the free theory, time evolution encounters conjugate points at a polynomial time; consequently complexity growth truncates at O(N\sqrt{N}N​), and we find an explicit operator which “fast-forwards” the free N-fermion time evolution with this complexity, (b) in a class of interacting integrable theories, the complexity is upper bounded by O(poly(N)), and (c) in chaotic theories, we argue that conjugate points do not occur until exponential times O(eN), after which it becomes possible to find infinitesimally nearby geodesics which approximate the time evolution operator. Finally, we explore the notion of eigenstate complexity in free, integrable, and chaotic models.
A bstract We use the SYK family of models with N Majorana fermions to study the complexity of time evolution, formulated as the shortest geodesic length on the unitary group manifold between the identity and the time evolution operator, in free, integrable, and chaotic systems. Initially, the shortest geodesic follows the time evolution trajectory, and hence complexity grows linearly in time. We study how this linear growth is eventually truncated by the appearance and accumulation of conjugate points, which signal the presence of shorter geodesics intersecting the time evolution trajectory. By explicitly locating such “shortcuts” through analytical and numerical methods, we demonstrate that: (a) in the free theory, time evolution encounters conjugate points at a polynomial time; consequently complexity growth truncates at O ( N \sqrt{N} N​ N ), and we find an explicit operator which “fast-forwards” the free N -fermion time evolution with this complexity, (b) in a class of interacting integrable theories, the complexity is upper bounded by O (poly( N )), and (c) in chaotic theories, we argue that conjugate points do not occur until exponential times O ( e N ), after which it becomes possible to find infinitesimally nearby geodesics which approximate the time evolution operator. Finally, we explore the notion of eigenstate complexity in free, integrable, and chaotic models.
We study the quantum complexity of time evolution in large-N chaotic systems, with the SYK model as our main example. This complexity is expected to increase linearly for exponential time prior to saturating at its maximum value, and is related to the length of minimal geodesics on the manifold of unitary operators that act on Hilbert space. Using the Euler-Arnold formalism, we demonstrate that there is always a geodesic between the identity and the time evolution operator e -iHt whose length grows linearly with time. This geodesic is minimal until there is an obstruction to its minimality, after which it can fail to be a minimum either locally or globally. We identify a criterion — the Eigenstate Complexity Hypothesis (ECH) — which bounds the overlap between offdiagonal energy eigenstate projectors and the k-local operators of the theory, and use it to argue that the linear geodesic will at least be a local minimum for exponential time. We show numerically that the large-N SYK model (which is chaotic) satisfies ECH and thus has no local obstructions to linear growth of complexity for exponential time, as expected from holographic duality. In contrast, we also study the case with N = 2 fermions (which is integrable) and find short-time linear complexity growth followed by oscillations. Our analysis relates complexity to familiar properties of physical theories like their spectra and the structure of energy eigenstates and has implications for the hypothesized computational complexity class separations PSPACE * BQP/poly and PSPACE * BQSUBEXP/subexp, and the “fast-forwarding” of quantum Hamiltonians.
A bstract We study the quantum complexity of time evolution in large- N chaotic systems, with the SYK model as our main example. This complexity is expected to increase linearly for exponential time prior to saturating at its maximum value, and is related to the length of minimal geodesics on the manifold of unitary operators that act on Hilbert space. Using the Euler-Arnold formalism, we demonstrate that there is always a geodesic between the identity and the time evolution operator e −iHt whose length grows linearly with time. This geodesic is minimal until there is an obstruction to its minimality, after which it can fail to be a minimum either locally or globally. We identify a criterion — the Eigenstate Complexity Hypothesis (ECH) — which bounds the overlap between off- diagonal energy eigenstate projectors and the k -local operators of the theory, and use it to argue that the linear geodesic will at least be a local minimum for exponential time. We show numerically that the large- N SYK model (which is chaotic) satisfies ECH and thus has no local obstructions to linear growth of complexity for exponential time, as expected from holographic duality. In contrast, we also study the case with N = 2 fermions (which is integrable) and find short-time linear complexity growth followed by oscillations. Our analysis relates complexity to familiar properties of physical theories like their spectra and the structure of energy eigenstates and has implications for the hypothesized computational complexity class separations PSPACE "Image missing" BQP/poly and PSPACE "Image missing" BQSUBEXP/subexp, and the “fast-forwarding” of quantum Hamiltonians.
Abstract We investigate the time evolution of the complexity of the operator by the Sachdev-Ye-Kitaev (SYK) model with N Majorana fermions. We follow Nielsen’s idea of complexity geometry and geodesics thereof. We show that it is possible that the bi- invariant complexity geometry can exhibit the conjectured time evolution of the complexity in chaotic systems: i) linear growth until t ∼ e N , ii) saturation and small fluctuations after then. We also show that the Lloyd’s bound is realized in this model. Interestingly, these characteristic features appear only if the complexity geometry is the most natural “non-Riemannian” Finsler geometry. This serves as a concrete example showing that the bi-invariant complexity may be a competitive candidate for the complexity in quantum mechanics/field theory (QM/QFT). We provide another argument showing a naturalness of bi-invariant complexity in QM/QFT. That is that the bi-invariance naturally implies the equivalence of the right-invariant complexity and left-invariant complexity, either of which may correspond to the complexity of a given operator. Without bi-invariance, one needs to answer why only right (left) invariant complexity corresponds to the “complexity”, instead of only left (right) invariant complexity.
We address the difference between integrable and chaotic motion in quantum theory as manifested by the complexity of the corresponding evolution operators. Complexity is understood here as the shortest geodesic distance between the time-dependent evolution operator and the origin within the group of unitaries. (An appropriate 'complexity metric' must be used that takes into account the relative difficulty of performing 'nonlocal’ operations that act on many degrees of freedom at once.) While simply formulated and geometrically attractive, this notion of complexity is numerically intractable save for toy models with Hilbert spaces of very low dimensions. To bypass this difficulty, we trade the exact definition in terms of geodesics for an upper bound on complexity, obtained by minimizing the distance over an explicitly prescribed infinite set of curves, rather than over all possible curves. Identifying this upper bound turns out equivalent to the closest vector problem (CVP) previously studied in integer optimization theory, in particular, in relation to lattice-based cryptography. Effective approximate algorithms are hence provided by the existing mathematical considerations, and they can be utilized in our analysis of the upper bounds on quantum evolution complexity. The resulting algorithmically implemented complexity bound systematically assigns lower values to integrable than to chaotic systems, as we demonstrate by explicit numerical work for Hilbert spaces of dimensions up to \sim 10^4 ∼ 10 4 .
A bstract Heisenberg time evolution under a chaotic many-body Hamiltonian H transforms an initially simple operator into an increasingly complex one, as it spreads over Hilbert space. Krylov complexity, or ‘K-complexity’, quantifies this growth with respect to a special basis, generated by H by successive nested commutators with the operator. In this work we study the evolution of K-complexity in finite-entropy systems for time scales greater than the scrambling time t s > log( S ). We prove rigorous bounds on K-complexity as well as the associated Lanczos sequence and, using refined parallelized algorithms, we undertake a detailed numerical study of these quantities in the SYK 4 model, which is maximally chaotic, and compare the results with the SYK 2 model, which is integrable. While the former saturates the bound, the latter stays exponentially below it. We discuss to what extent this is a generic feature distinguishing between chaotic vs. integrable systems.