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 the connection between differential privacy and gentle quantum measurement, including a gap between diverse-state and identical-state shadow tomography. It proves a two-way connection on product states and develops an online, gentle QPMW protocol for shadow tomography.

  • Problem

    Shadow-tomography lower bounds faced a gap because results for diverse product states did not obviously transfer to the identical-state setting.

    Source: §6.3 · p. 58

  • Method

    The paper uses a two-way gentleness–privacy connection and a Damage Lemma with epoch-based analysis to control cumulative damage in QPMW.

    Source: §1.6 · p. 14, §4 · p. 29

  • Results

    QPMW performs shadow tomography with success probability 1 −β while using an online and (ε, δ)-gentle procedure.

    Source: §1.5 · p. 10, §6 · p. 38

  • Takeaways & Limitations

    The gentleness–privacy connection applies even to measurements far from trivial and supports online, gentle shadow tomography.

    Source: §4 · p. 29, §6 · p. 38

    Whether the product-measurement condition can be removed remains an open problem.

    Source: §1.3 · p. 8

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

This section develops a two-way connection between gentle quantum measurement and differential privacy, including its guarantees, limitations, and distinction from related results. It applies the connection to Laplace measurements, safe quantum subroutines, and shadow tomography through quantum private multiplicative weights, with analyses of both upper- and lower-bound consequences.

1.1 Gentle Measurement

  • Gentle measurement limits post-measurement damage when outcomes are predictable, formalizing an information–disturbance tradeoff that supports applications in quantum physics and computing.The paper defines α-gentleness through trace distance for every outcome, allows (α, δ)-gentleness, and commonly considers product states or all states.Source: §1.1 · pp. 3–4
  • Gentle measurements are useful because they can reveal information while preserving states for repeated verification, quantum algorithms, and other applications [4] [6].The introduction also connects them to the nonabelian hidden subgroup problem and quantum advice complexity classes such as BQP/qpoly.Source: §1.1 · pp. 3–4

1.2 Differential Privacy

  • Differential privacy balances accurate population statistics against negligible disclosure about any individual by requiring multiplicatively similar output probabilities on neighboring databases.For noisy Hamming weight, Laplace noise yields σ-DP while preserving a useful estimate when σ is not too large.Source: §1.2 · pp. 5–6

1.3 The Connection

  • Quantum differential privacy defines neighboring states through changes to one register and compares measurement-output probabilities, independently of post-measurement states.For product states, neighbors differ in at most one tensor factor; the definition also extends to (ε, δ)-DP.Source: §1.3 · pp. 6–7
  • The main framework focuses on product states because unrestricted entanglement or correlation prevents nontrivial versions of the theorem from applying broadly.On non-product states, the relevant measurements retain correct output probabilities but need not remain gentle.Source: §1.3 · pp. 7–8
  • Adding Laplace noise to an n-qubit Hamming-weight measurement makes it both gentle and private, whereas the unnoised measurement is neither.The noisy quantum measurement is σ-DP on all n-qubit states, and its gentleness follows because noise dominates intrinsic Hamming-weight variation.Source: §1.1 · pp. 4–5, §1.3 · p. 7
  • Theorem 5 gives the central two-way connection: α-gentle measurements are O(α)-DP, while product measurements that are ε-DP are O(ε√n)-gentle on product states.The second direction’s √n dependence is unavoidable, while whether the product-measurement condition can be removed remains open.Source: §1.3 · pp. 7–8
  • The connection shows that ε-differential privacy implies only O(ε√n)-gentleness in the relevant setting, while weaker bounds can force measurements close to trivial.Efficiently converting privacy into gentleness additionally requires an efficient QSampling procedure, which does not automatically follow from an efficient DP algorithm.Source: §1.3 · p. 8

1.4 Applications

  • The applications include an O(√n/σ)-gentleness guarantee for Laplace noise measurements and coherent estimation of circuit acceptance probabilities within ±1/n^O(1) inside BQP algorithms.The framework reduces broader safe-subroutine tasks to designing or locating suitable efficient DP algorithms, after which gentleness follows from the connection.Source: §1.4 · p. 9

