PaperlayerView exact revision on arXiv

Source-linked AI summary

Gentle Measurement of Quantum States and Differential Privacy

Scott Aaronson, Guy N. Rothblum

arXiv:1904.08747v1quant-ph

TL;DR

The paper studies how to obtain accurate statistical information while limiting privacy loss or quantum-state damage, including shadow tomography in identical- and diverse-state settings. It proves a two-way connection between gentleness and differential privacy, develops Quantum Private Multiplicative Weights, and applies these ideas to an online, gentle shadow-tomography procedure.

  • Problem

    The paper addresses how to obtain accurate statistical information while limiting privacy loss or quantum-state damage, including whether lower bounds for diverse-state shadow tomography apply to the identical-state setting.

  • Method

    The paper proves a two-way connection between gentleness and differential privacy and uses a Damage Lemma, epochs, and Quantum Private Multiplicative Weights for shadow tomography.

  • Results

    The resulting shadow-tomography procedure has a stated success probability, is online, and is (ε, δ)-gentle.

  • Takeaways & Limitations

    The connection supports lower-bound results for diverse-state shadow tomography and helps address the gap between diverse-state and identical-state settings.

  • Takeaways & Limitations

    Whether the product-measurement condition can be removed remains an open problem, and known counterexamples are extremely artificial.

Abstract

from arXiv · show

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.

1 Introduction

The paper establishes a two-way connection between differential privacy and gentle quantum measurement, then applies it to quantum algorithms and shadow tomography. Its applications include QPMW, lower bounds, and techniques for safely using quantum estimation subroutines.

  • The Connection: Theorem 5 gives a two-way connection between differential privacy and gentleness on product states, including measurements far from trivial.The reverse direction requires product measurements, while the necessity of that condition remains open.
  • The Connection: O(√(n/σ))-gentleness follows for the Laplace-noise measurement Lσ on product states.This is obtained by combining the differential-privacy-to-gentleness direction with the privacy of Laplace noise.
  • Other Applications: The paper also derives a safe quantum-subroutine estimation result and shows that quantum DP composition requires caveats absent classically.A 0-DP measurement on product states is shown to be 0-DP on all states, with the argument relying on complex amplitudes.
  • Shadow Tomography: QPMW is an explicit shadow-tomography procedure that is online and (ε, δ)-gentle.It quantizes the classical Private Multiplicative Weights algorithm and estimates many known measurements on copies of an unknown state.
  • Shadow Tomography: QPMW improves the dependence on m from (log m)^4 to (log m)^2, while its dependence on d and 1/ε is worse than the prior theorem.Its running time is roughly O(mL)+d^O(1), improving on Aaronson’s d^O(log log d) dependence.
  • Shadow Tomography: The DP/gentleness connection yields information-theoretic and computational lower bounds for gentle and online shadow tomography.These lower bounds are obtained by porting classical differential-privacy and adaptive-data-analysis results, and therefore also apply to the classical special case.
  • Techniques: The Damage Lemma relates update probabilities in damaged and ideal executions, enabling epoch-based control of QPMW’s total damage.Quantum damage is additive, unlike the multiplicative privacy guarantees preserved by classical composition.

2 Preliminaries

The preliminaries introduce quantum-state representations, measurements, and operations, then define product states and connect measurement gentleness with differential privacy. They also establish that the relevant DP and gentleness properties extend from pure product states to mixed product states.

  • Quantum states: A d-dimensional pure quantum state is a unit vector in C^d, represented in ket notation as a superposition over an orthonormal basis.Its amplitudes have squared magnitudes summing to one; qubits are the special case d = 2.
  • Measurements: Projective measurements return basis state |v_i⟩ with probability |⟨ψ|v_i⟩|^2 for pure states, or ⟨v_i|ρ|v_i⟩ for mixed states, and collapse the state accordingly.More general measurements are represented by POVMs, whose positive semidefinite elements sum to the identity.
  • Quantum states: A mixed state ρ is a positive semidefinite d × d matrix with Tr(ρ) = 1, equivalently a convex combination of pure-state outer products.Diagonal mixed states represent classical probability distributions, while rank-one states are pure.
  • Measurements: A POVM specifies outcome probabilities, while an implementation additionally specifies post-measurement states through matrices B_i satisfying B_i†B_i = E_i.The probability of outcome i is Tr(E_iρ), and quantum operations can describe conditional, potentially trace-decreasing behavior.
  • Product states: A product state factors across n registers, whereas entangled states cannot; implementing a measurement gently may require coherent action across all registers.Measuring registers separately can generate garbage information that destroys gentleness, even for product or LOCC measurements.
  • Connection to privacy: If M is ε-DP on pure product states, it is ε-DP on mixed product states; the analogous extension holds for α-gentleness.The same pure-to-mixed extension also holds when the property is assumed on all pure states.

