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

arXiv:2209.14689 · Physics Letters B

On quantum complexity

Mohsen Alishahiha

Published May 25, 2023• 12 citations
arXivHTMLPDF

Abstract

The ETH ansatz for matrix elements of a given operator in the energy eigenstate basis results in a notion of thermalization for a chaotic system. In this context for a certain quantity - to be found for a given model - one may impose a particular condition on its matrix elements in the energy eigenstate basis so that the corresponding quantity exhibits linear growth at late times. The condition is to do with a possible pole structure the corresponding matrix elements may have. Based on the general expectation of complexity one may want to think of this quantity as a possible candidate for the quantum complexity. We note, however, that for the explicit examples we have considered in this paper, there are infinitely many quantities exhibiting similar behavior.

DOI
10.1016/j.physletb.2023.137979

Related papers

Bounds on Chaos from the Eigenstate Thermalization Hypothesis

Chaitanya Murthy, Mark Srednicki

We show that the known bound on the growth rate of the out-of-time-order four-point correlator in chaotic many-body quantum systems follows directly from the general structure of operator matrix elements in systems that obey the eigenstate thermalization hypothesis. This ties together two key paradigms of thermal behavior in isolated many-body quantum systems.

arXiv:1906.10808•Physical Review Letters•Dec 3, 2019•135 citations

Why ETH? On thermalization and locality

Stefan Eccles

The eigenstate thermalization hypothesis (ETH) is foundational to modern discussions of thermalization in closed quantum systems. In this work, we expand on traditional explanations for the prevalence of ETH by emphasizing the role of operator locality. We introduce an operator-specific perturbation problem that can be thought of as a means of understanding the onset or breakdown of ETH for specific classes of operators in a given system. We derive explicit functional forms for the off-diagonal variances of operator matrix elements for typical local operators under various `scrambling ansatzes', expressed in terms of system parameters and parameters of the corresponding perturbation problem. We provide simple tests and illustrations of these ideas in chaotic spin chain systems.

arXiv:2502.04784•Feb 7, 2025•0 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

Microstate distinguishability, quantum complexity, and the eigenstate thermalization hypothesis

Ning Bao, Jason Pollack, David Wakeham +1 more

Abstract In this work, we use quantum complexity theory to quantify the difficulty of distinguishing eigenstates obeying the eigenstate thermalization hypothesis (ETH). After identifying simple operators with an algebra of low-energy observables and tracing out the complementary high-energy Hilbert space, the ETH leads to an exponential suppression of trace distance between the coarse-grained eigenstates. Conversely, we show that an exponential hardness of distinguishing between states implies ETH-like matrix elements. The BBBV lower bound on the query complexity of Grover search then translates directly into a complexity-theoretic statement lower bounding the hardness of distinguishing these reduced states.

arXiv:2009.00632•Classical and Quantum Gravity•Jun 23, 2021•5 citations

Out-of-time-order correlations and the fine structure of eigenstate thermalization

Marlon Brenes, Silvia Pappalardi, Mark T. Mitchison +2 more

Out-of-time-order correlators (OTOCs) have become established as a tool to characterise quantum information dynamics and thermalization in interacting quantum many-body systems. It was recently argued that the expected exponential growth of the OTOC is connected to the existence of correlations beyond those encoded in the standard Eigenstate Thermalization Hypothesis (ETH). We show explicitly, by an extensive numerical analysis of the statistics of operator matrix elements in conjunction with a detailed study of OTOC dynamics, that the OTOC is indeed a precise tool to explore the fine details of the ETH. In particular, while short-time dynamics is dominated by correlations, the long-time saturation behavior gives clear indications of an operator-dependent energy scale ω_{GOE} associated to the emergence of an effective Gaussian random matrix theory. We provide an estimation of the finite-size scaling of ω_{GOE} for the general class of observables composed of sums of local operators in the infinite-temperature regime and found linear behavior for the models considered.

arXiv:2103.01161•Physical review. E•Sep 15, 2021•52 citations

Matrix Models for Eigenstate Thermalization

Daniel Louis Jafferis, David K. Kolchmeyer, Baur Mukhametzhanov +1 more

A new theoretical framework of chaotic, thermalizing quantum many-body systems unifies several extant, disjoint descriptions and points toward unexpected connections between quantum chaos and quantum gravity.

Physical Review X•Sep 20, 2023•30 citations
The ETH ansatz for matrix elements of a given operator in the energy eigenstate basis results in a notion of thermalization for a chaotic system. In this context for a certain quantity - to be found for a given model - one may impose a particular condition on its matrix elements in the energy eigenstate basis so that the corresponding quantity exhibits linear growth at late times. The condition is to do with a possible pole structure the corresponding matrix elements may have. Based on the general expectation of complexity one may want to think of this quantity as a possible candidate for the quantum complexity. We note, however, that for the explicit examples we have considered in this paper, there are infinitely many quantities exhibiting similar behavior.
The eigenstate thermalization hypothesis (ETH) is foundational to modern discussions of thermalization in closed quantum systems. In this work, we expand on traditional explanations for the prevalence of ETH by emphasizing the role of operator locality. We introduce an operator-specific perturbation problem that can be thought of as a means of understanding the onset or breakdown of ETH for specific classes of operators in a given system. We derive explicit functional forms for the off-diagonal variances of operator matrix elements for typical local operators under various `scrambling ansatzes', expressed in terms of system parameters and parameters of the corresponding perturbation problem. We provide simple tests and illustrations of these ideas in chaotic spin chain systems.
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 In this work, we use quantum complexity theory to quantify the difficulty of distinguishing eigenstates obeying the eigenstate thermalization hypothesis (ETH). After identifying simple operators with an algebra of low-energy observables and tracing out the complementary high-energy Hilbert space, the ETH leads to an exponential suppression of trace distance between the coarse-grained eigenstates. Conversely, we show that an exponential hardness of distinguishing between states implies ETH-like matrix elements. The BBBV lower bound on the query complexity of Grover search then translates directly into a complexity-theoretic statement lower bounding the hardness of distinguishing these reduced states.
Out-of-time-order correlators (OTOCs) have become established as a tool to characterise quantum information dynamics and thermalization in interacting quantum many-body systems. It was recently argued that the expected exponential growth of the OTOC is connected to the existence of correlations beyond those encoded in the standard Eigenstate Thermalization Hypothesis (ETH). We show explicitly, by an extensive numerical analysis of the statistics of operator matrix elements in conjunction with a detailed study of OTOC dynamics, that the OTOC is indeed a precise tool to explore the fine details of the ETH. In particular, while short-time dynamics is dominated by correlations, the long-time saturation behavior gives clear indications of an operator-dependent energy scale ω_{GOE} associated to the emergence of an effective Gaussian random matrix theory. We provide an estimation of the finite-size scaling of ω_{GOE} for the general class of observables composed of sums of local operators in the infinite-temperature regime and found linear behavior for the models considered.