学术活动发布与订制系统

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

Umesh Vazirani is the Strauch Distinguished Professor of Electrical Engineering and Computer Science at University of California, Berkeley, and is the director of the Berkeley Quantum Information and Computation Center. Professor Vazirani has done foundational work on the computational foundations of randomness, algorithms and novel models of computation. His 1993 paper with Ethan Bernstein helped launch the field of quantum complexity theory. In 2007-08, he was appointed Keenan Visiting Professor for distinguished teaching at Princeton University. He is the author of two books An Introduction to Computational Learning Theory with Michael Kearns (MIT Press) and Algorithms with Sanjoy Dasgupta and Christos Papadimitriou (McGraw Hill).