{'fraction_non_alphanumeric': 0.038707590569292696, 'fraction_numerical': 0.010566417481311098, 'mean_word_length': 4.410266381489403, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The complexity of energy eigenstates as a mechanism for equilibration

Understanding the mechanisms responsible for the equilibration of isolated quantum many-body systems is a long-standing open problem. In this work we obtain a statistical relationship between the equilibration properties of Hamiltonians and the complexity of their eigenvectors, provided that a conjecture about the incompressibility of quantum circuits holds. We quantify the complexity by the size of the smallest quantum circuit mapping the local basis onto the energy eigenbasis. Specifically, we consider the set of all Hamiltonians having complexity C, and show that almost all such Hamiltonians equilibrate if C is super-quadratic with the system size, which includes the fully random Hamiltonian case in the limit C to infinity, and do not equilibrate if C is sub-linear. We also provide a simple formula for the equilibration time-scale in terms of the Fourier transform of the level density. Our results are statistical and, therefore, do not apply to specific Hamiltonians. Yet, they establish a fundamental link between equilibration and complexity theory.


I. INTRODUCTION
A physical system that has been sitting for a while is often described by a thermal or Gibbs state. This presupposes that, whatever the initial state was, the system evolved into a stationary state. But this is impossible for closed systems evolving unitarily, unless the initial state was already stationary. However, often, the reduced density matrix of a subsystem does evolve to a quasi-stationary state, and stays close to it for most of the time-this is called local equilibration. Identifying which conditions are responsible for this process is a longstanding question in Physics, both for classical [1,2] and quantum systems [3][4][5]. Recently, significant advances in the understanding of this problem have been achieved due to three factors. First, powerful numerical techniques have enabled the dynamical simulation of large many-body systems [6,7]. Second, the use of quantuminformation ideas, and in particular of entanglement theory, has provided new perspectives into this question [8][9][10]. Finally, experiments with ultra-cold atoms have allowed the manipulation and observation of many-body systems with high control [11]. Interestingly, these experiments have challenged the current understanding of these questions, since no thermalisation was observed in certain non-integrable systems [12,13].
Local equilibration can be explained by the mechanism of dephasing [4,8,14,15], under the condition of no degenerate energy gaps (also known as no resonant transitions) [16]. In more recent work [17] it has been shown that if the amount of degenerate energy gaps is small the dephasing mechanism still accounts for local equilibration. This could be the complete answer, but it turns out that it does not explain all equilibration processes. For example, the systems of quasi-free bosons have infinitelymany degenerate energy gaps, and in some cases enjoy local equilibration [9,18,19]. Our results also allow for constructing examples with arbitrarily many degenerate energy gaps which still enjoy local equilibration.
In this work, we consider a different mechanism for local equilibration, which is complementary to dephasing since it is based on the structure of the energy eigenvectors instead of the energy eigenvalues. This mechanism is independent of the energy spectrum, hence it allows for constructing Hamiltonians which enjoy local equilibration despite having many degenerate energy gaps. Additionally, this mechanism provides a simple formula for calculating equilibration time scales, in terms of the Fourier transform of the level density. The time scales obtained in this way decrease with the system's size. This is in striking contrast with the dephasing mechanism, which provides upper bounds to the equilibration time that grow doubly-exponentially with the system's size [8,20]. (With certain assumption on the spectrum, this bound can be improved to just exponential in the system's size [17].) In the middle of these two extreme behaviours there is the physics of extensive systems, like Hamiltonians with local interactions, for which equilibration time scales are expected to grow polynomially with the system's size. This observation suggests that the mechanism introduced in this work, based on the complexity of the energy eigenvectors, is not responsible for the equilibration of standard extensive systems. However, it could account for other types of equilibration phenomena where the underlying dynamics is sufficiently complex. Leaving aside these considerations, the main motivation of this work is purely theoretical. We consider all hermitian matrices as possible many-body Hamiltonians, without imposing any locality condition, and explore the relationship between their equilibration properties and the complexity of their eigenvectors. We believe that looking at the physics of equilibration from the perspective of quantum computation will bring new insights.
In the theory of quantum computation every algorithm can be represented by a quantum circuit, a sequence of one and two-qubit unitaries (also called gates), which processes the input data to generate the output [21].
These gates can be seen as elementary computational steps, so that harder computations require more gates. Then, it seems natural to quantify the complexity C of the energy eigenvectors by the length of the smallest quantum circuit that maps the local basis onto the energy eigenbasis. In this work we establish a link between the equilibration properties of a Hamiltonian and the complexity of its eigenvectors. In order to achieve this we need a conjecture about the incompressibility of quantum circuits, also discussed in [22]. Unfortunately, the mathematical techniques that are available only allow to prove a statistical relationship between equilibration and complexity. That is, we show that the overwhelming majority of Hamiltonians with a certain complexity C equilibrate or not depending on the value of C. However, for a given Hamiltonian with complexity C, we cannot be certain about its equilibration properties. Hence, our results do not provide a sharp equilibration condition, like the no degeneracy of energy gaps. Yet, we believe that these results are important because they articulate a relationship between concepts from quantum computation and the physics of equilibration.
The present article is structured as follows: first, in Section II we describe the physical set up that we are going to consider throughout this work. In Section III we study the equilibration properties of Hamiltonians in the limit of large complexity. In Section III we analyse the dynamics of the convergence towards equilibrium, and the associated time scales. In Section V we establish the relationship between the equilibration properties of a Hamiltonian and the complexity of its eigenstates, and formalise the above mentioned conjecture. The proofs of all our results are detailed in the Appendix.

II. PHYSICAL SET UP
We consider a system of N qubits (spin-1 2 particles) with Hamiltonian where |Ψ n are the eigenvectors, E n are the eigenvalues, and d = 2 N . The Hamiltonian characterises the dynamics of the system: if ρ is the state of the N qubits at time t = 0 then ρ(t) = e −itH ρ e itH is the state at time t. The diagonalising unitary U maps the local basis |n = |n 1 , . . . , n N to the energy eigenbasis |Ψ n = U |n , for all n ∈ {0, 1} N . Suppose that we are interested in a subset of the N qubits-we refer to it as the subsystem, while the rest of qubits are referred to as the environment. The Hilbert space factorizes as H = H S ⊗H E , with the corresponding dimensions satisfying d = d S d E . If ρ is a state of the N qubits, the reduced state of the subsystem is ρ S = tr E ρ. Local equilibration happens when the subsystem evolves towards a particular state, and stays close to it for most of the time. If the state ρ S (t) equilibrates to the statē ρ S , then this must be the time-averaged state [10] (2) As in [8][9][10], we quantify the departure from equilibrium at time t by the trace distance ρ S (t) −ρ S 1 , which is directly related to the probability of distinguishing ρ S (t) fromρ S with the optimal measurement [21,23]. In order to prove equilibration, the only condition on the spectrum of the Hamiltonian that we need is that g/d is a small number, where g is the maximal degeneracy of the Hamiltonian Note that this is not a very demanding condition for a large system. Apart from this, the spectrum is arbitrary, and in particular, it can have many degenerate energy gaps [16]. So essentially, in our construction, the spectrum does not influence whether the Hamiltonian equilibrates or not. However, it does influence the dynamics of the convergence towards equilibrium. As we will see, this is characterised by the Fourier transform of the level density µ(E), where the second equality holds for finite-dimensional systems.

III. EQUILIBRATION IN HAMILTONIANS WITH GENERIC EIGENSTATES
Before quantifying the complexity of Hamiltonians it is convenient to study the limit of large complexity. As we see below, this corresponds to sample the diagonalising unitary U according to the Haar measure [24]. The following result (proven in the Appendix) bounds the departure from equilibrium in Hamiltonians that are generic according to this type of sampling.
Result 1. For any N -qubit initial state ρ, almost all Hamiltonians (1) with a given spectrum for all t.
The meaning of "almost all" is controlled by the free parameter ǫ ∈ (0, 1), which is an upper bound for the fraction of Hamiltonians (1) that violate the bound. For example, if we set ǫ = 0.01, then 99% of the Hamiltonians satisfy the above bound. Note that this bound is independent of the initial state ρ, but the set of Hamiltonians which violate it could depend on ρ. A this point we do not know much about the nature of the Hamiltonians which satisfy or violate this bound. In Section III we are able to say a bit more by analysing the equilibration time scales of the Hamiltonians which satisfy the bound. Let us discuss the significance of the three terms inside the brackets of (5). The first term depends on the spectrum of H and the time t. At time t = 0 the bound is useless, sinceμ(0) = 1. For sufficiently long times, it is expected that the phases in the sum (4) cancel each other, resulting in a small number, and implying equilibration. Actually, Result 2 below shows that this is the case for most of the times, independently of the existence of degenerate energy gaps. However, in finite systems (d < ∞), there are some very special (and very long) times t req for whichμ(t req ) ≈μ(0). These are the quasi-recurrences, in which the system goes back to a non-equilibrium state. In the thermodynamic limit quasi-recurrences tend to disappear. Below, the quantityμ(t) is calculated for some meaningful spectra. The second term also depends on the spectrum of H, and implies that Hamiltonians with huge degeneracy cannot be warranted to equilibrate. The third term implies that equilibration needs the environment to be much larger than the subsystem. This condition is necessary in all approaches to equilibration known to the authors [4, 8-10, 14, 15, 18, 19].
Although quasi-recurrences take the subsystem out of equilibrium, the following result (proven in the Appendix) shows that, in most circumstances, the subsystem is close to the stationary stateρ S for most of the time.
Result 2. For any N -qubit initial state ρ, almost all Hamiltonians (1) with a given spectrum This shows that, in the reasonable regime where g, d S ≪ d E equilibration is expected for all Hamiltonians except for a fraction ǫ ∈ (0, 1), when the diagonalising unitary is sampled according to the Haar measure. This establishes the existence of a mechanism for equilibration which is only based on the genericness of the diagonalising unitary U , or equivalently, the genericness of the energy eigenstates. This mechanism does not rely on any condition for the energy spectrum (other than g ≪ d E )-even in the presence of many degenerate energy gaps equilibration happens.

IV. TIME SCALES
Result 1 shows that the dynamics of the convergence to equilibrium is given by the function |μ(t)|, which only depends on the spectrum. The structure of the Fourier transform (4) provides a rough time-scale for equilibration where ∆E is the variance of the distribution µ(E). In many systems of physical interest both, the range of energies ∆E and the equilibration time scale t eq , increase with the system's size. But this is incompatible with (7). This implies that these systems do not have a generic diagonalising unitary U (according to the Haar measure), and hence, if they equilibrate, they do it by means of a different mechanism. Contrary, Hamiltonians with generic diagonalising unitaries have non-vanishing interacting terms involving any subset of the qubits constituting the system. This explains why the equilibration time scale decreases with the system size. These type of interactions, involving a large number of particles, do not happen in Nature, but can be used to articulate a connection between equilibration and complexity. Next, we exactly calculate |μ(t)| for two standard spectra, each representing an extreme case.

A. Spectrum of a random Hamiltonian
Let us consider random Hamiltonians sampled from the gaussian unitary ensemble [25]. According to this, each matrix element H ij = H * ji ∈ C is an independent random variable with probability density It is shown in [25] that, according to this measure, the eigenvalues of H are statistically independent from the eigenvectors of H, and the diagonalising unitary U follows the Haar measure [24], as in results 1 and 2. The gaussian unitary ensemble is often used to model some aspects of atomic nuclei, see [26]. The convergence function corresponding to the spectrum of a random matrix is, in the large-d limit, where J 1 is the Bessel function of first kind (see Appendix). This gives an equilibration time-scale where E max is the largest eigenvalue of the Hamiltonian. Note that both, in terms of N and in terms of E max , the equilibration time (9) is much smaller than the one obtained for the spectrum of an integrable system, see Eq. (13) below. This is expected, since the spectrum associated to (9) is maximally chaotic.

B. Spectrum of an integrable system
Let us consider Hamiltonians with the diagonalising unitary U being generic (according to the Haar measure), and the spectrum being the one of the Ising model in a transverse magnetic field h. Note that this is a purely academic problem, since we do not expect the Ising model to have a generic diagonalising unitary, nor an equilibration time scale that decreases with the system's size. The eigen-energies are parametrized by the vectors n = (n 1 , . . . , n N ), where n k ∈ {0, 1} are the occupation numbers of the energy eigen-modes: In the t ≪ 1 regime we obtain (see Appendix) This gives an equilibration time-scale t eq = 1 where E max is the largest eigenvalue of the Hamiltonian (see Appendix).

V. EQUILIBRATION AND COMPLEXITY
In this section we analyse the quantitative relation between equilibration and complexity, and show that as mentioned in Section II, the limit of large complexity corresponds to sample the diagonalising unitary U according to the Haar measure.
In the theory of quantum computation every algorithm can be represented by a quantum circuit, a sequence of one and two-qubit unitaries (also called gates), which processes the input data to generate the output [21]. This is analogous to classical computation, where algorithms can be represented by circuits of logical gates. These gates can be seen as elementary computational steps, so that harder computations require more gates. Following this idea, it seems natural to quantify the complexity of the energy eigenvectors by the number of gates, denoted C, of the circuit that brings the local basis to the energy eigenbasis. Now, we can obtain statistical properties of Hamiltonians as in Results 1 and 2 above. But instead of sampling over all unitaries (Haar measure), we sample over all unitaries that can be implemented by a quantum circuit of a particular length C. It was proven in [22] that, in this setup, taking the limit C → ∞ is equivalent to sample according to the Haar measure. Hence, in this limit, we recover our previous results.

A. Large complexity
A central part in the proof of Result 1 consists of performing an average over all possible diagonalising unitaries U , distributed according to the Haar measure. However, the averaged expression only contains a fourth power of U ⊗ U * (the tensor product between U and its complex-conjugate U * ). Here one can use the concept of t-design: a finite set of unitaries U i ∈ SU(d) with associated probabilities p i is a t-design if Then, if instead of all unitaries one averages over a subset being a 4-design, the same result is obtained. In [27] strong evidence was provided to the fact that random circuits constitute good approximations to 4-designs. Recently, this has been rigorously proven in [22], which allows us to show the following.

Result 3. Suppose that a given initial state ρ evolves under a Hamiltonian
where U is any circuit with C gates. For almost all such circuits we have for all t.
The meaning of "almost all" is again controlled by the free parameter ǫ ∈ (0, 1), which is an upper bound for the fraction of circuits with C gates that violate the bound [28]. The constant α depends on the universal gate set, and it is calculated in [22,27]. Compared to Result 1 there is an extra term inside the brackets in (15), which disappears in the large-C limit. When C is quadratic in the number of qubits (or larger), for α ′ > 3/α, the extra term is exponentially small in N . One can also proceed as in the proof or Result 2, and obtain a bound for the time average of ρ S (t) −ρ S 1 in the limit T → ∞. Note that the quadratic scaling of C in (16) is the minimum needed to warrant that the circuit U which diagonalises H contains a gate connecting a sufficient fraction of all pairs of qubits. In order to interpret the circuit length C of U as the complexity of the eigenvectors of H we have to consider the following caveat. Suppose that the unitary U can be written as a circuit of length C, and there is another unitary U ′ which can be written as a circuit of length C ′ ≪ C and constitutes a good approximation to U (e.i. the operator norm of the difference U − U ′ ∞ is very small). In this case it does not make much sense to say that U has complexity C. However, we conjecture that the overwhelming majority of unitaries do not have this property. Formally, for any ǫ > 0 and any integer k, the fraction of circuits of length N k which can be ǫapproximated by a circuit of length N k−αǫ tends to zero as N → ∞, for some positive constant α. Support for this conjecture is given in [22], where the relation to equilibration is also discussed. Result 3 together with this conjecture establishes the statistical relationship between equilibration and the complexity of the energy eigenvectors.

B. Small complexity
Consider a Hamiltonian with no interaction between subsystem and environment: H = H S ⊗I E + I S ⊗H E where I S (I E ) is the identity matrix for the subsystem(environment). In this case, the reduced density matrix ρ S (t) = e −itHS ρ S e itHS does not converge to anything, unless it is in a stationary state from the beginning [ρ S , H S ] = 0. Therefore, interaction is necessary for equilibration. The condition of no degenerate energy gaps implies that there is interaction across all possible bipartitions subsystem-environment [8]. It also implies local equilibration, independently of the complexity of the Hamiltonian. Therefore, in order to investigate the lack of equilibration, we have to restrict to Hamiltonians with many degenerate energy gaps.
For simplicity, we consider Hamiltonians of the freefermion type. Letn k = |1 1| be the occupation operator for the the k th qubit, ω k the corresponding excitation energy, and Let the subsystem be an M -qubit subset of the N qubits, and the environment the remaining N − M qubits. In the case C = 0 the Hamiltonian H = N k=1 ω knk is local and its eigenvectors |n 1 , . . . , n N are product. Hence, each qubit evolves independently, the subsystem does not interact with the environment, and there is no equilibration. Next we see that this is still the case when the complexity C is sufficiently small.
Let us lower-bound the probability that a random circuit U for N qubits has no gates involving any of M fixed qubits. The random circuit is generated by repeating the following process C times: uniformly pick a gate from the universal gate set; if this is a single-qubit gate apply it to a qubit chosen uniformly from the N qubits; if this is a two-qubit gate apply it to a pair of qubits chosen uniformly. The probability p that no gate is applied to any of the M qubits satisfies In this event, there is no interaction subsystemenvironment, and hence, no equilibration. Suppose the complexity is sublinear: C ≤ N ν with 0 < ν < 1. If we fix the size of the subsystem M , in the large-N limit we have p ≈ 1 − 2M/N 1−ν , and then Result 4. For almost all circuits U with sublinear complexity, the associated Hamiltonian (17) does not enjoy local equilibration.

VI. CONCLUSIONS
In this work we have addressed the problem of equilibration in isolated quantum many-body systems evolving under unitary dynamics. We have pointed out the existence of a mechanism for local equilibration which is based on the complexity of the energy eigenvectors. We have shown that: almost all Hamiltonians whose diagonalising unitary is a circuit of length C equilibrate if C is super-quadratic with the system's size, and do not equilibrate if C is sub-linear with the system's size. What happens in between these two regimes is an open problem that we leave for the future. Since these results are statistical, it is difficult to extract conclusions for physically relevant Hamiltonians, like those with local interactions.
Under the action of this equilibration mechanism, the equilibration time scale decreases with the system's size. This is not expected in Hamiltonians with local interactions. In particular, the equilibration time scale of the Ising model with long-range interactions [29] diverges with the system's size. Clearly, this class of Hamiltonians belong to the ǫ-fraction of cases that violate our bounds. However, our results could apply to sufficiently chaotic systems.
The relation between equilibration and the complexity of solving the dynamics of a physical system that emerges from our results resembles the situation in classical mechanics, where the notion of integrability plays an important role [2]. In fact, there exists a link between equilibration (formalised by weak mixing [2]) and the difficulty of solving the dynamics of a classical system: integrable systems violate weak mixing, while sufficiently chaotic systems satisfy it. Now, if the circuit size is interpreted as the complexity of solving the dynamics of a quantum system, the resulting picture resembles what happens in classical mechanics. Hence, our results may also contribute to the problem of finding a definition for quantum integrability-a proposal in terms of computational complexity can be found in [30].
Dephasing under the condition of no degenerate energy gaps [8,15] and the complexity of the energy eigenvectors are two independent mechanisms that explain the phenomenon of local equilibration. Are there other mechanisms, apart from these two? Does any of them play a dominant role in natural phenomena?
Note added after completion of this work: results related to the ones presented here have been obtained independently in References [31] and [32].
and note that Ω t [ρ] = ρ S (t) −ρ S . The sum En =E n ′ runs over all pairs of eigenstates n, n ′ ∈ {1, . . . , d} with different energies Before doing the general case, we first consider the case where the initial state is pure ψ = |ψ ψ|. Some calculation shows Due to the Schur-Weyl duality [33], the matrix M 0 is a linear combination of permutations where the index π runs over the 4! permutations of four elements, c π ∈ C are some coefficients, and the unitaries V π permute the four factor spaces in which M acts. For instance n 1 , n 2 , n 3 , n 4 |V (2341) = n 2 , n 3 , n 4 , n 1 |.
Let us obtain the coefficients c π from (A6). Note that M 0 has the following symmetries These four different coefficients can be determined with the following equations: tr(M 0 V (4312) ) = tr S (tr 2 E |ψ ψ|) =: β . These equations follow from the identity trV π = d cicl(π) , where cicl(π) is the number of cicles in the permutation π. The solution of the system of equations (A8) is: Assuming d > d E > 0 and using β ≤ 1 we obtain Combining (A3) and (A6) we get where × n, k, n ′ , k ′ |V π |n ′ , k ′ , n, k .
The constraints E n = E n ′ and E k = E k ′ imply that f π (t) = 0 for most π. The only permutations π for which f π (t) = 0 are following ones In summary: Using we obtain and also Define w = ( En=E n ′ 1) and note that w ≤ gd. Direct calculation shows the Haar measure by the average over unitaries which are circuits with C gates. As in (A5) we define the linear map U which symmetrises any d 4 × d 4 matrix X. It can be shown that E is a projector [33], so its eigenvalues are 1 and 0. Let K(C) be the set of N -qubit circuits with C gates, from a particular universal gate set. We denote by · U∈K(C) the average over all unitaries in K(C) with equal weights. It is shown in [27] that where λ = 1 − α/N , the constant α > 0 depends on the universal gate set, and the linear map E ′ has bounded norm E ′ (X) 2 ≤ 1 for all X with X 2 = tr(X † X) ≤ 1. The matrix M defined in (A4) satisfies Using this, identity (A22) and the fact that Reproducing the argument of Result 1, but using (A23) instead of (A17) one obtains Result 3. where where ϕ k (x) are the eigenfunctions of the quantum harmonic oscillator. To see how the determinant works in (B3) consider the example When substituting (B3) in (B2), we obtain products of objects of the form and dE 1 · · · dE n K(E 1 , E 2 ) · · · K(E n , E 1 ) e i(t1E1+···+tnEn) = tr P e it1X P e it2X · · · P e itnX (B6) for n = 2, 3, 4-where P = d−1 k=0 |ϕ k ϕ k | is the projector onto the d-dimensional lower-energy subspace of the harmonic oscillator, and X is the position operator. For any pair of bounded operators A, B, the Cauchy-Schwartz inequality tells This can be used to bound (B6) for the case n = 4: tr P e it1X P e it2X P e it3X P e it4X ≤ tr e −it2XP e −it1XP 2 e it1XP e it2X tr P e −it3XP e it3X ≤ tr P tr P tr P tr P ≤ d.
By setting t 4 = 0 and t 3 = 0, we obtain the same bound for n = 3, 2. It is shown in [25] that in the large-d limit we have This is called "the semi-circle law". In this limit, the integral (B5) can be evaluated where J 1 is the Bessel function of the first kind. When substituting (B3) in (B2), we obtain several terms, each being a product of objects of the form (B5) or (B6). According to (B8) and (B10), each of these factors (B5) or (B6) is bounded by d. Since |μ(t)| 4 H is equal to (B2) divided by d 4 , all terms are of order 1/d or smaller, except for the single term with a four-fold product of (B5). This implies that in the large-d limit we have where the inequality follows from the convexity of the logarithm, and the approximation holds when the integrand oscillates heavily, that is when t ≫ 1. In the large-N limit, the largest eigenvalue is which is proportional to N .