The Taub Faculty of Computer Science Events and Talks

We prove a new connection between gentle measurement (where one wants to measure n quantum states, in a way that damages the states only by a little) and differential privacy (where one wants to query a database about n users, in a way that reveals only a little about any individual user). The connection is bidirectional, though with loss of parameters in going from DP to gentle measurement. Exploiting this connection, we present a new algorithm for approximating the outcomes of many measurements on a collection of quantum states, a task called "shadow tomography". The new algorithm has the advantages of being online (the measurements can be chosen adaptively) and gentle.

This talk is intended for a general theory audience. No background on quantum mechanics or quantum computing will be assumed

Joint work with Scott Aaronson (UT Austin).