Quantum Computing and the Laws of Physics

I'll survey what's known about the power of highly-entangled quantum states as resources to accelerate computation.  I'll describe some striking examples, due to John Watrous, where quantum states seem useful as exponentially-compact "witnesses" to the truth of a mathematical statement, or "advice" for solving a problem.  On the other hand, I'll also show that the power of such quantum advice is limited: it can always be simulated by classical advice together with exponentially greater computation time.  Finally, I'll explain how, if we only care about the behavior of an entangled quantum state on "simple" measurements, or "most" measurements from some probability distribution, then it's often possible to describe the state using exponentially fewer classical bits, and to "learn" the state using exponentially fewer measurements, than is needed in traditional quantum state tomography.  Indeed, Andrew Drucker and I recently showed that, for many practical purposes, any entangled state (no matter how hard to describe) can be "simulated" by the ground state of some easy-to-describe Hamiltonian.