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:2610.02113

Quantum Advantage for Two-Party Differential Privacy

Daniel Alabi, Emil T. Khabiboulline

quant-phcs.CRcs.ITSubmitted Oct 1, 2026• Announced Oct 2, 2026• 0 citations
arXivHTMLPDF

Abstract

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 $Ω(\sqrt{n})$ error under pure differential privacy and $Ω(\sqrt{n}/\log n)$ 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 $\varepsilon$ quantum differential privacy (QDP) and expected error at most $\frac{2}{\sinh \varepsilon}+γ$, for every $γ>0$. For approximate $(\varepsilon, δ)$ QDP, an exact hockey-stick divergence calculation yields strictly smaller error, while preserving the $O(1)$-versus-$Ω(\sqrt{n}/\log n)$ 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.

AI Summary

The paper asks whether quantum communication can overcome classical information-theoretic accuracy limits for two-party differentially private Hamming-distance estimation, with both parties required to produce the same output. It studies privacy of terminal views under Klauck-honest nonpreemptive (KHNP) strategies: observers may retain private systems but must preserve every prescribed outgoing message exactly and complete the protocol. For inputs of length $n$, it constructs a pure $\varepsilon$-quantum-DP protocol using $O(n)$ communication and achieving expected absolute error below $2/\sinh\varepsilon+\gamma$ for any $\gamma>0$. For suitable constant privacy parameters, this contrasts with classical KHNP lower bounds of $\Omega(\sqrt n)$ under pure privacy and $\Omega(\sqrt n/\log n)$ under strong approximate privacy, with $\delta=o(1/n)$. The construction combines independent cyclic-geometric noise shares with a coherent round trip. A small input-independent guard makes all input encodings nonorthogonal. Equality of the incoming and prescribed outgoing Gram matrices forces an exactly message-preserving observer’s retained complementary state to be input-independent. Privacy then follows by postprocessing an ideal noisy-release functionality. An exact finite-cycle hockey-stick-divergence calculation calibrates a larger noise parameter $\alpha_n^\star>\varepsilon$, giving the approximate-privacy error bound $2/\sinh\alpha_n^\star+\gamma$. The separation depends on exact message preservation, classical inputs and private random tapes, and idealized exact local operations. The protocol fails against measurement-and-abort attacks and provides neither malicious nor simulation-based security. Weaker prescribed-channel privacy already permits an exact classical realization. For arbitrary retention-capable adversaries, the paper supplies a classical $O(\sqrt n)$-error baseline; a quantum accuracy advantage remains open.

Likely largely AI-generatedAI use disclosedStrong assumptions
using GPT 5.6 Sol, the authors optimized the noise mechanism to obtain a more accurate approximate DP protocol.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
15 + 7 pages, 2 figures. Also on ePrint

Related papers

Quantum Information Ordering and Differential Privacy

Naqueeb Ahmad Warsi, Ayanava Dasgupta, Masahito Hayashi

We study quantum differential privacy (QDP) by defining a notion of the order of informativeness between two pairs of quantum states. In particular, we show that if the hypothesis testing divergence of the one pair dominates over that of the other pair, then this dominance holds for every $f$-divergence. This approach completely characterizes $(\varepsilon,δ)$-QDP mechanisms by identifying the most informative $(\varepsilon,δ)$-DP quantum state pairs. We apply this to study precise limits for privatized hypothesis testing and privatized quantum parameter estimation, including tight upper-bounds on the quantum Fisher information under QDP. Finally, we establish near-optimal contraction bounds for differentially private quantum channels with respect to the Hockey-Stick divergence.

quant-pharXiv:2511.01467•IEEE Transactions on Information Theory•Nov 4, 2025•8 citations

Differentially private quantum sensor networks

Daniel J. Spencer, Kaiyan Shi, Emil T. Khabiboulline +2 more

