Speaker: Umesh Vazirani

Roger A. Strauch Professor, Electrical

Engineering & Computer Science

UC Berkeley

Title: Quantum Hamiltonian Complexity: Through the Computational Lens

Abstract:

Quantum Hamiltonian complexity studies questions at the intersection of condensed matter physics and complexity theory. In this talk I will focus on three basic questions:

1. Do `typical' quantum states that occur in Nature have succinct (polynomial) description?

2. Can quantum systems at room temperature exhibit exponential complexity?

3. Is the scientific method sufficiently powerful to comprehend general quantum systems?

Each of these issues is best studied through the computational lens as a question about computation. The resulting questions lie at the core of computational complexity theory. The first asks about the structure of solutions to the quantum analog of SAT. The second asks whether there is a quantum analog of the PCP theorem. And the third can be formulated as a question about interactive proof systems with BQP provers.

The computational lens is a major theme for the new Simons Institute at Berkeley, and I will briefly describe a special semester-long program on Quantum Hamiltonian Complexity that we are organizing at the Simons Institute in Spring 2014.

Biography:

Prof. Vazirani’s research focuses on algorithms and complexity, the computational foundations of randomness, and novel models of computation. His 1993 paper with Ethan Bernstein helped launch the field of quantum complexity theory. He is the author of two books, “An introduction to computational learning theory” with Michael Kearns, and “Algorithms” with Sanjoy Dasgupta and Christos Papadimitriou. He is a fellow of the ACM and recipient (with Arora and Rao) of the 2012 Fulkerson Prize for his work on graph separators.

*This lecture is open to the public. Space is limited and there is no registration; coming early is strongly recommended.*

Find more information on the department's Distinguished Lecture Series

here or contact the department by

e-mail or at 416-978-3619.