News for hackers. Stuff that matters.
Re:A first for physics: Fundamental quantum physics problem ... by misja111 on Thursday December 10, 2015 @03:14AM (#10709513)
But spectral gaps do occur in nature. Does that mean that even though it is impossible to compute if a spectral gap will occur or not, we could just observe such a system in nature and that way we could build a computer which would compute uncomputable results?
Re:A first for physics: Fundamental quantum physics problem ... by sharpneli on Thursday December 10, 2015 @04:01AM (#10709668)
In nature it does not matter if the spectral gap is really tiny. It's de facto without spectral gap if it's just small enough.

Whereas for this particular decision problem the mere existence of spectral gap matters.

Re:A first for physics: Fundamental quantum physics problem ... by selimthegrim on Thursday December 10, 2015 @09:18AM (#10710682)
Who says? Graphene gaps, (it must gap) even though its so small it's impossible to observe in practice. This had very important consequences for topological materials theory...
Re:A first for physics: Fundamental quantum physics problem ... by sharpneli on Thursday December 10, 2015 @09:54AM (#10710836)
This is exactly what I meant.

Even if it has theoretical reasons to have a tiny gap in practice it works as zero gap.

Re:A first for physics: Fundamental quantum physics problem ... by tobycubitt on Friday December 18, 2015 @02:29PM (#10760409)
Except that in our result, the spectrum is either continuous, or the spectral gap is guaranteed to be >= 1 (in natural units). It does not become arbitrarily small in the gapped case.

The reason you can't use this to compute the uncomputable is that real systems are finite, and the spectral gap is always computable in principle (maybe with a lot of effort) for any finite system. A real (possibly very large but still finite) system will either have a gap or not, and you'll be able to measure it. This definitely doesn't solve an undecidable problem.

However, the undecidability in the idealised infinite lattice limit "shows through" to the experimentally accessible finite-size case, in the form of some rather unusual finite-size physics. This is discussed in more detail in the paper itself (the relevant section is quoted verbatim here http://mathoverflow.net/a/225905) and in the comments on Scott Aaronson's blog.

Re:A first for physics: Fundamental quantum physics problem ... by lmm on Thursday December 10, 2015 @12:43PM (#10711992)
Sounds like it doesn't it? Could we build a big sheet of this material that encoded e.g. a search for a counterexample to the Riemann Hypothesis, and then just measure whether it had a gap or not? I can't believe that it would be that simple, but I can't immediately see anything wrong with that logic.
Re:A first for physics: Fundamental quantum physics problem ... by mathgenius on Thursday December 10, 2015 @03:20AM (#10709535)
I think not, since these systems are "infinite", ie. you would never know how big to build it before you got close enough to the correct result.