Undecidability of the spectral gap in rotationally symmetric Hamiltonians

Abstract

The problem of determining the existence of a spectral gap in a lattice quantum spin system was previously shown to be undecidable for one [J. Bausch et al., "Undecidability of the spectral gap in one dimension", Physical Review X 10 (2020)] or more dimensions [T. S. Cubitt et al., "Undecidability of the spectral gap", Nature 528 (2015)]. In these works, families of nearest-neighbor interactions are constructed whose spectral gap depends on the outcome of a Turing machine Halting problem, therefore making it impossible for an algorithm to predict its existence. While these models are translationally invariant, they are not invariant under the other symmetries of the lattice, a property which is commonly found in physically relevant cases. This poses the question of whether the spectral gap problem could be decidable for Hamiltonians with stronger symmetry constraints. We give a negative answer to this question, in the case of models with 4-body (plaquette) interactions on the square lattice satisfying rotation, but not reflection, symmetry: rotational symmetry is not enough to make the problem decidable.

arXiv comment47 pages, 14 figures, 11 tables

References in corpus (24)

• Entanglement spectrum of a topological phase in one dimension
• Classification of Gapped Symmetric Phases in 1D Spin Systems
• Undecidability of the Spectral Gap (short version)
• The power of quantum systems on a line
• An Introduction to Spontaneous Symmetry Breaking
• Symmetry Breaking and Finite Size Effects in Quantum Many-Body Systems
• Matrix product operators and states: NP-hardness and undecidability
• Quantum measurement occurrence is undecidable
• More Really is Different
• Fundamental limitations in the purifications of tensor networks
• Undecidability of the Spectral Gap in One Dimension
• Size-Driven Quantum Phase Transitions
• Projected Entangled Pair States: Fundamental analytical and numerical limitations
• Memory effects can make the transmission capability of a communication channel uncomputable
• Non-signaling deterministic models for non-local correlations have to be uncomputable
• Uncomputability of Phase Diagrams
• Undecidable problems in quantum field theory
• Undecidability in Tensor Network States
• Measurement-based quantum computation and undecidable logic
• Uncomputability and complexity of quantum control
• Uncomputably Complex Renormalisation Group Flows
• Undecidability in Physics: a Review
• How Real is Incomputability in Physics?
• The membership problem for constant-sized quantum correlations is undecidable