Presenter: Scott Aaronson, Computer Science, University of Texas Austin
Host: Leo Radzihovsky
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 survey a career's-worth results showing that, for many purposes, quantum states can effectively be described with vastly less classical information. 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 this 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.
