Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper investigates answering counting queries on quantum-encoded datasets with differential privacy, a critical area for privacy-preserving data analysis in the quantum realm. The authors demonstrate that answering these queries reduces to amplitude estimation between orthogonal states and analyze the privacy properties of two amplitude measurement algorithms. They prove improved privacy bounds for repeated measurements in the computational basis, showing privacy amplification, and derive a tight bound on the global sensitivity for amplitude estimation, enabling a differentially private version of the algorithm.
Quantum algorithms for differentially private counting queries can actually *amplify* privacy due to inherent randomness, a surprising twist on classical privacy mechanisms.
Differential privacy is a mathematical notion of data privacy that has fast become the de facto standard in privacy-preserving data analysis. Recently a lot of work has focused on differential privacy in the quantum setting. Continuing on this line of study, we investigate how to answer counting queries on a quantum encoded dataset with differential privacy. An example of a counting query is ``How many people in the dataset are over the age of 25 and with a university education?''Counting queries form the most basic but nonetheless rich set of statistics extractable from a dataset. We show that answering these queries on a quantum encoded dataset reduces to measuring the amplitude of one of two orthogonal states. We then analyze the differential privacy properties of two algorithms from literature to measure amplitude: one which performs repeated measurements in the computational basis, and the other which utilizes the classic amplitude estimation algorithm. For the first technique, we prove privacy results for the case of counting queries that improve on previously known results on general queries, and show that the mechanism in fact \emph{amplifies} privacy due to inherent randomness. For the second method, we derive a tight bound on maximum possible change in the amplitude if we add or remove a single item in the dataset, a quantity called global sensitivity which is central in making an algorithm differentially private. We then show a differentially private version of the amplitude estimation algorithm for counting queries. We also discuss how these methods can be outsourced to a quantum server to blindly compute counting queries with differential privacy.