{"id":"f97ca4df-35b6-46a8-a315-4c65bb8835db","arxiv_id":"2507.02601","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"For a 1D shift-invariant nearest-neighbor quantum chain, deciding the long-term average single-site state is RE-complete with a single defect, and EXPSPACE- or PSPACE-complete for finite lattices with i.i.d. inputs.","lead":"This paper proves that deciding whether a simple one-dimensional quantum system thermalizes can be as hard as the halting problem, and remains extremely hard (EXPSPACE- or PSPACE-complete) even for finite lattices with almost uniform initial states. It sharpens earlier undecidability results by demonstrating intractability for nearly i.i.d. inputs and by mapping the finite-size complexity landscape.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 15's PSPACE-hardness rests on an unproved orthogonality/dephasing claim for the new phase-estimation encoding; if that claim fails, the finite-lattice PSPACE result is unsupported.","rationale":"The reader's weakest-assumption pick, Lemma 9, is actually fairly well supported: read-only first track plus reversibility does force any difference between legal configurations to appear on Q or M cells when head positions coincide, so cross terms of observables supported on A-cells vanish. I therefore do not regard Lemma 9 as the most fragile point. The genuinely load-bearing gap is Theorem 15's PSPACE-hardness proof in Section 10.4.2: the new phase-estimation encoding modifies the Hilbert space and, crucially, replaces the clock states by partially traced reduced states. The paper asserts rather than proves that these reduced states remain exactly orthogonal and that the dephasing lemma survives partial tracing over HQ_in. Without that, the entire time-averaging machinery of Section 5 cannot be applied to the PSPACE construction. This is the same class of dephasing issue the reader flagged, but localized at Theorem 15 rather than Lemma 9; it is also independently visible in the reader's list of unresolved items. The gap appears fillable, so a REJECT is not warranted; the paper should be accepted only conditional on a complete proof of the PSPACE encoding's orthogonality and dephasing properties.","tokens_in":35570,"tokens_out":13640,"duration_ms":173236,"concrete_test":"Take a small input v, instantiate the Section 10.4.2 construction explicitly (including the R_{πβ} and R_{-π2^{-|v|}} one-body terms and the k1,k2,k3 counters), and numerically compute the reduced matrices |j;x⟩⟨j;x| = tr_{HQ_in}(U^{j-1}|x⟩⟨x|(U†)^{j-1}) for all j up to the orbit period. Check whether ⟨j;x|j′;x⟩=0 for all j≠j′ and whether the analogue of Lemma 13 holds for all pairs of legal initial configurations. If any overlap is nonzero, Theorem 15's proof collapses; if all overlaps are zero and cross terms vanish, the concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 10.4.2 introduces a new 1-qubit phase-estimation encoding for Theorem 15. The proof asserts \"Then ⟨j;x|j′;x⟩=0 if j≠j′, and Lemma 13 is verified as well\" after defining |j;x⟩⟨j;x| as the partial trace over HQ_in of U^{j-1}|x⟩⟨x|(U†)^{j-1}. This is load-bearing because the Nagaj-Wocjan time-average formula (15)-(16) used throughout requires an orthonormal clock basis |j;x⟩. For partially traced reduced states, mutual orthogonality and the cancellation of cross terms in Lemma 13 must be re-proven in the reduced Hilbert space; the two-sentence justification (\"differ in Qu at least\") does not rule out two different step numbers whose reduced states coincide on all registers outside HQ_in, e.g., two rotations of the same qubit separated by an uncompute cycle, or states differing only by a global phase in HQ_in. If orthogonality fails, the effective dynamics is not a Hamiltonian clock automaton on a classical configuration space, and the PSPACE-hardness reduction is unsupported. Since Theorem 15 is a headline result for finite lattices with unary input size, this is a substantive gap, not a stylistic one.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":35724,"tokens_out":23210,"duration_ms":262225,"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":[{"comment":"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.","section":"10.4.2"},{"comment":"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.","section":"5.4 and 5.5"},{"comment":"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.","section":"5.6.2 and 8"},{"comment":"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.","section":"10.4"}],"minor_comments":[{"comment":"The text contains several typographical errors ('extention', 'discueese', 'depening', 'defitiniton'); please proofread the manuscript carefully.","section":"Abstract and Section 1"},{"comment":"The problem statement for SAH is mislabeled as [[SAS(d,H,fψ,η,ε1)]]; it should read [[SAH(d,fH,η,ε1)]].","section":"1.2"},{"comment":"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.","section":"5.4"},{"comment":"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.","section":"5.3"},{"comment":"Reference [1] should be Bhatia, not Bahatia, and reference [7] should be Wocjan, not Wojcan.","section":"References"},{"comment":"The display '22(L+1)' is likely intended as 2^{2(L+1)}; as printed, the bound is hard to parse.","section":"10.1"},{"comment":"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.","section":"Throughout"},{"comment":"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.","section":"10.4.2"}],"recommendation":"major_revision","confidential_remarks":"The PSPACE-hardness part is the main risk. If the authors cannot supply a complete proof of the orthogonality/dephasing claim in Section 10.4.2 and a full specification of the polynomial-parameter scaling, the PSPACE theorem should be removed or explicitly deferred to future work. The rest of the paper may be publishable after correcting Eq. (15) and filling the placeholder references, but the advertised completeness claims require a full proof, not a sketch."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThis 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.\n\nCredit 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.\n\nSoft 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.\n\nThere 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.\n\nVerdict: 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.\n\nRecommendation: engage with it—assign a referee who knows both quantum Hamiltonian complexity and reversible Turing machines.","headline":"A serious extension of the Shiraishi–Matsumoto thermalization intractability results, worth refereeing, but the PSPACE-hardness proof is not yet checkable as written.","tokens_in":36357,"tokens_out":1952,"would_cite":false,"duration_ms":21118,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","81P68"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["quantum thermalization","computational complexity","undecidability","RE-completeness","EXPSPACE-completeness","one-dimensional spin chain","reversible Turing machines","long-time average"],"falsifier":"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.","tokens_in":35262,"feed_emoji":"⚫","tokens_out":7108,"duration_ms":80628,"temperature":0.7,"pith_summary":"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.","feed_headline":"Computing thermal averages in 1D chains is undecidable","feed_subtitle":"Even an almost-identical initial state encodes the halting problem; finite lattices are EXPSPACE-complete.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the long-term average decision problem and proves the earlier intractability result that this paper extends.","marker":"[10]"},{"why":"Supplies the Hamiltonian cell automaton correspondence showing that time evolution under H=U+U† has almost uniform time averages over computational steps.","marker":"[7]"},{"why":"Supplies the reversible Turing machine model (URTM) that the Hamiltonian dynamics emulates.","marker":"[6]"},{"why":"Provides the EXPSPACE-complete problem (equivalence of regular expressions with union, concatenation, and exponentiation) used for the i.i.d. and finite-lattice hardness proofs.","marker":"[9]"},{"why":"Provides the polynomial root isolation procedure in NC used to compute trace distances in the EXPSPACE containment argument.","marker":"[8]"}],"fun_headline_variants":["Thermal averages in 1D remain undecidable even for near-uniform states","Almost-uniform initial states still make thermalization undecidable","Finite 1D chains: thermal averaging is EXPSPACE-complete","Thermalization intractability: from undecidable to EXPSPACE-hard","Even single-defect 1D lattices encode halting problem"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Thermal averages in 1D remain undecidable even for near-uniform states","Almost-uniform initial states still make thermalization undecidable","Finite 1D chains: thermal averaging is EXPSPACE-complete","Thermalization intractability: from undecidable to EXPSPACE-hard","Even single-defect 1D lattices encode halting problem"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000677,"raw_usage":{"total_tokens":3081,"prompt_tokens":953,"completion_tokens":2128,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":569,"completion_tokens_details":{"reasoning_tokens":2039}},"tokens_in":569,"tokens_out":2128,"duration_ms":17575,"temperature":1.0,"reasoning_tokens":2039,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T20:26:56.483882+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Undecidability in quantum thermalization","cited_arxiv_id":null,"evidence_quote":"Defines the long-term average decision problem and proves the earlier intractability result that this paper extends."},{"cited_title":"Wojcan, Hamiltonian quantum cellar automata in one dimen- sion, Phys","cited_arxiv_id":null,"evidence_quote":"Supplies the Hamiltonian cell automaton correspondence showing that time evolution under H=U+U† has almost uniform time averages over computational steps."},{"cited_title":"Morita, Theory of Reversible Computing, Springer, 2017","cited_arxiv_id":null,"evidence_quote":"Supplies the reversible Turing machine model (URTM) that the Hamiltonian dynamics emulates."},{"cited_title":"Sipser, Introduction to the Theory of Computation, 3rd ed., Cource Technology Prt., 2012","cited_arxiv_id":null,"evidence_quote":"Provides the EXPSPACE-complete problem (equivalence of regular expressions with union, concatenation, and exponentiation) used for the i.i.d. and finite-lattice hardness proofs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the polynomial root isolation procedure in NC used to compute trace distances in the EXPSPACE containment argument."}],"review_version":1}