The discussion centers on the undecidability of the spectral gap problem in quantum many-body Hamiltonians, as established in a paper published in Nature. This problem is analogous to the Halting Problem, demonstrating that there is no universal algorithm capable of determining whether a given Hamiltonian has a spectral gap. Participants debate the implications of this undecidability, emphasizing that while experimental determination may be possible, theoretical analysis remains limited. The conversation also touches on the potential for creative mathematicians to devise case-specific solutions, despite the overarching undecidability.
PREREQUISITESPhysicists, mathematicians, and computer scientists interested in the intersections of quantum mechanics, undecidability, and computational theory will benefit from this discussion.
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.