More on Intractability of Thermalization: (almost) i.i.d. inputs and finite lattices

Keiji Matsumoto

REVIEW 4 major objections 8 minor 11 references

More on Intractability of Thermalization: (almost) i.i.d. inputs and finite lattices

T0 review · 4 major / 8 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that deciding the long-time average of a single-site observable in a one-dimensional spin chain is undecidable (RE-complete) when the initial state has one defect, and EXPSPACE-complete or PSPACE-complete for finite…

desk verdict A serious extension of the Shiraishi–Matsumoto thermalization intractability results, worth refereeing, but the PSPACE-hardness proof is not yet checkable as written. read the letter →

arxiv 2507.02601 v1 pith:GXJ4ARJ4 submitted 2025-07-03 quant-ph

Keiji Matsumoto This is my paper · ORCID

classification quant-ph MSC 68Q1781P68

keywords quantumthermalizationcomputationalcomplexityundecidabilityRE-completenessEXPSPACE-completenessone-dimensionalspinchainreversibleTuringmachineslong-timeaverage

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper extends a previous result on the computational intractability of thermalization to simpler initial states and finite lattices. It proves that, in a one-dimensional lattice with a shift-invariant nearest-neighbor Hamiltonian, deciding whether the time-averaged single-site state ends up near a specific pure state or near a specific mixed state is undecidable when the initial state is almost i.i.d., namely all sites in the same state except one defect; the decision problem is RE-complete, exactly as hard as the halting problem. For fully i.i.d. initial states the same decision is at least EXPSPACE-hard, and for finite lattices it is EXPSPACE-complete when the lattice size is written in binary and PSPACE-complete when the size is given in unary. The upshot is that no Turing machine can in general predict the long-term local behavior of such chains, however simple the initial state looks, so the approach to equilibrium can encode arbitrary computation.

What carries the argument

The central object is the Hamiltonian cell automaton $H^L = U^L + (U^L)^\dagger$, where $U^L$ is a local three-site unitary that implements one step of a reversible Turing machine $M_A$ on a length-$L$ tape with a finite control. Starting from a classical configuration $|x\rangle$, the time evolution $e^{-itH}|x\rangle$ stays in the span of the path states $|j;x\rangle = U^j|x\rangle$, and the infinite-time average visits each step almost uniformly ($p_{j;x} \approx 1/J_x$). The input $v$ is encoded not in the Hamiltonian but in the amplitudes of $|\psi_v\rangle$, with the input bit string stored as the relative frequency of 1s in the read-only first track of M-cells; upon halting, an amplification stage flips A-cells from $a_1$ to $a_2$, so the time-averaged single-site state distinguishes halting from non-halting. The dephasing lemma (Lemma 9) is what makes the encoding work: because the first track is read-only and the machine is reversible, any two distinct legal initial configurations have time-evolved path states that differ on the finite control or on an M-cell, so all interference cross terms vanish and the superposition initial state behaves like its probabilistic mixture.

What would settle it

Run the construction for a small reversible Turing machine that halts on one input and not another, compute the exact infinite-time average of the single-site state for a modest lattice by diagonalizing H=U+U†, and check whether halting inputs converge to 1/2(|e1>⟨e1|+|e2>⟨e2|) while non-halting inputs stay near |e1>⟨e1|; a single counterexample would falsify the reduction. Equivalently, exhibit two legal initial configurations whose time-evolved paths agree on every non-A site at some pair of times, violating Lemma 9's orthogonality.

Watch

Extended reading notes

Core claim

The central claim is that the infinite-time, space-averaged single-site reduced state of a 1D translation-invariant nearest-neighbor Hamiltonian is not efficiently computable, and in the almost-i.i.d. single-defect case it is not computable at all. The paper constructs, for any universal reversible Turing machine M, a fixed Hamiltonian and a family of single-site states |ψ_v> depending on the input v, such that the dynamics starting from |e0>⊗|ψ_v>^{⊗L} either stays within ε_1 of |e1>⟨e1| for all time (if M does not halt on v) or has long-time average within ε_1 of (1/2)(|e1>⟨e1| + |e2>⟨e2|) (if M halts). Thus the decision problem SAS/SAH is RE-complete. For the i.i.d. initial state (all sites |ψ_v>), the same dichotomy is obtained with a machine solving an EXPSPACE-complete problem, giving EXPSPACE-hardness; a matching exponential-space algorithm for finite lattices proves EXPSPACE-completeness, and a space-saving encoding of the input into the Hamiltonian using phase-estimation-like rotations proves PSPACE-completeness under unary input size.

Load-bearing premise

