Scott Aaronson: Gentle Measurement of Quantum States and Differential Privacy

We prove a surprising 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 gentlemeasurement.  By exploiting
this connection, together with the Private Multiplicative Weights
algorithm of Hardt and Rothblum, we're able to give a new protocol for
so-called "shadow tomography" of quantum states, which improves over
the parameters of a previous protocol for that task due to Aaronson,
and which has the additional advantage of being "online" (that is, the
measurements are processed one at a time).

Joint work with Guy Rothblum (Weizmann Institute); paper still in preparation.