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:2012.13890

Undecidability of the fate of relaxation in one-dimensional quantum systems

Naoto Shiraishi, Keiji Matsumoto

Published Dec 27, 2020• 2 citations
arXivHTMLPDF

Abstract

We investigate the relaxation dynamics in an isolated quantum many-body system. The stationary value of an observable after relaxation is a topic of researches in the field of quantum thermalization, since thermalization is a relaxation phenomena where this stationary value coincides with the equilibrium value. Therefore, computing the stationary value in quantum many-body systems is regarded as an important problem. We, however, prove that the stationary value in quantum many-body systems is incomputable. More precisely, we show that whether the stationary value is in the vicinity of a given value or not is an undecidable problem. Our undecidable result is still satisfied when we restrict our system to a one-dimensional shift-invariant system with nearest-neighbor interaction, our initial state to a product state of a state on a single site, and our observable to a shift-sum of a one-body observable. This result clearly shows that there is no general theorem or procedure to decide the presence or absence of thermalization in a given quantum many-body system.

DOI
10.48550/arxiv.2012.13890

Related papers

Undecidability in quantum thermalization

Naoto Shiraishi, Keiji Matsumoto

The investigation of thermalization in isolated quantum many-body systems has a long history, dating back to the time of developing statistical mechanics. Most quantum many-body systems in nature are considered to thermalize, while some never achieve thermal equilibrium. The central problem is to clarify whether a given system thermalizes, which has been addressed previously, but not resolved. Here, we show that this problem is undecidable. The resulting undecidability even applies when the system is restricted to one-dimensional shift-invariant systems with nearest-neighbour interaction, and the initial state is a fixed product state. We construct a family of Hamiltonians encoding dynamics of a reversible universal Turing machine, where the fate of a relaxation process changes considerably depending on whether the Turing machine halts. Our result indicates that there is no general theorem, algorithm, or systematic procedure determining the presence or absence of thermalization in any given Hamiltonian.

arXiv:2012.13889•Nature Communications•Aug 24, 2021•26 citations

The Complexity of Thermalization in Finite Quantum Systems

Dhruv Devulapalli, T. C. Mooney, James D. Watson

Thermalization is the process through which a physical system evolves toward a state of thermal equilibrium. Determining whether or not a physical system will thermalize from an initial state has been a key question in condensed matter physics. Closely related questions are determining whether observables in these systems relax to stationary values, and what those values are. Using tools from computational complexity theory, we demonstrate that given a Hamiltonian on a finite-sized system, determining whether or not it thermalizes or relaxes to a given stationary value is computationally intractable, even for a quantum computer. In particular, we show that the problem of determining whether an observable of a finite-sized quantum system relaxes to a given value is PSPACE-complete, and so no efficient algorithm for determining the value is expected to exist. Further, we show the existence of Hamiltonians for which the problem of determining whether the system thermalizes to the Gibbs expectation value is PSPACE-complete. We also show that the related problem of determining whether the system thermalizes to the microcanonical expectation value is contained in PSPACE and is PSPACE-hard under quantum polynomial time reductions. In light of recent results demonstrating undecidability of thermalization in the thermodynamic limit, our work shows that the intractability of the problem is due to inherent difficulties in many-body physics rather than particularities of infinite systems.

arXiv:2507.00405•Jul 1, 2025•0 citations

Powerlaw Decays and Thermalization in Isolated Many-Body Quantum Systems

Marco Távora, Eduardo Jonathan Torres-Herrera, Léa Ferreira dos Santos

Despite being ubiquitous, out-of-equilibrium quantum systems are much less understood than systems at equilibrium. Progress in the field has benefited from a symbiotic relationship between theoretical studies and new experiments on coherent dynamics. The present work strengthens this connection by providing a general picture of the relaxation process of isolated lattice many-body quantum systems that are routinely studied in experiments with cold atoms, ions traps, and nuclear magnetic resonance. We show numerically and analytically that the long-time decay of the probability for finding the system in its initial state necessarily shows a power-law behavior $\propto t^{ - \gamma }$. This happens independently of the details of the system, such as integrability, level repulsion, and the presence or absence of disorder. Information about the spectrum, the structure of the initial state, and the number of particles that interact simultaneously is contained in the value of $\gamma$. From it, we can anticipate whether the initial state will or will not thermalize.

Bulletin of the American Physical Society•Jan 21, 2016•0 citations

Inevitable power-law behavior of isolated many-body quantum systems and how it anticipates thermalization

Marco Távora, Eduardo Jonathan Torres-Herrera, Léa Ferreira dos Santos

Despite being ubiquitous, out-of-equilibrium quantum systems are much less understood than systems at equilibrium. Progress in the field has benefited from a symbiotic relationship between theoretical studies and new experiments on coherent dynamics. The present work strengthens this connection by providing a general picture of the relaxation process of isolated lattice many-body quantum systems that are routinely studied in experiments with cold atoms, ions traps, and nuclear magnetic resonance. We show numerically and analytically that the long-time decay of the probability for finding the system in its initial state necessarily shows a power-law behavior $\ensuremath{\propto}{t}^{\ensuremath{-}\ensuremath{\gamma}}$. This happens independently of the details of the system, such as integrability, level repulsion, and the presence or absence of disorder. Information about the spectrum, the structure of the initial state, and the number of particles that interact simultaneously is contained in the value of $\ensuremath{\gamma}$. From it, we can anticipate whether the initial state will or will not thermalize.

arXiv:1601.05807•Physical Review A•Oct 28, 2016•58 citations

Studying non-equilibrium many-body dynamics using one-dimensional Bose gases

Tim Langen, Michael Gring, Maximilian Kuhnert +7 more

