Leo Zhou, DuBridge Postdoctoral Scholar at Caltech, will be presenting "Quantum Advantages in Energy Minimization" as part of the Quantum Research Institute's winter seminar series from 2:00 - 3:00 pm in West Hall, Room 340 (3rd floor). A Zoom option is also provided.

Seminar Description:
Minimizing the energy of a many-body system is a fundamental problem in many fields. Although we hope a quantum computer can help us solve this problem better than classical computers, we have a very limited understanding of where a quantum advantage may be found. In this talk, I will present some recent theoretical advances that shed light on quantum advantages in this domain. First, I describe rigorous analyses of the Quantum Approximate Optimization Algorithm applied to minimize energies of classical spin glasses. For certain families of spin glasses, we find the QAOA has a quantum advantage over the best known classical algorithms. Second, we study the problem of finding a local minimum of the energy of quantum systems. While local minima are much easier to find than ground states, we show that finding a local minimum under thermal perturbations is computationally hard for classical computers, but easy for quantum computers.