Quantum sensing is a promising technology capable of demonstrating clear advantage over comparable classical techniques for precise measurement. One application of quantum sensing is in function estimation, which can be done using a network of entangled quantum sensors, allowing for measurements with greater optimal sensitivity than unentangled sensing protocols. In cases where quantum sensor networks will be used to measure data that should remain private (e.g., biomedical data), it is imperative that these protocols include a privacy mechanism to hide sensitive information. In this work, we show that entangled sensor networks are vulnerable to certain privacy-violating attacks. To mitigate these attacks, we introduce secure sensing protocols endowed with differential privacy. We reconcile differential privacy with retaining Heisenberg-limited scaling, and introduce several protocols achieving varying balances between the two. We show that our main protocol, an $n$-node network sensing protocol that injects noise directly into the sensing Hamiltonian, exhibits a tradeoff between the desirable $O(1/n^2)$ Heisenberg scaling of the mean-squared error of the function estimate and the level of privacy attainable. Under assumptions on the network (a common source of randomness and a constant fraction of honest parties), we show that this protocol is locally implementable and achieves $(O(1), δ)$-differential privacy for arbitrarily small $δ$ while retaining Heisenberg scaling of the mean-squared error. We prove that our protocols are resilient to attacks by broad classes of classical and quantum adversaries, and find advantages in the privacy-utility tradeoff when using quantum techniques.

quant-pharXiv:2607.06521•Jul 8, 2026•1 citation

When Does Quantum Differential Privacy Compose?

Daniel Alabi, Theshani Nuradha

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.

quant-pharXiv:2601.00337•Leibniz international proceedings in informatics•Jan 2, 2026•4 citations

Quantum Differential Privacy in the Local Model

Armando Angrisani, Elham Kashefi

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

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

High quantum local differential privacy breaks entanglement

Sujeet Bhalerao, Theshani Nuradha, Felix Leditzky

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 $\varepsilon$-QLDP channel with a $d$-dimensional input is entanglement-breaking whenever $\varepsilon\leq\log\frac{d}{d-1}$. We also prove an approximate version for $(\varepsilon,δ)$-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.

quant-pharXiv:2609.13418•Sep 15, 2026•0 citations

On Quantum Advantage in Information Theoretic Single-Server PIR

Dorit Aharonov, Zvika Brakerski, Kai-Min Chung +3 more

In (single-server) Private Information Retrieval (PIR), a server holds a large database $DB$ of size $n$, and a client holds an index $i \in [n]$ and wishes to retrieve $DB[i]$ without revealing $i$ to the server. It is well known that information theoretic privacy even against an `honest but curious' server requires $Ω(n)$ communication complexity. This is true even if quantum communication is allowed and is due to the ability of such an adversarial server to execute the protocol on a superposition of databases instead of on a specific database (`input purification attack'). Nevertheless, there have been some proposals of protocols that achieve sub-linear communication and appear to provide some notion of privacy. Most notably, a protocol due to Le Gall (ToC 2012) with communication complexity $O(\sqrt{n})$, and a protocol by Kerenidis et al. (QIC 2016) with communication complexity $O(\log(n))$, and $O(n)$ shared entanglement. We show that, in a sense, input purification is the only potent adversarial strategy, and protocols such as the two protocols above are secure in a restricted variant of the quantum honest but curious (a.k.a specious) model. More explicitly, we propose a restricted privacy notion called \emph{anchored privacy}, where the adversary is forced to execute on a classical database (i.e. the execution is anchored to a classical database). We show that for measurement-free protocols, anchored security against honest adversarial servers implies anchored privacy even against specious adversaries. Finally, we prove that even with (unlimited) pre-shared entanglement it is impossible to achieve security in the standard specious model with sub-linear communication, thus further substantiating the necessity of our relaxation. This lower bound may be of independent interest (in particular recalling that PIR is a special case of Fully Homomorphic Encryption).

