Physics Colloquium

Statistical mechanics of classical and quantum computation

Statistical physics provides powerful tools to evaluate physical properties of large, disordered systems. In this talk, I will discuss how these insights can also describe computational properties. In classical computation, I will show how depth affects feature learning in neural networks. These results develop a new diagrammatic method for computing partition functions that describe neural networks trained by Langevin dynamics or Bayesian inference. In quantum computation, I will describe a theory of average-case quantum complexity that addresses how useful quantum computers are for unstructured problems (e.g., unlike factoring) based on spin glass theory. This leads to results previously inaccessible to traditional techniques from computer science, including 1) efficient classical algorithms for quantum systems (including SYK) previously thought to admit quantum advantage, 2) evidence of average-case quantum hardness where complexity theoretic conjectures only predict worst-case (QMA) hardness, and 3) new perspectives on where quantum advantage exists, accompanied by progress in quantum algorithms.

Join via Zoom: https://caltech.zoom.us/j/84497014003

Meeting ID: 844 9701 4003