1.5 Shadow Tomography

  • QPMW performs shadow tomography online and gently, improving Aaronson’s dependence on m from (log m)^4 to (log m)^2 while also improving running-time dependence on d.Its dependence on d and 1/ε is worse than Aaronson’s, although the authors conjecture this reflects the analysis; QPMW’s running time is roughly O(mL) + d^O(1).Source: §1.5 · pp. 10–11
  • The paper ports differential-privacy and adaptive-data-analysis results to obtain information-theoretic and computational lower bounds for gentle and online shadow tomography.The online sample complexity is optimal up to polynomial factors, and under a one-way-function assumption any online or gentle procedure needs d^Ω(1) time; these bounds also apply to the classical special case.Source: §1.5 · p. 11

1.6 Techniques

  • QPMW quantizes Private Multiplicative Weights by maintaining a hypothesis, answering close queries from it, and measuring noisy updates only when the hypothesis disagrees substantially.The analysis must control adaptively chosen measurements because the connection theorem applies only to product measurements on product states, and accumulated damage must remain negligible for most measurements.Source: §1.6 · pp. 12–14
  • No-update rounds cause damage bounded by their update probability: likely-update rounds are few, while many unlikely rounds each cause little damage after conditioning on no update.The analysis uses Laplace-measurement differential privacy and the Gaussian answer distribution induced by product states.Source: §1.6 · p. 14
  • Quantum damage is additive rather than multiplicative, so slight state corruption can disrupt the classical privacy-loss composition argument and potentially cascade into further corruption.The concern arises because small multiplicative amplitude changes can become additive changes after rotating to another basis.Source: §1.6 · p. 14
  • The Damage Lemma connects update probabilities in damaged (“real”) and fresh-copy (“ideal”) executions, enabling epoch-based bounds on total damage, gentleness, and accuracy.Epochs each have constant update probability, while the number of updates is bounded, so the number of epochs and accumulated damage remain bounded.Source: §1.6 · p. 14
  • A 0-DP measurement on product states is 0-DP on all states and therefore trivial, while incompatible-basis examples show quantum-DP composition requires caveats absent classically.The first result relies on separable mixed states having positive density among complex mixed states; the composition result also uses the Damage Lemma.Source: §1.6 · p. 15

1.7 Related Work

  • The paper is presented as the first connection between gentle quantum measurement and differential privacy, distinct from prior quantum-DP and gentle-tomography work.Zhou and Ying study channels acting on nearby quantum states, whereas this paper compares databases differing in one entry; Bennett, Harrow, and Lloyd [12] studied gentle full tomography without connecting it to DP.Source: §1.7 · pp. 15–16
  • Classical DP anticipated the paper technically through adaptive-data-analysis guarantees, but quantum measurements can irreversibly collapse states, making even many non-adaptive measurement averages challenging.The relevant classical works are Dwork et al. and Rogers et al.; the quantum setting differs physically from changes in an observer’s prior and posterior.Source: §1.7 · p. 16

2 Preliminaries

The preliminaries establish the classical and quantum notions used throughout, including states, measurements, distances, separability, product measurements, and sequential operations. They also show that privacy and gentleness guarantees for pure states extend without loss of generality to mixed states.

2.1 Classical Probability Theory

  • The paper introduces probability-distribution distance measures, including Kullback–Leibler divergence and squared Hellinger distance.Hellinger distance is highlighted as a classical measure involving square roots of probabilities.Source: §2.1 · p. 17

2.2 Quantum Information Basics

  • A d-dimensional pure quantum state is a unit vector expressed as a superposition of an orthonormal basis, with amplitudes determining computational-basis measurement probabilities.Unitary transformations preserve pure states, while projective measurements return basis outcomes and collapse the state to the observed basis vector.Source: §2.2 · pp. 17–18

2.3 Mixed States, Superoperators, Quantum Operations, and POVMs

  • Mixed states are density matrices, while superoperators, quantum operations, and POVMs respectively formalize general state transformations, conditional processes, and measurements with outcome probabilities Tr(E_iρ).A POVM specifies outcome effects but not uniquely the post-measurement states; an implementation additionally specifies operators B_i.Source: §2.3 · pp. 18–19

