The Complexity of Thermalization in Finite Quantum Systems

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

Read The Complexity of Thermalization in Finite Quantum Systems by Dhruv Devulapalli, T. C. Mooney, James D. Watson (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-00405.txt.

Introduction

Dhruv Devulapalli, Mooney, and Watson wrote a 2025 paper proving that predicting thermalization in small quantum systems is computationally intractable. Thermalization is a system's drift toward equilibrium. Whether a given system will settle, and to what values, is a basic question in condensed matter physics.

Using complexity theory, the authors show that deciding whether an observable relaxes to a stated value is PSPACE-complete, even for a quantum computer. They exhibit Hamiltonians where even asking whether the system reaches the standard thermal value is equally hard. A related microcanonical version is also hard under quantum reductions. The results extend earlier work on undecidability in infinite systems. In practice, no efficient general algorithm can certify thermalization. Simulation and experiment remain case-by-case arts.

Catalog record

CREATORDhruv Devulapalli, T. C. Mooney, James D. Watson
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE108 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-00405

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The Complexity of Thermalization in Finite Quantum Systems Dhruv Devulapalli, T. C. Mooney, James D. Watson 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 𝖯𝖲𝖯𝖠𝖢𝖤 \mathsf{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 is contained in 𝖯𝖲𝖯𝖠𝖢𝖤 \mathsf{PSPACE} and is 𝖯𝖲𝖯𝖠𝖢𝖤 \mathsf{PSPACE} -hard under quantum polynomial time reductions. We also present evidence that determining thermalization is 𝖯𝖲𝖯𝖠𝖢𝖤 \mathsf{PSPACE} -hard under classical polynomial time reductions and state a physically reasonable conjecture under which it is 𝖯𝖲𝖯𝖠𝖢𝖤 \mathsf{PSPACE} -complete. 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. 1 Introduction Statistical mechanics has been remarkably successful at describing the physics of large numbers of particles in thermal equilibrium. Experimental outcomes of systems in thermal equilibrium can be predicted using statistical ensembles based on macroscopic observables, independently of the system’s microstate. Therefore, the process through which an isolated system evolves toward thermal equilibrium, known as thermalization, has been a central topic of investigation in condensed matter physics. In classical systems, the emergence of thermalization has been attributed to ergodicity and chaotic dynamics [ 1 ] . Ergodic systems evolve such that they eventually come arbitrarily close to every point in phase space on a constant energy surface. As classical measurements can be modeled as long-time averages, the long-time behavior of ergodic systems is hence similar to that of a uniform distribution over the constant-energy submanifold of phase space, also known as the classical microcanonical ensemble [ 2 , 3 ] . The true relationship between thermalization and ergodicity in classical systems is subtle and nuanced. Ergodicity is difficult to prove and has only been rigorously shown for some systems [ 4 , 5 , 6 , 7 ] , notably for systems with suitably strong chaotic behavior [ 8 , 9 ] . Indeed, it has been argued that ergodicity is neither necessary nor sufficient for thermalization [ 10 ] . Nevertheless, ergodicity has remained a useful conceptual tool to understand thermalization in classical systems. However, the ergodic explanation of thermalization can’t be naturally extended to isolated quantum systems. In particular, unitary time evolution does not sample all wavefunctions within a given energy range of the starting state, and hence cannot be ergodic. As an alternative, the Eigenstate Thermalization Hypothesis (ETH) [ 11 , 12 , 1 ] has been proposed to explain the exhibition of thermalization in isolated quantum systems. ETH proposes that observables with slowly varying diagonal elements (in the energy eigenbasis) and small off-diagonal elements approach their microcanonical thermal values. However, the ETH has not been proven to be generally applicable. Indeed, systems exist that do not thermalize, due to phenomena such as many-body localization [ 13 ] , quantum many-body scars [ 14 ] , and integrability [ 1 , 15 ] (although one can consider integrable systems as equilibrating to generalized Gibbs ensembles that take their additional conservation laws into account [ 16 , 17 ] ). A large volume of theoretical and experimental work has gone into determining which properties and initial states ensure thermalization [ 18 , 19 , 20 , 21 , 22 ] . A natural question thus arises: How can we determine whether a given quantum system thermalizes? While this question has been studied by physicists, it was first considered from the viewpoint of computational complexity theory by [ 23 ] , who proved that even for product initial states with translationally invariant Hamiltonians, the problem of determining whether a system thermalizes or not is undecidable in the limit of an infinitely large system. Their results utilize techniques inspired by previous work in the field of Hamiltonian complexity proving complexity and computability results in physics [ 24 , 25 ] . However, in the lab — and nature more generally — we only have access to physical systems of finite size. This raises the question of how difficult it is to predict thermalization of these finite-sized systems. While the result of [ 23 ] proving undecidability in the thermodynamic limit, along with the more general hardness of simulating quantum systems, suggests this may be a difficult task, it is entirely possible that there exists an efficient algorithm for it. The result of [ 23 ] makes use of a reduction from an undecidable problem (the Halting problem) to the problem of determining whether a system thermalizes, but undecidable instances may require a large (unbounded) size and therefore may not be seen in systems of finite size such as those encountered in nature and the lab. In this work we consider the problem of determining whether a finite-sized quantum system relaxes to a given value, or thermalizes. To study this from a complexity-theoretic perspective, we formulate relaxation as a decision problem. Definition 1.1 ((Informal) Finite-Size Relaxation, \mathsf{FSRelax} ) . Consider an input of a k -local Hamiltonian H acting on N qudits with constant local Hilbert space dimension d , a sum of local observables \mathcal{A}_{N}=\frac{1}{N}\sum_{i}A_{i} , an input classical description of product state \ket{\psi_0} , a value A^{*} , and constants c,\epsilon . Let the long time average of \mathcal{A}_{N} be \displaystyle\bar{\mathcal{A}}_{N}\coloneqq\lim_{T\rightarrow\infty}\frac{1}{T}\int_{0}^{T}dt\bra{\psi_0}e^{iHt}\mathcal{A}_{N}e^{-iHt}\ket{\psi_0} (1) Then, output: YES if |\bar{\mathcal{A}}_{N}-A^{*}|\leq\epsilon or NO if |\bar{\mathcal{A}}_{N}-A^{*}|\geq c\epsilon . \mathsf{FSRelax} is depicted in Fig. 1 . Figure 1: The relaxation decision problem. For a given initial state \ket{\psi} , we plot the time-average of \mathcal{A}_{N}\coloneqq\frac{1}{T}\int_{0}^{T}dt\bra{\psi_0}e^{iHt}\mathcal{A}_{N}e^{-iHt}\ket{\psi_0} . A^{*} is indicated by the dashed green line. Given the promise that \bar{\mathcal{A}}_{N}\coloneqq\lim_{T\rightarrow\infty}\langle\mathcal{A}_{N}\rangle_{T} is such that either |\bar{\mathcal{A}}_{N}-A^{*}|\geq c\epsilon or |\bar{\mathcal{A}}_{N}-A^{*}|\leq\epsilon,\mathsf{FSRelax} is the problem of deciding which of these two holds. One relevant state of interest that describes the thermal behavior of an isolated system is the microcanonical ensemble, which represents the set of possible states within a fixed range of energy of our initial state. Definition 1.2 (Microcanonical Ensemble) . For a Hamiltonian H with eigenstates \{\ket{\lambda_i}\} and corresponding eigenenergies \{\lambda_{i}\} the quantum microcanonical ensemble \rho_{\textsf{MC}}(H,E) at energy E is defined as \rho_{\textsf{MC}}(H,E)=\frac{1}{W}\sum_{i}f\left(\frac{\lambda_{i}-E}{w}\right)\outerproduct{\psi_i}{\psi_i}, (2) where f is an energy window function (typically decaying rapidly in its argument), W=\sum_{i}f\left(\frac{\lambda_{i}-E}{w}\right) and w is a characteristic energy width. To investigate thermalization, we define the following decision problem: Definition 1.3 ((Informal) Finite-Size Thermalization to the microcanonical state, \mathsf{FSTherm(MC)} ) . Consider an input of a k -local Hamiltonian H acting on N qudits with local Hilbert space dimension d , a sum of local

Read the complete text