Should Complexity Theorists Learn Quantum Computation?



Umesh Vazirani
UC Berkeley

Wednesday, October 31, 2012
2:30pm 165 Olin Hall



Quantum computation is entering an exciting new phase where quantum thinking is becoming increasingly relevant to complexity theory. On the  one hand, powerful quantum techniques have played an important role in 
recent advances in questions about lattice cryptosystems, lower  bounds for linear programs and the Lasserre hierarchy of semidefinite programs. On the other, much as probabilistic thinking did starting in the early 80s, 
quantum computing is expanding the core questions of complexity theory in fundamental new directions. For example, here is a list of three basic questions about quantum mechanics that are at their heart questions about computational  complexity:

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 tackle 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. I will briefly 
outline these connections and the state of the art on these questions. 

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