Abstract
The investigation of thermalization in isolated quantum manybody systems has a long history, dating back to the time of developing statistical mechanics. Most quantum manybody 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 onedimensional shiftinvariant systems with nearestneighbour 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.
Introduction
Thermalization, or relaxation to equilibrium, in isolated quantum manybody systems is a ubiquitous yet profound phenomenon. The history of investigation of thermalization dates back to Boltzmann^{1} and von Neumann^{2}, and many theoretical physicists have studied this problem. The problem originated in the field of nonequilibrium statistical mechanics. However, some techniques developed in quantum information theory have gained attention to provide fresh insight into this old problem^{3}. From the experimental side, the recent development of experimental techniques to manipulate cold atoms enabled us to observe thermalization of isolated quantum manybody systems in the laboratory^{4,5,6,7,8,9}. Experimentalists not only tested established theoretical results, but also revealed some unexpected behaviours^{9}.
A central problem in this field is whether a given system thermalizes^{3,10}. Although almost allnatural quantum manybody systems are expected to thermalize, some systems, including integrable and localized systems, are known to never achieve thermalization^{11,12,13,14,15}. To resolve this problem, the eigenstate thermalization hypothesis (ETH) has been raised as a clue to understanding thermalization phenomena. The ETH claims that all the energy eigenstates of a given Hamiltonian are thermal, that is, indistinguishable from the equilibrium state, as long as we observe macroscopic observables^{16,17,18,19,20,21}. Studies based on numerical simulations support that most nonintegrable thermalizing systems satisfy the ETH^{20,22,23,24}. In contrast, recent theoretical studies and elaborated experiments have revealed that some nonintegrable systems do not satisfy the ETH^{9,25,26,27,28,29,30,31}. Numerous other theoretical ideas, including largeness of effective dimension^{10}, typicality^{10,32,33,34}, and quantum correlation^{35,36,37} have been proposed to elucidate thermalization phenomena; however, none of them provides a decisive answer.
We approach the problem of thermalization from the opposite side. We examine the difficulty of the problem from the viewpoint of theoretical computer science. This type of approach is employed in some problems in physics, including prediction of dynamical systems^{38}, repeated quantum measurements^{39}, and the spectral gap problem^{40}. In this approach, these problems were unexpectedly shown to be undecidable, that is, there is no algorithm to determine, e.g., the presence or absence of a spectral gap in arbitrary systems in the case of the spectral gap problem.
Our main achievement in this paper is the finding that whether a given system thermalizes or not with respect to a given observable is undecidable in general. This result shows not merely the difficulty of this problem, but also the logical impossibility of solving it. Hence, the fate of thermalization in a general setup is independent of the basic axioms of mathematics, as implied in the Gödel’s incompleteness theorem^{41}. We prove this by demonstrating that the relaxation and thermalization phenomena in onedimensional systems have the power of universal computation. Our result not only sets a limit on what we can know about quantum thermalization, but also elucidates a rich variety of thermalization phenomena, which can implement any computational task.
Results
Statement of main results
We first clarify the precise statements of our results, namely, the undecidability of relaxation and thermalization. Since the undecidability of thermalization can be obtained by modifying the result on relaxation, we shall mainly treat relaxation and briefly comment on how to extend this result to thermalization. Throughout this study, we consider a onedimensional lattice system of size L with the periodic boundary condition (we finally take L → ∞ limit), with ddimensional local Hilbert space \({{{{{{{\mathcal{H}}}}}}}}\). Although we do not specify the necessary dimension, we roughly estimate that d ≃ 120 suffices to obtain undecidability, which is minuscule compared to other results of undecidability in physics^{40}. Let \(\left\psi (t)\right\rangle\) be the state of the system at time t. The longtime average of an observable \({{{{{{{{\mathcal{A}}}}}}}}}_{L}\) for a given initial state \(\left\psi (0)\right\rangle =\left{\psi }_{0}^{L}\right\rangle\) is given by \({\bar{{{{{{{{\mathcal{A}}}}}}}}}}_{L}={{{\mbox{lim}}}}_{T\to \infty }\frac{1}{T}\int\nolimits_{0}^{T}dt\langle \psi (t) {{{{{{{{\mathcal{A}}}}}}}}}_{L} \psi (t)\rangle\). Our interest takes the form of whether the thermodynamic limit of the longtime average \({\bar{{{{{{{{\mathcal{A}}}}}}}}}}_{L}\), denoted by \(\bar{{{{{{{{\mathcal{A}}}}}}}}}:= {{{\mbox{lim}}}}_{L\to \infty }{\bar{{{{{{{{\mathcal{A}}}}}}}}}}_{L}\), converges to the vicinity of a given target value A^{*}. This question concerns the fate of a relaxation process with an initial state, an observable, and a Hamiltonian. If A^{*} is equal to the equilibrium value \({{{{{{{{\mathcal{A}}}}}}}}}^{{{{{{{{\rm{MC}}}}}}}}}:= {{{\mbox{lim}}}}_{L\to \infty }{{{{{{{\rm{Tr}}}}}}}}[{{{{{{{{\mathcal{A}}}}}}}}}_{L}{\rho }_{L}^{{{{{{{{\rm{MC}}}}}}}}}]\) with the microcanonical state \({\rho }_{L}^{{{{{{{{\rm{MC}}}}}}}}}\), this question asks whether thermalization with respect to \({{{{{{{\mathcal{A}}}}}}}}\) takes place. We remark that we take the longtime limit (T → ∞) first, and then take the thermodynamic limit (L → ∞). The symbol \({{{{{{{\mathcal{A}}}}}}}}\) means the thermodynamic limit of \({{{{{{{{\mathcal{A}}}}}}}}}_{L}\), while the order of the limit is always in the aforementioned one.
We restrict the class of the Hamiltonians, observables, and initial states to simple ones. The Hamiltonian of the system is restricted to be nearestneighbour interaction and shiftinvariant. Hence, the d^{2} × d^{2} local Hamiltonian h_{i,i+1}, which acts only on sites i and i + 1, fully determines the system Hamiltonian as H ≔ ∑_{i}h_{i,i+1}. We further restrict observables to a spatial average of a singlesite operator: \({{{{{{{{\mathcal{A}}}}}}}}}_{L}:= \frac{1}{L}\mathop{\sum }\nolimits_{i = 1}^{L}{A}_{i}\), where A_{i} acts only on the site i. In addition, we restrict the initial state as the following form of a product state: \(\left{\psi }_{0}^{L}\right\rangle =\left{\phi }_{0}\right\rangle \otimes \left{\phi }_{1}\right\rangle \otimes \left{\phi }_{1}\right\rangle \otimes \cdots \otimes \left{\phi }_{1}\right\rangle\), where \(\left{\phi }_{0}\right\rangle\) and \(\left{\phi }_{1}\right\rangle\) are states on a singlesite orthogonal to each other; 〈ϕ_{0}∣ϕ_{1}〉 = 0.
In our setup, both the observable (A) and the initial state (\(\left{\phi }_{0}\right\rangle\) and \(\left{\phi }_{1}\right\rangle\)) are given arbitrarily and fixed. Moreover, we put a promise that either \(\left\bar{{{{{{{{\mathcal{A}}}}}}}}}{A}^{* }\right \, < \, {\varepsilon }_{1}\) or \(\left\bar{{{{{{{{\mathcal{A}}}}}}}}}{A}^{* }\right\, > \,{\varepsilon }_{2}\) holds with errors 0 < ε_{1} < ε_{2}. An alternative expression of the above promise is that we are allowed to answer incorrectly for \({\varepsilon }_{1}\le \left\bar{{{{{{{{\mathcal{A}}}}}}}}}{A}^{* }\right\le {\varepsilon }_{2}\). The ratio of errors M : = ε_{2}/ε_{1} can be set arbitrarily large. The input of this decision problem is the Hamiltonian. Even in this very simple setup, we show that whether the longtime average of \({{{{{{{\mathcal{A}}}}}}}}\) from this initial state \(\left{\psi }_{0}^{L}\right\rangle\) under a given Hamiltonian H relaxes to the vicinity of a given value A^{*} is undecidable.
Theorem 1
Given two states \(\left{\phi }_{0}\right\rangle\) and \(\left{\phi }_{1}\right\rangle\) on a single site, orthogonal to each other, and a singlesite operator A arbitrarily. We require that there exists a state \(\left{\phi }_{2}\right\rangle\) orthogonal to \(\left{\phi }_{0}\right\rangle\) and \(\left{\phi }_{1}\right\rangle\) such that 〈ϕ_{2}∣A∣ϕ_{2}〉 ≠ 〈ϕ_{1}∣A∣ϕ_{1}〉. The initial state and the observable are set as \(\left{\psi }_{0}^{L}\right\rangle =\left{\phi }_{0}\right\rangle \otimes \left{\phi }_{1}\right\rangle \otimes \cdots \otimes \left{\phi }_{1}\right\rangle\) and \({{{{{{{{\mathcal{A}}}}}}}}}_{L}:= \frac{1}{L}\mathop{\sum }\nolimits_{i = 1}^{L}{A}_{i}\). Here, the longtime average \(\bar{{{{{{{{\mathcal{A}}}}}}}}}\) is a function of the Hamiltonian H. We also fix M > 0 arbitrarily large.
Then, there exist ε_{1}, ε_{2} with ε_{2} = Mε_{1}, and A^{*} which satisfy the following: we suppose the promise that either \(\left\bar{{{{{{{{\mathcal{A}}}}}}}}}{A}^{* }\right\, < \,{\varepsilon }_{1}\) or \(\left\bar{{{{{{{{\mathcal{A}}}}}}}}}{A}^{* }\right\, > \, {\varepsilon }_{2}\) holds (see Fig. 1). In this setting, deciding which is true for a given shiftinvariant nearestneighbour interaction Hamiltonian H = ∑_{i}h_{i,i+1} is undecidable.
If A^{*} is equal to the equilibrium value \({{{{{{{{\mathcal{A}}}}}}}}}^{{{{{{{{\rm{MC}}}}}}}}}\), our result reads undecidability of thermalization: Whether a given system with a fixed initial state thermalizes or not with respect to a fixed observable A is undecidable. By defining \({A}_{\max }^{01}:= {\max}{\left\psi \right\rangle \in {{{{{{{\rm{span}}}}}}}}\{\left{\phi }_{0}\right\rangle ,\left{\phi }_{1}\right\rangle \}}\langle \psi  A \psi \rangle\) and \({A}_{\min }^{01}:= {\min}_{\left\psi \right\rangle \in {{{{{{{\rm{span}}}}}}}}\{\left{\phi }_{0}\right\rangle ,\left{\phi }_{1}\right\rangle \}}\langle \psi  A \psi \rangle\), the precise statement can be expressed as follows:
Theorem 2
Given two states \(\left{\phi }_{0}\right\rangle\) and \(\left{\phi }_{1}\right\rangle\) on a single site, orthogonal to each other, and a singlesite operator A arbitrarily. We require that there exist states \(\left{\phi }_{2}\right\rangle\) and \(\left{\phi }_{3}\right\rangle\) orthogonal to \(\left{\phi }_{0}\right\rangle\), \(\left{\phi }_{1}\right\rangle\), \(A\left{\phi }_{0}\right\rangle\), and \(A\left{\phi }_{1}\right\rangle\) such that \(\langle {\phi }_{2} A {\phi }_{2}\rangle \, > \,{A}_{\max }^{01}\) and \(\langle {\phi }_{3} A {\phi }_{3}\rangle \, < \,{A}_{\min }^{01}\). The initial state and the observable are set as \(\left{\psi }_{0}^{L}\right\rangle =\left{\phi }_{0}\right\rangle \otimes \left{\phi }_{1}\right\rangle \otimes \cdots \otimes \left{\phi }_{1}\right\rangle\) and \({{{{{{{{\mathcal{A}}}}}}}}}_{L}:= \frac{1}{L}\mathop{\sum }\nolimits_{i = 1}^{L}{A}_{i}\). We also fix M > 0 arbitrarily large.
Then, there exist ε_{1}, ε_{2} with ε_{2} = Mε_{1}, which satisfy the following: We suppose the promise that either \(\left\bar{{{{{{{{\mathcal{A}}}}}}}}}{{{{{{{{\mathcal{A}}}}}}}}}^{{{{{{{{\rm{MC}}}}}}}}}\right \, < \, {\varepsilon }_{1}\) or \(\left\bar{{{{{{{{\mathcal{A}}}}}}}}}{{{{{{{{\mathcal{A}}}}}}}}}^{{{{{{{{\rm{MC}}}}}}}}}\right\, > \, {\varepsilon }_{2}\) holds. In this setting, deciding which is true for a given shiftinvariant nearestneighbour interaction Hamiltonian H = ∑_{i}h_{i,i+1} is undecidable.
The condition on the presence of \(\left{\phi }_{2}\right\rangle\) and \(\left{\phi }_{3}\right\rangle\) ensures that the initial state is not at the edge of the spectrum of A. We note that the equilibrium value \({{{{{{{{\mathcal{A}}}}}}}}}^{{{{{{{{\rm{MC}}}}}}}}}\) depends on the choice of the Hamiltonian, and thus the promise restricts the class of Hamiltonians.
Mapping classical Turing machines to a quantum system
We here sketch the main idea of the proof. A rigorous proof is presented in the Supplementary Note. We first introduce a key ingredient, the halting problem of a Turing machine (TM), which is a prominent example of undecidable problems. The halting problem of a TM asks whether the TM with a given input halts at some time or does not halt and runs forever. Turing proved in his celebrated paper that there exists no general procedure to solve the halting problem^{42}.
Following various studies demonstrating undecidability^{43}, we apply the reduction to the halting problem. We shall construct a family of Hamiltonians with which the longtime average of an observable is connected to the halting or nonhalting of a TM. Below, a universal reversible Turing machine (URTM) is arbitrarily given and fixed, whose possible input code is denoted by u.
Lemma:
Given a complete orthogonal normal basis of the local Hilbert space \(\{\left{e}_{i}\right\rangle \}\) and an observable A on a single site satisfying 〈e_{1}∣A∣e_{1}〉 = 0 and 〈e_{2}∣A∣e_{2}〉 > 0 arbitrarily. Then, for any η > 0, there exists a shiftinvariant nearestneighbour interaction Hamiltonian H and a set of unitary operators {V_{u}} on the local Hilbert space \({{{{{{{\mathcal{H}}}}}}}}\) corresponding to all possible inputs for the fixed URTM u such that they satisfy \({V}_{{{{{{{{\boldsymbol{u}}}}}}}}}\left{e}_{0}\right\rangle =\left{e}_{0}\right\rangle\) for any u and the following property:
Set the initial state as
If the URTM halts with the input u, then
holds, and if the URTM does not halt with the input u, then
holds.
By setting the initial state, the observable, and the Hamiltonian in Theorem 1 as \(\left{e}_{0}\right\rangle \otimes {(\left{e}_{1}\right\rangle )}^{\otimes L1}\), V^{†}AV, and \({{V}_{{{{{{{{\boldsymbol{u}}}}}}}}}^{{{{\dagger}}} }}^{\otimes L}H{V}_{{{{{{{{\boldsymbol{u}}}}}}}}}^{\otimes L}\), respectively, the degree of freedom in the choice of unitary transformation is mapped onto that of the local Hamiltonian. Then, the setup of Lemma can be mapped onto that of Theorem 1 by shifting the origin of A so that 〈ϕ_{1}∣A∣ϕ_{1}〉 = 0, and setting \(\left{\phi }_{i}\right\rangle\) (i = 0, 1, 2) to \(\left{e}_{i}\right\rangle\). Because the halting problem of the URTM is undecidable, the above lemma directly implies the undecidability of the longtime average in quantum manybody systems.
To prove the lemma, we first introduce an elaborated classical machine that simulates the given URTM and changes the value of A depending on whether the URTM halts. We then construct a quantum manybody system emulating the above classical machine. Since the dynamics of the quantum system is a superposition of classical machines with different inputs, we first compute the longtime average for computational basis initial states, which corresponds to a single input, and then treat the quantum superposition.
Classical machines
Here, we outline the construction of a classical TM, which simulates the halting problem of a given URTM and changes the longtime average of the observable A depending on the behaviour of the URTM. This machine consists of three TMs, TM1, TM2, and TM3, on two types of cells, Mcells and Acells. Unlike conventional TMs, the finite control settles in the line of cells. TM2 simulates the URTM with the input code u, whose reversibility is induced by the unique direction property^{44}. TM1 decodes the input code u from a sequence of two qubits. Two TMs, TM1 and TM2, work in Mcells. TM3 is a simple TM, which flips the state of Acells if and only if TM2 halts. Through the above trick, the longtime average \(\bar{{{{{{{{\mathcal{A}}}}}}}}}\) in our system reflects the result of the halting problem of TM2.
An Mcell consists of three layers: The first layer simulates the URTM, and the second and the third layers, both of which consist of sequences of qubits, store the input code of TM2. The relative frequency of 1 in the second layer is set to β whose binary expansion is equal to the input code u. TM1 decodes a bit sequence u on the first layer from the second and the third layers by estimating the relative frequency of 1 (see the first part of Fig. 2), and then TM2 runs with this input u. Throughout this procedure, the machine passes all Acells transparently.
Acells are responsible for changing the longtime average of \({{{{{{{{\mathcal{A}}}}}}}}}_{L}\). At the initial state, all Acells are set to the state a_{1}, whose expectation value of A is zero. If and only if TM2 halts, TM3 starts flipping states of Acells from a_{1} to another state a_{2}, whose expectation value of A is a nonzero value. To inflate the difference between the halting and nonhalting cases, we set the initial state such that most of the cells are Acells.
The procedure is summarized as follows:

