Quantum computation has taught us that a quantum system is best visualized as a wild tiger rather than a tame Schrodinger’s cat. Indeed the exponential power of quantum systems, which makes quantum computers possible, is also an enormous obstacle to analyzing and understanding physical systems. Is there a way to tame the quantum tiger and neutralize this curse of exponentially? In this talk I will address this question in two settings:
- Are there general classes of quantum systems whose states can be efficiently (polynomially) computed on a traditional classical computer?
- Is it possible for a classical experimentalist to test that an untrusted quantum system behaves as commanded? For example, is it possible to test that a claimed quantum computer is really quantum?
The talk will discuss recent breakthroughs in both settings, as well as many exciting open questions. I will make every attempt to keep the discussion widely accessible.
Based on joint results with Zeph Landau and Thomas Vidick, and with Ben Reichardt and Falk Unger.