The Complexity of Translationally-Invariant Low-Dimensional Spin Lattices in 3D

Abstract

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.

20 pages. 3 figures in main text; with technical appendix

References in corpus (3)

• The power of quantum systems on a line
• Hamiltonian Quantum Cellular Automata in 1D
• The Complexity of Translationally-Invariant Spin Chains with Low Local Dimension

Cited by in corpus (9)

• Undecidability of the Spectral Gap in One Dimension
• Uncomputability of Phase Diagrams
• General conditions for universality of Quantum Hamiltonians
• The Complexity of Translationally Invariant Problems beyond Ground State Energies
• Translationally-Invariant Universal Quantum Hamiltonians in 1D
• Universal Translationally-Invariant Hamiltonians
• Perturbation Gadgets: Arbitrary Energy Scales from a Single Strong Interaction
• How smooth is quantum complexity?
• The Complexity of Approximating Critical Points of Quantum Phase Transitions