The complexity of translationally invariant low-dimensional spin lattices in 3D

Johannes Bausch, Stephen Piddock

Research output: Contribution to journalArticle (Academic Journal)peer-review

6 Citations (Scopus)
225 Downloads (Pure)


In this paper, we consider spin systems in three spatial dimensions, and prove that the local Hamiltonian problem for 3D lattices with face-centered cubic unit cells, 4-local translationally-invariant interactions between spin-3/2 particles and open boundary conditions is QMAEXP-complete. We go beyond a mere embedding of past hard 1D history state constructions, and utilize a classical Wang tiling problem as binary counter in order to translate one cube side length into a binary description for the verifier input. We further make use of a recently-developed computational model especially well-suited for history state constructions, and combine it with a specific circuit encoding shown to be universal for quantum computation. These novel techniques allow us to significantly lower the local spin dimension, surpassing the best translationally-invariant result to date by two orders of magnitude (in the number of degrees of freedom per coupling). This brings our models en par with the best non-translationally-invariant construction.
Original languageEnglish
Article number111901
Number of pages26
JournalJournal of Mathematical Physics
Issue number11
Early online date22 Nov 2017
Publication statusPublished - Nov 2017


  • quant-ph
  • cs.CC
  • 68Q17, 81V70, 68Q10, 82D25


Dive into the research topics of 'The complexity of translationally invariant low-dimensional spin lattices in 3D'. Together they form a unique fingerprint.

Cite this