Can measurement incompatibility be certified under bounded classical communication?

Union maximal leakage measures the information a common explanation needs

The paper asks a question that ordinary Bell tests cannot answer once a classical message is allowed. In a Bell experiment with independent measurement choices and no communication, compatible measurements on either side yield a local hidden-variable model, so a Bell inequality violation rules out compatibility. If a classical message is permitted, the receiver can learn about the sender's input and use that information to select a measurement or produce an output, and the local bounds of Bell inequalities need no longer hold even with compatible measurements.

The proposed test sidesteps this by asking how much information about the sender's input x a common classical explanation must carry. A common classical simulation encodes x in a finite random variable Z and then generates the outcome b through a response channel, so that p(b|x,y) = Σ_z q(z|x) p_B(b|y,z). The quantity Λ(q) := Σ_z max_x q(z|x) equals N times the optimal guessing probability of X given Z, and is also 2^{L_max(X→Z)}, the exponential of maximal leakage.

Because different joint distributions can reproduce the same observed marginals while revealing different amounts about x, the paper minimizes this quantity over all joint distributions q(s|x) whose marginals match p(b|x,y). The result is union maximal leakage, log2 Λ∪(p), where the union refers to explaining all receiver settings together rather than one setting at a time. It is computed from the observed probabilities by a linear program, without reconstructing the state or the measurement operators.

Compatible measurements cannot exceed the message alphabet

Theorem 2.1(i) states that in any nonsignalling operational theory, compatible receiver measurements satisfy Λ∪(p) ≤ N P_g(X|B), where B is everything the receiver holds after communication and before the measurement setting y is chosen. For the classical communication scenario, N P_g(X|B) ≤ |M|, the size of the message alphabet; for a transmitted quantum system of dimension d, the bound is d with a separable shared state and d² with an arbitrary shared state. The classical case allows arbitrary nonsignalling assistance.

The intuition is that if the receiver's measurements are compatible for each message value, the message together with the outcome of the corresponding parent measurement forms a parent on B, and guessing X from that outcome cannot beat the optimal measurement on B. For k fixed-length bits, |M| ≤ 2^k, with equality if all bit strings are allowed. The alphabet need not have power-of-two size: three possible messages give the threshold three, even though their binary encoding requires two bits.

Theorem 2.1(ii) supplies the converse. For every conditional distribution p, the least message-alphabet size of a realization satisfying the one-way communication assumptions, with some nonsignalling shared resource and compatible receiver measurements, is exactly ⌈Λ∪(p)⌉. So the same quantity that bounds compatible explanations also determines the minimum classical communication needed to reproduce the observations. A realization attaining this minimum reproduces p(b|x,y) but may use a different shared resource and sender encoding.

Shared randomness and separable states cannot beat the bound

A natural escape route would be to let the shared resource carry part of the explanation. Lemma 2.2 closes it under the paper's assumptions: a protocol using shared randomness or a separable quantum state as its initial resource satisfies Λ∪(p) ≤ |M|. The proof writes the shared-randomness protocol as a convex combination over a hidden variable λ, samples an outcome independently for each receiver setting conditional on (m, λ), and uses the fact that the maximum of a sum is at most the sum of its maxima.

Separable states inherit the same bound because finite mixtures of product states have the same classical form, and every separable state can be approximated in trace norm by such mixtures. With the protocol fixed, each outcome probability converges to that of the original state, and the convex hull of finitely many deterministic protocols is closed, so the limiting distribution also has a classical model.

The consequence is sharp: any exact one-way classical simulation with shared randomness requires a message with at least ⌈Λ∪(p)⌉ possible values, or ⌈log2 Λ∪(p)⌉ fixed-length bits. In quantum theory, a violation of the bound also implies that the initially shared state is entangled, and this conclusion does not require the receiver's measurements to be compatible.

A fixed quantum resource violates exactly when Bell nonlocality is available

The bound above concerns what compatible measurements can achieve. A separate question is whether a given shared quantum state and set of receiver measurements can be made to violate the test by some choice of sender operations. Theorem 3.1 answers it exactly: for a fixed shared quantum state and receiver measurements, a violation is possible exactly when, for some message value, the receiver's measurements are Bell-nonlocal against two-outcome sender measurements on that state.

This characterization does double duty. It identifies which fixed quantum resources the test can detect, and it marks the test's limits under the operations specified in the theorem. Known Bell-nonlocal families therefore give detection beyond pairs, and the connection also explains why the test includes the standard random-access certificate with two input bits and one communicated bit: with uniformly chosen inputs, every violation of that certificate's compatibility bound is also detected by the union-leakage criterion.

The paper is explicit that the freedom to use any nonsignalling resource matters for the simulation result. There are probabilities attainable with shared entanglement and one classical bit that satisfy Λ∪(p) = 2 but require three message values for a compatible quantum realization, even when the shared state may be chosen freely. Restricting the compatible explanation to quantum resources can therefore require more communication, even for probabilities that admit a quantum realization, and incorporating that restriction into a tractable stronger test remains open.

Binary receiver outcomes turn a violation into private randomness

For binary receiver outcomes, the paper shows that a violation also certifies randomness private from the sender, even when the receiver's measurement depends on the sender's message and the sender retains quantum side information. The privacy is quantified through an explicit conditional entropy bound of the form [Λ∪(p_B) − |M|]_+, where p_B(b|x,y) = Σ_m p(m,b|x,y) and the entropy is still conditioned on the public message. The raw output need not be uniform; extraction from many outputs is the next step.

