Quantum NP and Beyond

Saturday, Oct. 17, 2015 2:30 pm2:55 pm

Add to Calendar


The theory of NP-completeness has been the basis for our understanding of important phenomena in the quantum world. The development of the class QMA (the quantum analog of NP) has shed light on the limits of quantum computers as well as the complexity of fundamental problems in condensed matter physics. The connection between these areas arises from the close relationship between the complexity of constraint satisfaction problems and the properties of ground states of local Hamiltonians describing quantum systems. This talk will be a brief survey of how QMA has helped inform our understanding of quantum computation and entanglement as well as some of the questions at the forefront of quantum Hamiltonian complexity.