Spin Glasses and Computational Complexity - Daniel Gottesman

A spin glass is a type of spin system with a complicated space of configurations, so that getting from one local minimum to another requires changing the state of very many spins. A spin glass can get caught for very long times at a local minimum of energy, rather than reaching its true ground state. Finding the ground state energy of a spin glass is often a computationally hard problem, complete for the complexity class QMA, a quantum analogue of NP. I will discuss which types of interactions are known to give us computationally hard problems and spin glasses.