Quantum Hamiltonian Complexity

  • Umesh Vazirani | Berkeley

We consider three basic questions about quantum mechanics:

  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 questions is best studied through a computational lens as a question
about computation. The resulting questions lie at the core of 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.

In this talk I will describe recent progress on these issues.

Speaker Details

Umesh Vazirani received his B.Tech. in computer science from MIT in 1981 and his Ph.D. in computer science from U.C. Berkeley in 1986. He is currently professor of computer science at U.C. Berkeley and director of BQIC -the Berkeley center for Quantum Information and Computation. Prof. Vazirani is a theoretician with broad interests in novel models of computation. He has done seminal work in quantum computation and on the computational foundations of randomness. He is the author of two books “An introduction to computational learning theory” with Michael Kearns and “Algorithms” with Sanjoy Dasgupta and Christos Papadimitriou.

Watch Next