The proof assumes that two different starting configurations of the simulating machine can never evolve to states that look identical on every site that the chosen observable can see; if two histories ever merged on all those sites, the entangled pieces would interfere and the reduction would break down.

Editorial extensions

If this is right

For almost-i.i.d. initial states, the problems SAS(d,H,fψ,η,ε₁) and SAH(d,fH,η,ε₁) are RE-complete, so no algorithm that always halts can decide even which of two well-separated behaviors the system exhibits.
For fully i.i.d. initial states, the same question is EXPSPACE-hard, so any procedure that solves it requires exponential space in the worst case.
On finite lattices with the size written in binary, SAHF is EXPSPACE-complete; with the size in unary it is PSPACE-complete, so the difficulty depends on how the lattice size is supplied.
Since the single-site observable A is almost arbitrary (any A with ⟨e1|A|e1⟩ ≠ ⟨e2|A|e2⟩), the intractability is a property of the state dynamics, not a special observable.
The single-defect initial state is so simple that local perturbations of |ψ> ≈ |e1> have unpredictable, computation-theoretically hard long-term consequences.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the RE-completeness result survives in a physically realistic regime, it suggests that no local observable, symmetry, or integrability-based shortcut can certify thermalization in generic translation-invariant 1D chains; one could test this by searching for small instances where the predicted halting/non-halting dichotomy is reproduced numerically.
The dephasing mechanism, a read-only track making distinct histories disagree on all observable-relevant sites, might be imported to prove intractability for other families of initial states, such as product states with a small number of defects, or for open-system dynamics with the same Hamiltonian.
The PSPACE-complete version suggests that a phase-estimation-style encoding of input into the Hamiltonian could be reused when one wants to show hardness for systems whose initial state is fixed, at the price of a more complex local Hamiltonian.
A concrete potential extension is to lower the dimension threshold d0 or sharpen the reduction in settings where the paper leaves open whether the reduction can be made many-one rather than Turing; this would require a closer analysis of the encoding and decoding stages.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague,

This paper refines the earlier Shiraishi–Matsumoto undecidability result for long-term averages of local observables in 1D shift-invariant Hamiltonians. The main new claims: for initial states that are i.i.d. except a single defect, the decision problem is RE-complete; for finite lattices, it is EXPSPACE-complete when the size is given in binary and PSPACE-complete when L is given in unary. If the proofs hold, this sharply changes the picture: even nearly uniform initial states lead to undecidable thermalization questions.

Credit where due: the core construction is a Hamiltonian cell automaton emulating a reversible Turing machine, with the input encoded in the amplitudes of |ψ⟩ rather than in a classical tape. The dephasing lemma (Lemma 9) that lets the superposition initial state be replaced by a mixture for local observables is the heart of the paper, and the argument there is given in real detail. The good-configuration probability estimates (Sections 5.2 and 8.3) are also careful and plausible. The reduction from Halt is convincing in outline.

Soft spots, in proportion. The paper is not in a publishable state. There are unresolved equation references ('(??)' in 5.6.2 and 8), which break the chain of verification in exactly the places where constants matter. More substantively, Section 10.4.2's PSPACE-hardness proof is a sketch. The new encoding uses a 1-qubit phase-estimation trick with a partially traced clock state |j;x⟩⟨j;x|. The paper asserts orthogonality ⟨j;x|j′;x⟩=0 for j≠j′ and that Lemma 13 carries over, but this is exactly the kind of claim that needs proof. The reduced states could in principle coincide up to global phase in HQ_in, and the existing two-sentence justification does not rule it out. If that fails, the Nagaj–Wojcjan time-average formula cannot be applied to the reduced dynamics, and the PSPACE-hardness result is unsupported. I want to stress this is a gap in presentation/proof, not an evident falsehood; my guess is it is fillable.

There is also a factor discrepancy in the eigenvalue formula in Section 5.5 (the 4s² bound vs. 8/(J+1)²) and the paper is riddled with typos. These are fixable but contribute to the sense that the preprint was rushed out.

Verdict: this deserves a serious referee. The core RE-completeness result for the single-defect state looks solid enough to anchor the paper, and the finite-lattice bounds are important if true. I would not cite the PSPACE-completeness theorem until the Section 10.4.2 gap is closed, but I would send it to review with a request for major revision.

Recommendation: engage with it—assign a referee who knows both quantum Hamiltonian complexity and reversible Turing machines.

Referee Report

4 major / 8 minor

