  In differential privacy (DP), we want to query a database about n users, in a
way that "leaks at most eps about any individual user," even conditioned on any
outcome of the query. Meanwhile, in gentle measurement, we want to measure n
quantum states, in a way that "damages the states by at most alpha," even
conditioned on any outcome of the measurement. In both cases, we can achieve
the goal by techniques like deliberately adding noise to the outcome before
returning it. This paper proves a new and general connection between the two
subjects. Specifically, we show that on products of n quantum states, any
measurement that is alpha-gentle for small alpha is also O(alpha)-DP, and any
product measurement that is eps-DP is also O(eps*sqrt(n))-gentle. Illustrating
the power of this connection, we apply it to the recently studied problem of
shadow tomography. Given an unknown d-dimensional quantum state rho, as well as
known two-outcome measurements E_1,...,E_m, shadow tomography asks us to
estimate Pr[E_i accepts rho], for every i in [m], by measuring few copies of
rho. Using our connection theorem, together with a quantum analog of the
so-called private multiplicative weights algorithm of Hardt and Rothblum, we
give a protocol to solve this problem using O((log m)^2 (log d)^2) copies of
rho, compared to Aaronson's previous bound of ~O((log m)^4 (log d)). Our
protocol has the advantages of being online (that is, the E_i's are processed
one at a time), gentle, and conceptually simple. Other applications of our
connection include new lower bounds for shadow tomography from lower bounds on
DP, and a result on the safe use of estimation algorithms as subroutines inside
larger quantum algorithms.
