RQC Colloquium

12th RQC Colloquium

• Speaker

  Prof. Scott Aaronson
  (University of Texas at Austin)

• Date

  9:00-10:00 (JST), May. 17, 2023 (Wednesday)

• Venue

  Online

• Title

  How Much Information Is In A Quantum State?

• Inquiries

  rqc_colloquium_inquiry[at]ml.riken.jp

Abstract
To describe an entangled state of n particles, we formally need an amount of classical information that grows exponentially with n. But given that almost all the information disappears on measurement, in what sense was it “really there”? In this talk, I’ll first review a career’s-worth results showing that, for many purposes, quantum states can effectively be described with vastly less classical information including my 2004 simulation of quantum advice by classical advice for decision problems, my 2007 “Quantum Occam’s Razor Theorem,” and my 2016 proposal of “shadow tomography” of quantum states (enhanced by my and Rothblum’s 2019 connection to differential privacy). In the other direction, however, I’ll discuss the exponential separation between quantum and randomized communication complexities due to Bar-Yossef, Jayram, and Kerenidis, as well as brand-new work by me, Buhrman, and Kretschmer, which builds on their separation to show that “FBQP/qpoly != FBQP/poly” (unconditionally, there exist relational problems solvable using quantum advice but not classical advice). I’ll end by explaining how that theorem directly suggests a new type of quantum supremacy experiment – one that, in contrast to the recent supremacy experiments by Google, USTC, and Xanadu, would not depend on any unproved computational hardness assumptions, but would seek a direct “experimental witness for the vastness of n-particle Hilbert space.”
I believe this type of experiment is just now becoming technologically feasible.

Speaker Bio:
Scott Aaronson is Schlumberger Chair of Computer Science at the University of Texas at Austin, and founding director of its Quantum Information Center. He received his bachelor's from Cornell University and his PhD from UC Berkeley. Before coming to UT Austin, he spent nine years as a professor in Electrical Engineering and Computer Science at MIT. Aaronson's research in theoretical computer science has focused mainly on the capabilities and limits of quantum computers. His first book, Quantum Computing Since Democritus, was published in 2013 by Cambridge University Press. He received the National Science Foundation's Alan T. Waterman Award, the United States PECASE Award, the Tomassoni-Chisesi Prize in Physics, and the ACM Prize in Computing, and is a Fellow of the ACM and the AAAS.

Flyer: 12th RQC Colloquium Flyer