2019/04/18 by Scott Aaronson, Aaronson, Scott, Guy N. Rothblum +1 · 7 citations
Computer Science · Mathematics · #Cryptography and Data Security #FOS: Physical sciences #Privacy-Preserving Technologies in Data #Quantum Physics (quant-ph) #Random Matrices and Applications
paper · pdf · doi:10.48550/arxiv.1904.08747
openalex publication_date 2019/04/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 E1,...,Em, shadow tomography asks us to estimate Pr[Ei 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 Ei'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.