<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto"><span style="background-color: rgba(255, 255, 255, 0);">%%%%%%%%%%% NOTE A NON-STANDARD DAY %%%%%%%%%%<br><br>Departments of Mathematics & Computer Science<br>Combinatorics & Theory Seminar<br><br><a href="x-apple-data-detectors://0" dir="ltr" x-apple-data-detectors="true" x-apple-data-detectors-type="calendar-event" x-apple-data-detectors-result="0" style="-webkit-text-decoration-color: rgba(0, 0, 0, 0.258824);">Thursday, February 28</a><br>Ry 251@ <a href="x-apple-data-detectors://1" dir="ltr" x-apple-data-detectors="true" x-apple-data-detectors-type="calendar-event" x-apple-data-detectors-result="1" style="-webkit-text-decoration-color: rgba(0, 0, 0, 0.258824);">3:30pm</a><br><br>Scott Aaronson<br>University of Texas at Austin<br><br>Title: Gentle Measurement of Quantum States and Differential Privacy<br><br>Abstract: In differential privacy (DP), we want to query a database about n<br>users, in a way that "leaks at most eps about any individual user,"<br>conditioned on any outcome of the query. Meanwhile, in gentle<br>measurement, we want to measure n quantum states, in a way that<br>"damages the states by at most alpha," conditioned on any outcome of<br>the measurement. In both cases, we can achieve the goal by techniques<br>like deliberately adding noise to the outcome before returning it. We<br>prove a new and general connection between the two subjects.<br>Specifically, on products of n quantum states, any measurement that is<br>alpha-gentle for small alpha is also O(alpha)-DP, and any product<br>measurement that is eps-DP is also O(eps*sqrt(n)) -gentle.<br><br>Illustrating the power of this connection, we apply it to the recently<br>studied problem of shadow tomography. Given an unknown d-dimensional<br>quantum state rho, as well as known two-outcome measurements<br>E_1,...,E_m, shadow tomography asks us to estimate Pr[E_i accepts<br>rho], for every i in [m], by measuring few copies of rho. Using our<br>connection theorem, together with a quantum analog of the so-called<br>private multiplicative weights algorithm of Hardt and Rothblum, we<br>give a protocol to solve this problem using O((log m)^2 (log d)^2)<br>copies of rho, compared to Aaronson's previous bound of ~O((log m)^4<br>(log d)). Our protocol has the advantages of being online (that is,<br>the E_i's are processed one at a time), gentle, and conceptually<br>simple.<br><br>Joint work with Guy Rothblum (to appear in STOC'2019).<br><br>(Refreshments will be served prior to the talk in Ry. 255 <a href="x-apple-data-detectors://3" dir="ltr" x-apple-data-detectors="true" x-apple-data-detectors-type="calendar-event" x-apple-data-detectors-result="3" style="-webkit-text-decoration-color: rgba(0, 0, 0, 0.258824);">@ 3:15pm</a>)</span><div dir="ltr"></div></body></html>