2.4 Separable and Entangled

  • Product states factor across registers, whereas entangled states do not; product, mixture-of-products, and LOCC measurements differ in how local POVMs and classical communication are organized.Implementing such measurements gently may require a coherent circuit over all registers to uncompute garbage, an issue that does not affect differential privacy because post-measurement garbage need not be revealed.Source: §2.4 · p. 20

2.5 Distance Between Quantum States

  • Trace distance is a metric on mixed states that generalizes classical total variation distance and equals the maximum distinguishing bias over two-outcome measurements.It is contractive under quantum operations, including discarding part of a state, and its trace norm is convex.Source: §2.5 · p. 21

2.6 Additivity of Damage

  • Sequential quantum operations have additive damage: applying operations with individual trace-distance damages ε_1,...,ε_m changes the initial state by at most ε_1 + ··· + ε_m.This establishes composition of gentle measurements, while a conditional damage lemma supports later bounds for sequences whose measurements all accept and underlies limited composition for quantum DP algorithms.Source: §2.6 · pp. 22–24

2.7 Pure vs. Mixed States

  • Differential privacy on pure product states, or on all pure states, implies the same ε-DP guarantee for mixed product states, or all mixed states.Convexity ensures the relevant maximum and minimum probability ratios are attained on pure states, including the other registers.Source: §2.7 · p. 25
  • Gentleness on pure product states, or on all pure states, likewise implies the same α-gentle guarantee for mixed product states, or all mixed states.Purifying the input, applying the same measurement implementation, and tracing out the added registers preserves the α trace-distance bound.Source: §2.7 · pp. 25–26

3 Basic Relations Among DP, Gentleness, and Triviality

This section establishes basic two-way relations between differential privacy, gentleness, and near-triviality on all quantum states. It also explains why these relations are limited, motivating the later restriction to product states.

Main connection

  • Theorem 20 shows that ε-DP implies O(εn)-gentleness, while α-gentleness for α ≤ 1/4.01 implies O(α)-DP on all states.These implications are obtained through near-triviality and hold for measurements on all states.Source: §3 · pp. 26, 29

Limitation

  • These all-state relations are limited because the proof’s mixed state ξ := (ρ + σ)/2 need not be a product state, so the connection is only interesting in a nearly trivial regime.Gentleness on product states can imply differential privacy but not triviality; the later product-state results avoid this limitation.Source: §3 · pp. 26, 28, 29

Triviality

  • ε-triviality compares every outcome probability across states, immediately implies ε-DP, and is equivalent to state-independent output probabilities when ε = 0.Unlike gentleness, triviality and differential privacy depend only on outcome probabilities, not post-measurement states.Source: §3 · p. 26

Gentleness and triviality

  • Gentleness on all states implies near-triviality, and near-triviality conversely yields (e^ε − 1)-gentleness, hence O(ε)-gentleness for ε ≤ 1.The converse constructs a measurement implementation whose conditioned post-measurement states remain close to the inputs.Source: §3 · pp. 27–28

Privacy and triviality

  • If M is ε-DP on all states, then it is 2εn-trivial; the analogous product-state statement is useful only when ε ≪ 1/n.The proof repeatedly swaps registers with a fixed state and applies differential privacy one register at a time.Source: §3 · pp. 28–29

4 Proof of Main Result

This section proves Theorem 5, establishing a two-way connection between gentleness and differential privacy for product states, including measurements far from trivial. Specifically, gentleness implies O(α)-DP, while product-measurement ε-DP implies O(ε√n)-gentleness.

4 Proof of Main Result

  • Theorem 5 establishes a two-way connection between gentleness and differential privacy on product states, even for measurements far from trivial.The two directions are proved through Lemmas 28 and 32.Source: §4 · p. 29, §4.2 · p. 34

4.1 Gentleness Implies DP on Product States

  • If M is α-gentle on product states, then M is ln-based, and therefore O(α), differentially private on product states.The proof compares post-measurement restrictions register by register and applies the preceding lemma independently for every output.Source: §4.1 · pp. 29–30

4.2 DP Implies Gentleness On Product States

  • If M is any product measurement that is ε-DP on product states, then M is O(ε√n)-gentle on product states.The proof first handles product-of-projectives measurements via classical posterior-distribution bounds, then extends the argument to POVMs using unitary dilations; the garbage register does not affect inner products.Source: §4.2 · pp. 32–34

5 Separating Examples

