Contact Info
Department of Applied Mathematics
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 519-888-4567, ext. 32700
Fax: 519-746-4319
PDF files require Adobe Acrobat Reader
QNC 101
Leo Zhou, California Institute of Technology
Quantum Computational Advantages in Energy Minimization
Finding the minimum of 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.
Contact Info
Department of Applied Mathematics
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 519-888-4567, ext. 32700
Fax: 519-746-4319
PDF files require Adobe Acrobat Reader
The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is co-ordinated within the Office of Indigenous Relations.