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

DOI10.1063/1.5011338MaRDI QIDQ4599491zbMATH OpenOpenAlexFDO

Authors Johannes Bausch, Stephen Piddock

Publication date 2 January 2018

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

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

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)

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.

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

Cites work

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

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)