The discussion revolves around the spectral gap problem in quantum many-body systems and its implications of undecidability, as presented in a recent paper. Participants explore the theoretical and experimental aspects of determining whether a system is gapped or gapless, and the relationship to concepts like the halting problem and Gödel's incompleteness theorem.
Participants express differing views on the implications of undecidability, with some believing it applies universally and others suggesting it may be limited to specific analytical approaches. The discussion remains unresolved regarding the practical implications and existence of real-world examples of undecidable spectral gap problems.
There are limitations in the discussion regarding assumptions about the applicability of undecidability to various methods of analysis and the nature of the systems being studied. The scope of the discussion is also restricted to theoretical considerations without concrete examples of systems exhibiting these properties.
This.ddd123 said:or that we can't compute it for all cases (i.e. we can find out creative solutions for specific cases but not a general solution)?
The specially constructed cases correspond to an infinite set of problems, and they prove that no algorithm can solve all of them.ddd123 said:I mean: what if we actually find the threshold for one of those specially constructed cases in the paper, by a mathematical intuition or by brute force?
Scott Aaronson said:Update (Dec. 20): My colleague Seth Lloyd calls my attention to a PRL paper of his from 1993, which also discusses the construction of physical systems that are gapped if a given Turing machine halts and gapless if it runs forever. So this basic idea has been around for a while. As I explained in the post, the main contribution of the Cubitt et al. paper is just to get undecidability into “the sort of system physicists could plausibly care about” (or for which they could’ve plausibly hoped for an analytic solution): in this case, 2D translationally-invariant nearest-neighbor Hamiltonians with bounded local dimension.
Seth Lloyd said:References [2-3] belong to the medieval era of quantum information theory, pre-Shor and pre-arXiv: the contemporary reader may compare them to illuminated manuscripts. I now redescribe their results in contemporary language.