PIRSA:10100053

Spin Glasses and Computational Complexity

Gottesman, D. (2010). Spin Glasses and Computational Complexity. Perimeter Institute. https://pirsa.org/10100053

Gottesman, Daniel. Spin Glasses and Computational Complexity. Perimeter Institute, Oct. 20, 2010, https://pirsa.org/10100053 

          @misc{ pirsa_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},
            year = {2010},
            month = {oct},
            note = {PIRSA:10100053 see, \url{https://pirsa.org}}
          }

Daniel Gottesman

University of Maryland, College Park

Talk number
PIRSA:10100053
Collection
Talk Type
Subject
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.