The complexity of translationally invariant spin chains with low local dimension (Q1683948)

The main result proved in the paper is the follwing: The local Hamiltonian problem with translationally invariant interactions between neigbouring spins on a chain with local dimension 42 is \(\text{QMA}_{\text{EXP}}\)-complete. This holds true even for Hamiltonians with local terms of the form \(\mathbf{h} + p(n)\mathbf{b}\), where \(\mathbf{h}\) and \(\mathbf{b}\) are fixed 2-local interactions and \(p(n)\) is a fixed polynomial in the chain of length \(n\). The result is an improvement by several ordeers of magnitude over the best knwon results. The paper uses new ideas and sophisticated techniques, specifically for encoding quantum computations.