The Complexity of Translationally Invariant Spin Chains with Low Local Dimension

• DOI: 10.1007/s00023-017-0609-7
• Publication Date: 2017-10-29T08:51:04Z
• Authors: Johannes Bausch; Toby Cubitt; Maris Ozols
• Keywords: Hamiltonian (control theory); Unitary transformation

We prove that estimating the ground state energy of a translationally invariant, nearest-neighbour Hamiltonian on 1D spin chain is $$\textsf {QMA}_{{\textsf {EXP}}}$$ -complete, even for systems low local dimension ( $$\approx 40$$ ). This an improvement over best previously known result by several orders magnitude, and it shows spin-glass-like frustration can occur in invariant quantum with comparable to smallest-known non-translationally similar behaviour. While previous constructions such rely standard models computation, we construct new model particularly well-suited encoding computation into system. allows us shift proof burden from optimizing computational model, proving universality simple model. Previous techniques allow only linear sequence gates, hence (or nearly linear) path graph all states. extend these allowing significantly more general paths, including branching cycles, thus enabling highly efficient our However, this requires sophisticated analysing spectrum resulting Hamiltonian. To address this, introduce framework graphs unitary edge labels. After relating Laplacian labelled graph, analyse its combining matrix analysis spectral theory techniques.