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• 0 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•98 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•0 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•323 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•0 citations

Online Shadow Tomography Matching the Classical Bounds

Sitan Chen, Ryan O'Donnell, Angelos Pelecanos +1 more

In Online Shadow Tomography, we are given copies of an unknown $d$-dimensional quantum state $ρ$, an adversary (adaptively) proposes a sequence of bounded observables $A^{(1)},\ldots,A^{(m)}$, and after each $A^{(t)}$ is given we must estimate $\mathrm{Tr}(A^{(t)}ρ)$ to within $\pm ε$. This is the direct quantum generalization of the classical problem of Adaptive Data Analysis. Prior results for online Shadow Tomography were suboptimal in all three parameters $m, d, ε$, lagging behind the best known and classical rates, for which there is some evidence of optimality. In this work, we finally close this gap, giving a pair of algorithms matching the classical rates. Our first algorithm is the first to achieve $o(\log^2 m)$-dependence together with $\mathrm{poly}(\log(d)/ε)$; moreover, it improves all three exponents even in the Offline Shadow Tomography setting. Our second algorithm is known to be optimal among bounds independent of $d$, and improves the best prior result by a $\sqrt{m} \log m$ factor. The key to our proof is a new framework for quantifying post-measurement damage, based on the quantum Efron-Stein decomposition.

quant-pharXiv:2607.29686•Aug 3, 2026•0 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.
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.
In Online Shadow Tomography, we are given copies of an unknown ddd-dimensional quantum state ρρρ, an adversary (adaptively) proposes a sequence of bounded observables A(1),…,A(m)A^{(1)},\ldots,A^{(m)}A(1),…,A(m), and after each A(t)A^{(t)}A(t) is given we must estimate Tr(A(t)ρ)\mathrm{Tr}(A^{(t)}ρ)Tr(A(t)ρ) to within ±ε\pm ε±ε. This is the direct quantum generalization of the classical problem of Adaptive Data Analysis. Prior results for online Shadow Tomography were suboptimal in all three parameters m,d,εm, d, εm,d,ε, lagging behind the best known and classical rates, for which there is some evidence of optimality. In this work, we finally close this gap, giving a pair of algorithms matching the classical rates. Our first algorithm is the first to achieve o(log⁡2m)o(\log^2 m)o(log2m)-dependence together with poly(log⁡(d)/ε)\mathrm{poly}(\log(d)/ε)poly(log(d)/ε); moreover, it improves all three exponents even in the Offline Shadow Tomography setting. Our second algorithm is known to be optimal among bounds independent of ddd, and improves the best prior result by a mlog⁡m\sqrt{m} \log mm​logm factor. The key to our proof is a new framework for quantifying post-measurement damage, based on the quantum Efron-Stein decomposition.