We show that the spectral gap problem is undecidable. Specifically, we construct families of translationally-invariant, nearest-neighbour Hamiltonians on a 2D square lattice of d-level quantum systems (d constant), for which determining whether the system is gapped or gapless is an undecidable problem. This is true even with the promise that each Hamiltonian is either gapped or gapless in the strongest sense: it is promised to either have continuous spectrum above the ground state in the thermodynamic limit, or its spectral gap is lower-bounded by a constant in the thermodynamic limit. Moreover, this constant can be taken equal to the local interaction strength of the Hamiltonian.
arXiv comments
v1: 146 pages, 56 theorems etc, 15 figs. See shorter companion paper arXiv:1502.04135 for version omitting technical details. v2: Small fix to abstract wording. v3: Simplified and shortened parts of proof. 127p, 55 thms, 10 figs. v4: Minor intro edits. v5: Published version. Adds explanatory pseudo-code for all Turing Machines, and other presentational improvements. 150 pages, 55 thms, 13 figs
Linked by 6 identifiable commenters in 6 comments across 4 threads, from Dec 2015 to Mar 2025. Found in 1 HN submission from Dec 2015 to Dec 2015. Open submission discussions.
Here is a free updated version from 2022. https://arxiv.org/pdf/1502.04573 Edit: Alright, I'm back after skimming the paper. This is a halting oracle. Here is what I understand, with my limited knowledge of QM. There are two ingredients (Theorem 3: Main Theorem, page 6). 1. For…
So the most physically grounded example I know of is the undecidability of some spectral gaps[0] (is there a discrete jump between the ground state and the excited states), which as far as I can tell doesn't rely on self-reference. [0]: https://arxiv.org/pdf/1502.04573.pdf
Like many stuff in theoretical physics - hey, most of the physical model is rather unlikely. They not even have a proper arrow of time in the standard model nor can they predict the spectral gap with certainty along a long list of problems. https://arxiv.org/abs/1502.04573 But…
I can't tell how much of this is "quantum physics" and how much is "mathematical theory that also arises in quantum physics". As in, I doubt their construction allows "building something" which then allows solving a conventionally unsolvable problem. With new physics you may be…
Here is a free updated version from 2022. https://arxiv.org/pdf/1502.04573 Edit: Alright, I'm back after skimming the paper. This is a halting oracle. Here is what I understand, with my limited knowledge of QM. There are two ingredients (Theorem 3: Main Theorem, page 6). 1. For…
markisusView on HNParent context