3 Basic Relations Among DP, Gentleness, and Triviality

This section defines triviality and establishes basic two-way relations among differential privacy, gentleness, and near-trivial measurements on all states. These relations are informative but limited because they operate in a nearly trivial regime.

  • Scope: Theorem 20 relates privacy and gentleness only through near-triviality, motivating the later product-state connection that works far from triviality.The section also notes that its statements have classical analogues for probability distributions.
  • Triviality: ε-triviality requires every outcome probability to be within an e^ε multiplicative factor across all states.At ε = 0, output probabilities are completely state-independent; triviality immediately implies ε-DP.
  • Gentleness and privacy: α-gentleness on all states implies ln(1/(1−4α))-DP when α is sufficiently small.The argument applies independently to each measurement outcome, yielding the stronger outcome-wise conclusion.
  • Gentleness and triviality: An ε-trivial measurement is (e^ε − 1)-gentle on all states, and therefore O(ε)-gentle for ε ≤ 1.The proof constructs an implementation from the spectral decomposition of each POVM element.
  • Privacy and triviality: ε-DP on all states implies 2εn-triviality, while ε-DP on product states implies 2εn-triviality on product states.The product-state version is interesting only when ε is much smaller than 1/n.

4 Proof of Main Result

The main result connects differential privacy and gentleness directly on product states, avoiding the near-triviality restriction. The proof first handles classical product distributions, then transfers the bound to quantum product measurements.

  • Gentleness Implies DP on Product States: α-gentleness on product states implies ln(1/(1−4α))-DP on product states, and hence O(α)-DP for small α.The proof compares neighboring product states differing on one register and applies the all-states relation with other registers fixed.
  • Gentleness Implies DP on Product States: For α approaching 1/4, the DP bound diverges, and the gap near this threshold remains open.A single-qubit measurement example is 1/2-gentle but provides no privacy, showing that divergence is necessary by 1/2.
  • DP Implies Gentleness: An ε-DP classical algorithm on a product distribution changes every output-conditioned posterior by at most 2ε√n in variation distance.The proof decomposes the posterior into sequential conditional distributions, bounds their log-ratios using DP, and combines them through KL divergence and Pinsker’s inequality.
  • DP Implies Gentleness: A product-of-projectives measurement that is ε-DP on product states is O(ε√n)-gentle on product states.Quantum post-measurement overlaps are identified with classical Hellinger distances between a product prior and its output-conditioned posterior.
  • DP Implies Gentleness: Any product measurement that is ε-DP on product states is O(ε√n)-gentle on product states.The quantum extension uses the same posterior-distance argument after embedding the measurement into a suitable implementation.

5 Separating Examples

The separating examples show that the established privacy–gentleness conversions have essentially optimal dependence on α, n, and √n. Randomized response and noisy Hamming-weight measurements supply the matching constructions.

  • Randomized Response: For every α ∈ (0, 1), some measurement is α-gentle on arbitrary states but fails ε-DP for every ε below the stated logarithmic threshold, even on product states.This construction uses randomized response applied only to the first qubit.
  • Randomized Response: Corollary 24 and Lemma 28 are tight up to a factor of 4 in front of α.The one-qubit randomized-response construction provides the matching separation.
  • Optimality of the n Factor: The arbitrary-state DP-to-gentleness conversion requires an n-factor blowup in ε, even for product-of-projectives measurements.This establishes that Proposition 27 is essentially tight.
  • Optimality of the n Factor: L_n/2 is 1/3-gentle on neither arbitrary n-qubit states, despite being 1/(n/2)-DP on all n-qubit states.L_σ measures total Hamming weight and adds Laplace noise of average magnitude σ; the example is classical, so implementation details do not matter.
  • Optimality of the √n Factor: The product-state DP-to-gentleness conversion requires a √n-factor blowup in ε, even for product-of-projectives measurements.The L_σ example shows that the corresponding O(ε√n) dependence is asymptotically tight.

6 Shadow Tomography

