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

The Complexity of Thermalization in Finite Quantum Systems

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

Published Jul 1, 2025• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2507.00405

Related papers

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

Naoto Shiraishi, Keiji Matsumoto

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.

arXiv:2012.13890•Dec 27, 2020•2 citations

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

Strong and Weak Thermalization of Infinite Nonintegrable Quantum Systems

Mari Carmen Bañuls, J. I. Cirac, M. B. Hastings

When a nonintegrable system evolves out of equilibrium for a long time, local observables are in general expected to attain stationary expectation values, independent of the details of the initial state. But the thermalization of a closed quantum system is not yet well understood. Here we show that it presents indeed a much richer phenomenology than its classical counterpart. Using a new numerical technique, we identify two distinct regimes, strong and weak, occurring for different initial states. Strong thermalization, intrinsically quantum, happens when instantaneous local expectation values converge to the thermal ones. Weak thermalization, well known in classical systems, shows convergence to thermal values only after time averaging. Remarkably, we find a third group of states showing no thermalization, neither strong nor weak, to the time scales one can reliably simulate.

arXiv:1007.3957•Physical Review Letters•Feb 4, 2011•358 citations

Thermalization in Nature and on a Quantum Computer

Arnau Riera, Christian Gogolin, Jens Eisert

In this work, we show how Gibbs or thermal states appear dynamically in closed quantum many-body systems, building on the program of dynamical typicality. We introduce a novel perturbation theorem for physically relevant weak system-bath couplings that is applicable even in the thermodynamic limit. We identify conditions under which thermalization happens and discuss the underlying physics. Based on these results, we also present a fully general quantum algorithm for preparing Gibbs states on a quantum computer with a certified runtime and error bound. This complements quantum Metropolis algorithms, which are expected to be efficient but have no known runtime estimates and only work for local Hamiltonians.

arXiv:1102.2389•Physical Review Letters•Feb 23, 2012•189 citations

Key observable for linear thermalization

Yuuya Chiba, Akira Shimizu

For studies on thermalization of an isolated quantum many-body system, the fundamental issue is to determine whether a given system thermalizes or not. However, most studies tested only a small number of observables, and it was unclear whether other observables thermalize. Here, we study whether ``linear thermalization'' occurs for all additive observables: We consider a quantum many-body system prepared in an equilibrium state and its unitary time evolution induced by a small change $\mathrm{\ensuremath{\Delta}}f$ of a physical parameter $f$ of the Hamiltonian, and examine whether all additive observables relax to the equilibrium values in a manner fully consistent with thermodynamics up to the linear order in $\mathrm{\ensuremath{\Delta}}f$. We find that the additive observable conjugate to $f$ is key for linear thermalization in that its linear thermalization guarantees, under physically reasonable conditions, linear thermalization of all additive observables. Such a linear thermalization occurs in the timescale of $\mathcal{O}(|\mathrm{\ensuremath{\Delta}}f{|}^{0})$, and lasts at least for a period of $o(1/\sqrt{|\mathrm{\ensuremath{\Delta}}f|})$. We also consider linear thermalization against the change of other parameters, and find that linear thermalization of the key observable against $\mathrm{\ensuremath{\Delta}}f$ guarantees its linear thermalization against small changes of any other parameters. Furthermore, we discuss the generalized susceptibilities for cross responses and their consistency between quantum mechanics and thermodynamics. We demonstrate our main result by performing numerical calculations for spin models. The present paper offers an efficient way of judging linear thermalization because it guarantees that examination of the single key observable is sufficient.

arXiv:2303.03868•Physical Review Research•Jul 20, 2023•3 citations

On thermalization in many-body classical Floquet systems

Anton Kapustin

It is expected that a generic closed many-body system prepared in a well-behaved initial state and subjected to a periodic drive will eventually thermalize, i.e. approach the state of maximal entropy. This property, while compatible with and even demanded by the physical intuition, is much stronger than ergodicity or mixing and is difficult to justify mathematically. We describe an infinite set of classical many-body Floquet systems of algebraic origin for which thermalization of very general initial states can be proved. For example, we show that a Gibbs state of any sufficiently uniform local differentiable Hamiltonian heats up to infinite temperature at long times. We show that in agreement with the physical intuition, the only obstruction to thermalization is the existence of local observables which are periodic in time.

arXiv:2603.13631•Mar 13, 2026•0 citations
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.
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.
When a nonintegrable system evolves out of equilibrium for a long time, local observables are in general expected to attain stationary expectation values, independent of the details of the initial state. But the thermalization of a closed quantum system is not yet well understood. Here we show that it presents indeed a much richer phenomenology than its classical counterpart. Using a new numerical technique, we identify two distinct regimes, strong and weak, occurring for different initial states. Strong thermalization, intrinsically quantum, happens when instantaneous local expectation values converge to the thermal ones. Weak thermalization, well known in classical systems, shows convergence to thermal values only after time averaging. Remarkably, we find a third group of states showing no thermalization, neither strong nor weak, to the time scales one can reliably simulate.
In this work, we show how Gibbs or thermal states appear dynamically in closed quantum many-body systems, building on the program of dynamical typicality. We introduce a novel perturbation theorem for physically relevant weak system-bath couplings that is applicable even in the thermodynamic limit. We identify conditions under which thermalization happens and discuss the underlying physics. Based on these results, we also present a fully general quantum algorithm for preparing Gibbs states on a quantum computer with a certified runtime and error bound. This complements quantum Metropolis algorithms, which are expected to be efficient but have no known runtime estimates and only work for local Hamiltonians.
For studies on thermalization of an isolated quantum many-body system, the fundamental issue is to determine whether a given system thermalizes or not. However, most studies tested only a small number of observables, and it was unclear whether other observables thermalize. Here, we study whether ``linear thermalization'' occurs for all additive observables: We consider a quantum many-body system prepared in an equilibrium state and its unitary time evolution induced by a small change $\mathrm{\ensuremath{\Delta}}f$ of a physical parameter fff of the Hamiltonian, and examine whether all additive observables relax to the equilibrium values in a manner fully consistent with thermodynamics up to the linear order in $\mathrm{\ensuremath{\Delta}}f$. We find that the additive observable conjugate to fff is key for linear thermalization in that its linear thermalization guarantees, under physically reasonable conditions, linear thermalization of all additive observables. Such a linear thermalization occurs in the timescale of $\mathcal{O}(|\mathrm{\ensuremath{\Delta}}f{|}^{0})$, and lasts at least for a period of $o(1/\sqrt{|\mathrm{\ensuremath{\Delta}}f|})$. We also consider linear thermalization against the change of other parameters, and find that linear thermalization of the key observable against $\mathrm{\ensuremath{\Delta}}f$ guarantees its linear thermalization against small changes of any other parameters. Furthermore, we discuss the generalized susceptibilities for cross responses and their consistency between quantum mechanics and thermodynamics. We demonstrate our main result by performing numerical calculations for spin models. The present paper offers an efficient way of judging linear thermalization because it guarantees that examination of the single key observable is sufficient.
It is expected that a generic closed many-body system prepared in a well-behaved initial state and subjected to a periodic drive will eventually thermalize, i.e. approach the state of maximal entropy. This property, while compatible with and even demanded by the physical intuition, is much stronger than ergodicity or mixing and is difficult to justify mathematically. We describe an infinite set of classical many-body Floquet systems of algebraic origin for which thermalization of very general initial states can be proved. For example, we show that a Gibbs state of any sufficiently uniform local differentiable Hamiltonian heats up to infinite temperature at long times. We show that in agreement with the physical intuition, the only obstruction to thermalization is the existence of local observables which are periodic in time.