The section gives separating examples showing that the paper’s DP–gentleness relationships are essentially tight. Randomized response separates gentleness from DP, while noisy Hamming-weight measurements attain the required n and √n blowups in the reverse direction.

5 Separating Examples

  • The examples show that the DP–gentleness relationships proved earlier are essentially tight.The section establishes optimality through explicit measurements.Source: §5 · p. 34

5.1 Gentleness to DP

  • For one qubit, randomized response Rβ is 2β-gentle, yielding measurements that are α-gentle but fail the stated DP guarantee even on product states.Applying Rα/2 to the first qubit shows tightness up to a factor of 4 in α.Source: §5.1 · p. 35

5.2 DP to Gentleness

  • The noisy Hamming-weight measurement Lσ shows that DP on arbitrary states requires an n-factor blowup to obtain gentleness, even for product-of-projectives measurements.Specifically, L_{n/2} is not 1/3-gentle on n-qubit states, despite being DP on all n-qubit states.Source: §5.2 · p. 36
  • On product states, the same construction shows that a √n blowup is necessary for DP-to-gentleness conversion, even for product-of-projectives measurements.Using Lσ with σ = √n, the measurement is not α-gentle on n-qubit product states for any α = o(1).Source: §5.2 · pp. 36–37

6 Shadow Tomography

This section applies the DP–gentleness connection to shadow tomography through the online, gentle QPMW protocol, analyzing its accuracy across ideal, hybrid, and real executions. It also develops lower bounds for gentle and online tomography by transferring differential-privacy and adaptive-data-analysis hardness results to establish near-optimal sample-complexity requirements.

6 Shadow Tomography

  • QPMW builds on Private Multiplicative Weights and uses online quantum-state learning to perform gentle online shadow tomography with copies of an unknown state.The protocol processes known two-outcome measurements one at a time and aims to bound both estimation error and damage to the copies.Source: §6 · p. 38, §6.2 · p. 39

6.1 Online Learning of Quantum States

  • Aaronson et al. [7] showed that online quantum-state learning makes only O updates under adaptive measurement sequences, while tolerating approximate update conditions.The learner maintains a hypothesis state, updates when its prediction is sufficiently inaccurate, and can be implemented with polynomial computation per measurement.Source: §6.1 · p. 38

6.2 Online Shadow Tomography

  • Theorem 39 establishes that, for a suitable noise magnitude, QPMW is (α, δ)-gentle and achieves ε-bounded error with probability at least 1 −β given sufficiently many copies.Accuracy is transferred from an ideal fresh-copy execution to the real execution using the algorithm’s gentleness; independent repetitions reduce the error probability.Source: §6.2 · pp. 39, 43, 44
  • QPMW’s gentleness analysis groups rounds into epochs, showing each epoch causes bounded damage while triggering an update with constant probability.The analysis handles long sequences of conditioned no-update operations by relating damage to update probability, then uses damage additivity and Azuma’s inequality across epochs.Source: §6.2 · pp. 40–41
  • The online-learning conditions hold simultaneously across epochs because epoch lengths, Laplace-noise accuracy, and update behavior are controlled with high probability.The analysis bounds the total number of rounds and applies a union bound over epochs before invoking the quantum online-learning theorem.Source: §6.2 · p. 45
  • The error probability can be reduced to β by running O(log(1/β)) independent executions and taking the median answer in each round.This amplification preserves the online protocol’s per-round answer guarantee.Source: §6.2 · pp. 45, 47
  • Gentleness transfers hybrid-run accuracy to the real execution by bounding each successive hybrid’s event-probability change by αe, yielding total error τ + k·αe.The first hybrid is the real execution and the final hybrid refreshes the state between epochs; the parameter choice makes the accumulated term O(α).Source: §6.2 · p. 47
  • With small constant failure probability, real QPMW avoids premature termination and returns ε-accurate answers for every measurement.The same guarantee is established first for hybrid executions and then transferred to real executions through a hybrid argument, with accumulated gentleness bounded by O(α).Source: §6.2 · pp. 46–47
  • When the update probability λt is small, concentration-based analysis improves the disturbance caused by conditioning on “no update” beyond the generic O(σ√n) bound.Inputs are partitioned by Hamming-weight deviation; although far inputs contribute more to the KL divergence, their subgaussian probabilities decay faster, enabling the improved bound.Source: §6.2 · p. 48
  • QPMW performs accurate shadow tomography online and gently for a d-dimensional state using two-outcome measurements.The measurements E_1, . . . , E_m are processed one at a time, while the protocol estimates their acceptance probabilities with accuracy ±ε.Source: §6.3 · p. 57