The paper applies QPMW, a quantum analogue of private multiplicative weights, to obtain online, gentle shadow tomography and derives lower bounds through the DP–gentleness connection.

  • Online Shadow Tomography: Theorem 39 establishes that suitable noise yields an (α, δ)-gentle online shadow tomography procedure with sufficiently many copies.The analysis separately establishes gentleness, ideal-run accuracy, hybrid-run accuracy, and real-run accuracy.
  • Online Shadow Tomography: The algorithm combines noisy measurement updates with online learning and analyzes update and non-update rounds to control accuracy and damage.The gentleness proof relates damage from conditioned no-update sequences to the probability of triggering an update.
  • Lower Bounds for Shadow Tomography: QPMW’s sample complexity is optimal up to a polynomial factor for shadow tomography that is gentle on all product states.This conclusion follows from a lower bound for gentle shadow tomography derived using differential privacy.
  • Lower Bounds for Shadow Tomography: The lower-bound argument must bridge diverse-state and identical-state settings because standard shadow tomography assumes inputs of the form ρ⊗n.The paper states that lower bounds in the diverse-state setting do not obviously transfer to the identical-state setting and closes this gap with an additional claim.
  • Lower Bounds for Shadow Tomography: The paper also derives lower bounds for online shadow tomography, concluding that QPMW achieves optimal sample complexity up to polynomial factors under the stated conditions.These lower bounds apply even to non-gentle online procedures through the connection with adaptive data analysis.

7 Computational Efficiency

The paper develops efficient implementations of gentle measurements, including Laplace-noise measurements and QSampling procedures, and analyzes their computational implications for shadow tomography and quantum algorithms.

  • Efficient gentle measurements: An O(n)-size quantum circuit implements the Laplace-noise measurement Lσ to exp(n) accuracy when σ = exp(O(n)).The construction exploits additive noise, whose integer addition can be efficiently inverted to uncompute the noise.
  • Efficient gentle measurements: The Laplace-noise implementation is maximally gentle: its only damage is the disturbance necessarily caused by learning the output, even for non-product inputs.
  • Efficient gentle measurements: A polynomial-time two-part algorithm yields an efficient gentle measurement when it prepares |ζX⟩ states and maps polynomially many copies to an output state nearly unentangled with them.The resulting procedure coherently maps |X⟩ to |X⟩|φX⟩ with inverse-polynomial accuracy.
  • Efficient gentle measurements: Sparse output distributions can be QSampled efficiently when an efficient classical sampler is available and each support has polynomial size.The procedure estimates empirical frequencies from sampled states and prepares the desired superposition without explicitly recording zero-frequency strings.
  • Shadow tomography: QPMW runs in roughly O(mL)+d^O(1) time, improving the dependence on d from Aaronson’s quasipolynomial-time procedure to polynomial.Here L is an upper bound on the time needed to implement one measurement E_i.
  • Complexity consequences: The connection also transfers differential-privacy lower bounds to gentle shadow tomography and establishes cryptographic hardness results for gentle and online procedures.Under the stated encryption assumption, the paper rules out d^o(1)·poly(m)-time gentle shadow tomography and d^o(1)·poly(m)-time online shadow tomography.
  • Quantum-algorithm applications: Efficient gentle measurements provide safe ways to run estimation subroutines on superpositions without generating unwanted garbage.The paper also derives an oracle-simulation consequence from such procedures.

8 Open Problems

The paper closes by identifying open questions about extending the DP–gentleness connection, improving shadow-tomography complexity, and understanding computational and structural limits.

  • Generalizing the connection: Can ε-DP on product states imply O(ε√n)-gentleness for broader classes of quantum measurements, beyond product measurements?
  • Reversing the connection: The authors ask whether quantum measurement results can yield new insights into classical differential privacy, reversing the paper’s main direction of application.
  • Quantum DP models: Open problems concern quantum differential privacy in the local model and composition of quantum DP algorithms while preserving accuracy or multiplicative privacy.
  • Shadow-tomography complexity: The true sample complexity of shadow tomography remains open, including whether dependence on d is necessary after dropping online or gentleness requirements.The paper notes that existing lower bounds apply under additional constraints and that classical offline non-gentle tomography has an O(·) upper bound independent of d.
  • Composition and sample complexity: An advanced composition theorem for gentleness could potentially reduce QPMW’s sample complexity from (log m)^2(log d)^2/ε^O(1) to (log m)^2 log d/ε^O(1).
  • Computational limits: Further questions ask whether polynomial-time DP algorithms can fail to induce efficiently implementable gentle measurements and whether d^Ω(1) time is needed without online or gentle constraints.
  • Quantum-algorithm applications: The authors also seek broader examples of safely invoking quantum algorithms as subroutines through gentle measurements.

10 Appendix: DP, Gentleness, and Triviality on Separable versus Entangled States