Summary. The paper studies the computational complexity of the infinite-time average of spatially averaged single-site observables for one-dimensional shift-invariant nearest-neighbor Hamiltonians. It considers two types of initial states: a product state with a single defect (Theorems 2 and 3: the corresponding decision problems SAS and SAH are undecidable, in fact RE-complete) and an i.i.d. product state (Lemma 5, leading to EXPSPACE-hardness), plus finite-lattice versions in which the lattice size is part of the input (Theorem 14: EXPSPACE-complete with binary input size; Theorem 15: PSPACE-complete with unary input size). The proofs use reversible Turing machines, Hamiltonian cell automata of Nagaj--Wocjan type, dephasing lemmas that replace superpositions of classical configurations by probabilistic mixtures, and concentration estimates for 'good' configurations. The claimed contribution is that the long-term average of a local observable remains intractable even for almost product initial states and for finite lattices, with the precise complexity class depending on the encoding of the lattice size.

Significance. If the main theorems are correct, they substantially strengthen the earlier undecidability result of Shiraishi--Matsumoto: the single-defect version is RE-complete, and the finite-lattice version has a sharp EXPSPACE/PSPACE dichotomy depending on the encoding of the lattice size. The reductions are many-one and do not rely on fitted parameters; the parameter alpha and the thresholds are set by explicit error bounds. The RE-membership argument in Section 7 and the concentration estimates in Sections 5 and 8 are useful technical contributions. The paper also gives credit-worthy explicit constructions and, in the single-defect and EXPSPACE parts, a comparatively detailed proof structure. However, the PSPACE-completeness proof in Section 10.4 is only sketched and contains a key unproved orthogonality claim; the eigenvalue formula in Eq. (15) also appears incorrect. These gaps affect advertised completeness results, so the paper needs substantial revision before the claims can be accepted.

major comments (4)

[10.4.2] The proof of PSPACE-hardness of SAHF' is not complete. The states |j;x> are defined as partial traces over H_Qin, and the paper asserts '⟨j;x|j′;x⟩=0 if j≠j′' and 'Lemma 13 is verified as well' solely because the unreduced configurations differ in Qu when the k1,k2,k3 tracks coincide. Partial traces can be identical for different global states, for example when two global states differ only by a phase or by a unitary acting inside H_Qin, so the orthogonality needed for the time-average formula (15)-(16) and for the cancellation of cross terms in Lemma 13 is not established. The reversible implementation of the 'copy and refresh' step is also not specified, so it is unclear that the dynamics is generated by a valid Hamiltonian cell automaton. This gap is load-bearing because Theorem 15 is a headline claim.
[5.4 and 5.5] Eq. (15) and the energy-gap discussion in Section 5.5 use omega_{k,x}=2 cos(2π k/(Jx+1)) together with sine eigenvectors sin(jkπ/(Jx+1)). These sine eigenvectors are the eigenvectors of the finite open chain H^L=U^L+(U^L)^†, whose eigenvalues are 2 cos(π k/(Jx+1)), not 2 cos(2π k/(Jx+1)). As a result the exact identities (16), (28), and (29), and the gap lower bound in Section 5.5, are not justified as written. Even if the asymptotic O(1/L) conclusions survive after correction, the paper must supply a corrected spectral derivation.
[5.6.2 and 8] Two displayed derivations rely on unresolved placeholder references '(??)': the inequality used just before (30) in the non-halting case, and the claim about the relative frequency of a2 in the discussion motivating the second main lemma. These are not merely cosmetic; the first is used to prove the non-halting case and the second motivates the modified amplification stage, so the stated error bounds cannot be checked from the manuscript. The missing equations or derivations must be supplied.
[10.4] The PSPACE reduction parameters are left unspecified. For PSPACE-hardness one needs a polynomial bound on the block length and lattice size in terms of the input length; however l is not redefined after Section 8, where it is exponential in the input length, and the new decoding still uses the n' and beta encodings whose good-configuration probability was estimated only for exponentially large blocks in Section 8.3. The construction therefore does not yet show that the Hamiltonian and initial state can be described with polynomially many bits and that the dephasing and concentration arguments survive at polynomial scales.

minor comments (8)