(i)
TM1 decodes the input code u on the first layer.

(ii)
TM2, a URTM, runs with the input u in the first layer.

(iii)
If and only if TM2 halts, then TM3 starts flipping the states in Acells (see the second part of Fig. 2). This induces a visible difference between the longtime average of \({{{{{{{{\mathcal{A}}}}}}}}}_{L}\) in the case of halting and nonhalting.

(iv)
In the case of halting, the head returns to the cell where TM2 halts due to the periodic boundary condition. By this time, all Acells have already been flipped, and TM3 stops.
Because the halting problem of TM2 with an arbitrary input u is undecidable, the longtime average of \({{{{{{{{\mathcal{A}}}}}}}}}_{L}\) with an arbitrary local unitary transformation V_{u} is likewise undecidable.
Hamiltonian construction and its eigenstates
Our implementation of the classical TM in quantum systems stems from the construction of the FeynmanKitaev Hamiltonian^{45,46}, while we delete the clock part. Each site takes one of the states of the finite control or that of a single cell in the tape, or some additional symbols. If the site i is a state of the finite control, then the head reads the site i + 1 or i − 1 (see Fig. 3). In the initial state, we set the finite control at site 1, and set all other sites not to the states of the finite control. Because the dynamics conserve the number of sites of the finite control, only a single site takes the state of the finite control at all times.
The dynamics of TM are encoded in the local Hamiltonian as follows. Suppose, e.g., that the cell at the head is s_{a}, the state of the finite control is q_{b}, and the TM moves to the right with keeping the state of the finite control and the cell. Then, the local Hamiltonian h_{i,i+1} must contain the term
Similarly, we add all transition rules of TMs (both TM1, TM2, and TM3) to the local Hamiltonian in the form of (4). Owing to the deterministic property of TMs, all the legal states of the total system have a unique descendant state.
Because treatment of almost uniform initial states is slightly complicated, we first take an analogous and easier setting. Our original setting is discussed in the next section. We set the initial state as a nonuniform computational basis state, such that the dynamic of TMs is uniquely determined without quantum fluctuation. Let \(\left{{{{{{{{\boldsymbol{x}}}}}}}}}^{1}\right\rangle\) denote the initial configuration of the total system, and \(\left{{{{{{{{\boldsymbol{x}}}}}}}}}^{n}\right\rangle\) be the nth state (i.e., after n − 1 steps from \(\left{{{{{{{{\boldsymbol{x}}}}}}}}}^{1}\right\rangle\)). By restricting the Hilbert space to the subspace spanned by \(\{\left{{{{{{{{\boldsymbol{x}}}}}}}}}^{n}\right\rangle \}\), the total Hamiltonian is expressed as (see also Fig. 3)
where the Jth state is the final state of this dynamics. This Hamiltonian takes the same form as a singleparticle system on a closed onedimensional lattice with only hopping terms. Employing the result on a tridiagonal matrix, eigenenergies and energy eigenstates are calculated as
with j = 1, 2, …, J.
By expanding the initial state as \(\left{{{{{{{{\boldsymbol{x}}}}}}}}}^{1}\right\rangle =\mathop{\sum }\nolimits_{j = 1}^{J}{c}_{j}{E}_{j}\rangle\), the longtime average of \({{{{{{{{\mathcal{A}}}}}}}}}_{L}\) reads \({\bar{{{{{{{{\mathcal{A}}}}}}}}}}_{L}=\mathop{\sum }\nolimits_{j = 1}^{J}{{c}_{j}}^{2}\langle {E}_{j} A {E}_{j}\rangle\), because all the offdiagonal elements vanish in the longtime average. Since the number of steps until TM2 halts is independent of the system size L, by setting L to be sufficiently large, we can make the flipping of Acells start before J/2 steps. In this condition, half of the Acells have been flipped before 3J/4 steps, which confirms the nonzero expectation value of \({\bar{{{{{{{{\mathcal{A}}}}}}}}}}_{L}\) in the case of halting. In contrast, in the case of nonhalting, the flipping by TM3 does not occur, and hence the longtime average \({\bar{{{{{{{{\mathcal{A}}}}}}}}}}_{L}\) is kept close to zero.
Uniform initial state
We now describe the decoding process from the second and third layers of Mcells in our original setting, almost uniform initial states. The sites in the second and third layers are set to \(\sqrt{\beta }\left1\right\rangle +\sqrt{1\beta }\left0\right\rangle\) and \(\sqrt{\gamma }\left1\right\rangle +\sqrt{1\gamma }\left0\right\rangle\), respectively. The state on m of Mcells is a superposition of 2^{m} × 2^{m} computational basis states. TM1 runs on each computational basis state, and thus the dynamics of TMs is also a superposition of 2^{m} × 2^{m} branches.
The quantity β stores the input code in the form such that the binary expansion of β equals the input code u. TM1 calculates β by estimating the relative frequency of the state \(\left1\right\rangle\) in the second layer. Due to the law of large numbers, the set of computational basis states such that the relative frequency of \(\left1\right\rangle\) is not close to β has negligibly small probability amplitude. The quantity γ (more precisely, \(1/{{{{{{\mathrm{ln}}}}}}}\,\gamma\)) characterizes the length of qubits that TM1 must read in. TM1 reads the qubits in the second layer until it first encounters \(\left1\right\rangle\) in the third layer (the first part of Fig. 2). By setting γ to be sufficiently small, the probability of two unwanted cases, namely, (a) TM1 stops decoding before u is decoded to the last, and (b) TM1 can access only an insufficiently small number of qubits in the second layer and fails to estimate the correct β, becomes negligible.
From relaxation to thermalization
We shall sketch how Theorem 2, the undecidability of thermalization, is derived from the proof techniques of Theorem 1. Careful calculation with slightly modified version of TM3 implies that the longtime average \(\bar{{{{{{{{\mathcal{A}}}}}}}}}\) when TM2 halts approaches 〈e_{2}∣A∣e_{2}〉. Since the basis \(\{\left{e}_{i}\right\rangle \}\) with i ≥ 2 can be set arbitrarily in the proof of Theorem 1, it suffices to show the presence of an orthogonal normal basis \(\{\left{e}_{i}\right\rangle \}\) such that \(\langle {e}_{2} A {e}_{2}\rangle ={{{{{{{{\mathcal{A}}}}}}}}}^{{{{{{{{\rm{MC}}}}}}}}}\). We remark that the Hamiltonian depends on the basis \(\{\left{e}_{i}\right\rangle \}\), and thus \({{{{{{{{\mathcal{A}}}}}}}}}^{{{{{{{{\rm{MC}}}}}}}}}\) also depends on it through the Hamiltonian.
Since \(\left{\phi }_{0}\right\rangle\) and \(\left{\phi }_{1}\right\rangle\) are not at the edge of the spectrum of A, the equilibrium value \({{{{{{{{\mathcal{A}}}}}}}}}^{{{{{{{{\rm{MC}}}}}}}}}\) always settles between the maximum and the minimum expectation values of A in the subspace orthogonal to \(\left{\phi }_{0}\right\rangle\), \(\left{\phi }_{1}\right\rangle\), \(A\left{\phi }_{0}\right\rangle\), and \(A\left{\phi }_{1}\right\rangle\). Let \(\left{\sigma }_{\max }\right\rangle\) and \(\left{\sigma }_{\min }\right\rangle\) be states in this subspace accompanying the maximum and minimum expectation values of A. We set \(\left{e}_{2}(p)\right\rangle := \sqrt{p}\left{\sigma }_{\max }\right\rangle +\sqrt{1p}\left{\sigma }_{\min }\right\rangle\) and change p from p = 0 to p = 1. With recalling \(\langle {e}_{2}(0) A {e}_{2}(0)\rangle \le {{{{{{{{\mathcal{A}}}}}}}}}^{{{{{{{{\rm{MC}}}}}}}}}\le \langle {e}_{2}(1) A {e}_{2}(1)\rangle\) and the continuity of 〈e_{2}(p)∣A∣e_{2}(p)〉, we find that there exists a proper p (a proper \(\left{e}_{2}\right\rangle\)) which realizes \(\langle {e}_{2}(p) A {e}_{2}(p)\rangle ={{{{{{{{\mathcal{A}}}}}}}}}^{{{{{{{{\rm{MC}}}}}}}}}\). Using this Hamiltonian with this basis \(\{\left{e}_{i}\right\rangle \}\), we arrive at the undecidability of thermalization by following the same argument to that of relaxation.
We here remark two points. First, the tuning of \(\left{e}_{2}\right\rangle\) can be accomplished in the choice of the local Hamiltonian, and both the observable and the initial state are kept as arbitrary fixed parameters. Second, since a finite error from the equilibrium value is allowed, we can compute a proper p (i.e., a proper local Hamiltonian) within this error in a finite number of steps.
No sufficiently large system size
Our result claims that we cannot solve the problem of thermalization by any elaborated method even with unlimited computational resource. In order to elucidate the significance of the constructed systems, we compare them with nearintegrable systems, H = H_{int} + εV, where H_{int} is an integrable Hamiltonian and ε is a small parameter. In nearintegrable systems, the small parameter ε determines the necessary system size and time length to distinguish the true thermodynamic limit from prethermal plateaus, and by taking ε → 0 the necessary size diverges. If our computational resource is unlimited, by setting the system size and running time sufficiently large depending on ε as determined above we safely obtain the true longtime behaviour in the thermodynamic limit within an arbitrarily small error.
In contrast to nearintegrable systems, the constructed systems of undecidability have no such small parameters and no sufficiently large system size. This fact is clearly demonstrated by introducing the busy beaver function BB(n). The busy beaver function gives the largest number of steps which a halting TM with n internal states and an empty input can take. Since the number of internal states can be connected to the length of the input code to a TM with a fixed number of internal states, the busy beaver function also serves as the indicator of the necessary time steps with respect to the length of the input. In terms of thermalization, the busy beaver function provides the necessary system size and time length to observe the true thermodynamic limit. However, the busy beaver function is proven to be uncomputable. More surprisingly, if the ZermeloFraenkel set theory with the axiom of choice (ZFC), which is roughly equivalent to the whole of our mathematics, is consistent, then BB(748) is shown to be uncomputable^{47,48}. Notice that all possible TMs with 748 internal states can be implemented by a (large but) finite set of Hamiltonians. These Hamiltonians obviously have no small parameters going to zero, because no quantity tends to go to zero in a finite set. In spite of this, we do not have a sufficiently large system size for these (finite number of) Hamiltonians.
Discussion
The presence or absence of thermalization in a given quantum manybody system, which has been a topic of debate among researchers in various fields, is proven to be undecidable. Hence, there exists no general systematic procedure to determine the longtime behaviour of quantum manybody systems. The undecidability is still valid for a class of simple systems; onedimensional systems with a shiftinvariant and nearestneighbour interaction. Our result leads to a fundamental limitation to reach a general theory on thermalization.
Our proof also shows the computational universality of thermalization phenomena. Contrary to the apparent simplicity of thermalization phenomena, the above fact leads to an astonishing consequence that the variety of thermalization phenomena is no less than all possible tasks computers can manage. A striking example bridging physics and mathematics is a system that thermalizes if and only if the Riemann hypothesis is true. The above system reflects the existence of a TM which halts if and only if the Riemann hypothesis is false^{49}.
From the context of physics, the extremely slow relaxation of our model in case of halting is induced by quasiconserved nonlocal quantities, which are close to conserved quantities but not conserved. Recently, some nonintegrable systems (the transverse Ising model with z magnetic field) have been reported to relax very slowly, which is caused by quasiconserved local quantities^{23,50,51}. Numerical simulations with ordinal size and time length fail to address thermalization in these systems. Similar things can also be seen in glassy systems, whose connection with computational hardness is also discussed intensively^{52}. The extremely slow relaxation in our system might be understood from the aforementioned more general viewpoints, which is worth further investigation.
We remark that our definition of thermalization is conditional with respect to an observable. There exists another definition of thermalization in an unconditional form, where a system is said to thermalize if and only if the system thermalizes with respect to all macroscopic observables. In this article, we do not employ this alternative definition because no shiftinvariant system is proven to thermalize in this sense. To prove undecidability, we should prepare infinitely many thermalizing and nonthermalizing systems with proof. Constructing a thermalizing system in this sense is considered to be a very hard problem, and therefore we give up adopting this definition.
We finally comment on the limitations of our result and conclude this study. First, our result does not exclude the possibility that one proves the presence or absence of thermalization in specific systems. Our result only excludes the possibility to obtain a general and ultimate criterion to judge the presence or absence of thermalization. We emphasize that our results do not tarnish the meaningfulness of numerical simulations in ordinal systems with finite size. Second, our undecidability is shown in only a highly artificial model with a particular form of Hamiltonians, which is another limitation of our result. One needs to proceed to a more natural model exhibiting undecidability, or to find a set of a restricted class of physical Hamiltonians whose fate of thermalization is now decidable. These problems are left for future works.
Method
Decoding from the second and third layers
We discuss how to decode the input code u from the sequence of two qubits in the second and third layers. The amount of β, whose binary expansion is equal to u, is guessed by the relative frequency of 1’s in the second layer (see Fig. 2). We expand m copies of \(\sqrt{\beta }\left1\right\rangle +\sqrt{1\beta }\left0\right\rangle\) as
where w is a sequence of 01 with length m, and N_{1}(w) is the number of 1’s in the binary sequence w. The probability amplitude for a state \(\left{{{{{{{\boldsymbol{w}}}}}}}}\right\rangle\) is \({\left{c}_{{{{{{{{\boldsymbol{w}}}}}}}}}\right}^{2}={\beta }^{{N}_{1}({{{{{{{\boldsymbol{w}}}}}}}})}{(1\beta )}^{m{N}_{1}({{{{{{{\boldsymbol{w}}}}}}}})}\). Due to the law of large numbers, the probability amplitude for states with relative frequency of 1’s close to β converges to 1 in the large m limit:
Here, the symbol \(\frac{{N}_{1}({{{{{{{\boldsymbol{w}}}}}}}})}{m}\simeq \beta\) means that \(\frac{{N}_{1}({{{{{{{\boldsymbol{w}}}}}}}})}{m}\) is close to β, whose rigorous definition is presented soon later (in (11)). Hence, if m is sufficiently large compared with the length of the input code, TM1 guesses β correctly from the frequency of 1’s.
The length m is determined by another bit sequence, \(\sqrt{\gamma }\left1\right\rangle +\sqrt{1\gamma }\left0\right\rangle\), in the third layer. Let 0 < ξ < 1 be a given accuracy. We encode the information of m into γ as satisfying
In other words, almost all qubits are \(\left0\right\rangle\) in this sequence, and \(\left1\right\rangle\) appears only after mth digit with probability larger than 1 − ξ. Owing to this, if \(\left1\right\rangle\) appears at the \(m^{\prime}\)th digit for the first time, this is taken as the sign that \(m\le m^{\prime}\). Based on the observed value \(m^{\prime}\), the length of the output by TM1 (i.e., the presumed length of the digit of β) is determined as \(n^{\prime} =\lceil \frac{1}{4}{{{{{{{\mathrm{log}}}}}}}\,}_{2}m^{\prime} \rceil\), which ensures
With this choice of output length \(n^{\prime}\), guessing \(m^{\prime}\) larger than the true value m does not affect the correctness of the estimation of β.
Modification of TM3 in case of thermalization
When we show the undecidability of thermalization, we need to modify TM3 to another TM named TM3+. TM3 flips all Acells from a_{1} to a_{2}, and after the flipping TM3 stops. Similarly, TM3+ first flips all Acells from a_{1} to a_{2}, but after the flipping TM3+ still runs in order to spend time steps of order O(L^{2}). Note that TM1 and TM2 take O(1) steps, and TM3 takes O(L) steps. In TM3+, most of the steps before stopping are dominated by those after flipping. This additional trick makes the longtime average of \({{{{{{{\mathcal{A}}}}}}}}\) with halting TM2 from 〈e_{2}∣A∣e_{2}〉/2 (in case with TM3) to 〈e_{2}∣A∣e_{2}〉.
In the construction of TM3+, we introduce two new states of Acells, b_{l}, and b_{r}, and equip the rule such that the position of b_{l} is fixed and the position of b_{r} moves right one cell through a single round trip of the finite control between b_{l} and b_{r}. At the beginning, b_{r} sits right of b_{l}, and we set TM3+ stop when b_{r} hits b_{l} from left. In this setting, it takes O(L^{2}) steps until b_{r} hits b_{l} from left, which indeed meets the requirement.
Busy beaver function
The busy beaver function BB(n) is defined as follows: We consider all possible TMs with n internal states, and start running these TMs with empty inputs. Some TMs will halt, and some other TMs will not. We pay attention only to the former TMs and record the maximum number of steps before halting, which is BB(n). Since we exclude nonhalting TMs, BB(n) must be finite for all n.
We remark that a TM with m internal states and input u with length l can be emulated by another TM with m + l internal states and empty input. The emulation is performed as follows: This TM first outputs the code u on the blank tape by using l internal states, and then works as the TM with m internal states. Conversely, a URTM can emulate any TM with any number of internal states, whose information is given in the input code for the URTM. Thus, the busy beaver function also characterizes the maximum number of steps in terms of the length of the input.
The uncomputability of BB(n) is a direct consequence of the undecidability of the halting problem. We show this by contradiction. Suppose that BB(n) is computable for any n. Then, for any input code u with length l, we run this TM with this input for BB(m + l) steps and observe whether this TM halts or not. By definition, if this TM does not halt at this step, we can confirm that this TM does not halt forever. This procedure solves the halting problem, which is a contradiction.
The uncomputability of BB(748) is shown by resorting to the fact that there is a TM with 748 internal states such that this TM halts if and only if ZFC is inconsistent^{47,48}. Gödel’s incompleteness theorem shows that ZFC cannot prove the consistency of ZFC itself if ZFC is consistent. Following a similar argument to above, ZFC cannot compute BB(748) if ZFC is consistent.
Proof
All the results in this paper are rigorously proved in the Supplementary Note.
Data availability
Data sharing is not applicable to this article as no datasets were generated or analyzed during the current study.
References
 1.
