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

DOI10.1063/1.5011338zbMATH Open1386.82008arXiv1702.08830OpenAlexW2592387983MaRDI QIDQ4599491FDOQ4599491

Authors: Johannes Bausch, Stephen Piddock 

Publication date: 2 January 2018

Published in: Journal of Mathematical Physics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1702.08830

Recommendations

• The complexity of translationally invariant spin chains with low local dimension
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Complexity classification of local Hamiltonian problems
• The complexity of quantum spin systems on a two-dimensional square lattice
• A complexity classification of spin systems with an external field

zbMATH Keywords

quantum ring machine

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Cites Work

• An introduction to tile-based self-assembly and a survey of recent results
• Quantum computation and quantum information. 10th anniversary edition
• Quantum Complexity Theory
• Characterization of universal two-qubit Hamiltonians
• The Complexity of the Local Hamiltonian Problem
• The power of quantum systems on a line
• The complexity of translationally invariant spin chains with low local dimension
• Efficient algorithm for a quantum analogue of 2-SAT
• Title not available (Why is that?)
• Size-driven quantum phase transitions
• Space-time circuit-to-Hamiltonian construction and its applications
• Complexity of commuting Hamiltonians on a square lattice of qubits

Cited In (7)

• How smooth is quantum complexity?
• A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory
• Trading inverses for an irrep in the Solovay-Kitaev theorem
• Universal qudit Hamiltonians
• The complexity of translationally invariant spin chains with low local dimension
• Translationally invariant universal quantum Hamiltonians in 1D
• Perturbation gadgets: arbitrary energy scales from a single strong interaction

This page was built for publication: The complexity of translationally invariant low-dimensional spin lattices in 3D

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4599491)