We consider three basic questions about quantum mechanics:
Each of these questions is best studied through a computational lens as a questionabout 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 askswhether 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.