Taming the Quantum Tiger

Опубликовано 27 июля 2016, 19:31

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: 1. Are there general classes of quantum systems whose states can be efficiently (polynomially) computed on a traditional classical computer? 2. 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.