Speaker Umesh Vazirani
Host Madhu Sudan
Date recorded 13 June 2012
We consider three basic questions about quantum mechanics:
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.
©2012 Microsoft Corporation. All rights reserved.