Quantum Research Institute Seminar | Quantum Advantages in Energy Minimization

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.