Boltzmann, L. Ueber die mechanischen Analogien des zweiten Hauptsatzes der Thermodynamik. J. f.ür. die reine und Angew. Mathematik 100, 201 (1887).
 2.
von Neumann, J., Beweis des Ergodensatzes und des HTheorems in der neuen Mechanik. Z. Phys. 57, 30 (1929) [English version, Proof of the ergodic theorem and the Htheorem in quantum mechanics, Eur. Phys. J. H 35, 201 (2010)].
 3.
Gogolin, C. & Eisert, J. Equilibration, thermalisation, and the emergence of statistical mechanics in closed quantum systems. Rep. Prog. Phys. 79, 056001 (2016).
 4.
Kinoshita, T., Wenger, T. & Weiss, D. S. A quantum Newton’s cradle. Nature 440, 900 (2006).
 5.
Trotzky, S. Probing the relaxation towards equilibrium in an isolated strongly correlated onedimensional Bose gas. Nat. Phys. 8, 325 (2012).
 6.
Gring, M. Relaxation and prethermalization in an isolated quantum system. Science 337, 1318 (2012).
 7.
Langen, T. Experimental observation of a generalized Gibbs ensemble. Science 348, 207 (2015).
 8.
Kaufman, A. M. Quantum thermalization through entanglement in an isolated manybody system. Science 353, 794 (2016).
 9.
