Uncomputability of Phase Diagrams

Abstract

The phase diagram of a material is of central importance to describe the properties and behaviour of a condensed matter system. We prove that the general task of determining the quantum phase diagram of a many-body Hamiltonian is uncomputable, by explicitly constructing a one-parameter family of Hamiltonians for which this is the case. This work builds off recent results from Cubitt et al. and Bausch et al., proving undecidability of the spectral gap problem. However, in all previous constructions, the Hamiltonian was necessarily a discontinuous function of its parameters, making it difficult to derive rigorous implications for phase diagrams or related condensed matter questions. Our main technical contribution is to prove undecidability of the spectral gap for a continuous, single-parameter family of translationally invariant, nearest-neighbour spin-lattice Hamiltonians on a 2D square lattice: $H(\phi )$ where $\phi \in \mathbb{R}$. As well as implying uncomputablity of phase diagrams, our result also proves that undecidability can hold for a set of positive measure of a Hamiltonian's parameter space, whereas previous results only implied undecidability on a zero measure set.

arXiv comment63 pages, 6 figures

References in corpus (11)

• Undecidability of the Spectral Gap (short version)
• Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory
• Magnetic Proximity Effect as a Pathway to Spintronic Applications of Topological Insulators
• The spectral gap for some spin chains with discrete symmetry breaking
• Universal Quantum Hamiltonians
• Hofstadter butterfly as Quantum phase diagram
• DCA${}^{+}$: Dynamical Cluster Approximation with continuous lattice self-energy
• Size-Driven Quantum Phase Transitions
• The Complexity of Translationally-Invariant Spin Chains with Low Local Dimension
• Analysis and limitations of modified circuit-to-Hamiltonian constructions
• The Complexity of Translationally-Invariant Low-Dimensional Spin Lattices in 3D

Cited by in corpus (9)

• Undecidable problems in quantum field theory
• Certified algorithms for equilibrium states of local quantum Hamiltonians
• Glassy word problems: ultraslow relaxation, Hilbert space jamming, and computational complexity
• Undecidability of the Spectral Gap (full version)
• Uncomputably Complex Renormalisation Group Flows
• Undecidability in Physics: a Review
• Can quantum gravity be both consistent and complete?
• Chemically Motivated Simulation Problems are Efficiently Solvable by a Quantum Computer
• Undecidability of the spectral gap in rotationally symmetric Hamiltonians