TOC Seminar: Gentle Measurement of Quantum States and Differential Privacy
Speaker: Scott AaronsonRecorded on November 20, 2018 at 17:30
About This Video
Abstract: We prove a surprising connection between gentle measurement (where one wants to measure n quantum states, in a way that damages the states only by a little) and differential privacy (where one wants to query a database about n users, in a way that reveals only a little about any individual user). The connection is bidirectional, though with loss of parameters in going from DP to gentlemeasurement. By exploiting this connection, together with the Private Multiplicative Weights algorithm of Hardt and Rothblum, we're able to give a new protocol for so-called "shadow tomography" of quantum states, which improves over the parameters of a previous protocol for that task due to Aaronson, and which has the additional advantage of being "online" (that is, the measurements are processed one at a time).