![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Undecidable physics problems
Dec. 11th, 2015 12:29 pmA 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.
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.
