Source-linked AI summary
Random Numbers Certified by Bell's Theorem
S. Pironio, A. Acin, S. Massar, A. Boyer de la Giroday, D. N. Matsukevich, P. Maunz, S. Olmschenk, D. Hayes, L. Luo, T. A. Manning, C. Monroe
TL;DR
Randomness generators need certification that remains meaningful when devices are imperfect or untrusted. This paper uses Bell-violating entangled systems to certify private randomness without trusting device internals, demonstrating 42 new random bits at 99% confidence while identifying security and implementation boundaries.
Problem
Statistical tests cannot establish genuine private randomness, especially when random-number devices are untrusted or may be prepared by an adversary.
Method
The paper relates Bell violation to min-entropy and applies martingale-based analysis to repeated device use, including devices with internal memory.
Results
The experiment guarantees 42 new random bits at 99% confidence, while the observed data are unlikely under local models and separate output streams pass statistical tests.
Takeaways & Limitations
Bell-violating quantum correlations can support randomness expansion and certification without assumptions about the devices’ internal workings.
Takeaways & Limitations
The protocol is not yet proven universally composable against an adversary holding quantum side information measured later.
Abstract
from arXiv · showhide
Randomness is a fundamental feature in nature and a valuable resource for applications ranging from cryptography and gambling to numerical simulation of physical and biological systems. Random numbers, however, are difficult to characterize mathematically, and their generation must rely on an unpredictable physical process. Inaccuracies in the theoretical modelling of such processes or failures of the devices, possibly due to adversarial attacks, limit the reliability of random number generators in ways that are difficult to control and detect. Here, inspired by earlier work on nonlocality based and device independent quantum information processing, we show that the nonlocal correlations of entangled quantum particles can be used to certify the presence of genuine randomness. It is thereby possible to design of a new type of cryptographically secure random number generator which does not require any assumption on the internal working of the devices. This strong form of randomness generation is impossible classically and possible in quantum systems only if certified by a Bell inequality violation. We carry out a proof-of-concept demonstration of this proposal in a system of two entangled atoms separated by approximately 1 meter. The observed Bell inequality violation, featuring near-perfect detection efficiency, guarantees that 42 new random numbers are generated with 99% confidence. Our results lay the groundwork for future device-independent quantum information experiments and for addressing fundamental issues raised by the intrinsic randomness of quantum theory.
A Theoretical results
The theoretical analysis proceeds in two stages: first relating Bell violation to quantum randomness, then applying that relation to repeated device use that may include memory effects.
- A Theoretical results: The proof first quantifies randomness for quantum systems with a specified Bell expectation.It then applies this relation to experimental data from Bell-violating devices used repeatedly, without assuming identical and independent behavior across trials.
A.1 Quantum randomness versus Bell violation
This section relates Bell-inequality violation to output min-entropy and develops computable bounds using semidefinite programming. For CHSH, the resulting relation is tight up to numerical precision.
- Quantum randomness versus Bell violation: Bell expressions are linear combinations of joint probabilities, with local models constrained by a classical bound I0.CHSH is the special case with two measurements and binary outcomes per system.
- Quantum randomness versus Bell violation: The output randomness is quantified by conditional min-entropy, whose minimum compatible value is obtained by maximizing an output probability over quantum states and measurements.The optimization ranges over arbitrary Hilbert-space dimensions and all relevant input-output pairs.
- Quantum randomness versus Bell violation: Semidefinite-programming relaxations produce successively tighter lower bounds on min-entropy as functions of Bell violation.These bounds are convex and equal zero at the classical point.
- Quantum randomness versus Bell violation: For CHSH, the upper and lower min-entropy bounds coincide up to numerical precision 10^-9, making the Bell-violation relation tight.The numerical calculation uses the second relaxation step.
- Quantum randomness versus Bell violation: The same method also gives a local min-entropy bound, and local min-entropy lower-bounds global min-entropy.For CHSH, the authors obtain a tight analytical lower bound using two-qubit states and the accessible quantum region.
A.2 Randomness produced by Bell devices used n times in succession
The repeated-use analysis estimates Bell violation statistically while allowing devices to retain internal memory. Martingale methods connect observed data to a lower bound on the min-entropy of the full output string.
- Randomness produced by Bell devices used n times in succession: The devices are used n times in succession, with random input pairs sampled independently from a fixed distribution, while their behavior may depend on all previous events.The final output string is characterized by min-entropy conditioned on the complete input string.
- Randomness produced by Bell devices used n times in succession: Conditioning each round on the past yields a per-round randomness bound f(I(W_i)) based on that round’s Bell violation.Convexity combines the roundwise bounds into a bound for the complete output string.
- Randomness produced by Bell devices used n times in succession: The observed inputs and outputs provide an estimator for the average conditional Bell violation, including when devices have memory.The estimator is constructed so its conditional expectation equals the current-round Bell violation.
- Randomness produced by Bell devices used n times in succession: Martingale increments are bounded, allowing the Azuma-Hoeffding inequality to control deviations between observed and underlying Bell violations.This supports randomness certification with one device reused sequentially rather than requiring independent devices in parallel.
- Randomness produced by Bell devices used n times in succession: With probability at least 1 −δ, the experimentally estimated Bell violation yields a lower bound on the output-string min-entropy.The bound follows by combining the statistical estimate with the single-round entropy relation.
A.3 Bounds using no-signalling only
The min-entropy analysis can be extended beyond quantum theory by imposing only no-signalling constraints. The resulting optimization is linear and gives Bell-violation-dependent probability bounds.
- Bounds using no-signalling only: No-signalling conditions replace the full quantum formalism in the min-entropy optimization problem.The devices are constrained not to enable arbitrarily fast communication, even at a hidden level.
- Bounds using no-signalling only: Because the no-signalling constraints define a polytope, linear programming yields bounds of the form P*(ab|xy) ≤ αI + β.The coefficients may depend on the outputs and inputs.
- Bounds using no-signalling only: The corresponding local probability P*(a|x) is also bounded by a finite set of linear inequalities.This provides an analogous local min-entropy constraint.
- Bounds using no-signalling only: For binary inputs and outputs, deterministic points and Popescu-Rohrlich boxes determine the relevant extremal bounds.The deterministic points have I = ±2, while Popescu-Rohrlich boxes have I = ±4.
- Bounds using no-signalling only: The repeated-use analysis carries over by replacing the quantum maximum violation Iq with the no-signalling maximum violation Ins.This substitution produces a min-entropy bound for sequentially used devices under no-signalling constraints.
B Quantum randomness expanders
The protocol expands a small private random seed into a longer private string by combining Bell-violation-based entropy bounds with classical randomness extraction. Its security applies even when devices have internal memory, but universal composability against stored quantum side-information remains unproved.
- Protocol: The protocol uses an initial seed to generate random measurement inputs, evaluates the observed Bell violation, bounds output min-entropy, and extracts nearly uniform randomness.The input seed is divided into strings for measurement settings and extraction.
- Extraction: The raw output can be converted into a nearly uniform string uncorrelated with adversary information using a classical extractor and a small random seed.The extractor output has size O(nf(Î−ε)).
- Protocol: A positive min-entropy bound makes the final string longer than the initial seed.The extracted string is slightly shorter than the raw output but remains longer overall when the entropy bound is positive.
- Expansion: For sufficiently large n, a seed of length O(√n log2√n) can produce a final string of length O(n).The input distribution can reduce the randomness needed to generate measurement settings while retaining linear output entropy.
- Security scope: Security currently covers quantum adversaries who measure their side-information before extraction, not fully quantum adversaries retaining quantum memory.A universally composable proof would require an entropy bound conditioned on the adversary’s quantum information.
- Security scope: The protocol’s practical advantage is that its entropy bound remains valid for devices with internal memory.The paper contrasts this feature with earlier protocols whose stronger expansion results assume devices have no memory.
C Requirements on the devices
Device-independent randomness certification requires quantum behavior, fresh independent inputs, and noncommunication between the devices. These conditions avoid assumptions about internal device details, but their practical enforcement involves experimental and technological boundaries.
- Core requirements: The security proof assumes quantum-theoretic devices, independent random inputs revealed only at each round, and separated noncommunicating devices.These assumptions constrain the devices’ behavior without specifying their states, measurements, dimension, or internal workings.
- Core requirements: The locality assumption factorizes the devices’ Hilbert space and makes each measurement depend only on its corresponding local input.The resulting mathematical condition is used in the optimization underlying the randomness bound.
- Scope: If any minimal requirement fails, a Bell violation no longer guarantees the presence of randomness.The paper notes that some conditions might be weakened only at the expense of the randomness generation rate.
- Implementation choices: Strict space-like separation is not necessary when the two systems are otherwise sufficiently separated and noninteracting during measurements.The experiment uses separate systems without requiring space-like separation.
- Implementation choices: Shielding can enforce noninteraction, but its adequacy is a technological assumption that cannot be completely ruled out.This issue is especially relevant when an adversary supplies the devices.
- Implementation choices: Using two ions in one trap could increase data rates, but their coupling and closely spaced measurements prevent assuming separate noninteracting devices without modeling the experiment.The demonstrated setup instead uses ions in independent chambers.
- Experimental validity: A Bell violation obtained without closing the detection or post-selection loopholes cannot certify randomness.Relying on fair sampling would require detailed device knowledge and could fail unnoticed.
D.1 Experimental system
The experiment stores individual 171Yb+ ions in separate radio-frequency traps and encodes qubits in two hyperfine ground-state levels. Each sequence begins with optical pumping and microwave preparation.
- Apparatus: Individual 171Yb+ ions are stored in independent radio-frequency Paul traps in vacuum chambers separated by about 1 meter.The chambers are placed in a 3.4 G magnetic field defining the quantization axis.
- Qubit encoding: The qubits use the F = 1, mF = 0 and F = 0, mF = 0 hyperfine levels of the S1/2 ground state as |1⟩ and |0⟩.These levels provide the computational basis for each atom.
- State preparation: Each experimental sequence prepares each atom using a 1 µs optical-pumping pulse followed by a 10 µs microwave pulse.The preparation targets the |0⟩+|1⟩ state.
D.2 Generation of measurement settings
Measurement settings are generated by combining independent online randomness sources and delivering selected bits to the experimental controller before each entanglement event.
- Randomness sources: The experiment combines radioactive-decay, atmospheric-noise, and remote computer/network randomness sources using XOR.The procedure is intended to produce independent and uniform measurement settings.
- Setting delivery: Before each entanglement event, two least significant bits are sent to the FPGA controlling the experimental sequence.After photon coincidence, the FPGA applies setting-dependent microwave phases and returns the settings with detection results.
D.3 Comparison with local causality
The analysis treats the observed CHSH violation as a statistical test against local causality. Using a martingale bound, it applies to local models even when they retain memory of prior settings and outputs.
- The usual interpretation of a Bell violation is formalized statistically by comparing the observed CHSH value with predictions of local theories.
- The martingale analysis bounds the probability that a local deterministic theory produces a violation at least as large as the observed value.The bound is derived using bounded martingale increments and the Azuma-Hoeffding inequality.
- The resulting inequality remains valid for local models with internal memory of past measurement settings and outputs.
- 0.000767 is the upper bound on the probability that the experimental results were produced by a local model.
D.4 Statistical tests
Statistical tests were used to check the settings and outputs for obvious non-random patterns, while the paper emphasizes that Bell-based certification provides a stronger guarantee than such tests.
- The tests evaluate p-values for the measurement settings, each atom’s outputs separately, and the two atoms’ outputs jointly.
- The input string and the outputs from each atom separately pass the tests, with input p-values exceeding the significance level α = 0.001.
- The joint output string fails the tests because the two atoms’ measurement outputs are correlated rather than independent random variables.
- 42 new random bits are guaranteed at the 99% confidence level independently of assumptions about how the experiment was realized.This certification is distinguished from statistical tests, which only indicate the absence of obvious non-random patterns.
- 0.7610, 0.7933, 0.7933, and 0.2867 are the Fisher-test p-values supporting compatibility of the data with no-signalling conditions.Four two-sided Fisher tests were performed, one for each no-signalling condition.