Bernien, H. Probing manybody dynamics on a 51atom quantum simulator. Nature 551, 579 (2017).
 10.
Tasaki, H. Typicality of thermal equilibrium and thermalization in isolated macroscopic quantum systems. J. Stat. Phys. 163, 937 (2016).
 11.
Cazalilla, M. A. Effect of suddenly turning on interactions in the Luttinger model. Phys. Rev. Lett. 97, 156403 (2006).
 12.
Rigol, M., Dunjko, V., Yurovsky, V. & Olshanii, M. Relaxation in a completely integrable manybody quantum system: an ab initio study of the dynamics of the highly excited states of 1D lattice hardcore bosons. Phys. Rev. Lett. 98, 050405 (2007).
 13.
Essler, F. & Fagotti, M. Quench dynamics and relaxation in isolated integrable quantum spin chains. J. Stat. Mech. 064002, https://iopscience.iop.org/article/10.1088/17425468/2016/06/064002 (2016).
 14.
Basko, D. M., Aleiner, I. L. & Altshuler, B. L. Metalinsulator transition in a weakly interacting manyelectron system with localized singleparticle states. Ann. Phys. 321, 1126 (2006).
 15.
Pal, A. & Huse, D. A. Manybody localization phase transition. Phys. Rev. B 82, 174411 (2010).
 16.