6.3 Lower Bounds for Shadow Tomography

  • The lower bounds apply even to offline gentle algorithms and online non-gentle algorithms, and already hold in the classical special case.They therefore do not rely on specifically quantum-mechanical effects.Source: §6.3 · p. 57
  • Theorem 50 gives a sample-complexity lower bound for any procedure that is gentle on all product states and accurate on identical-state inputs.Thus, under the stated small-δ gentleness requirement, QPMW is optimal up to a polynomial factor.Source: §6.3 · p. 57
  • A key obstacle is that privacy-based lower bounds naturally concern diverse-state inputs, whereas shadow tomography is defined for identical states ρ⊗n.The paper closes this gap by converting identical-state accuracy into diverse-state accuracy with only a small loss in privacy parameters.Source: §6.3 · p. 58
  • Claim 52 performs the conversion by sampling with replacement from a database’s empirical distribution, preserving accuracy while worsening differential privacy only modestly.The resulting algorithm runs in O(|X|) time using one oracle call, and the privacy loss follows from group privacy plus a balls-and-bins bound.Source: §6.3 · pp. 58–59
  • Classical shadow-tomography procedures with the Chernoff-bound sample complexity necessarily violate gentleness, measured as variation-distance damage from Bayesian updating.Theorem 50 applies to the classical special case, where the required procedure cannot remain gentle.Source: §6.3 · p. 59
  • Theorem 53 shows that any online shadow-tomography procedure achieving ε-accuracy requires a nontrivial sample-complexity lower bound [35].The bound applies even without requiring gentleness.Source: Online shadow tomography · p. 59
  • QPMW achieves optimal online-shadow-tomography sample complexity up to polynomial factors, unless n = mΩ(1) or n = dΩ(1), matching Aaronson’s lower bound [6].The result concerns copies of ρ and follows from combining the online lower bound with Aaronson’s earlier bound.Source: Online shadow tomography · p. 59
  • The online lower bound is classical: it restates a result of Nissim et al. [35] and follows from adaptive-data-analysis lower bounds and computational-hardness results of Hardt and Ullman and Steinke and Ullman.Adaptive data analysis is an identical-state special case of online shadow tomography, where the goal is accurate answers without overfitting to the sample.Source: Online shadow tomography · p. 60

7 Computational Efficiency

This section examines the computational efficiency of gentle measurements and QPMW shadow tomography, including their use in quantum algorithms and the associated cryptographic barriers. It also presents an explicit Laplace-noise implementation while identifying an open question concerning efficient quantum samplers.

7 Computational Efficiency

  • The section develops computational-efficiency results for gentle measurements, QPMW shadow tomography, and cryptographic limitations on gentle or online procedures.It focuses on implementing measurements efficiently and applying the resulting tools to shadow tomography.Source: §7 · p. 60

7.1 Efficiency of DP and Gentle Measurements

  • Efficient implementation of DP-derived gentle measurements reduces to efficiently uncomputing garbage, equivalently QSampling the DP algorithm’s output distribution.The reduction can fail computationally when garbage remains entangled; fast classical sampling does not always imply fast QSampling, as noted by Aharonov and Ta-Shma and Aaronson.Source: §7.1 · pp. 60–61
  • Proposition 54 gives an O(n)-size circuit for L_σ with 1/exp(n) accuracy when σ = exp(O(n)), using reversible additive noise computation.The construction is maximally gentle for every input state, including non-product states, because its damage is only that required to learn the output.Source: §7.1 · pp. 61–62
  • Proposition 55 efficiently implements two-part gentle measurements when state preparation and output extraction can be combined with reversible uncomputation of nearly independent garbage.Theorem 56 further shows that efficient classical sampling yields efficient QSampling for distributions whose output states have polynomially sparse support, with inverse-polynomial trace-distance error.Source: §7.1 · p. 62

