[challenge]: Complexity classification of certified 1D thermodynamic limits

Released by

Jie Wang (AMSS, Chinese Academy of Sciences) & Jin-Guo Liu (Hong Kong University of Science and Technology (Guangzhou))

Contact email

cacate0129@gmail.com

Method

Other

Challenge issue

Difficulty: ★★★ (rated by Jie Wang)

Background

Ground-energy density of translation-invariant chains is undecidable in general, yet certified poly-time algorithms exist for 1D equilibrium observables at finite temperature (Fawzi–Fawzi–Scalet, arXiv:2311.18706; arXiv:2402.19030) and RG-compressed relaxations certify 1D chains in the thermodynamic limit (arXiv:2212.03014). The boundary between "physics is computable" and "physics is undecidable" in 1D is not characterized.

Research objective

Classify exactly when the ground-energy density of translation-invariant 1D chains is computable to precision ε in time polynomial in 1/ε with a certified error bar — ideally a dichotomy theorem (gapped ⇒ poly; generic gapless ⇒ hard; frontier characterized). Upper bounds: RG compression with rate analysis + zero-temperature limits of the free-energy machinery. Lower bounds: embed hard tiling/halting structure into gapless TI families. Stress-test candidate algorithms against adversarial instance generators.

Verification plan

• Success gate: a proved classification plus an implementation whose certified error bars are validated on exactly solvable chains (containment) and whose measured runtime matches the proved scaling on a generated instance ladder — theory and artifact must agree.
• Hope signal: a poly-time certified algorithm for the gapped case alone (with promise) — a major result already.
• Pivot signal: the frontier provably encodes number-theoretic problems with no clean characterization — the embedding theorem becomes the paper.

Why this may lead to research output

A Hamiltonian-complexity landmark whose algorithmic half ships as certified software.

References

1. Fawzi, Fawzi, Scalet, Certified algorithms for equilibrium states of local quantum Hamiltonians, arXiv:2311.18706 (Nat. Commun.).
2. Scalet, A faster algorithm for the free energy in one-dimensional quantum systems, arXiv:2402.19030.
3. Kull et al., RG lower bounds, arXiv:2212.03014 (PRX).

The payload names no repository files, tests, or entry points; begin by reading the cited Fawzi–Fawzi–Scalet and Kull et al. papers and defining the promised classification. Done requires a proved complexity classification, a certified implementation, validated error bars on exactly solvable chains, and runtime measurements matching the analysis.