Deutsch, J. M. Quantum statistical mechanics in a closed system. Phys. Rev. A 43, 2046 (1991).
 17.
Srednicki, M. Chaos and quantum thermalization. Phys. Rev. E 50, 888 (1994).
 18.
Horoi, M., Zelevinsky, V. & Brown, B. A. Chaos vs thermalization in the nuclear shell model. Phys. Rev. Lett. 74, 5194 (1995).
 19.
Tasaki, H. From quantum dynamics to the canonical distribution: general picture and a rigorous example. Phys. Rev. Lett. 80, 1373 (1998).
 20.
Rigol, M., Dunjko, V. & Olshanii, M. Thermalization and its mechanism for generic isolated quantum systems. Nature 452, 854 (2008).
 21.
Biroli, G., Kollath, C. & Läuchli, A. M. Effect of rare fluctuations on the thermalization of isolated quantum systems. Phys. Rev. Lett. 105, 250401 (2010).
 22.
Santos, L. F. & Rigol, M. Onset of quantum chaos in onedimensional bosonic and fermionic systems and its relation to thermalization. Phys. Rev. E 81, 036206 (2010).
 23.
Kim, H., Ikeda, T. N. & Huse, D. A. Testing whether all eigenstates obey the eigenstate thermalization hypothesis. Phys. Rev. E 90, 052105 (2014).
 24.
