| Abstract: | Given an unknown D-dimensional quantum state rho, as well as M two-outcome measurements E_1,...,E_M, how many copies of rho do we need, if we want to learn the approximate probability that E_i accepts rho for *every* i? In this talk, I'll show you the surprising result -- I didn't believe it myself at first -- that one can achieve this using a number of copies that's polylogarithmic in both M and D. So for example, one can learn whether *every* size-n^3 quantum circuit accepts or rejects an n-qubit state, given only n^O(1) copies of the state. To explain this will require first surveying previous results on measuring quantum states in "gentle" ways and succinctly describing them, including my 2004 postselected learning theorem, and my 2006 "Quantum OR Bound" (with an erroneous proof fixed in 2016 by Harrow, Lin, and Montanaro). |
