Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1904.08747 · Electronic colloquium on computational complexity

Gentle Measurement of Quantum States and Differential Privacy

Scott Aaronson, Guy N. Rothblum

Published Apr 18, 2019• 10 citations
arXivHTMLPDF

Abstract

In differential privacy (DP), we want to query a database about n users, in a way that "leaks at most eps about any individual user," even conditioned on any outcome of the query. Meanwhile, in gentle measurement, we want to measure n quantum states, in a way that "damages the states by at most alpha," even conditioned on any outcome of the measurement. In both cases, we can achieve the goal by techniques like deliberately adding noise to the outcome before returning it. This paper proves a new and general connection between the two subjects. Specifically, we show that on products of n quantum states, any measurement that is alpha-gentle for small alpha is also O(alpha)-DP, and any product measurement that is eps-DP is also O(eps*sqrt(n))-gentle. Illustrating the power of this connection, we apply it to the recently studied problem of shadow tomography. Given an unknown d-dimensional quantum state rho, as well as known two-outcome measurements E_1,...,E_m, shadow tomography asks us to estimate Pr[E_i accepts rho], for every i in [m], by measuring few copies of rho. Using our connection theorem, together with a quantum analog of the so-called private multiplicative weights algorithm of Hardt and Rothblum, we give a protocol to solve this problem using O((log m)^2 (log d)^2) copies of rho, compared to Aaronson's previous bound of ~O((log m)^4 (log d)). Our protocol has the advantages of being online (that is, the E_i's are processed one at a time), gentle, and conceptually simple. Other applications of our connection include new lower bounds for shadow tomography from lower bounds on DP, and a result on the safe use of estimation algorithms as subroutines inside larger quantum algorithms.

DOI
10.48550/arxiv.1904.08747

Related papers

Gentle measurement of quantum states and differential privacy

Scott Aaronson, Guy N. Rothblum

In differential privacy (DP), we want to query a database about n users, in a way that “leaks at most ε about any individual user,” even conditioned on any outcome of the query. Meanwhile, in gentle measurement, we want to measure n quantum states, in a way that “damages the states by at most α,” even conditioned on any outcome of the measurement. In both cases, we can achieve the goal by techniques like deliberately adding noise to the outcome before returning it. This paper proves a new and general connection between the two subjects. Specifically, we show that on products of n quantum states, any measurement that is α-gentle for small α is also O( α) -DP, and any product measurement that is ε-DP is also O( ε√n) -gentle.

ACM Symposium on Theory of Computing (STOC)•Jun 20, 2019•122 citations

Dimension-Free Polylogarithmic Quantum Shadow Tomography

Fernando Granha Jeronimo, Qizhao Huang, Lenny Liu

Shadow Tomography is a fundamental problem in quantum information theory. Given multiple copies of an unknown $d$-dimensional quantum state $ρ$ and a known collection of observables $E_1,\ldots,E_M$, the goal is to estimate all expectation values $\{\text{Tr}(ρE_i)\}_{i=1}^M$ to additive accuracy $\varepsilon$ with probability at least $1-δ$. An elusive open question from the seminal shadow tomography work of Aaronson is whether this task admits a dimension-independent sample complexity with only polylogarithmic dependence on $M$, as suggested by the best-known lower bounds. In this work, we propose two different quantum protocols for shadow tomography with the best sample complexity \[ O\left( \frac{\log(M)\log(M/δ)}{\varepsilon^2} \right), \] which is polylogarithmic in the number of observables and independent of the dimension of the unknown state, thereby answering Aaronson's original question while also providing an exponential improvement in the prior best dimension independent sample complexity of shadow tomography from Sinha (STOC 2025) and, more recently, Chen, O'Donnell, Pelecanos, and Wright. Our approach first reduces the general shadow tomography problem to a finite-ensemble estimation problem via a minimax argument. We then develop an observable-independent protocol that repeatedly applies the pretty-good measurement while updating the prior distribution over the finite ensemble according to the measurement outcomes. A tail analysis of the resulting estimation error yields simultaneous accuracy guarantees for all observables and a cubic-logarithmic upper bound. We also introduce a refined recovery-label measurement for the same finite ensemble, which yields the bound in our main theorem.

quant-pharXiv:2608.06345•Aug 7, 2026•6 citations

Shadow Tomography of Quantum States

Scott Aaronson

