## 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

**SQuInT Local Organizers**

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

**Tweet About SQuInT 2019!**