7.2 Efficiency of Shadow Tomography

  • QPMW’s threshold and L_σ measurements are quantum-polynomial-time when the underlying POVMs E_1,...,E_m are efficiently implementable, but QPMW still faces m-round and hypothesis-state computation costs.Its running time is roughly O(mL) + d^O(1), improving Aaronson’s [6] O(mL) + d^O(log log d) dependence on d from quasipolynomial to polynomial, while remaining linear in m because it is online.Source: §7.2 · pp. 63–64
  • Under quantum-secure symmetric-key encryption, no gentle shadow tomography procedure can run in d^o(1) · poly(m) time, even offline, classically, or only on identical-state inputs.This follows from the quantum variant of Ullman’s differential-privacy hardness result and gentleness implying differential privacy.Source: §7.2 · pp. 64–65
  • Under the same assumption, no online shadow tomography procedure can run in d^o(1) · poly(m) time, even if it is non-gentle, classical, or restricted to identical-state inputs.Theorem 59 uses the quantum extension of Steinke and Ullman ’s adaptive-query hardness, yielding Corollary 60.Source: §7.2 · pp. 65–66

7.3 Quantum Complexity Implication

  • The result provides a template for safely invoking any coherently and polynomial-time implementable DP algorithm as a subroutine inside larger quantum algorithms.The paper contrasts this with outputs encoded in amplitudes, where small estimation errors preserve state overlap and do not require gentle measurement for safe uncomputation.Source: §7.3 · pp. 66–67
  • Theorem 7 shows that BQP can coherently query an oracle estimating Pr[C accepts] to inverse-polynomial additive accuracy, by implementing the oracle itself with a gentle measurement.For polynomially many sequential queries, the per-query gentleness can be chosen so the final state is within trace distance 1/10 of the ideal-oracle output.Source: §7.3 · pp. 66–67
  • The construction applies an efficient Laplace-noise measurement, whose approximate estimates weakly entangle output and computation registers, then uncomputes the computation registers with bounded trace-distance damage.Gentleness breaks the entanglement caused by orthogonal estimate states, enabling safe uncomputation while retaining explicit probability estimates.Source: §7.3 · pp. 66–67
  • For classical randomized subroutines, Adleman’s trick uses one shared random string across all superposed inputs, avoiding unwanted entanglement while achieving simultaneous success by amplification and a union bound.The passage identifies this as a special-case solution for producing polynomial-size approximate descriptions of sparse output distributions.Source: §7.3 · pp. 67–68
  • It remains open whether general polynomial-time quantum samplers over sparse supports necessarily admit efficient coherent mappings to polynomial-size approximate descriptions of their output distributions.Adleman’s trick does not extend to quantum algorithms, motivating the possibility of using a more sophisticated DP algorithm than Laplace noise.Source: §7.3 · pp. 67–68

8 Open Problems

The open problems ask how far the differential-privacy–gentleness bridge extends, including beyond product measurements, toward classical privacy, and into local quantum privacy. They also target shadow-tomography complexity, composition, experimental feasibility, computational barriers, and safe quantum subroutines.

8 Open Problems

  • Can ε-DP on product states imply O(ε√n)-gentleness for arbitrary quantum measurements, including LOCC measurements, or can ε-triviality imply O(ε)-gentleness?The questions also ask whether the original measurement or another measurement with essentially identical product-state output probabilities can achieve this gentleness while differing on entangled states.Source: §8 · p. 68
  • Can quantum measurement theory yield new results for classical differential privacy, reversing the paper’s use of differential privacy to design QPMW?QPMW is identified as a quantum measurement procedure of independent interest derived using the DP/gentleness connection.Source: §8 · p. 68
  • How much is possible in the quantum-DP local model, and how does it relate to separately measuring each state because of experimental limitations?In the local model, each user individually obscures their state before submitting it to the database.Source: §8 · p. 68