arXiv:1902.09768•Feb 26, 2019•0 citations
We introduce information-theoretically private quantum protocols for two-party Hamming distance when both parties must output the same estimate. Classically, for input length nnn, information-theoretic protocols require Ω(n)Ω(\sqrt{n})Ω(n​) error under pure differential privacy and Ω(n/log⁡n)Ω(\sqrt{n}/\log n)Ω(n​/logn) error under strong approximate differential privacy, whereas computational security permits O(1)O(1)O(1) error. In Klauck's honest, nonpreemptive, message-preserving model, we give an O(n)O(n)O(n)-communication quantum protocol with pure ε\varepsilonε quantum differential privacy (QDP) and expected error at most 2sinh⁡ε+γ\frac{2}{\sinh \varepsilon}+γsinhε2​+γ, for every γ>0γ>0γ>0. For approximate (ε,δ)(\varepsilon, δ)(ε,δ) QDP, an exact hockey-stick divergence calculation yields strictly smaller error, while preserving the O(1)O(1)O(1)-versus-Ω(n/log⁡n)Ω(\sqrt{n}/\log n)Ω(n​/logn) separation for δ=o(1/n)δ=o(1/n)δ=o(1/n). Thus, quantum communication achieves O(1)O(1)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.
The paper asks whether quantum communication can overcome classical information-theoretic accuracy limits for two-party differentially private Hamming-distance estimation, with both parties required to produce the same output. It studies privacy of terminal views under Klauck-honest nonpreemptive (KHNP) strategies: observers may retain private systems but must preserve every prescribed outgoing message exactly and complete the protocol.
For inputs of length nnn, it constructs a pure ε\varepsilonε-quantum-DP protocol using O(n)O(n)O(n) communication and achieving expected absolute error below 2/sinh⁡ε+γ2/\sinh\varepsilon+\gamma2/sinhε+γ for any γ>0\gamma>0γ>0. For suitable constant privacy parameters, this contrasts with classical KHNP lower bounds of Ω(n)\Omega(\sqrt n)Ω(n​) under pure privacy and Ω(n/log⁡n)\Omega(\sqrt n/\log n)Ω(n​/logn) under strong approximate privacy, with δ=o(1/n)\delta=o(1/n)δ=o(1/n).
The construction combines independent cyclic-geometric noise shares with a coherent round trip. A small input-independent guard makes all input encodings nonorthogonal. Equality of the incoming and prescribed outgoing Gram matrices forces an exactly message-preserving observer’s retained complementary state to be input-independent. Privacy then follows by postprocessing an ideal noisy-release functionality. An exact finite-cycle hockey-stick-divergence calculation calibrates a larger noise parameter αn⋆>ε\alpha_n^\star>\varepsilonαn⋆​>ε, giving the approximate-privacy error bound 2/sinh⁡αn⋆+γ2/\sinh\alpha_n^\star+\gamma2/sinhαn⋆​+γ.
The separation depends on exact message preservation, classical inputs and private random tapes, and idealized exact local operations. The protocol fails against measurement-and-abort attacks and provides neither malicious nor simulation-based security. Weaker prescribed-channel privacy already permits an exact classical realization. For arbitrary retention-capable adversaries, the paper supplies a classical O(n)O(\sqrt n)O(n​)-error baseline; a quantum accuracy advantage remains open.
We study quantum differential privacy (QDP) by defining a notion of the order of informativeness between two pairs of quantum states. In particular, we show that if the hypothesis testing divergence of the one pair dominates over that of the other pair, then this dominance holds for every fff-divergence. This approach completely characterizes (ε,δ)(\varepsilon,δ)(ε,δ)-QDP mechanisms by identifying the most informative (ε,δ)(\varepsilon,δ)(ε,δ)-DP quantum state pairs. We apply this to study precise limits for privatized hypothesis testing and privatized quantum parameter estimation, including tight upper-bounds on the quantum Fisher information under QDP. Finally, we establish near-optimal contraction bounds for differentially private quantum channels with respect to the Hockey-Stick divergence.
Quantum sensing is a promising technology capable of demonstrating clear advantage over comparable classical techniques for precise measurement. One application of quantum sensing is in function estimation, which can be done using a network of entangled quantum sensors, allowing for measurements with greater optimal sensitivity than unentangled sensing protocols. In cases where quantum sensor networks will be used to measure data that should remain private (e.g., biomedical data), it is imperative that these protocols include a privacy mechanism to hide sensitive information. In this work, we show that entangled sensor networks are vulnerable to certain privacy-violating attacks. To mitigate these attacks, we introduce secure sensing protocols endowed with differential privacy. We reconcile differential privacy with retaining Heisenberg-limited scaling, and introduce several protocols achieving varying balances between the two. We show that our main protocol, an nnn-node network sensing protocol that injects noise directly into the sensing Hamiltonian, exhibits a tradeoff between the desirable O(1/n2)O(1/n^2)O(1/n2) Heisenberg scaling of the mean-squared error of the function estimate and the level of privacy attainable. Under assumptions on the network (a common source of randomness and a constant fraction of honest parties), we show that this protocol is locally implementable and achieves (O(1),δ)(O(1), δ)(O(1),δ)-differential privacy for arbitrarily small δδδ while retaining Heisenberg scaling of the mean-squared error. We prove that our protocols are resilient to attacks by broad classes of classical and quantum adversaries, and find advantages in the privacy-utility tradeoff when using quantum techniques.
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 provides a robust framework for protecting sensitive data, while maintaining its utility for computation. In essence, a differentially private algorithm takes as input the data of multiple parties, and returns an output disclosing minimal information about any individual party. Previous research has introduced several quantum extensions of differential privacy, with applications ranging from quantum machine learning on private classical data to quantum shadow tomography. However, the local model of quantum differential privacy – where each party is responsible for privatizing their own data at a local level – has received limited attention. This work delves into locally differentially private quantum measurements. Although any measurement can be made locally differentially private by adding noise to the outcome, we demonstrate that certain quantum measurements inherently satisfy some degree of local differential privacy for specific classes of input states. This finding has two significant implications: first, limiting the analysis to classical noise injection mechanisms may lead to suboptimal privacy-utility trade-offs for quantum data; second, the theory of differential privacy can be harnessed to further investigate the capabilities of quantum measurements. Motivated by these insights, we establish strong data processing inequalities for the quantum relative entropy under local differential privacy and apply these results to asymmetric hypothesis testing of quantum states with restricted measurements. Additionally, we prove an equivalence between quantum statistical queries and quantum differential privacy in the local model, thereby addressing an open question posed by Arunachalam et al. (2021). Finally, we consider the task of quantum multi-party computation under local differential privacy, demonstrating that parity functions can be efficiently learned in this model, whereas the corresponding classical task requires exponentially many samples.
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 ε\varepsilonε-QLDP channel with a ddd-dimensional input is entanglement-breaking whenever ε≤log⁡dd−1\varepsilon\leq\log\frac{d}{d-1}ε≤logd−1d​. We also prove an approximate version for (ε,δ)(\varepsilon,δ)(ε,δ)-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.
In (single-server) Private Information Retrieval (PIR), a server holds a large database DBDBDB of size nnn, and a client holds an index i∈[n]i \in [n]i∈[n] and wishes to retrieve DB[i]DB[i]DB[i] without revealing iii to the server. It is well known that information theoretic privacy even against an `honest but curious' server requires Ω(n)Ω(n)Ω(n) communication complexity. This is true even if quantum communication is allowed and is due to the ability of such an adversarial server to execute the protocol on a superposition of databases instead of on a specific database (`input purification attack'). Nevertheless, there have been some proposals of protocols that achieve sub-linear communication and appear to provide some notion of privacy. Most notably, a protocol due to Le Gall (ToC 2012) with communication complexity O(n)O(\sqrt{n})O(n​), and a protocol by Kerenidis et al. (QIC 2016) with communication complexity O(log⁡(n))O(\log(n))O(log(n)), and O(n)O(n)O(n) shared entanglement. We show that, in a sense, input purification is the only potent adversarial strategy, and protocols such as the two protocols above are secure in a restricted variant of the quantum honest but curious (a.k.a specious) model. More explicitly, we propose a restricted privacy notion called \emph{anchored privacy}, where the adversary is forced to execute on a classical database (i.e. the execution is anchored to a classical database). We show that for measurement-free protocols, anchored security against honest adversarial servers implies anchored privacy even against specious adversaries. Finally, we prove that even with (unlimited) pre-shared entanglement it is impossible to achieve security in the standard specious model with sub-linear communication, thus further substantiating the necessity of our relaxation. This lower bound may be of independent interest (in particular recalling that PIR is a special case of Fully Homomorphic Encryption).