Abstracts
Poster Abstracts | Talk 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.
Read this article online: https://www.scottaaronson.com/papers/dpgentle.pdf
(Session 13 : Tuesday from 3:15pm - 3:45pm)
- Home
- SQuInT
- Registration
- Program
- Instructions for Presenters
- Survey
- Lodging and Transportation
- Hotel Floor Maps (.pdf)
- Faculty Favorites at Old Town
- Past SQuInT Meetings
SQuInT Chief Organizer
Akimasa Miyake, Associate Professor
amiyake@unm.edu
Rafael Alexander, Postdoctoral Fellow
Chris Jackson, Postdoctoral Fellow
SQuInT Administrator
Gloria Cordova
gjcordo1@unm.edu
505 277-1850
SQuInT Assistant
Wendy Jay
SQuInT Founder
Ivan Deutsch, Regents' Professor, CQuIC Director
ideutsch@unm.edu