[Abstract and Section 1] The text contains several typographical errors ('extention', 'discueese', 'depening', 'defitiniton'); please proofread the manuscript carefully.
[1.2] The problem statement for SAH is mislabeled as [[SAS(d,H,fψ,η,ε1)]]; it should read [[SAH(d,fH,η,ε1)]].
[5.4] In the derivation of (28), the time average of tr ρ_x(t,L)B is written as ⟨x′|e^{-itH}B e^{itH}|x⟩; the index x′ should be x throughout that displayed derivation.
[5.3] The identity '⟨x|e^{itH}P_A e^{-itH}|x⟩ = ⟨x|e^{itH}P_A e^{-itH}|x⟩' is tautological as printed; the right-hand side should presumably be ⟨x|P_A|x⟩, expressing conservation of the number of A-cells.
[References] Reference [1] should be Bhatia, not Bahatia, and reference [7] should be Wocjan, not Wojcan.
[10.1] The display '22(L+1)' is likely intended as 2^{2(L+1)}; as printed, the bound is hard to parse.
[Throughout] Please use a single convention for the imaginary unit (ι versus i) and ensure that e^{-itH} and e^{itH} are used consistently in all Heisenberg-picture expressions.
[10.4.2] The sentence 'the input is not encoded to the eigenvector of the Hamiltonian' is confusing because the paragraph immediately explains that the information encoded in the state is moved to the Hamiltonian; please clarify the intended distinction.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the hardness results are many-one reductions from Halt and EXPSPACE-complete regular-expression equivalence, with no fitted parameter or self-referential construction forcing the target answer.

full rationale

The paper's derivation chain is self-contained and does not reduce to its inputs by construction. The main hardness results (Theorems 3 and 14) are proven by explicit reductions: Lemma 4 and Lemma 5 construct, for a given reversible Turing machine M, a shift-invariant nearest-neighbor Hamiltonian H and a state map fψ such that the long-term behavior (8) or (10) is decided exactly by whether M halts or accepts; the answer of the target thermalization problem is therefore determined by the external halting/acceptance behavior, not by any parameter fitted to the desired output. The dephasing step (Lemma 9) is justified inside the paper using the support condition (19), the read-only first track, and the fact that distinct legal initial configurations differ on M-cells or the finite control; this is a mathematical argument, not an assumption equivalent to the conclusion. The time-average formula (15)-(16) is imported from the independent external work [7] and then generalized to off-diagonal observables with explicit error bounds, so it is real evidence rather than a self-citation. Citation of the authors' previous work [10] appears only as context and motivation, not as a load-bearing black-box theorem. The constants α, ε1, and the thresholds are chosen to satisfy explicit error bounds (e.g., (18), (23), (24)) and are not inferred from the decision answers. The RE-completeness upper bound in Section 7 is an explicit simulation-and-check procedure with a termination criterion proven from the promised alternatives (8) and (9). The skeptic's concern about Theorem 15 is a possible correctness gap in the new 1-qubit phase-estimation encoding: the asserted orthogonality ⟨j;x|j′;x⟩=0 for the partially traced clock states is a proof claim that may need further justification. That is a proof-completeness issue, not circularity, since the claim is not an input to the reduction but an intermediate assertion; if it fails, the reduction is unsupported, but it does not make the result equivalent to its own assumptions. Overall, no circular step was found; the paper's central claims have independent computational content from the external hard problems to which they reduce.

Assumptions & free parameters 1 free parameters · 3 assumptions · 0 invented entities

The construction introduces no new physical entities. The core extra input beyond prior literature is the choice of α, the amplitude of the non-trivially encoded component in the single-site state, plus the standard assumptions of efficient computability and energy-gap lower bounds.

free parameters (1)

α = (ε1/4)^2
Amplitude of the M-cell component in the initial single-site state; chosen by hand to make final error bounds ≤ ε1 (Eq. 18). The reduction's correctness depends on α being small.

assumptions (3)

standard math Nagaj-Wocjan Hamiltonian cellular automaton correspondence: e^{-itH}|x> stays in span{|j;x>} with time-averaged weights p_{j;x} as in Eqs. (15)-(16).
Invoked as the bridge from reversible Turing machine dynamics to continuous-time Hamiltonian evolution; cited from [7] without proof.
domain assumption Energy gaps of finite-size Hamiltonians are bounded below by an easily computable rational (Eq. (7)) and the Hamiltonian/state components are easily computable from the input.
Stated in Section 1.2 as conditions so the single-site problem is tractable; without them even a single system is undecidable, so the hardness is attributed to many-body effects.
domain assumption Existence of a reversible universal Turing machine that never loops on legal, correctly formatted inputs.
Used to construct the RTM M_A in Section 3; justified briefly by adding a history track to a universal TM (citing [6]).

how reviews work

0 comments

Cite this review

Pith. "Pith review of More on Intractability of Thermalization: (almost) i.i.d. inputs and finite lattices." pith.science (2026). https://pith.science/paper/GXJ4ARJ4

@misc{pith2026250702601,
  author       = {Pith},
  title        = {Pith review of: More on Intractability of Thermalization: (almost) i.i.d. inputs and finite lattices},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GXJ4ARJ4}},
  note         = {Machine review of arXiv:2507.02601}
}

