Undecidable physics problems

[leblon]

A few days ago a certain paper published in Nature made quite a splash in physics and math circles. There are two arXiv versions: a short summary and a full version. The paper claims to prove that the problem of deciding whether a family of many-body Hamiltonians has an energy gap in the thermodynamic limit is algorithmically undecidable. More specifically, the authors construct an infinite sequence of translationally-invariant quantum spin systems on a square lattice, with nearest-neighbor interactions and fixed spin size, such that there is no algorithm for deciding for each system whether it is gapped or gapless in the thermodynamic limit.

This implies, by the way, that certain yes/no questions about physical systems may be unanswerable. That is, one cannot determine within any reasonable axiomatization of math whether the answer is yes or no. For example, the above result shows that there exists an infinite sequence of spin Hamiltonians for which it is literally impossible to prove whether they do or do not have an energy gap in the thermodynamic limit.

I do not know whether the proof in this paper is actually correct. But the more I think about the result, the less surprising it seems. Indeed, there is a famous undecidable problem in combinatorics (the Wang tiling problem) which can be reformulated as a problem in classical statistical mechanics (each Wang tiling of a plane can be regarded as a ground state of some classical spin system). Thus there is an infinite sequence of classical statistical mechanics problems (with an unbounded number of local spin states) which is algorithmically undecidable. The only slight surprise is that in the quantum setting one can get an undecidable sequence of problems by keeping the number of local degrees of freedom fixed and changing the Hamiltonians instead.

By the way, the first author's last name (Cubitt) is perfect for a quantum physicist.

Comments

tilings

[a-shen.livejournal.com]

For tiling the trick is that this is "undecidability in the limit": in the standard example of undecidability you need about N computational steps to find whether N*N-tiling exists, so it is quite unimpressive even if for unbounded N we get an algorithmicall unsolvable problem (this unsolvability is closely related to Godel-type undecidability, the reason why they happen is the same). In a different construction you can show that the existence of N*N-tiling is an NP-complete problem.

So the question whether this result is "serious" depends on what happens with this "limit" - how large should the system be to approach it...

Re: tilings

[leblon.livejournal.com]

I don't think in the paper there are any estimates of complexity of evaluating the gap for an N x N system.

Re: tilings

[a-shen.livejournal.com]

but if they prove undecidability by some reduction for some computation, it is typically clear from the construction how much computation you can embed in a given size system...

Re: tilings

[leblon.livejournal.com]

Ah, I see. I think this is explained in the short version on pp. 4-5.

[juan-gandhi.livejournal.com]

I wonder if it ever gets blended with the quantum nondeterminism.

OTOH, it would be cool to eventually get this kind of argument into comp sci, where people use to believe that everything they think they can build they can build (and that all monads are strong, stuff like that).

[leblon.livejournal.com]

Well, the negative answer to Hilbert's tenth problem taught mathematicians that solving math problems is not a mechanical process, even in principle. Now physicists are learning the same lesson (until now, many still say that "in principle everything is contained in the Lagrangian of the Standard Model"). But I would assume computer scientists already know this stuff. After all, Turing was the first computer scientist.

[plinioseviltwin.livejournal.com]

"This implies that certain yes/no questions about physical systems may be unanswerable"

I don't see why. For example, in the Wang problem the question about any particular set of tiles is pretty answerable, the answer is either yes or no and does not depend on any choice of axiomatization. The Berger's result only says that there is no *universal* procedure that gives a yes/no answer for an *arbitrary* set of tiles.

[leblon.livejournal.com]

At first I was puzzled by this conclusion too. But apparently this is a standard result connecting algorithmic undecidability and unanswerability (=logical independence from axioms). See http://arxiv.org/abs/1204.0299 , the paragraph after Remark 2.3. This is a very nice review paper, by the way.

[plinioseviltwin.livejournal.com]

Now I see, thanks.

Still, if I understand Cubitt's et al. paper correctly, a statement about a mass gap of a lattice model is essentially a statement about natural numbers (that is, not a statement about some weird stuff like arbitrary sets in the continuum hypothesis). Such statements can be independent from the given system of axioms, but this doesn't mean that they are unanswerable: they still can be proved or disproved in a larger system of axioms, and those larger systems can be completely reasonable. See Goodstein's theorem for example.

A nice review indeed! So we can now extend it by yet another example of an undecidable problem, this time coming from physics.

[leblon.livejournal.com]

Thanks for mentioning Goodstein's theorem; I vaguely remember hearing about it, but I did not realize the implications. Indeed, this undecidable problem from physics does not seem to involve any weird stuff like the continuum hypothesis. But doesn't the argument in Poonen's review show that the energy gap question will be unanswerable in any extension of the Peano arithmetic?

[plinioseviltwin.livejournal.com]

The argument shows that for any extension of the Peano arithmetic there exist an energy gap statement that is independent from this extension. But it doesn't imply that there is energy gap statement independent from any extension.

[leblon.livejournal.com]

OK, right.