Beugeling, W., Moessner, R. & Haque, M. Finitesize scaling of eigenstate thermalization. Phys. Rev. E 89, 042112 (2014).
 25.
Shiraishi, N. & Mori, T. Systematic construction of counterexamples to eigenstate thermalization hypothesis. Phys. Rev. Lett. 119, 030601 (2017).
 26.
Mori, T. & Shiraishi, N. Thermalization without eigenstate thermalization hypothesis after a quantum quench. Phys. Rev. E 96, 022153 (2017).
 27.
Moudgalya, S., Rachel, S., Bernevig, B. A. & Regnault, N. Exact excited states of nonintegrable models. Phys. Rev. B 98, 235155 (2018).
 28.
Moudgalya, S., Regnault, N. & Bernevig, B. A. Entanglement of exact excited states of AffleckKennedyLiebTasaki models: exact results, manybody scars, and violation of the strong eigenstate thermalization hypothesis. Phys. Rev. B 98, 235156 (2018).
 29.
Shiraishi, N. Analytic model of thermalization: quantum emulation of classical cellular automata. Phys. Rev. E 97, 062144 (2018).
 30.
Turner, C. J., Michailidis, A. A., Abanin, D. A., Serbyn, M. & Papić, Z. Weak ergodicity breaking from quantum manybody scars. Nat. Phys. 14, 745 (2018).
 31.
