[quantum-info] Tomorrow: Special Wednesday lunch seminar at IQC: Toby Cubitt "Frustratingly undecidable (or undecidably frustrating)"

William Matthews will at northala.net
Tue Aug 2 21:03:04 EDT 2011


Toby Cubitt will be giving a talk on Wednesday August 3rd, 2011 at 12:30pm.  The talk will be in the IQC Seminar Room, RAC1 2009

Title: "Frustratingly undecidable (or undecidably frustrating)"

Abstract:
"Frustration" in many-body systems occurs when the ground state cannot simultaneously minimize the energy of all its local interactions. It plays a key role in the physics of many condensed matter systems, such as spin models, or even water ice. Indeed, it was first studied by Pauling, who showed that the anomalous value for the zero-temperature entropy of ice, obtained by extrapolating from experimental calorimeter data, is caused by frustration in the position of the hydrogen atom in the crystal lattice. 

Since it can play an important role in determining physical properties, it would be highly desirable to know which many-body systems are frustrated, and which are frustration-free. More precisely, given a Hamiltonian describing the local interactions in a many-body system, we would like to determine whether its ground state is frustrated or not.

It turns out that this question is impossible to answer. We show that even for the very simple case of a translationally-invariant, 1-dimensional spin chain with two-body interactions and fixed, finite dimensional spins, determining whether the ground state is frustrated is not just difficult to determine, it is undecidable (in the halting problem sense).

(Joint work with Michael Wolf and David Perez-Garcia)

_______________________________________________

_______________________________________________


More information about the quantum-info mailing list