Frustration-freeness is decidable but unprovable
Abstract
The frustration-free property is valuable in quantum many-body systems, which states that its ground states simultaneously minimize all local interaction terms, even when these terms act on overlapping degrees of freedom. Prominent examples include the AKLT model and Kitaev's toric code model, which serve as paradigmatic models of symmetry-protected topological phases and topological order, respectively. A fundamental question is whether a given Hamiltonian is frustration-free for all system sizes. Here we establish two seemingly contradictory results concerning this decision problem. First, we prove that frustration-freeness is decidable for any fixed local Hilbert space dimension. Specifically, there exists a finite, Hamiltonian-independent system-size cutoff such that frustration-freeness at this cutoff size guarantees frustration-freeness at all system sizes. Second, on the other hand, we also show that there exists a frustration-free Hamiltonian whose frustration-freeness cannot be proved within the standard axioms of mathematics (ZFC). We reconcile these seemingly contradictory results by showing that the cutoff, although finite for each local Hilbert space dimension, is uncomputable as a function of that dimension. Our findings reveal an unexpected fundamental distinction between decidability and provability arising in quantum many-body physics.
Related
- Mutation-acyclicity in rank four is decidable but not semialgebraic
- Frustration-Free Models for Topological Holography: Fusion Spin Chains as Boundary Algebras
- Quantized six-vertex realizations of frustration graphs
- Frustration-induced multiferroicity in hauerite MnS2
- Boundary-induced geometrical frustration in a square Rydberg-atom lattice
BibTeX
@misc{shiraishi2026frustrationfreeness,
title = {{Frustration-freeness is decidable but unprovable}},
author = {Naoto Shiraishi},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.07337},
eprint = {2611.07337},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.07337},
}
RIS
TY - UNPB
TI - Frustration-freeness is decidable but unprovable
AU - Naoto Shiraishi
PY - 2026
DA - 2026/11/05
PB - arXiv
DO - 10.48550/arxiv.2611.07337
UR - https://arxiv.org/abs/2611.07337
AB - The frustration-free property is valuable in quantum many-body systems, which states that its ground states simultaneously minimize all local interaction terms, even when these terms act on overlapping degrees of freedom. Prominent examples include the AKLT model and Kitaev's toric code model, which serve as paradigmatic models of symmetry-protected topological phases and topological order, respectively. A fundamental question is whether a given Hamiltonian is frustration-free for all system sizes. Here we establish two seemingly contradictory results concerning this decision problem. First, we prove that frustration-freeness is decidable for any fixed local Hilbert space dimension. Specifically, there exists a finite, Hamiltonian-independent system-size cutoff such that frustration-freeness at this cutoff size guarantees frustration-freeness at all system sizes. Second, on the other hand, we also show that there exists a frustration-free Hamiltonian whose frustration-freeness cannot be proved within the standard axioms of mathematics (ZFC). We reconcile these seemingly contradictory results by showing that the cutoff, although finite for each local Hilbert space dimension, is uncomputable as a function of that dimension. Our findings reveal an unexpected fundamental distinction between decidability and provability arising in quantum many-body physics.
ER -