Non-equilibrium dynamics of isolated quantum many-body systems play an important role in many areas of physics. However, a general answer to the question of how these systems relax is still lacking. We experimentally study the dynamics of ultracold one-dimensional (1D) Bose gases. This reveals the existence of a quasi-steady prethermalized state which differs significantly from the thermal equilibrium of the system. Our results demonstrate that the dynamics of non-equilibrium quantum many-body systems is a far richer process than has been assumed in the past.

AIP conference proceedings•Jan 1, 2014•6 citations

Relaxation Dynamics and Pre-thermalization in an Isolated Quantum System

Maximilian Kuhnert, Michael Gring, Tim Langen +6 more

Understanding non-equilibrium dynamics of many-body quantum systems is crucial for many fundamental and applied physics problems ranging from de-coherence and equilibration to the development of future quantum technologies such as quantum computers which are inherently non-equilibrium quantum systems. One of the biggest challenges is that there is no general approach to characterize the resulting quantum states.

Bulletin of the American Physical Society•Feb 27, 2012•3 citations
We investigate the relaxation dynamics in an isolated quantum many-body system. The stationary value of an observable after relaxation is a topic of researches in the field of quantum thermalization, since thermalization is a relaxation phenomena where this stationary value coincides with the equilibrium value. Therefore, computing the stationary value in quantum many-body systems is regarded as an important problem. We, however, prove that the stationary value in quantum many-body systems is incomputable. More precisely, we show that whether the stationary value is in the vicinity of a given value or not is an undecidable problem. Our undecidable result is still satisfied when we restrict our system to a one-dimensional shift-invariant system with nearest-neighbor interaction, our initial state to a product state of a state on a single site, and our observable to a shift-sum of a one-body observable. This result clearly shows that there is no general theorem or procedure to decide the presence or absence of thermalization in a given quantum many-body system.
The investigation of thermalization in isolated quantum many-body systems has a long history, dating back to the time of developing statistical mechanics. Most quantum many-body systems in nature are considered to thermalize, while some never achieve thermal equilibrium. The central problem is to clarify whether a given system thermalizes, which has been addressed previously, but not resolved. Here, we show that this problem is undecidable. The resulting undecidability even applies when the system is restricted to one-dimensional shift-invariant systems with nearest-neighbour interaction, and the initial state is a fixed product state. We construct a family of Hamiltonians encoding dynamics of a reversible universal Turing machine, where the fate of a relaxation process changes considerably depending on whether the Turing machine halts. Our result indicates that there is no general theorem, algorithm, or systematic procedure determining the presence or absence of thermalization in any given Hamiltonian.
Thermalization is the process through which a physical system evolves toward a state of thermal equilibrium. Determining whether or not a physical system will thermalize from an initial state has been a key question in condensed matter physics. Closely related questions are determining whether observables in these systems relax to stationary values, and what those values are. Using tools from computational complexity theory, we demonstrate that given a Hamiltonian on a finite-sized system, determining whether or not it thermalizes or relaxes to a given stationary value is computationally intractable, even for a quantum computer. In particular, we show that the problem of determining whether an observable of a finite-sized quantum system relaxes to a given value is PSPACE-complete, and so no efficient algorithm for determining the value is expected to exist. Further, we show the existence of Hamiltonians for which the problem of determining whether the system thermalizes to the Gibbs expectation value is PSPACE-complete. We also show that the related problem of determining whether the system thermalizes to the microcanonical expectation value is contained in PSPACE and is PSPACE-hard under quantum polynomial time reductions. In light of recent results demonstrating undecidability of thermalization in the thermodynamic limit, our work shows that the intractability of the problem is due to inherent difficulties in many-body physics rather than particularities of infinite systems.
Despite being ubiquitous, out-of-equilibrium quantum systems are much less understood than systems at equilibrium. Progress in the field has benefited from a symbiotic relationship between theoretical studies and new experiments on coherent dynamics. The present work strengthens this connection by providing a general picture of the relaxation process of isolated lattice many-body quantum systems that are routinely studied in experiments with cold atoms, ions traps, and nuclear magnetic resonance. We show numerically and analytically that the long-time decay of the probability for finding the system in its initial state necessarily shows a power-law behavior ∝t−γ\propto t^{ - \gamma }∝t−γ. This happens independently of the details of the system, such as integrability, level repulsion, and the presence or absence of disorder. Information about the spectrum, the structure of the initial state, and the number of particles that interact simultaneously is contained in the value of γ\gammaγ. From it, we can anticipate whether the initial state will or will not thermalize.
Despite being ubiquitous, out-of-equilibrium quantum systems are much less understood than systems at equilibrium. Progress in the field has benefited from a symbiotic relationship between theoretical studies and new experiments on coherent dynamics. The present work strengthens this connection by providing a general picture of the relaxation process of isolated lattice many-body quantum systems that are routinely studied in experiments with cold atoms, ions traps, and nuclear magnetic resonance. We show numerically and analytically that the long-time decay of the probability for finding the system in its initial state necessarily shows a power-law behavior $\ensuremath{\propto}{t}^{\ensuremath{-}\ensuremath{\gamma}}$. This happens independently of the details of the system, such as integrability, level repulsion, and the presence or absence of disorder. Information about the spectrum, the structure of the initial state, and the number of particles that interact simultaneously is contained in the value of $\ensuremath{\gamma}$. From it, we can anticipate whether the initial state will or will not thermalize.
Non-equilibrium dynamics of isolated quantum many-body systems play an important role in many areas of physics. However, a general answer to the question of how these systems relax is still lacking. We experimentally study the dynamics of ultracold one-dimensional (1D) Bose gases. This reveals the existence of a quasi-steady prethermalized state which differs significantly from the thermal equilibrium of the system. Our results demonstrate that the dynamics of non-equilibrium quantum many-body systems is a far richer process than has been assumed in the past.