The appendix separates behavior on product or separable states from behavior on entangled states, while proving limited conditions under which properties on product states extend to all states.

  • Separations: Measurements can be exponentially gentle on all product states yet extremely non-gentle, non-private, or nontrivial on selected entangled states.These examples show that near-undetectability on separable inputs can coexist with large information leakage on entangled inputs.
  • Separations: A product-state separation is possible even for mixture-of-products measurements: exp(-n)-DP on product states does not imply meaningful DP on arbitrary states.
  • Limits of the separation: The appendix shows that the exponential separations between product-state and arbitrary-state properties are optimal up to the exact exponential scaling factor.
  • Separable mixed states: Product-state DP extends to separable mixed states by convexity, but product-state gentleness does not automatically extend in the same way.The measurement Lσ is given as a counterexample to the gentleness extension.
  • Why the separation occurs: The separation is specifically quantum because DP is closed under convex combinations but not under superpositions.The CHSH example produces behavior on an entangled Bell state that is not a convex combination of its behavior on the product components.
  • Complex versus real quantum mechanics: The extension depends on complex amplitudes: the analogous implication fails for real-amplitude qubits.A two-rebit measurement can behave identically on separable states while accepting an entangled rebit state differently.
  • Extensions to arbitrary states: For complex-amplitude quantum mechanics, sufficiently strong triviality on product states implies corresponding triviality, DP, and gentleness on arbitrary states.Theorem 66 gives the exact zero-error case, while Corollary 68 gives a weak quantitative extension under exponentially small ε.

11 Appendix: General Neighbor Relations

The appendix compares several notions of neighboring quantum states and determines how changing the neighbor relation affects differential privacy.

  • Neighbor definitions: Superoperator neighbors differ by a general quantum operation on one register, while unitary neighbors differ by a unitary transformation on one register.For product states, superoperator neighboring means that at most one tensor factor changes.
  • Neighbor definitions: Conditioned neighbors allow normalized, outcome-dependent quantum operations and are strictly broader than superoperator neighbors.The appendix gives examples separating conditioned, superoperator, and unitary neighbor relations.
  • Effect on privacy: Replacing superoperator neighbors with unitary neighbors changes DP by at most a factor of two in ε.This holds whether privacy is required on product states or on all states.
  • Effect on privacy: DP with respect to postselected neighbors collapses to triviality, with 4ε-DP implying 4ε-triviality.

12 Appendix: Differential Privacy Beyond Product and LOCC Measurements

The appendix constructs quantum measurements that satisfy differential privacy while escaping product-measurement structure, and conjecturally even LOCC structure. The constructions use noisy sums of locally sensitive parity tests to separate what unrestricted measurements can compute from what product or LOCC measurements can recover.

  • A second measurement is conjectured to be differentially private but not implementable by LOCC, requiring entangling measurements.Its construction replaces pairwise tests with swap tests inside nested blocks and then adds Laplace noise.
  • Lemma 71 shows that no two-qubit mixture-of-products measurement perfectly accepts |0⟩|0⟩ and |1⟩|+⟩ while rejecting |0⟩|1⟩ and |1⟩|−⟩.The proof reduces the restriction to incompatible basis requirements for the second qubit.
  • An O-DP measurement exists on n qubits that cannot be approximated by any mixture-of-products measurement.The separation is stated in variation distance over measurement outcomes.
  • The unrestricted construction computes a noisy sum of block parities, while mixture-of-products measurements cannot obtain a nontrivial estimate or distinguish the extreme cases.The measurement groups qubits into blocks, computes each block parity, and adds Laplace noise to the sum.
  • Exponential decay in parity-guessing bias lets sufficiently large logarithmic blocks hide the parity from mixture-of-products measurements.With k := C log n, noisy local readings reduce parity bias below 1/n^3.
  • Under the LOCC conjecture, true swap tests compute the parity sum, whereas LOCC measurements cannot compute it even noisily.The proposed limitation arises because LOCC can only simulate each swap test imperfectly.

13 Appendix: On Composition of Quantum DP Algorithms

This appendix examines when quantum differential privacy composes and identifies both a restricted positive result and a failure regime. Gentleness supports accuracy, but privacy can still depend on how post-measurement states are produced.

  • Unlike classical differential privacy, composing quantum DP algorithms can damage the state and thereby threaten both privacy and accuracy.The difficulty arises because later algorithms act on disturbed states rather than the original input.
  • Gentleness composes additively, so sequentially applying α1-gentle and α2-gentle measurements yields an (α1 + α2)-gentle procedure.This preserves accuracy when the DP-to-gentleness connection applies.
  • Privacy under composition may fail when a measurement amplifies information from one register into the remaining registers.Thus, controlling post-measurement states is necessary for a general privacy-composition theorem.
  • Limited quantum-DP composition holds for measurements that are both εi-DP and αi-gentle, provided every outcome sequence has probability at least p.The proposition assumes a lower bound on the product of outcome probabilities.
  • For product measurements, the appendix derives composition guarantees under small total privacy loss and sufficiently large outcome probabilities.The resulting sequential measurement has relative accuracy and remains differentially private on product states.
  • Outside the regime where DP implies gentleness, individually DP measurements can compose without preserving accuracy.Theorem 75 gives measurements that are each ε-DP on product states but whose sequential use cannot return an accurate later result.
Loading 1904.08747v1…