Quantum Constraint Satisfaction | Richard M. Karp Distinguished Lecture

The local Hamiltonian problem is the cornerstone for the field of quantum Hamiltonian complexity, much in the same way as Boolean satisfiability (or, more generally, classical constraint satisfaction) was the starting point for our understanding of NP-completeness. In 1993, Kitaev famously defined the local Hamiltonian problem and proved that it is complete for the class QMA, the quantum analog of NP. This talk will survey aspects of NP-completeness and discuss what they mean in the quantum setting, such as search-to-decision, dichotomy theorems, unique solutions, and approximation. The talk will also discuss how we might cope with QMA-hardness in quantum applications.

Sandy Irani graduated with a degree in EECS from Princeton University in 1986. She completed her PhD in computer science at the University of California, Berkeley in 1991 under the supervision of Richard Karp. She has been on the faculty of the Department of Computer Science at UC Irvine since 1992. In the first part of her career, her research focused on online algorithms and their applications to scheduling and resource allocation. More recently, she has been working in quantum computation with a focus on quantum complexity theory. She is also the author of a web-based, interactive textbook replacement on discrete mathematics in collaboration with zyBooks. She is the 2021-2022 recipient of the UC Irvine Distinguished Faculty Award for Teaching and a fellow of the ACM.

The Richard M. Karp Distinguished Lectures were created in Fall 2019 to celebrate the role of Simons Institute Founding Director Dick Karp in establishing the field of theoretical computer science, formulating its central problems, and contributing stunning results in the areas of computational complexity and algorithms. Formerly known as the Simons Institute Open Lectures, the series features visionary leaders in the field of theoretical computer science and is geared toward a broad scientific audience.

Light refreshments will be available prior to the start of the lecture. 

The lecture recording URL will be emailed to registered participants. This URL can be used for immediate access to the livestream and recorded lecture. Lecture recordings will be publicly available on SimonsTV about 12 to 15 days following each presentation unless otherwise noted.

The Simons Institute regularly captures photos and video of activity around the Institute for use in publications and promotional materials. 

If you require special accommodation, please contact our access coordinator at simonsevents [at] berkeley.edu with as much advance notice as possible.