Shadow Tomography

  • What is the true sample complexity of shadow tomography, including whether dependence on d is necessary without online or gentle requirements?The paper’s upper bound is (log m)^2 (log d)^2 /εO(1), while the best known lower bound is cited as [6]; Theorem 50 and Theorem 53 establish lower bounds under additional gentleness and online constraints, respectively.Source: Shadow Tomography · p. 69
  • Can shadow tomography use incoherent measurements on each copy separately, thereby becoming closer to experimental feasibility?The open problem specifically asks whether each copy of ρ can be measured separately.Source: Shadow Tomography · p. 69
  • Can quantum differential-privacy algorithms compose while preserving accuracy and, when possible, multiplicative privacy guarantees, including through non-black-box methods?This question distinguishes the regime where DP implies gentleness but outcome probabilities are too small for Lemma 17 from the regime where DP does not imply gentleness.Source: Shadow Tomography · p. 69
  • Does an advanced composition theorem hold for gentleness, giving O(α√k) rather than O(αk) trace-distance damage after k sequential measurements?If so, the paper suggests improving QPMW’s sample complexity from (log m)^2 (log d)^2 /εO(1) to (log m)^2 (log d) /εO(1); the comparison references.Source: Shadow Tomography · p. 69
  • Further problems ask about efficient DP algorithms lacking efficiently implementable gentle measurements, computational lower bounds for unrestricted shadow tomography, and safely using gentle procedures as quantum subroutines.The questions include conditional or unconditional black-box examples, cryptographic assumptions for d^Ω(1) computation time, and generalizations of Theorem 7.Source: Shadow Tomography · pp. 69–70

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

The appendix shows that DP, triviality, and gentleness on product or separable states can coexist with extreme failures on entangled states, while sufficiently strong product-state guarantees extend to arbitrary states in complex quantum mechanics but not real quantum mechanics.

10.1 Separations

  • Measurements can be exponentially gentle, private, or trivial on product and separable states while being extremely far from those properties on selected entangled states.The appendix gives separations for DP, triviality, and gentleness, including a measurement that is not α-gentle for any α < 1/4.01 on arbitrary states.Source: §10 · p. 73, §10.1 · pp. 74–75
  • The DP separation is specifically quantum: convex combinations preserve DP, but superpositions can produce entangled-state behavior that is not DP despite DP on product states.The examples separate DP on product states from DP on arbitrary states, including for mixture-of-products measurements; the classical analogue does not exhibit this separation.Source: §10.1 · pp. 74–75

10.2 Relationships

  • This exact extension fails for real-amplitude qubits: a two-rebit measurement is constant on product and separable states but accepts an entangled state with certainty.The appendix identifies this as a phenomenon that differs fundamentally between qubits and rebits.Source: §10.2 · pp. 75–76
  • In complex quantum mechanics, exact 0-triviality, 0-DP, or 0-gentleness on all product states implies 0-triviality on all states.The argument extends the property from product states to separable mixed states and then uses the positive density of separable states to make the associated linear functional constant everywhere.Source: §10.2 · pp. 75–76
  • For ordinary complex quantum mechanics, sufficiently small ε-triviality on product states yields approximate triviality on arbitrary states, with the threshold depending exponentially on the number of registers.The result uses the fact that a suitable mixture with the maximally mixed state is separable, then transfers the product-state guarantee to all states.Source: §10.2 · p. 77

11 Appendix: General Neighbor Relations

The appendix distinguishes superoperator, unitary, and conditioned neighbor relations for general quantum states, showing that unitary-neighbor DP is nearly equivalent to superoperator-neighbor DP, whereas conditioned-neighbor DP becomes trivial.

General neighbor relations

  • For product states, superoperator neighboring is equivalent to changing a single tensor factor, but this equivalence is not evidently canonical for correlated or entangled states.The appendix motivates the broader definitions because single-register changes admit multiple inequivalent formulations beyond product states.Source: §11 · p. 77
  • The three relations form a strict hierarchy: unitary neighbors imply superoperator neighbors, which imply conditioned neighbors, but not conversely for general states.The appendix gives correlated-state examples separating each inclusion.Source: §11 · p. 78
  • ε-DP on all states with respect to postselected neighbors is 4ε-trivial, so conditioned-neighbor privacy collapses the framework.The proof connects arbitrary mixed states through postselection on a shared measured state and chains the resulting privacy inequalities.Source: §11 · p. 78
  • Unitary-neighbor ε-DP implies 2ε-DP for superoperator neighbors, both on product states and on arbitrary states.This establishes that replacing superoperator neighbors with unitary neighbors changes only the privacy parameter by a factor of two.Source: §11 · p. 78

