<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div dir="auto" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div class=""><p class="MsoNormal"><!--[endif]--><o:p class=""></o:p></p><p class="MsoNormal"><o:p class=""> </o:p></p><p class="MsoNormal">
<b class=""><span style="font-size:
14.0pt;font-family:"Times New Roman",serif;color:#C00000" class="">Scott Aaronson</span></b></p><p class="MsoNormal"><span style="font-family: "Times New Roman", serif; font-size: 14pt; text-align: center;" class=""><span class="Apple-tab-span" style="white-space:pre"> </span> </span><span style="font-family: "Times New Roman", serif; font-size: 14pt; text-align: center;" class="">University of Texas, Austin</span></p><p class="MsoNormal" style="text-align:justify"><span style="font-size:16.0pt;
font-family:"Times New Roman",serif;mso-fareast-font-family:"Times New Roman";
mso-fareast-theme-font:minor-fareast" class=""> </span><span style="font-family: "Times New Roman", serif;" class="">Title: “Gentle Measurement of Quantum State
& Differential Privacy”<o:p class=""></o:p></span></p><div class=""><span style="mso-bidi-font-size:12.0pt;font-family:"Times New Roman",serif;
mso-bidi-font-weight:bold" class=""> </span><br class="webkit-block-placeholder"></div><p class="MsoNormal" style="margin-left:49.5pt;text-align:justify"><span style="mso-bidi-font-size:12.0pt;font-family:"Times New Roman",serif;
mso-bidi-font-weight:bold" class="">Abstract:</span><span style="mso-bidi-font-size:
12.0pt;font-family:"Times New Roman",serif;color:#212121;background:white" class=""> </span><span style="font-family: "Times New Roman", serif;" class="">In differential privacy (DP), we want to query a database about n<br class="">
users, in a way that "leaks at most eps about any individual user,"<br class="">
conditioned on any outcome of the query. Meanwhile, in gentle<br class="">
measurement, we want to measure n quantum states, in a way that<br class="">
"damages the states by at most alpha," conditioned on any outcome of<br class="">
the measurement. In both cases, we can achieve the goal by techniques<br class="">
like deliberately adding noise to the outcome before returning it. We<br class="">
prove a new and general connection between the two subjects.<br class="">
Specifically, on products of n quantum states, any measurement that is<br class="">
alpha-gentle for small alpha is also O(alpha)-DP, and any product<br class="">
measurement that is eps-DP is also O(eps*sqrt(n)) -gentle.<br class="">
<br class="">
Illustrating the power of this connection, we apply it to the recently<br class="">
studied problem of shadow tomography. Given an unknown d-dimensional<br class="">
quantum state rho, as well as known two-outcome measurements<br class="">
E_1,...,E_m, shadow tomography asks us to estimate Pr[E_i accepts<br class="">
rho], for every i in [m], by measuring few copies of rho. Using our<br class="">
connection theorem, together with a quantum analog of the so-called<br class="">
private multiplicative weights algorithm of Hardt and Rothblum, we<br class="">
give a protocol to solve this problem using O((log m)^2 (log d)^2)<br class="">
copies of rho, compared to Aaronson's previous bound of ~O((log m)^4<br class="">
(log d)). Our protocol has the advantages of being online (that is,<br class="">
the E_i's are processed one at a time), gentle, and conceptually<br class="">
simple.<o:p class=""></o:p></span></p><p class="MsoNormal" style="text-align:justify"><span style="mso-bidi-font-size:
12.0pt;font-family:"Times New Roman",serif" class=""> Joint
work with Guy Rothblum (to appear in STOC'2019).<o:p class=""></o:p></span></p><div style="text-align: justify;" class=""><span style="mso-bidi-font-size:
12.0pt;font-family:"Times New Roman",serif" class=""> </span><br class="webkit-block-placeholder"></div><p class="MsoNormal" style="text-align:justify"><span style="mso-bidi-font-size:
12.0pt;font-family:"Times New Roman",serif" class="">
<b class=""><span style="color:#C00000" class="">Note:
Non-Standard Day<o:p class=""></o:p></span></b></span></p><p class="MsoNormal" align="center" style="text-align:center"><span style="mso-bidi-font-size:12.0pt;font-family:"Times New Roman",serif" class=""> Thursday, February 28, 2018<o:p class=""></o:p></span></p><p class="MsoNormal" align="center" style="text-align:center"><span style="mso-bidi-font-size:12.0pt;font-family:"Times New Roman",serif" class="">Ry. 251 @
3:30 pm<o:p class=""></o:p></span></p><p class="MsoNormal" align="center" style="text-align:center"><span style="mso-bidi-font-size:12.0pt;font-family:"Times New Roman",serif" class="">(Refreshments
will be served prior to the talk in Ry. 255 @ 3:00pm)<o:p class=""></o:p></span></p><div style="text-align: center;" class=""><span style="mso-bidi-font-size:12.0pt;font-family:"Times New Roman",serif" class=""> </span><br class="webkit-block-placeholder"></div><div class=""><span style="font-size:11.0pt;font-family:"Times New Roman",serif" class=""> </span><br class="webkit-block-placeholder"></div>
<!--EndFragment--></div><div class=""><br class="webkit-block-placeholder"></div><div class="">
<div style="color: rgb(0, 0, 0); font-family: Helvetica; font-size: inherit; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-variant-east-asian: normal; font-variant-position: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div style="color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-variant-east-asian: normal; font-variant-position: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div style="color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-variant-east-asian: normal; font-variant-position: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div style="color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-variant-east-asian: normal; font-variant-position: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><div style="color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-variant-east-asian: normal; font-variant-position: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; font-size: 11px;" class=""><br class="webkit-block-placeholder"></div><div style="color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-variant-east-asian: normal; font-variant-position: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><div class=""><p class="MsoNormal" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; text-decoration: none; font-variant-ligatures: normal; font-variant-east-asian: normal; font-variant-position: normal; line-height: normal;"><b class=""><font size="4" class="">Donna Brooms-Blue</font></b></p><br class="Apple-interchange-newline" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; text-decoration: none;"></div>
</div></div></div></div></div></div><br class=""></div></body></html>