Taming the Quantum Tiger

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.

Speaker Details

Umesh Vazirani is the Roger A. Strauch Professor of Electrical Engineering and Computer Science at the University of California, Berkeley, and director of the Berkeley Quantum Computation Center. He is one of the founders of the field of quantum computing, starting with his 1993 paper with his student Ethan Bernstein “Quantum complexity theory”. He has also worked on classical algorithms for Online Ad Auctions, as well as graph separators, for which he was awarded (joint with Sanjeev Arora and Satish Rao) the 2012 Fulkerson Prize.

Series:
Microsoft Research Talks
Date:
Speakers:
Umesh Vazirani
Affiliation:
Berkeley

    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks