Source-linked AI summary
Full randomness from arbitrarily deterministic events
Rodrigo Gallego, Lluis Masanes, Gonzalo de la Torre, Chirag Dhara, Leandro Aolita, Antonio Acin
TL;DR
The paper addresses randomness amplification from imperfect randomness without relying on additional good-quality randomness. It presents a Bell-violation-based protocol whose output becomes indistinguishable from an ideal free random bit, while the final hash function is not explicitly constructed.
Problem
Existing randomness-distillation procedures require additional good-quality randomness, whereas Bell-certified randomness can support distillation with a deterministic hash function.
Method
The protocol partitions quintuplets into blocks, randomly selects one distilling block, and uses the remaining blocks to check Bell violation.
Results
In the protocol’s limit, P(guess) approaches 1/2, making the generated bit k indistinguishable from an ideal free random bit.
Takeaways & Limitations
Bell-certified randomness makes randomness amplification possible because the distillation procedure can use a deterministic hash function.
Takeaways & Limitations
The authors prove the existence of the final function f but do not provide an explicit description, and exhaustive search over all functions is computationally costly.
Abstract
from arXiv · showhide
Do completely unpredictable events exist in nature? Classical theory, being fully deterministic, completely excludes fundamental randomness. On the contrary, quantum theory allows for randomness within its axiomatic structure. Yet, the fact that a theory makes prediction only in probabilistic terms does not imply the existence of any form of randomness in nature. The question then remains whether one can certify randomness independent of the physical framework used. While standard Bell tests approach this question from this perspective, they require prior perfect randomness, which renders the approach circular. Recently, it has been shown that it is possible to certify full randomness using almost perfect random bits. Here, we prove that full randomness can indeed be certified using quantum non-locality under the minimal possible assumptions: the existence of a source of arbitrarily weak (but non-zero) randomness and the impossibility of instantaneous signalling. Thus we are left with a strict dichotomic choice: either our world is fully deterministic or there exist in nature events that are fully random. Apart from the foundational implications, our results represent a quantum protocol for full randomness amplification, an information task known to be impossible classically. Finally, they open a new path for device-independent protocols under minimal assumptions.
Appendix A: Mermin inequalities
The five-party Mermin inequality tests binary inputs and outputs under non-signaling correlations, using only half of all input combinations. Its maximal violation is attainable by quantum correlations.
- The inequality uses five binary inputs and five binary outputs distributed according to a non-signaling conditional probability P(a|x).
- The expression separates input combinations into X0 and X1, with parity conditions on the five outputs defining I(a, x).
- Only half of all possible input combinations appear in the Bell inequality.
- Maximal non-signaling violation occurs when the left-hand side is zero, and quantum correlations attain this algebraic maximum.
Appendix B: Partial unpredictability in the five-party Mermin inequality
The five-party Mermin inequality certifies partial unpredictability in a majority vote of three outputs at maximal violation. This property supplies the randomness-bearing building block for the amplification protocol.
- For larger party numbers, some functions cannot be deterministically fixed while maximally violating a Mermin inequality.
- Theorem 1 bounds the probability of a three-output majority vote under every non-signaling correlation attaining maximal five-party Mermin violation.
- The theorem is established by numerically solving a linear program over five-partite non-signaling distributions.
- The optimal majority-vote guessing probability is 3/4, yielding 1/4 ≤ P(maj(a) = 0) ≤ 3/4.
- This majority-vote GHZ paradox is the simplest one in which randomness can be certified and forms the protocol’s building block.
Appendix C: Protocol for full randomness amplification
The protocol uses a weak randomness source to select inputs for grouped five-party Bell tests, checks nonlocal correlations, and distills a final bit from one selected block. Its security compares the resulting distribution with an ideal free random bit.
- Resources and output: The protocol uses an ϵ-source and 5N quantum systems, with source bits satisfying a conditional unpredictability bound.
- Resources and output: Each quantum system is modeled as a black box with binary input and output, and the protocol returns either a bit or an abort symbol.
- Protocol steps: The source generates N input quintuplets for 5N boxes, after which output quintuplets are produced.
- Protocol steps: Input quintuplets outside X are discarded, and the protocol aborts if fewer than N/3 remain.
- Protocol steps: Remaining quintuplets form Nb blocks of Nd quintuplets; one source-selected block is distilled while the others test Bell violation.
- Protocol steps: The protocol checks whether non-distilling blocks exhibit correlations compatible with maximal Mermin violation and aborts unless all checks pass.
- Distillation: The final bit is formed from the selected block using a function f applied to majority votes, while aborted executions return ∅.
- Security criterion: Security is evaluated by comparing the protocol distribution with an ideal free-bit distribution conditioned on the available information.
Appendix D: Proof of Theorem 2
The proof expresses the security comparison through conditional distributions and guessing probability. It combines block-level bounds tied to Bell violation with no-signaling and probability identities to derive the main security bound.
- Proof setup: The proof represents conditional probability distributions as vectors indexed by their arguments.
- Proof setup: The vector notation applies to full blocks and fixes e and z when representing P(B|Y, e, z).
- Core lemmas: The first crucial lemma bounds distinguishability between a distilled block and an ideal free bit as a function of Bell violation.
- Guessing probability: The proof decomposes the optimal guessing probability according to whether the protocol aborts.
- Security bound: A tensor-product expression relates the block distribution to the Bell-violation and correlation vectors, with scaling controlled by Nd.
- Security bound: No-signaling and Bayes-rule substitutions combine the intermediate bounds to produce the main security inequality.
1. Statement and proof of Lemma 1
Lemma 1 establishes a distillation function that maps majorities from many five-party Bell tests to a bit whose distinguishability from an ideal free bit is bounded by the Bell violation.
- Conclusion: The resulting calculation yields the stated bound for the distilled bit under no-signalling correlations.
- Statement: Lemma 1 guarantees a function f for every Nd ≥130 that maps Nd majority bits to a final bit k.The guarantee applies to any specified multipartite no-signalling distribution.
- Statement: The final bit is constructed as k = f(maj(a1), . . . maj(aNd)) from outcomes of Nd five-party experiments.
- Proof strategy: The proof represents majority probabilities through vectors differing by components orthogonal to the no-signalling subspace.This uses the identity P(w|x0) = Γx0w · P(A|X).
- Proof strategy: The bound is evaluated using vectors Λxiw and a function f supplied by the later lemma, with Nd ≥130 satisfying the required condition.
2. Statement and proof of Lemma 2
Lemma 2 bounds the Bell violation in the distillation block using the protocol’s non-abort probability and block sizes, relying on properties of the weak randomness source and no-signalling distributions.
- Statement: Lemma 2 relates the distillation block’s Bell violation to the probability that the protocol does not abort and to Nb and Nd.
- Input conditioning: The proof bounds the source-generated input string y after conditioning on g = 1, using that only half of the 5-bit inputs belong to X.The argument applies the source bound to obtain lower and upper probability estimates.
- Abort analysis: The protocol aborts whenever at least one block is “not right,” and the proof lower-bounds abortion using events with exactly one such block.
- No-signalling reduction: The proof uses no-signalling to remove dependence on the selected block index and then applies the source constraint for sufficiently large Nb.
3. Statement and proof of the additional Lemmas
The additional lemmas provide the linear predictability bound and the distillation function needed for the protocol, using rigorous numerical optimization and a probabilistic existence argument.
- Lemma 3: The construction imposes vectors orthogonal to the no-signalling subspace and constrains their squared components through the Mermin-test quantities.
- Lemma 3: The numerical constants are α = 0.8842, β = 1.260, and γ = 0.9732.
- Lemma 3 proof: Linear programming is used twice to handle the absolute-value constraints and obtain feasible bounds for every x0 ∈ X.The first optimization guesses signs; the second adds sign constraints and minimizes α.
- Lemma 3 conclusion: The optimization values are independent of x0, and Lemma 3 bounds majority predictability linearly in the five-party Mermin violation.
- Lemma 4: Lemma 4 establishes the existence of a function f satisfying the required bound for all relevant outcome-input sequences.A probabilistic argument selects f uniformly and shows that the failure probability is below one.
- Lemma 4 proof: The proof controls the failure probability with exponential bounds and a union bound over at most 45^Nd sequences.The resulting failure probability is at most 45^Nde^−9Nd and is smaller than 1/2.
Appendix E: Final remarks
The final remarks identify full randomness amplification as the paper’s goal, note that the extractor function is only existentially specified, and explain why Bell-certified randomness permits deterministic distillation.
- Final remarks: The protocol proves full randomness amplification but does not provide an explicit description of the function f that extracts the final bit.
- Final remarks: Searching all functions is computationally costly because their set has size 2^Nd, although a four-universal family could reduce this to polynomial size.The latter approach is left for future work.
- Alternative approach: A related optimization for seven parties gives Eve predictability 2/3 for a specified five-bit function, below the earlier value 3/4.
- Final remarks: Bell-certified randomness differs from ordinary extraction because the distillation can use a deterministic hash function after Bell-inequality certification.Other protocols such as two-universal hashing require additional good-quality randomness.