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 faster 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 minimizing 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. These results highlight exciting new directions in leveraging physics-inspired algorithms to achieve quantum advantages in broadly useful problems.

Leo Zhou is a DuBridge Postdoctoral Scholar at Caltech, hosted by John Preskill. He completed his PhD in Physics in 2021 from Harvard University under the guidance of Mikhail Lukin, after receiving his BSc in Physics and Mathematics in 2014 from MIT where he worked with Edward Farhi. His research interests are at the interface of computer science and physics, touching on many topics in quantum information theory, mathematical optimization, computational complexity, and many-body physics. He has made foundational contributions in quantum complexity theory and established key results on quantum optimization algorithms. He has also worked with experimentalists to realize quantum applications in physical systems such as Rydberg atoms and superconducting qubits.