Source-linked AI summary
Using complete measurement statistics for optimal device-independent randomness evaluation
O. Nieto-Silleras, S. Pironio, J. Silman
TL;DR
Bell-test analyses often use a single Bell-inequality violation, although the full outcome probabilities contain richer information. The paper uses the complete behavior to evaluate device-independent guessing probability and shows that optimizing over Bell expressions yields an optimal inequality for the given correlations.
Problem
A single Bell-inequality violation captures less information than the joint probabilities of a Bell test, and systematic use of the extra data remains an open question.
Source: §1 · pp. 1–2Method
Results
For each behavior, the optimal dual Bell expression reaches the primal guessing-probability value, so a Bell expression exists that certifies the full randomness present in the correlations.
Source: §4 · pp. 4–5Takeaways & Limitations
The complete behavior identifies a Bell inequality that certifies the maximal randomness compatible with the given non-local correlations.
Source: §7 · p. 7The analysis restricts measurements to projectors by enlarging the Hilbert-space dimension, with no loss of generality in the device-independent setting.
Source: §2 · p. 2
Abstract
from arXiv · showhide
The majority of recent works investigating the link between non-locality and randomness, e.g. in the context of device-independent cryptography, do so with respect to some specific Bell inequality, usually the CHSH inequality. However, the joint probabilities characterizing the measurement outcomes of a Bell test are richer than just the degree of violation of a single Bell inequality. In this work we show how to take this extra information into account in a systematic manner in order to optimally evaluate the randomness that can be certified from non-local correlations. We further show that taking into account the complete set of outcome probabilities is equivalent to optimizing over all possible Bell inequalities, thereby allowing us to determine the optimal Bell inequality for certifying the maximal amount of randomness from a given set of non-local correlations.
1 Introduction
Bell inequalities connect non-locality to certified randomness, but a single violation value compresses richer measurement data. This work uses the complete behavior to evaluate randomness systematically and find an optimal Bell inequality for given correlations.
1 Introduction
- The non-locality–randomness link is relevant to device-independent randomness generation, randomness amplification, and device-independent quantum key distribution.The paper also notes its fundamental interest.Source: §1 · p. 1
- Bell-test probabilities contain information beyond a single violation value, leaving open how useful that extra information is and how to use it systematically.In CHSH, eight independent probabilities determine the single violation number.Source: §1 · p. 1
- Low detection efficiencies can require low-entanglement states, for which CHSH is not optimal for randomness certification.Below approximately 0.82 efficiency, CHSH cannot be violated using maximally entangled two-qubit states.Source: §1 · pp. 1–2
- The paper evaluates the device-independent guessing probability from the complete non-local behavior and shows that an optimal Bell inequality exists for any non-local correlations.The optimal value and associated inequality can be computed using the SDP hierarchy; the paper studies three numerical examples.Source: §1 · p. 2
2 Background: the device-independent guessing probability
The paper models a Bell test as quantum devices producing joint probabilities and evaluates the randomness of one box’s output against an adversary’s information. Its device-independent bound maximizes the guessing probability over quantum realizations compatible with the observed behavior.
2 Background: the device-independent guessing probability
- Alice’s two boxes receive finite-set inputs and return finite-set outputs, with their joint statistics described by probabilities p_AB(ab|xy).The devices’ joint state may be correlated with Eve’s system.Source: §2 · p. 2
- The behavior p is the vector of joint probabilities, and different quantum realizations can produce the same behavior.The paper also defines normalized quantum behaviors and unnormalized behaviors as a convex cone.Source: §2 · p. 2
- The analysis can restrict measurements to projectors by enlarging the Hilbert-space dimension, without loss of generality in the device-independent setting.Source: §2 · p. 2
- For a fixed realization, guessing probability is the average probability that Eve correctly guesses Alice’s output using an optimal measurement.It is related to conditional quantum min-entropy by G(A|E,x*,Q) = 2^-Hmin(A|E,x*,Q).Source: §2 · p. 3
- The device-independent guessing probability maximizes the guessing probability over all quantum realizations compatible with the observed behavior p.This gives a randomness bound depending on p rather than on one specific realization.Source: §2 · pp. 2–3
3 The device-independent guessing probability as a conic linear program
The device-independent guessing probability can be formulated as an optimization over quantum decompositions of the observed behavior. Its variables form a conic linear program with an adversarial interpretation: each component represents a possible Eve guess and corresponding behavior.
3 The device-independent guessing probability as a conic linear program
- Conditioning on Eve’s outcomes gives unnormalized quantum behaviors whose sum recovers the observed behavior p.Conversely, any such decomposition can represent conditional joint probabilities for a quantum realization and Eve’s measurement.Source: §3 · p. 3
- The DIGP optimization uses these unnormalized behaviors as variables, constraining their sum to p and each variable to the cone of unnormalized quantum behaviors.The resulting objective and constraints form a conic linear program.Source: §3 · pp. 3–4
- The guessing probability, or equivalently min-entropy, operationally quantifies randomness because an extractor can map sufficiently unpredictable outcomes to a nearly uniform string uncorrelated with the adversary.The stated condition is G(K|E) ≤ 2^-t for extraction of a t-bit string.Source: §3 · p. 3
- Each feasible decomposition is an adversarial strategy: with probability tr(tilde p_a), Eve guesses output a and prepares behavior p_a = tilde p_a/tr(tilde p_a).The program selects the strategy maximizing the probability of a correct guess.Source: §3 · p. 4
4 Dual formulation and optimal Bell expressions
The dual formulation searches over Bell expressions to find the tightest upper bound on the device-independent guessing probability for a given behavior. Conic-program duality makes this bound equal to the adversary’s optimal guessing probability.
4 Dual formulation and optimal Bell expressions
- The dual optimization chooses coefficients f for a linear Bell expression f·p, minimizing its upper bound on the guessing probability for the given behavior.The constraint requires p′(a|x*) ≤ f·p′ for every quantum behavior p′.Source: §4 · p. 4
- A fixed Bell expression such as CHSH yields bounds using coefficients α and β, whereas the dual program optimizes the linear form for each behavior.The fixed-expression bound has the form G(A|E, x*) ≤ α c·p + β.Source: §4 · p. 4
- Strict feasibility of the dual problem ensures no gap between the primal and dual optima, so the Bell-expression bound is tight.The all-ones choice of f is strictly feasible because f·p = n².Source: §4 · p. 4
- The dual program finds a Bell expression that certifies the maximal randomness present in a behavior, with an optimum equal to the primal adversary strategy’s guessing probability.The primal searches over adversary strategies; the dual searches over Bell expressions certifying an upper bound.Source: §4 · pp. 4–5
5 Semidefinite programming relaxations
Semidefinite-programming relaxations approximate the quantum set from the outside, producing progressively tighter upper bounds on the guessing probability. Their dual forms also provide Bell expressions that certify randomness.
5 Semidefinite programming relaxations
- The hierarchy of outer approximations to the quantum set yields a sequence of upper bounds on the device-independent guessing probability.The bounds satisfy G1(A|E, x*) ≥ G2(A|E, x*) ≥ … ≥ G(A|E, x*).Source: §5 · p. 5
- Each relaxation is an SDP: membership in the approximating set is represented by a positive semidefinite matrix satisfying linear constraints.The constraints take the form tr(G Γk) = h·p̃.Source: §5 · p. 5
- The dual SDP relaxations use sum-of-squares constraints to certify nonnegativity for valid measurement operators.An SOS constraint of degree 2k can be represented as an SDP constraint.Source: §5 · p. 5
- The primal relaxations model adversary strategies over supra-quantum behaviors, while the dual returns Bell expressions giving bounds valid for quantum strategies.These bounds are valid but not necessarily optimal for strategies in the quantum set.Source: §5 · p. 6
6 Numerical examples
Three numerical examples compare randomness bounds from complete Bell behavior with bounds from selected Bell violations. Across noisy CHSH, partially entangled states, and qutrit correlations, complete behavior can improve certification and yield optimal inequalities beyond CHSH.
CHSH correlations in the presence of white noise
- For noisy maximally violating CHSH correlations, full behavior modestly improves randomness certification over CHSH value alone, and CHSH is optimal only at perfect visibility.The correlations mix maximally violating CHSH behavior with white noise; their CHSH violation scales with v.Source: §6 · p. 6
- The numerically optimal Bell inequalities for the noisy CHSH example vary with visibility, with CHSH coefficients occurring only at v=1.The CHSH case has f11=f22=1.Source: §6 · p. 6
Randomness from partially entangled states
- At v=0.99, complete correlations provide a very significant global-DIGP advantage over either one or two independent Bell-inequality violations for partially entangled states.The bound concerns outcomes for measurements A2 and B1 as a function of θ.Source: §6 · p. 7
Randomness from entangled qutrits
- G(A|E,1)=1/3 across a large interval of α with complete behavior, including values where the CGLMP violation is small.At maximal CGLMP violation, the certified local randomness is one trit; the interval may expand with higher-order relaxations or different measurements.Source: §6 · p. 7
7 Conclusion
The paper evaluates device-independent guessing probability from complete Bell behavior and identifies an optimal Bell inequality for each given non-local behavior. It also describes extensions to non-signaling theories and flags finite-statistics integration as an open question.
7 Conclusion
- The method evaluates device-independent guessing probability from complete non-local behavior and identifies a Bell inequality certifying maximal randomness for given correlations.The approach adapts the SDP hierarchy introduced in.Source: §7 · pp. 7–8
- Low-order SDP relaxations usually already yield the optimal guessing probability.This is described as typical of applications of the SDP hierarchy.Source: §7 · p. 8
- The approach extends to purely non-signaling settings, where linear programming can solve the corresponding programs.The constraints use linear no-signaling and probability-positivity conditions.Source: §7 · p. 8
- Integrating the method into DIRG and DIQKD protocols while accounting for finite-statistics effects remains an open question.The authors identify this as an interesting direction for further work.Source: §7 · p. 8