We introduce the problem of shadow tomography: given an unknown $D$-dimensional quantum mixed state $\rho$, as well as known two-outcome measurements $E_{1},\ldots,E_{M}$, estimate the probability that $E_{i}$ accepts $\rho$, to within additive error $\varepsilon$, for each of the $M$ measurements. How many copies of $\rho$ are needed to achieve this, with high probability? Surprisingly, we give a procedure that solves the problem by measuring only $\widetilde{O}\left(\varepsilon^{-4}\cdot\log^{4}M\cdot\log D\right)$ copies. This means, for example, that we can learn the behavior of an arbitrary $n$-qubit state, on all accepting/rejecting circuits of some fixed polynomial size, by measuring only $n^{O(1)}$ copies of the state. This resolves an open problem of the author, which arose from his work on private-key quantum money schemes, but which also has applications to quantum copy-protected software, quantum advice, and quantum one-way communication. Recently, building on this work, Branda͂o et al. have given a different approach to shadow tomography using semidefinite programming, which achieves a savings in computation time.

arXiv:1711.01053•SIAM Journal on Computing•Jun 20, 2018•513 citations

Quantum Differential Privacy in the Local Model

Armando Angrisani, Elham Kashefi

Differential privacy provides a robust framework for protecting sensitive data, while maintaining its utility for computation. In essence, a differentially private algorithm takes as input the data of multiple parties, and returns an output disclosing minimal information about any individual party. Previous research has introduced several quantum extensions of differential privacy, with applications ranging from quantum machine learning on private classical data to quantum shadow tomography. However, the local model of quantum differential privacy – where each party is responsible for privatizing their own data at a local level – has received limited attention. This work delves into locally differentially private quantum measurements. Although any measurement can be made locally differentially private by adding noise to the outcome, we demonstrate that certain quantum measurements inherently satisfy some degree of local differential privacy for specific classes of input states. This finding has two significant implications: first, limiting the analysis to classical noise injection mechanisms may lead to suboptimal privacy-utility trade-offs for quantum data; second, the theory of differential privacy can be harnessed to further investigate the capabilities of quantum measurements. Motivated by these insights, we establish strong data processing inequalities for the quantum relative entropy under local differential privacy and apply these results to asymmetric hypothesis testing of quantum states with restricted measurements. Additionally, we prove an equivalence between quantum statistical queries and quantum differential privacy in the local model, thereby addressing an open question posed by Arunachalam et al. (2021). Finally, we consider the task of quantum multi-party computation under local differential privacy, demonstrating that parity functions can be efficiently learned in this model, whereas the corresponding classical task requires exponentially many samples.

IEEE Transactions on Information Theory•Mar 18, 2025•10 citations

Optimal estimation of high-dimensional quantum states using locally gentle measurements

Cristina Butucea, Jan Johannes, Henning Stein

We study the task of estimating a $d-$dimensional quantum state $ρ$ under the constraint that the measurement is $α-$gentle. Such measurements $M$ do not collapse the state; they issue both a random variable $R^M = ω$ containing statistical information and a post-measurement state $ρ_{M \to ω}$ such that $\|ρ_{M\to ω} - ρ\|_{Tr} \leq α$. We describe gentle measurements and their connection to quantum differential privacy. Our results show that the optimal minimax estimation rate in Frobenius norm is of order $d^3/(n α^2)$, instead of $d^2/n$ for general measurements. Moreover, for rank $r$ states with $r\leq d$ we prove that the optimal minimax rate is $rd^2/(n α^2)$, instead of $rd/n$. Very surprisingly, the loss for gentleness $d/α^2$ scales with the ambient dimension of the Hilbert space, rather than the number of parameters $rd$, typically seen in classical differential privacy. We propose optimal gentle measurements and indicate how they can be physically implemented using an ancillary state and a CNOT gate to entangle it with the initial state. We notice that the resulting random variable has a likelihood that satisfies local differential privacy. Lower bounds are proven through a new quantum information-theoretic inequality applied to well chosen families of states in the manifold of (small-rank) quantum states.

math.STCross-listedarXiv:2607.24491•Jul 28, 2026•0 citations

Sample-optimal learning of quantum states using gentle measurements

Cristina Butucea, Jan Johannes, Henning Stein

Gentle measurements of quantum states do not entirely collapse the initial state. Instead, they provide a post-measurement state at a prescribed trace distance α from the initial state together with a random variable used for quantum learning of the initial state. We introduce here the class of α−locally-gentle measurements (α−LGM) on a finite dimensional quantum system which are product measurements on product states and prove a strong quantum Data-Processing Inequality (qDPI) on this class using an improved relation between gentleness and quantum differential privacy. We further show a gentle quantum Neyman-Pearson lemma which implies that our qDPI is asymptotically optimal (for small α). This inequality is employed to show that the necessary number of quantum states for prescribed accuracy ϵ is of order 1∕(ϵ2α2) for both quantum tomography and quantum state certification. Finally, we propose an α−LGM called quantum Label Switch that attains these bounds. It is a general implementable method to turn any two-outcome measurement into an α−LGM.