12 Appendix: Differential Privacy Beyond Product and LOCC Measurements

The appendix constructs a quantum measurement that is differentially private on all states but cannot be approximated by mixture-of-products measurements, ruling out a broad structure theorem. It also conjectures a related differentially private measurement requiring entangling operations beyond LOCC.

Beyond LOCC

  • The appendix conjectures that a modified differentially private measurement M′ cannot even be implemented approximately by LOCC measurements.M′ replaces direct pair-state tests with swap tests arranged in nested blocks and combines their parities with Laplace noise.Source: §12 · pp. 79, 81

Non-product measurements

  • The obstruction is that fixed local measurements cannot simultaneously distinguish |0⟩|0⟩ from |0⟩|1⟩ and |1⟩|+⟩ from |1⟩|−⟩ with certainty.The required second-qubit basis depends on the first-qubit outcome, which product measurements cannot adapt to.Source: §12 · pp. 79–80
  • A differentially private measurement on n qubits cannot be approximated by any mixture-of-products measurement.Theorem 72 constructs this measurement, while Lemma 71 supplies the two-qubit obstruction underlying the construction.Source: §12 · pp. 79–80
  • Choosing block size k := C log n makes mixture-of-products measurements’ parity-guessing bias fall below 1/n^3, while the noisy parity sum remains informative.The construction groups qubits into blocks, computes block parities, and adds Laplace noise; the parity hardness follows from constant local noise and exponential decay.Source: §12 · pp. 80–81

Beyond LOCC

  • The LOCC conjecture rests on swap-test limitations: Gaussian noise can hide rare failures, whereas true swap tests preserve enough signal to compute block parity.The proposed separation is that LOCC cannot compute the summed parities even noisily, while entangling swap tests can do so with high success probability.Source: §12 · p. 82

13 Appendix: On Composition of Quantum DP Algorithms

This appendix studies when sequential quantum-DP measurements compose, using the DP–gentleness connection to obtain limited positive results but also exhibiting a failure of composition. Composition preserves accuracy and privacy under additional gentleness and outcome-probability conditions, whereas outside the relevant regime even accuracy can fail.

Composition challenge

  • Gentleness composes additively by the triangle inequality, but privacy may fail because later measurements act on damaged states rather than the original product state.The appendix notes that information amplification into other registers could destroy privacy under subsequent measurements, while conjecturing that suitable implementations may preserve it.Source: §13 · pp. 82–83

Limited composition

  • Proposition 73 gives limited composition: sequential measurements that are ε_i-DP and α_i-gentle on product states remain accurate and ε-DP when every outcome sequence has sufficiently large probability.The required probability lower bound p must satisfy p ≫ α_1 + ··· + α_k; relative accuracy scales as (α_1 + ··· + α_k)/p.Source: §13 · p. 83

Product-measurement corollary

  • Corollary 74 removes gentleness as a separate assumption for product measurements, combining DP-to-gentleness with Proposition 73 to obtain approximate accuracy and privacy for sequential composition.It assumes total ε := ε_1 + ··· + ε_k is at most 1/n and imposes a lower bound on the product of outcome probabilities.Source: §13 · pp. 83–84

Failure of composition

  • Theorem 75 shows failure of composition: two measurements can each be ε-DP on product states, yet no implementation of the first enables accurate later output from the second.The failure occurs even without conditioning on the first outcome; the theorem applies when ε = O(...) as stated in the supplied passage.Source: §13 · p. 84

Failure construction

  • The counterexample uses randomized response followed by a noisy Hadamard-basis measurement: the first measurement damages phase information, making the second measurement inaccurate when 1/ε exceeds the stated n-dependent threshold.Independent bit flips corrupt the information needed to estimate the number of |+⟩ qubits, and the passage states impossibility when 1/ε is greater than n^1/4.Source: §13 · p. 84

Open questions

  • Open questions concern intermediate ε regimes, measurements with few outcomes, and more flexible composition that changes the order or otherwise modifies the algorithms.The appendix specifically asks about the range between 1/n and 1/n^1/4 and about reversing the prescribed measurement order.Source: §13 · pp. 84–85

Related papers

Loading 1904.08747v1…