Spin Glasses and Computational Complexity

          @misc{ scivideos_PIRSA:10100053,
            doi = {10.48660/10100053},
            url = {https://pirsa.org/10100053},
            author = {Gottesman, Daniel},
            keywords = {Quantum Information},
            language = {en},
            title = {Spin Glasses and Computational Complexity},
            publisher = {Perimeter Institute for Theoretical Physics},
            year = {2010},
            month = {oct},
            note = {PIRSA:10100053 see, \url{https://scivideos.org/pirsa/10100053}}
          }
          

Abstract

A system of spins with complicated interactions between them can have many possible configurations. Many configurations will be local minima of the energy, and to get from one local minimum to another requires changing the state of very many spins. A system like this is called a spin glass, and at low temperatures tends to get caught for very long times at a local minimum of energy, rather than reaching its true ground state. Indeed, in many cases, finding the ground state energy of a spin glass is a computationally hard problem, too hard to be solved on a classical computer or even a quantum computer in any reasonable amount of time. Which types of interactions give us computationally hard problems and spin glasses? I will survey what is known as we close in on finding the simplest complex spin systems.