arXiv:2505.24587•Electronic Journal of Statistics•Jan 1, 2026•5 citations
In differential privacy (DP), we want to query a database about n users, in a way that "leaks at most eps about any individual user," even conditioned on any outcome of the query. Meanwhile, in gentle measurement, we want to measure n quantum states, in a way that "damages the states by at most alpha," even conditioned on any outcome of the measurement. In both cases, we can achieve the goal by techniques like deliberately adding noise to the outcome before returning it. This paper proves a new and general connection between the two subjects. Specifically, we show that on products of n quantum states, any measurement that is alpha-gentle for small alpha is also O(alpha)-DP, and any product measurement that is eps-DP is also O(eps*sqrt(n))-gentle. Illustrating the power of this connection, we apply it to the recently studied problem of shadow tomography. Given an unknown d-dimensional quantum state rho, as well as known two-outcome measurements E_1,...,E_m, shadow tomography asks us to estimate Pr[E_i accepts rho], for every i in [m], by measuring few copies of rho. Using our connection theorem, together with a quantum analog of the so-called private multiplicative weights algorithm of Hardt and Rothblum, we give a protocol to solve this problem using O((log m)^2 (log d)^2) copies of rho, compared to Aaronson's previous bound of ~O((log m)^4 (log d)). Our protocol has the advantages of being online (that is, the E_i's are processed one at a time), gentle, and conceptually simple. Other applications of our connection include new lower bounds for shadow tomography from lower bounds on DP, and a result on the safe use of estimation algorithms as subroutines inside larger quantum algorithms.
In differential privacy (DP), we want to query a database about n users, in a way that “leaks at most ε about any individual user,” even conditioned on any outcome of the query. Meanwhile, in gentle measurement, we want to measure n quantum states, in a way that “damages the states by at most α,” even conditioned on any outcome of the measurement. In both cases, we can achieve the goal by techniques like deliberately adding noise to the outcome before returning it. This paper proves a new and general connection between the two subjects. Specifically, we show that on products of n quantum states, any measurement that is α-gentle for small α is also O( α) -DP, and any product measurement that is ε-DP is also O( ε√n) -gentle.
Shadow Tomography is a fundamental problem in quantum information theory. Given multiple copies of an unknown ddd-dimensional quantum state ρρρ and a known collection of observables E1,…,EME_1,\ldots,E_ME1​,…,EM​, the goal is to estimate all expectation values {Tr(ρEi)}i=1M\{\text{Tr}(ρE_i)\}_{i=1}^M{Tr(ρEi​)}i=1M​ to additive accuracy ε\varepsilonε with probability at least 1−δ1-δ1−δ. An elusive open question from the seminal shadow tomography work of Aaronson is whether this task admits a dimension-independent sample complexity with only polylogarithmic dependence on MMM, as suggested by the best-known lower bounds. In this work, we propose two different quantum protocols for shadow tomography with the best sample complexity O(log⁡(M)log⁡(M/δ)ε2), O\left( \frac{\log(M)\log(M/δ)}{\varepsilon^2} \right), O(ε2log(M)log(M/δ)​), which is polylogarithmic in the number of observables and independent of the dimension of the unknown state, thereby answering Aaronson's original question while also providing an exponential improvement in the prior best dimension independent sample complexity of shadow tomography from Sinha (STOC 2025) and, more recently, Chen, O'Donnell, Pelecanos, and Wright. Our approach first reduces the general shadow tomography problem to a finite-ensemble estimation problem via a minimax argument. We then develop an observable-independent protocol that repeatedly applies the pretty-good measurement while updating the prior distribution over the finite ensemble according to the measurement outcomes. A tail analysis of the resulting estimation error yields simultaneous accuracy guarantees for all observables and a cubic-logarithmic upper bound. We also introduce a refined recovery-label measurement for the same finite ensemble, which yields the bound in our main theorem.
We introduce the problem of shadow tomography: given an unknown DDD-dimensional quantum mixed state ρ\rhoρ, as well as known two-outcome measurements E1,…,EME_{1},\ldots,E_{M}E1​,…,EM​, estimate the probability that EiE_{i}Ei​ accepts ρ\rhoρ, to within additive error ε\varepsilonε, for each of the MMM measurements. How many copies of ρ\rhoρ are needed to achieve this, with high probability? Surprisingly, we give a procedure that solves the problem by measuring only O~(ε−4⋅log⁡4M⋅log⁡D)\widetilde{O}\left(\varepsilon^{-4}\cdot\log^{4}M\cdot\log D\right)O(ε−4⋅log4M⋅logD) copies. This means, for example, that we can learn the behavior of an arbitrary nnn-qubit state, on all accepting/rejecting circuits of some fixed polynomial size, by measuring only nO(1)n^{O(1)}nO(1) copies of the state. This resolves an open problem of the author, which arose from his work on private-key quantum money schemes, but which also has applications to quantum copy-protected software, quantum advice, and quantum one-way communication. Recently, building on this work, Branda͂o et al. have given a different approach to shadow tomography using semidefinite programming, which achieves a savings in computation time.
Differential privacy provides a robust framework for protecting sensitive data, while maintaining its utility for computation. In essence, a differentially private algorithm takes as input the data of multiple parties, and returns an output disclosing minimal information about any individual party. Previous research has introduced several quantum extensions of differential privacy, with applications ranging from quantum machine learning on private classical data to quantum shadow tomography. However, the local model of quantum differential privacy – where each party is responsible for privatizing their own data at a local level – has received limited attention. This work delves into locally differentially private quantum measurements. Although any measurement can be made locally differentially private by adding noise to the outcome, we demonstrate that certain quantum measurements inherently satisfy some degree of local differential privacy for specific classes of input states. This finding has two significant implications: first, limiting the analysis to classical noise injection mechanisms may lead to suboptimal privacy-utility trade-offs for quantum data; second, the theory of differential privacy can be harnessed to further investigate the capabilities of quantum measurements. Motivated by these insights, we establish strong data processing inequalities for the quantum relative entropy under local differential privacy and apply these results to asymmetric hypothesis testing of quantum states with restricted measurements. Additionally, we prove an equivalence between quantum statistical queries and quantum differential privacy in the local model, thereby addressing an open question posed by Arunachalam et al. (2021). Finally, we consider the task of quantum multi-party computation under local differential privacy, demonstrating that parity functions can be efficiently learned in this model, whereas the corresponding classical task requires exponentially many samples.
We study the task of estimating a d−d-d−dimensional quantum state ρρρ under the constraint that the measurement is α−α-α−gentle. Such measurements MMM do not collapse the state; they issue both a random variable RM=ωR^M = ωRM=ω containing statistical information and a post-measurement state ρM→ωρ_{M \to ω}ρM→ω​ such that ∥ρM→ω−ρ∥Tr≤α\|ρ_{M\to ω} - ρ\|_{Tr} \leq α∥ρM→ω​−ρ∥Tr​≤α. We describe gentle measurements and their connection to quantum differential privacy. Our results show that the optimal minimax estimation rate in Frobenius norm is of order d3/(nα2)d^3/(n α^2)d3/(nα2), instead of d2/nd^2/nd2/n for general measurements. Moreover, for rank rrr states with r≤dr\leq dr≤d we prove that the optimal minimax rate is rd2/(nα2)rd^2/(n α^2)rd2/(nα2), instead of rd/nrd/nrd/n. Very surprisingly, the loss for gentleness d/α2d/α^2d/α2 scales with the ambient dimension of the Hilbert space, rather than the number of parameters rdrdrd, typically seen in classical differential privacy. We propose optimal gentle measurements and indicate how they can be physically implemented using an ancillary state and a CNOT gate to entangle it with the initial state. We notice that the resulting random variable has a likelihood that satisfies local differential privacy. Lower bounds are proven through a new quantum information-theoretic inequality applied to well chosen families of states in the manifold of (small-rank) quantum states.
Gentle measurements of quantum states do not entirely collapse the initial state. Instead, they provide a post-measurement state at a prescribed trace distance α from the initial state together with a random variable used for quantum learning of the initial state. We introduce here the class of α−locally-gentle measurements (α−LGM) on a finite dimensional quantum system which are product measurements on product states and prove a strong quantum Data-Processing Inequality (qDPI) on this class using an improved relation between gentleness and quantum differential privacy. We further show a gentle quantum Neyman-Pearson lemma which implies that our qDPI is asymptotically optimal (for small α). This inequality is employed to show that the necessary number of quantum states for prescribed accuracy ϵ is of order 1∕(ϵ2α2) for both quantum tomography and quantum state certification. Finally, we propose an α−LGM called quantum Label Switch that attains these bounds. It is a general implementable method to turn any two-outcome measurement into an α−LGM.