Serbyn, M., Abanin, D. A. & Papić, Z. Quantum manybody scars and weak breaking of ergodicity. Nat. Phys. 17, 675 (2021).
 32.
Lloyd, S. Black Holes, Demons, and the Loss of Coherence, Ph.D. thesis (Rockefeller University, 1988).
 33.
Popescu, S., Short, A. J. & Winter, A. Entanglement and the foundations of statistical mechanics. Nat. Phys. 2, 754 (2006).
 34.
Reimann, P. Typicality for generalized microcanonical ensembles. Phys. Rev. Lett. 99, 160404 (2007).
 35.
Gogolin, C., Müller, M. P. & Eisert, J. Absence of thermalization in nonintegrable systems. Phys. Rev. Lett. 106, 040401 (2011).
 36.
Kim, H. & Huse, D. A. Ballistic spreading of entanglement in a diffusive nonintegrable system. Phys. Rev. Lett. 111, 127205 (2013).
 37.
Farrelly, T., Brandao, F. G. S. L. & Cramer, M. Thermalization and return to equilibrium on finite quantum lattice systems. Phys. Rev. Lett. 118, 140601 (2017).
 38.
Moore, C. Unpredictability and undecidability in dynamical systems. Phys. Rev. Lett. 64, 2354 (1990).
 39.
