Fall 2015: Theory Seminar
ICS, Room 209, 1:00pm
October 16, 2015:

Quantum NP and Beyond

Sandy Irani

Abstract: 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.