PIRSA:10100053

Spin Glasses and Computational Complexity

APA

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

MLA

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

BibTex

          @misc{ pirsa_10100053,
            doi = {},
            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}}
          }
          

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.