We prove that estimating the ground state energy of a translationally invariant, nearest-neighbour Hamiltonian on a 1D spin chain is QMAEXP -complete, even for systems of low local dimension ( ≈40 ). This is an improvement over the best previously known result by several orders of magnitude, and it shows that spin-glass-like frustration can occur in translationally invariant quantum systems with a local dimension comparable to the smallest-known non-translationally invariant systems with similar behaviour. While previous constructions of such systems rely on standard models of quantum computation, we construct a new model that is particularly well-suited for encoding quantum computation into the ground state of a translationally invariant system. This allows us to shift the proof burden from optimizing the Hamiltonian encoding a standard computational model, to proving universality of a simple model. Previous techniques for encoding quantum computation into the ground state of a local Hamiltonian allow only a linear sequence of gates, hence only a linear (or nearly linear) path in the graph of all computational states. We extend these techniques by allowing significantly more general paths, including branching and cycles, thus enabling a highly efficient encoding of our computational model. However, this requires more sophisticated techniques for analysing the spectrum of the resulting Hamiltonian. To address this, we introduce a framework of graphs with unitary edge labels. After relating our Hamiltonian to the Laplacian of such a unitary labelled graph, we analyse its spectrum by combining matrix analysis and spectral graph theory techniques.
Investigating translationally invariant qudit spin chains with a low local dimension, we ask what is the best possible tradeoff between the scaling of the entanglement entropy of a large block and the inverse-polynomial scaling of the spectral gap. Restricting ourselves to Hamiltonians with a "rewriting" interaction, we find the pair-flip model, a family of spin chains with nearest neighbor, translationally invariant, frustration-free interactions, with a very entangled ground state and an inverse-polynomial spectral gap. For a ground state in a particular invariant subspace, the entanglement entropy across a middle cut scales as logn for qubits (it is equivalent to the XXX model), while for qutrits and higher, it scales as n. Moreover, we conjecture that this particular ground state can be made unique by adding a small translationally-invariant perturbation that favors neighboring letter pairs, adding a small amount of frustration, while retaining the entropy scaling.
Abstract Recent work has characterized rigorously what it means for one quantum system to simulate another and demonstrated the existence of universal Hamiltonians—simple spin lattice Hamiltonians that can replicate the entire physics of any other quantum many-body system. Previous universality results have required proofs involving complicated ‘chains’ of perturbative ‘gadgets.’ In this paper, we derive a significantly simpler and more powerful method of proving universality of Hamiltonians, directly leveraging the ability to encode quantum computation into ground states. This provides new insight into the origins of universal models and suggests a deep connection between universality and complexity. We apply this new approach to show that there are universal models even in translationally invariant spin chains in 1D. This gives as a corollary a new Hamiltonian complexity result that the local Hamiltonian problem for translationally invariant spin chains in one dimension with an exponentially small promise gap is PSPACE-complete. Finally, we use these new universal models to construct the first known toy model of 2D–1D holographic duality between local Hamiltonians.