Eisert, J., Müller, M. P. & Gogolin, C. Quantum measurement occurrence is undecidable. Phys. Rev. Lett. 108, 260501 (2012).
 40.
Cubitt, T. S., PerezGarcia, D. & Wolf, M. M. Undecidability of the spectral gap. Nature 528, 207 (2015).
 41.
Gödel, K. Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme. I. Monatshefte f.ür. Mathematik und Phys. 38, 173 (1931).
 42.
Turing, A. M. On computable numbers, with an application to the Entscheidungsproblem. Proc. Lond. Math. Soc. 42, 230 (1937).
 43.
Moore, C. & Mertens, S. Nature of Computation (Oxford University Press, 2011).
 44.
Morita, K. Theory of Reversible Computing (Springer, 2017).
 45.
Feynman, R. Quantum mechanical computers. Opt. News 11, 11 (1985).
 46.
Kitaev, A. Y., Shen, A. H. & Vyalyi, M. N. Classical and Quantum Computation. Vol. 47 of Graduate Studies in Mathematics. (American Mathematical Society, 2002).
 47.
Yedidia, A. & Aaronson, S., A relatively small turing machine whose behavior is independent of set theory. Preprint at https://arxiv.org/abs/1605.04343.
 48.
Aaronson, S. The busy beaver frontier, https://www.scottaaronson.com/papers/bb.pdf (2020).
 49.
Calude, C. & Calude, E. Evaluating the complexity of mathematical problems: part 1. Complex Syst. 18, 387 (2010).
 50.
Bañuls, M. C., Cirac, J. I. & Hastings, M. B. Strong and weak thermalization of infinite nonintegrable quantum systems. Phys. Rev. Lett. 106, 050405 (2011).
 51.
Kim, H., Bañuls, M. C., Cirac, J. I., Hastings, M. B. & Huse, D. A. Slowest local operators in quantum spin chains. Phys. Rev. E 92, 012128 (2015).
 52.
Mezard, M. & Montanari, A. Information, Physics, and Computation. (Oxford University Press, 2009).
Acknowledgements
We thank Takahiro Sagawa for stimulating the discussion. N.S. was supported by JSPS GrantsinAid for Scientific Research Grant Number JP19K14615.
Author information
Affiliations
Contributions
N.S. and K.M. contributed equally to this work.
Corresponding authors
Ethics declarations
Competing interests
The authors declare no competing interest.
Additional information
Peer review information Nature Communications thanks Angelo Lucia and the other anonymous reviewer(s) for their contribution to the peer review of this work. Peer reviewer reports are available.
Publisher’s note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Supplementary information
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Shiraishi, N., Matsumoto, K. Undecidability in quantum thermalization. Nat Commun 12, 5084 (2021). https://doi.org/10.1038/s41467021250530
Received:
Accepted:
Published:
Comments
By submitting a comment you agree to abide by our Terms and Community Guidelines. If you find something abusive or that does not comply with our terms or guidelines please flag it as inappropriate.