Spectral Gap or Gapless Undecidable

[mfb]

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)?

This.

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?

The specially constructed cases correspond to an infinite set of problems, and they prove that no algorithm can solve all of them.

 

[Demystifier]

It seems that Seth Loyd had a very similar result a long time ago:
http://lanl.arxiv.org/abs/1602.05924

 

[Strilanc]

That was commented on in an update to the Scott Aaronson post I linked:

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.

Although I have to say I'm enjoying the 2016 paper you linked. I find Seth Lloyd entertaining to watch and read:

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.