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.
Metadata: arXiv. Abstracts retain their original authors’ rights.
In the conversation
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
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 each integer n, the authors construct a spin lattice model H(n).
2. There is a specific Universal Turing Machine, that halts on n iff H(n) is gapped.
Here is how to construct the oracle. For any Turing machine, find out what integer n it corresponds to for the specific Universal Turing Machine of the paper. Then physically construct H(n) and see if it's gapped.
However, this H(n) cannot be…
Read the full comment
physically realized. First, it is an idealized model in which lattice points only interact with their neighbors. Second, it actually a family of lattices, and the result is about the thermodynamic limit as the lattice becomes infinite.
Interestingly, Seth Lloyd appears to have previously proved this result in 1993. https://arxiv.org/pdf/1602.05924
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 you know, changing paradigms is a slow process and physicists have been shown to be the slowest to accept new things, especially multidisciplinary theories/findings:
http://www.pnas.org/content/112/24/7426.full
Which confirms my contact experience with many of them - not all of course :)
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 able to build machines that can compute more; however I don't think they are talking about such physics here.
But, they do quote: Marian B. Pour-El and Jonathan I. Richards. Computability in Analysis
and Physics. Springer, 1989.
M. B. Pour-El and J. Richards have earlier results:
http://www.sciencedirect.com/science/article/pii/00018708819...: The wave equation with computable initial data such…
Read the full comment
that its unique solution is not computable (1981)
http://philpapers.org/rec/POUTWE: The wave equation with computable initial data whose unique solution is nowhere computable (1997)
The Spectral Gap authors seem to call these results "easier" (page 8 at http://arxiv.org/pdf/1502.04573v2.pdf)
In honor of Alan Turing's hundredth birthday, I unwisely set out some thoughts about one of Turing's obsessions throughout his life, the question of physics and free will.