We develop an information-theoretic framework connecting stability, privacy, and generalization for quantum learning algorithms. Learning procedures are modeled as quantum instruments with classical-quantum outputs, and losses are represented by observables. We prove that under a classical-quantum sub-Gaussian condition, an information-theoretic stability measure controls the expected generalization error. Furthermore, we establish a high-probability generalization bound using quantum Rényi divergences to manage higher-order dependencies under non-commutativity.
In the trusted Data Processor setting, quantum differential privacy (QDP) provides a mechanism for stability. We show that one-neighbor QDP strictly bounds the information leaked by the classical-quantum output. Combining this with our stability theorem yields a direct privacy-to-generalization guarantee.
We also explore an untrusted Data Processor setting. Here, output privacy alone is insufficient since an adversarial processor could perform a highly informative procedure before applying noisy post-processing. To combat this, we introduce Information-Theoretic Admissibility (ITA), a certification condition ensuring the prescribed procedure is not just a degraded version of a strictly more informative, physically allowed operation on the encoded ensemble. We prove a fundamental separation: while admissibility and privacy are in strong tension in classical models, quantum non-orthogonality makes them compatible. A quantum measurement can be ITA - exhausting all relevant accessible information - without perfectly recovering the classical dataset. We illustrate this separation through a concrete quantum ITA example.
AI Summary
The paper studies when privacy and limited information leakage imply generalization for quantum learning, distinguishing trusted processors from adversarial processors that receive only quantum-encoded data. Learning algorithms are modeled as instruments producing a classical hypothesis $W$ and residual quantum output $B'$; losses are observables on evaluation and output systems.
Under a single classical–quantum sub-Gaussian condition with variance proxy $\alpha^2$, it proves $|\hat L-L|\leq\sqrt{2\alpha^2 I(S\mathrm{Te};WB')}$. The proof combines a relative-entropy variational bound with the loss moment-generating-function assumption. For i.i.d. data, tensor-product processing, additive losses, and conditional local sub-Gaussianity, a probability-$1-\eta$ bound replaces the information term by $\widetilde D_\gamma+\frac{\gamma}{\gamma-1}\ln(2/\eta)$ and includes a prefactor $2\alpha^2/n$ inside the square root, using noncommutative Hölder and Araki–Lieb–Thirring inequalities.
For permutation-invariant, support-consistent one-neighbor $(\varepsilon,\delta)$-private algorithms, a type-grid covering argument gives $I(S;WB')\leq(d-1)\ln(ne\varepsilon)+h_d(\varepsilon,\delta)$ for $1/n\leq\varepsilon<1$, where $d$ is the data-alphabet size and $h_d(\varepsilon,0)=0$. This privacy analysis takes the evaluation system to be trivial and requires the accumulated group-privacy error to remain below one.
For untrusted processors, information-theoretic admissibility excludes strictly more informative instruments under ensemble-dependent, branch-wise residual-output post-processing. Commuting inputs make admissibility require input-state recoverability; a nonorthogonal encoding with a Hamming-weight projective instrument illustrates admissibility without perfect classical-label recovery. Admissibility is explicitly not itself privacy, and the example is presented as a conceptual separation rather than a practical protocol.
Central claim may not hold: The privacy-to-stability theorem applies only under additional regularity and symmetry assumptions and with a trivial testing system, so it does not establish the abstract's broad implication for the full learning model.
The approximate-privacy overhead depends on an inadequately specified constant m, leaving the advertised bound solely in terms of dataset size, alphabet size, and privacy parameters unjustified.
The proposed quantum ITA example violates both support consistency and permutation invariance at n=2 and p=1/4, and a neighboring-output distinguishing event additionally forces delta to be at least 3/8.
Branch-wise ITA compares only instruments with identical classical outcome probabilities and therefore does not certify privacy against arbitrary alternative processing by an untrusted processor.
The high-probability theorem's classical-limit remark incorrectly equates Rényi divergence against the fixed product of marginals with Sibson mutual information.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
Comments
36 pages, 3 figures; The introduction has been substantially rewritten to provide better context, and certain proofs have been relocated from the appendices to the main body of the paper; The core mathematical framework and technical results remain unchanged
We develop an information-theoretic framework connecting stability, privacy, and generalization for quantum learning algorithms. Learning procedures are modeled as quantum instruments with classical-quantum outputs, and losses are represented by observables. We prove that under a classical-quantum sub-Gaussian condition, an information-theoretic stability measure controls the expected generalization error. Furthermore, we establish a high-probability generalization bound using quantum Rényi divergences to manage higher-order dependencies under non-commutativity.
In the trusted Data Processor setting, quantum differential privacy (QDP) provides a mechanism for stability. We show that one-neighbor QDP strictly bounds the information leaked by the classical-quantum output. Combining this with our stability theorem yields a direct privacy-to-generalization guarantee.
We also explore an untrusted Data Processor setting. Here, output privacy alone is insufficient since an adversarial processor could perform a highly informative procedure before applying noisy post-processing. To combat this, we introduce Information-Theoretic Admissibility (ITA), a certification condition ensuring the prescribed procedure is not just a degraded version of a strictly more informative, physically allowed operation on the encoded ensemble. We prove a fundamental separation: while admissibility and privacy are in strong tension in classical models, quantum non-orthogonality makes them compatible. A quantum measurement can be ITA - exhausting all relevant accessible information - without perfectly recovering the classical dataset. We illustrate this separation through a concrete quantum ITA example.
The paper studies when privacy and limited information leakage imply generalization for quantum learning, distinguishing trusted processors from adversarial processors that receive only quantum-encoded data. Learning algorithms are modeled as instruments producing a classical hypothesis W and residual quantum output B′; losses are observables on evaluation and output systems.
Under a single classical–quantum sub-Gaussian condition with variance proxy α2, it proves ∣L^−L∣≤2α2I(STe;WB′). The proof combines a relative-entropy variational bound with the loss moment-generating-function assumption. For i.i.d. data, tensor-product processing, additive losses, and conditional local sub-Gaussianity, a probability-1−η bound replaces the information term by Dγ+γ−1γln(2/η) and includes a prefactor 2α2/n inside the square root, using noncommutative Hölder and Araki–Lieb–Thirring inequalities.
For permutation-invariant, support-consistent one-neighbor (ε,δ)-private algorithms, a type-grid covering argument gives I(S;WB′)≤(d−1)ln(neε)+hd(ε,δ) for 1/n≤ε<1, where d is the data-alphabet size and hd(ε,0)=0. This privacy analysis takes the evaluation system to be trivial and requires the accumulated group-privacy error to remain below one.
For untrusted processors, information-theoretic admissibility excludes strictly more informative instruments under ensemble-dependent, branch-wise residual-output post-processing. Commuting inputs make admissibility require input-state recoverability; a nonorthogonal encoding with a Hamming-weight projective instrument illustrates admissibility without perfect classical-label recovery. Admissibility is explicitly not itself privacy, and the example is presented as a conceptual separation rather than a practical protocol.
Composition is a cornerstone of classical differential privacy, enabling strong end-to-end guarantees for complex algorithms through composition theorems (e.g., basic and advanced). In the quantum setting, however, privacy is defined operationally against arbitrary measurements, and classical composition arguments based on scalar privacy-loss random variables no longer apply. As a result, it has remained unclear when meaningful composition guarantees can be obtained for quantum differential privacy (QDP).
In this work, we clarify both the limitations and possibilities of composition in the quantum setting. We first show that classical-style composition fails in full generality for POVM-based approximate QDP: even quantum channels that are individually perfectly private can completely lose privacy when combined through correlated joint implementations. We then identify a setting in which clean composition guarantees can be restored. For tensor-product channels acting on product neighboring inputs, we introduce a quantum moments accountant based on an operator-valued notion of privacy loss and a matrix moment-generating function. Although the resulting Rényi-type divergence does not satisfy a data-processing inequality, we prove that controlling its moments suffices to bound measured Rényi divergence, yielding operational privacy guarantees against arbitrary measurements. This leads to advanced-composition-style bounds with the same leading-order behavior as in the classical theory.
Our results demonstrate that meaningful composition theorems for quantum differential privacy require carefully articulated structural assumptions on channels, inputs, and adversarial measurements, and provide a principled framework for understanding which classical ideas do and do not extend to the quantum setting.
Differential privacy has been an exceptionally successful concept when it comes to providing provable security guarantees for classical computations. More recently, the concept was generalized to quantum computations. While classical computations are essentially noiseless and differential privacy is often achieved by artificially adding noise, near-term quantum computers are inherently noisy and it was observed that this leads to natural differential privacy as a feature. In this work we discuss quantum differential privacy in an information theoretic framework by casting it as a quantum divergence. A main advantage of this approach is that differential privacy becomes a property solely based on the output states of the computation, without the need to check it for every measurement. This leads to simpler proofs and generalized statements of its properties as well as several new bounds for both, general and specific, noise models. In particular, these include common representations of quantum circuits and quantum machine learning concepts. Here, we focus on the difference in the amount of noise required to achieve certain levels of differential privacy versus the amount that would make any computation useless. Finally, we also generalize the classical concepts of local differential privacy, Rényi differential privacy and the hypothesis testing interpretation to the quantum setting, providing several new properties and insights.
Learning tasks play an increasingly prominent role in quantum information and computation. They range from fundamental problems such as state discrimination and metrology over the framework of quantum probably approximately correct (PAC) learning, to the recently proposed shadow variants of state tomography. However, the many directions of quantum learning theory have so far evolved separately. We propose a general mathematical formalism for describing quantum learning by training on classical-quantum data and then testing how well the learned hypothesis generalizes to new data. In this framework, we prove bounds on the expected generalization error of a quantum learner in terms of classical and quantum information-theoretic quantities measuring how strongly the learner's hypothesis depends on the specific data seen during training. To achieve this, we use tools from quantum optimal transport and quantum concentration inequalities to establish non-commutative versions of decoupling lemmas that underlie recent information-theoretic generalization bounds for classical machine learning. Our framework encompasses and gives intuitively accessible generalization bounds for a variety of quantum learning scenarios such as quantum state discrimination, PAC learning quantum states, quantum parameter estimation, and quantumly PAC learning classical functions. Thereby, our work lays a foundation for a unifying quantum information-theoretic perspective on quantum learning.
Learning tasks play an increasingly prominent role in quantum information and computation. They range from fundamental problems such as state discrimination and metrology over the framework of quantum probably approximately correct (PAC) learning, to the recently proposed shadow variants of state tomography. However, the many directions of quantum learning theory have so far evolved separately. We propose a general mathematical formalism for describing quantum learning by training on classical-quantum data and then testing how well the learned hypothesis generalizes to new data. In this framework, we prove bounds on the expected generalization error of a quantum learner in terms of classical and quantum information-theoretic quantities measuring how strongly the learner's hypothesis depends on the specific data seen during training. To achieve this, we use tools from quantum optimal transport and quantum concentration inequalities to establish non-commutative versions of decoupling lemmas that underlie recent information-theoretic generalization bounds for classical machine learning. Our framework encompasses and gives intuitively accessible generalization bounds for a variety of quantum learning scenarios such as quantum state discrimination, PAC learning quantum states, quantum parameter estimation, and quantumly PAC learning classical functions. Thereby, our work lays a foundation for a unifying quantum information-theoretic perspective on quantum learning.
Differential privacy provides a mathematical framework for guaranteeing privacy for sensitive data. In quantum information processing, the interaction of privacy constraints with quantum resources such as entanglement remains a question of interest. Given that the utility of many protocols, and often the presence of a quantum advantage, relies on quantum resources such as entanglement, it is crucial to understand when a privacy requirement for a quantum channel is compatible with the channel's ability to preserve entanglement. We study this question for quantum local differential privacy (QLDP). Our main result shows that every ε-QLDP channel with a d-dimensional input is entanglement-breaking whenever ε≤logd−1d. We also prove an approximate version for (ε,δ)-QLDP, where channels in the same high-privacy regime are close in diamond norm to an entanglement-breaking channel. We further prove a composition result for a collection of private quantum channels having entangled inputs and global measurements in the high-privacy regime. Finally, we apply our results to private quantum learning theory. We prove that any learning protocol using arbitrary quantum memory on copies of the output of an entanglement-breaking channel can be simulated by a protocol that measures the corresponding unprocessed input copies one at a time while storing only classical information. Combining this result with our high-privacy entanglement-breaking theorem, we show that under sufficiently private local noise, a learning protocol with quantum memory for purity testing and bipartite product testing is subject to the sample complexity lower bounds for protocols with single-copy measurements on the noiseless tasks. We also obtain stronger sample complexity lower bounds when a single highly private channel acts on the entire multipartite input.
We introduce information-theoretically private quantum protocols for two-party Hamming distance when both parties must output the same estimate. Classically, for input length n, information-theoretic protocols require Ω(n) error under pure differential privacy and Ω(n/logn) error under strong approximate differential privacy, whereas computational security permits O(1) error. In Klauck's honest, nonpreemptive, message-preserving model, we give an O(n)-communication quantum protocol with pure ε quantum differential privacy (QDP) and expected error at most sinhε2+γ, for every γ>0. For approximate (ε,δ) QDP, an exact hockey-stick divergence calculation yields strictly smaller error, while preserving the O(1)-versus-Ω(n/logn) separation for δ=o(1/n). Thus, quantum communication achieves O(1) information-theoretic error, matching the accuracy available classically only under computational assumptions.
The main construction uses a guarded coherent round trip and an equal-Gram rigidity principle that prevents an honest player from retaining input-dependent complementary information. We separate this model from weaker prescribed-channel privacy, which already admits an exact classical realization, and from fully retention-robust security, against which measurement-and-abort attacks remain possible. Therefore, we identify preservation of non-orthogonal quantum messages as a resource for privacy.