tl;dr Emil (my roommate while I was at Harvard) and I recently released work on how to obtain a quantum (accuracy) advantage for two-party differential privacy. Classically, there is a lower bound on how accurate any mechanism can be for two-party differential privacy. It turns out that we can circumvent that lower bound with the use of quantum communication!
Suppose we have two laboratories that hold confidential yes-or-no (i.e., for the presence or absence of a viral infection) test results for the same set of study participants. The labs want to know how often their results disagree, without exchanging everyone’s individual results. Both laboratories should finish with the same estimate.
| Study participant | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| Laboratory A | Yes | No | Yes | Yes |
| Laboratory B | Yes | Yes | No | Yes |
In this example, the laboratories disagree on participants 2 and 3, so the disagreement count is two. We can call this count the Hamming distance.
The calculation is fairly straightforward. But the privacy problem is harder: how can the laboratories compute it without exposing the individual entries along the way?
In our new work Quantum Advantage for Two-Party Differential Privacy, Emil T. Khabiboulline and I show that quantum communication can bypass a classical limit on the accuracy of this task. The result applies to a specific model: participants must send exactly the messages specified by the protocol and complete the interaction. Within that model, the expected error can stay constant as the lists grow.
A private answer needs a private conversation
Differential privacy requires that changing one entry in a confidential dataset have only a limited effect on what an observer can learn. Here, each laboratory needs that protection against the other.
Suppose a trusted analyst could receive both lists. Changing one entry changes the disagreement count by at most one, so the analyst can add a calibrated amount of random noise before releasing the answer. For a fixed privacy level, the required noise need not grow with the number of participants.
Without a trusted analyst, the laboratories must exchange messages to compute the answer themselves. Those messages can expose information that never appears in the final result. Sending an entire list and then adding noise to the answer would clearly fail to protect that list from its recipient. Privacy must therefore account for everything a participant is allowed to retain from the interaction, including private notes/randomness and copies of messages.
The classical accuracy barrier
Classical lower bounds show that satisfying differential privacy in the two-party setting has a substantial accuracy cost [1]. Fix a sufficiently strong level of pure differential privacy, and require both parties to receive the same estimate. Even the best classical protocol has (worst-case) inputs for which the average size of its error grows at least proportionally to the square root of the list length. This applies to information-theoretic privacy: protection must hold even against an observer with unlimited computing power [1]. Essentially, a hundredfold increase in list length therefore produces a tenfold increase in the square-root lower-bound scale. This describes how the unavoidable error grows.
Classical cryptography offers another route. Under (suitable) computational assumptions, secure computation can reproduce the accuracy available with a trusted analyst. That protection relies on certain computations being infeasible for the observer. Our main question is whether quantum communication can achieve constant error without relying on computational hardness assumptions.
On copying messages
A classical participant can save a copy of every message and still carry out the protocol correctly. Returning the original message, or deleting a working file, does not erase a copy already made. This ability to retain a transcript is central to the classical lower bounds. Quantum messages are quite different. Our protocol uses quantum states that overlap (in a precise way): the possible messages cannot be perfectly distinguished. Essentially, because of physical constraints, extracting a distinguishing record from such states cannot leave them exactly undisturbed.
Our construction uses a small, input-independent component, called a guard, to create the required overlap. Alice sends her encoded input and private randomness to Bob. Bob performs the prescribed quantum computation and returns the entire resulting state. We prove that returning exactly the prescribed state forces any extra system Bob retains from this round trip to be independent of Alice’s encoded input. He can subsequently learn the permitted noisy statistic, but the round trip cannot leave him an additional input-dependent record. Thus, the same rule has different consequences in the two settings. Classical messages can be copied while sending every prescribed message correctly. The quantum messages used here cannot support that kind of copying. This is how the protocol gets outside the scope of the classical lower bound.
Producing one answer that protects both parties
There is another useful detail: each party supplies independent random noise. If Alice generated all the noise, she would know it and could subtract it from the result. Bob would have the same advantage if he generated all the noise. Including both contributions means each participant faces uncertainty from the other participant’s private randomness. After the quantum round trip, Alice obtains the noisy result and sends the classical release to Bob. Both decode it in the same way and obtain the same estimate. For fixed privacy parameters, the expected absolute error is bounded independently of the list length. Communication grows linearly with that length. The advantage established in our work concerns accuracy under privacy constraints.
The conditions
The privacy guarantee concerns each participant’s complete information at the end of the protocol, subject to exact preservation of the prescribed messages and completion of every round. Participants may keep arbitrary private systems if they satisfy those conditions. A participant who measures a revealing intermediate message and then aborts falls outside this model. In our paper, we explain why such an attack prevents this construction from providing security against arbitrary malicious behavior. Extending the accuracy advantage to stronger adversaries remains open.
Also, the accuracy guarantee is an average over the protocol’s randomness. A rare fallback associated with the guard can produce a larger error; its probability is chosen to keep its contribution to expected error small.
The main takeaway of our work is that the physical nature of communication can affect the price of privacy. For this task of computing the Hamming distance (or inner products), the classical accuracy barrier depends on the ability to copy messages. Quantum communication changes that resource and allows both participants to learn a more accurate shared statistic.
References
[1] A. McGregor, I. Mironov, T. Pitassi, O. Reingold, K. Talwar, and S. Vadhan. The limits of two-party differential privacy. Electronic Colloquium on Computational Complexity, Tech. Rep. TR11-106, 2011. [Online]. Available: https://eccc.weizmann.ac.il/report/2011/106/
[2] Daniel Alabi, Emil T. Khabiboulline. Quantum Advantage for Two-Party Differential Privacy. https://eprint.iacr.org/2026/1669
