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 very limited understanding of where a quantum advantage may be found. In this talk, I will discuss some recent theoretical results that significantly advance our understanding. First, I describe some rigorous analyses of the Quantum Approximate Optimization Algorithm applied to minimize energy 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 a quantum system. 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.
Copyright. All Rights Reserved.