The proof compares the experiment with a hypothetical measurement that performs all receiver measurements sequentially and records their outcomes. This defines a parent measurement for each message and therefore obeys the compatibility bound. A violation forces disturbance in this sequential construction, which the proof relates to the remaining output uncertainty when the adversary holds a purification.

The guarantee is about the receiver's output alone, not about a shared key. In quantum key distribution with an untrusted receiver, compatibility of the effective receiver measurements, including the preceding channel, prevents the observed statistics alone from certifying a secret key. The private randomness result here does not establish a shared key, which would require a separate protocol and security analysis.

Entropy accumulation makes the guarantee composable across rounds

Turning a single-round entropy bound into usable private bits requires two further ingredients. Generalised entropy accumulation relates the single-round von Neumann entropy bound to the smooth conditional min-entropy of the complete output sequence, even when device memory correlates different rounds. Privacy amplification against quantum side information then maps the output sequence to a shorter bit string using a hash function chosen with independent public randomness.

The protocol fixes the witness coefficients before collecting data. For each of L rounds with independent uniform inputs, the round score is S_i = Nn w_{X_i Y_i M_i B_i}, and the run is accepted if the average score reaches a threshold w_0; otherwise it aborts. The dual of the union-leakage linear program supplies coefficients w_{xymb} satisfying W(p) = Σ w_{xymb} p(m,b|x,y) ≤ Λ∪(p) − |M| for every p, and every violation of the compatibility bound has such a witness with W(p) > 0.

Corollary 4.2 states that for sufficiently large L there is a fixed output length ℓ ≥ L r(w_0) − O(√L), with rate r(w_0) = 1 − h_2(1/2 + 2w_0 / (Nn(n−1))). The constant in O(√L) depends only on the fixed alphabets, coefficients, acceptance threshold and ε, not on the device dimensions. The extracted string satisfies a composable distance bound of ε from a uniform string independent of the adversary and the public transcript, with subnormalization weighting the distance by the probability of acceptance.

Two conditions bound what this means in practice. The receiver's memory and unreleased raw data must remain inaccessible to the adversary, and the inputs and hash seed require independent randomness, so this is not a claim of net randomness expansion. The public transcript may contain aggregate counts of each tuple (x,y,m,b), and the information those counts reveal about the outputs is accounted for in the finite-size correction.

The test certifies incompatibility, not every quantum advantage

The paper positions union maximal leakage against information-theoretic incompatibility tests that require quantum descriptions. Zhu's criteria compare Fisher information about quantum-state parameters with bounds from quantum estimation theory, and related criteria use properties of measurement operators or evaluate information measures on conditional quantum states, measurements and instruments. Those approaches need a specified state-estimation model or the measurement operators. The union-leakage test instead works from p(b|x,y) when the quantum description is unavailable but the classical communication can be bounded, and the sender's input x is a classical label that need not parameterize a known family of quantum states.

The comparison with prepare-and-measure work is also specific. For N uniformly distributed inputs, minimizing the receiver's optimal guessing probability over classical models that reproduce p gives Λ∪(p)/N, and the earlier linear program decides whether such a model exists for a specified guessing-probability bound. The union-leakage formulation uses fewer variables by optimizing directly over joint outcome distributions, and it turns the quantity into an incompatibility test by using the communication model, so the guessing probability need not be assumed or estimated separately.

The interpretation depends on which shared resources are allowed. With shared randomness, the required number of classical message values is studied through signalling dimension, and for a single receiver setting ⌈Λ∪(p)⌉ is the maximum-likelihood lower bound on that number. With arbitrary nonsignalling assistance and compatible receiver measurements, Theorem 2.1(ii) makes the bound attainable, including when there are several settings. Without the compatibility requirement, the simulation criterion bounds the communication value of each receiver setting separately; compatibility requires a common simulation of all settings within the same communication bound.

The decisive comparison is between Λ∪(p) and the message alphabet

The practical reading of this paper comes down to one comparison. Compute Λ∪(p) from the observed probabilities by the linear program, then compare it with the number of possible message values the experiment actually permits. If Λ∪(p) ≤ |M|, compatible measurements for each message can account for the data, and no incompatibility certificate follows. If Λ∪(p) > |M|, compatibility is ruled out for at least one message value, and in quantum theory the initially shared state is entangled.

Two features make this comparison more informative than a bare violation flag. First, the same quantity is tight in both directions: it is the minimum classical communication needed for a compatible explanation with arbitrary nonsignalling assistance, so the gap between Λ∪(p) and |M| measures how far the data sit beyond what compatible measurements can explain. Second, the Bell-nonlocality characterization tells the reader when a fixed quantum state and receiver measurements can produce that gap at all, namely exactly when two-outcome sender measurements can be Bell-nonlocal against one of the receiver's measurement families.

The boundary to keep in view is the resource model. The exact simulation result permits arbitrary nonsignalling resources, and restricting the compatible explanation to quantum resources can require more communication even for probabilities that admit a quantum realization. For binary receiver outcomes the violation additionally yields a conditional entropy bound and, through entropy accumulation and privacy amplification, composable randomness extraction for devices with memory, but only under the stated isolation and independent-randomness conditions, and without any claim of a shared key or net randomness expansion.

Sources used in this answer