read the original abstract

This work is an extention of Shiraishi and Matsumoto [10], and discusses the computational complexity of the long-term average of local observables in one-dimensional lattices with shift-invariant nearest-neighbor interactions for simple initial states. As shown in the previous paper, the problem is generally intractable. In this paper we refine the statement further. First, we consider restriction of the initial state, where the state of all the sites are the same except for a single site. We show this version of the problem is also undecidable (RE-complete). Then we turn to the case where the lattice size is finite: depening on the defitiniton of the input size, this version of problem is either EXPSPACE-complete or PSPACE-complete.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

11 extracted references · 11 canonical work pages

[1]

Bahatia, Matrix Analysis, Springer (1991)

R. Bahatia, Matrix Analysis, Springer (1991)

work page 1991
[2]

Undecidability of the Spectral Gap in One Dimension

J. Bausch, T. Cubitt, A. Lucia, D. Perez-Garcia, Undecidability of the Spectral Gap in One Dimension, https://arxiv.org/abs/1810.01858

work page Pith review arXiv
[3]

Barry Cooper, Computability Theory

S. Barry Cooper, Computability Theory. Chapman & Hall/CRC, Boca Ra- ton, FL, 2004

work page 2004
[4]

Cubitt, David Perez-Garcia and Michael M

Toby S. Cubitt, David Perez-Garcia and Michael M. Wolf in Nature, Unde- cidability of the Spectral gap. Vol.528, pages 207-211 December 10, 2015

work page 2015
[5]

Downey, D

R. Downey, D. Hirschfeldt, Algorithmic Randomness and Complexity. The- ory and Applications of Computability. Springer, New York, 2010

work page 2010
[6]

Morita, Theory of Reversible Computing, Springer, 2017

K. Morita, Theory of Reversible Computing, Springer, 2017

work page 2017
[7]

Wojcan, Hamiltonian quantum cellar automata in one dimen- sion, Phys

D.Nagaj, P. Wojcan, Hamiltonian quantum cellar automata in one dimen- sion, Phys. Rev. A A 78, 032311 (2008)

work page 2008
[8]

C. Neff. Specified precision polynomial root isolation is in NC.Journal of Computer and System Sciences, 48(3):429–463, 1994

work page 1994

Show all 11 references

[9]

Sipser, Introduction to the Theory of Computation, 3rd ed., Cource Technology Prt., 2012

M. Sipser, Introduction to the Theory of Computation, 3rd ed., Cource Technology Prt., 2012

2012
[10]

Undecidability in quantum thermalization

Shiraishi, N., Matsumoto, K. Undecidability in quantum thermalization. Nat Commun 12, 5084 (2021)

2021
[11]

Watrous, Limits on the power of quantum statistical zero-knowledge, Manuscript, 2003

J. Watrous, Limits on the power of quantum statistical zero-knowledge, Manuscript, 2003. A preliminary version appeared in Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, pages 459–468, 2002. 46

2003

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [1]

Bahatia, Matrix Analysis, Springer (1991)

R. Bahatia, Matrix Analysis, Springer (1991)

work page 1991

[2] [2]

Undecidability of the Spectral Gap in One Dimension

J. Bausch, T. Cubitt, A. Lucia, D. Perez-Garcia, Undecidability of the Spectral Gap in One Dimension, https://arxiv.org/abs/1810.01858

work page Pith review arXiv

[3] [3]

Barry Cooper, Computability Theory

S. Barry Cooper, Computability Theory. Chapman & Hall/CRC, Boca Ra- ton, FL, 2004

work page 2004

[4] [4]

Cubitt, David Perez-Garcia and Michael M

Toby S. Cubitt, David Perez-Garcia and Michael M. Wolf in Nature, Unde- cidability of the Spectral gap. Vol.528, pages 207-211 December 10, 2015

work page 2015

[5] [5]

Downey, D

R. Downey, D. Hirschfeldt, Algorithmic Randomness and Complexity. The- ory and Applications of Computability. Springer, New York, 2010

work page 2010

[6] [6]

Morita, Theory of Reversible Computing, Springer, 2017

K. Morita, Theory of Reversible Computing, Springer, 2017

work page 2017

[7] [7]

Wojcan, Hamiltonian quantum cellar automata in one dimen- sion, Phys

D.Nagaj, P. Wojcan, Hamiltonian quantum cellar automata in one dimen- sion, Phys. Rev. A A 78, 032311 (2008)

work page 2008

[8] [8]

C. Neff. Specified precision polynomial root isolation is in NC.Journal of Computer and System Sciences, 48(3):429–463, 1994

work page 1994