Answering Counting Queries with Differential Privacy on a Quantum Computer

• URL: http://arxiv.org/abs/2604.10881v1
• Date: Mon, 13 Apr 2026 00:57:33 GMT
• Title: Answering Counting Queries with Differential Privacy on a Quantum Computer
• Abstract summary: We show how to answer counting queries on a quantum encoded dataset with differential privacy.<n>We analyze the differential privacy properties of two algorithms to measure amplitude.
• Score: 0.7129650436893149
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Keeping a Secret Requires a Good Memory: Space Lower-Bounds for Private Algorithms [67.94856074923571]
  This paper introduces a novel proof technique based on a multi-player communication game.<n>We show that winning this communication game requires transmitting information proportional to the number of over-active users.<n>We show that this communication-theoretic technique generalizes to broad classes of problems, yielding lower bounds for private medians, quantiles, and max-select.
  arXiv  Detail & Related papers  (2026-02-12T17:49:07Z)
• Scalable Private Partition Selection via Adaptive Weighting [66.09199304818928]
  In a private set union, users hold subsets of items from an unbounded universe.<n>The goal is to output as many items as possible from the union of the users' sets while maintaining user-level differential privacy.<n>We propose an algorithm for this problem, MaxDegree (MAD), which adaptively reroutes weight from items with weight far above the threshold needed for privacy to items with smaller weight.<n>Our algorithms provide the best results among parallel algorithms and scale to datasets with hundreds of billions of items, up to three orders of magnitude larger than those analyzed by prior algorithms.
  arXiv  Detail & Related papers  (2025-02-13T01:27:11Z)
• Tight Auditing of Differentially Private Machine Learning [77.38590306275877]
  For private machine learning, existing auditing mechanisms are tight. They only give tight estimates under implausible worst-case assumptions. We design an improved auditing scheme that yields tight privacy estimates for natural (not adversarially crafted) datasets.
  arXiv  Detail & Related papers  (2023-02-15T21:40:33Z)
• On Differential Privacy and Adaptive Data Analysis with Bounded Space [76.10334958368618]
  We study the space complexity of the two related fields of differential privacy and adaptive data analysis. We show that there exists a problem P that requires exponentially more space to be solved efficiently with differential privacy. The line of work on adaptive data analysis focuses on understanding the number of samples needed for answering a sequence of adaptive queries.
  arXiv  Detail & Related papers  (2023-02-11T14:45:31Z)
• Private measures, random walks, and synthetic data [7.5764890276775665]
  Differential privacy is a mathematical concept that provides an information-theoretic security guarantee. We develop a private measure from a data set that allows us to efficiently construct private synthetic data. A key ingredient in our construction is a new superregular random walk, whose joint distribution of steps is as regular as that of independent random variables.
  arXiv  Detail & Related papers  (2022-04-20T00:06:52Z)
• Differential Privacy Amplification in Quantum and Quantum-inspired Algorithms [0.6827423171182154]
  We provide privacy bounds amplification for quantum and quantum-inspired algorithms. We show for the first time, that algorithms running on quantum encoding of a classical dataset amplify differential privacy.
  arXiv  Detail & Related papers  (2022-03-07T18:55:20Z)
• Quantum Differential Privacy: An Information Theory Perspective [2.9005223064604073]
  We discuss differential privacy in an information theoretic framework by casting it as a quantum divergence. A main advantage of this approach is that differential privacy becomes a property solely based on the output states of the computation.
  arXiv  Detail & Related papers  (2022-02-22T08:12:50Z)
• Robust and Differentially Private Mean Estimation [40.323756738056616]
  Differential privacy has emerged as a standard requirement in a variety of applications ranging from the U.S. Census to data collected in commercial devices. An increasing number of such databases consist of data from multiple sources, not all of which can be trusted. This leaves existing private analyses vulnerable to attacks by an adversary who injects corrupted data.
  arXiv  Detail & Related papers  (2021-02-18T05:02:49Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  We give efficient differentially private algorithms for basic clustering problems. Our results imply an improved algorithm for the Sample and Aggregate privacy framework. One of the tools used in our 1-Cluster algorithm can be employed to get a faster quantum algorithm for ClosestPair in a moderate number of dimensions.
  arXiv  Detail & Related papers  (2020-08-18T16:22:06Z)
• Tighter Generalization Bounds for Iterative Differentially Private Learning Algorithms [95.73230376153872]
  This paper studies the relationship between generalization and privacy preservation in iterative learning algorithms by two sequential steps. We prove that $(varepsilon, delta)$-differential privacy implies an on-average generalization bound for multi-Database learning algorithms. We then investigate how the iterative nature shared by most learning algorithms influence privacy preservation and further generalization.
  arXiv  Detail & Related papers  (2020-07-18T09:12:03Z)
• Differentially Private Algorithms for Statistical Verification of Cyber-Physical Systems [5.987774571079633]
  We show that revealing the number of the samples drawn can violate privacy. We propose a new notion of differential privacy which we call expected differential privacy.
  arXiv  Detail & Related papers  (2020-04-01T08:14:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.