Dr. Umesh Vazirani, University of California, Berkeley
Abstract
The exponential complexity of quantum systems is a double edged sword: while making quantum computers possible it is also an enormous obstacle to analyzing and understanding physical systems. Is there any way around this curse of exponentiality?
Here are three basic questions that explore this issue:
- Do 'typical' quantum states that occur in Nature have succinct (polynomial) description?
- Can quantum systems at room temperature exhibit exponential complexity?
- 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 quantum polynomial time provers.
This is a very active area, with a number of recent breakthroughs and many exciting open questions. In this talk I will try to summarize the state of the art, while keeping the talk widely accessible.