Abstracts

Gentle measurement of quantum states and differential privacy

Presenting Author: Scott Aaronson, University of Texas, Austin
Contributing Author(s): Guy Rothblum

In differential privacy (DP), we want to query a database about n users, in a way that "leaks at most $${\epsilon}$$ about any individual user," 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}$$," 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. We prove a new and general connection between the two subjects. Specifically, 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 $${\epsilon}$$-DP is also O($${\epsilon}$$$${ \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_1$$ 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\Bigl(\left(log m\right)^2 (log d)^2\Bigr)$$ copies of $${\rho}$$, compared to Aaronson's previous bound of $$Õ\Bigl(\left(log m\right)^4 (log d)\Bigr)$$. Our protocol has the advantages of being online (that is, the $$E_1$$'s are processed one at a time), gentle, and conceptually simple.

(Session 13 : Tuesday from 3:15pm - 3:45pm)

SQuInT Chief Organizer
Akimasa Miyake, Associate Professor
amiyake@unm.edu

SQuInT Local Organizers
Rafael Alexander, Postdoctoral Fellow
Chris Jackson, Postdoctoral Fellow