PaperlayerView exact revision on arXiv

Source-linked AI summary

Device-independent Randomness Expansion with Entangled Photons

Lynden K. Shalm, Yanbao Zhang, Joshua C. Bienfang, Collin Schlager, Martin J. Stevens, Michael D. Mazurek, Carlos Abellán, Waldimar Amaya, Morgan W. Mitchell, Mohammad A. Alhejji, Honghao Fu, Joel Ornstein, Richard P. Mirin, Sae Woo Nam, Emanuel Knill

arXiv:1912.11158v2quant-phphysics.data-an

TL;DR

Device-independent randomness experiments have faced an input-cost problem: they consume more random bits than they certify. This paper uses spot-checking with uniform bits and reports an expansion ratio of 1.24, while its security guarantee is against classical side information.

  • Problem

    Earlier device-independent randomness-generation experiments required far more random input bits than they generated, making randomness expansion an outstanding challenge.

    Source: p. 1

  • Method

    The protocol uses randomly scheduled spot-checking Bell trials in variable-length blocks, with uniform bits and no conversion to bits with a specific bias.

    Source: p. 2

  • Results

    An expansion ratio of 1.24 yielded 1,181,264,237 new random bits at soundness error 5.7×10^-7, with 949,576,566 bits consumed for spot checks and settings choices.

    Source: p. 4

  • Takeaways & Limitations

    The experiment certified an average of 3,606 bits/s, a rate the authors say brings device-independent randomness generation within reach of real-time integration in randomness beacons despite substantial latency before certification.

    Source: p. 5

    The reported security covers classical side information, not quantum side information; extending the analysis to quantum side information would require QEFs, which the authors’ current construction method makes too computationally costly for this experiment.

    Source: p. 4

Abstract

from arXiv · show

With the growing availability of experimental loophole-free Bell tests, it has become possible to implement a new class of device-independent random number generators whose output can be certified to be uniformly random without requiring a detailed model of the quantum devices used. However, all of these experiments require many input bits in order to certify a small number of output bits, and it is an outstanding challenge to develop a system that generates more randomness than is consumed. Here, we devise a device-independent spot-checking protocol that consumes only uniform bits without requiring any additional bits with a specific bias. Implemented with a photonic loophole-free Bell test, we can produce 24% more certified output bits (1,181,264,237) than consumed input bits (953,301,640). The experiment ran for 91.0 hours, creating randomness at an average rate of 3606 bits/s with a soundness error bounded by $5.7\times 10^{-7}$ in the presence of classical side information. Our system will allow for greater trust in public sources of randomness, such as randomness beacons, and may one day enable high-quality private sources of randomness as the device footprint shrinks.

SUPPLEMENTARY INFORMATION: DEVICE-INDEPENDENT RANDOMNESS EXPANSION WITH ENTANGLED PHOTONS

The Supplementary Information lays out probability-estimation methods and an end-to-end randomness-generation protocol. It formalizes the experiment as variable-length blocks with a uniformly chosen spot-checking trial at each block’s end.

SUPPLEMENTARY INFORMATION: DEVICE-INDEPENDENT RANDOMNESS EXPANSION WITH ENTANGLED PHOTONS

  • The Supplementary Information covers probability estimation, end-to-end protocol design, PEF construction, parameter selection, calibration-based PEF updates, and analysis results.It assigns these topics to Sects. I–VI.Source: SUPPLEMENTARY INFORMATION:… · p. 8
  • Each block has a uniformly selected length from 1 to 2^k trials, with its final trial designated the spot-checking trial.The average block length is (1 + 2^k)/2.Source: SUPPLEMENTARY INFORMATION:… · p. 8
  • Only the spot-checking trial uses uniformly random settings; all earlier trials use fixed settings X = 0 and Y = 0.The block’s trials produce binary setting inputs and binary outcomes at Alice and Bob.Source: SUPPLEMENTARY INFORMATION:… · p. 8

I. PROBABILITY ESTIMATION

This section introduces probability estimation for certifying randomness with respect to classical side information. Its central tools are models of allowed distributions and probability estimation factors (PEFs).

I. PROBABILITY ESTIMATION

  • Probability estimation is introduced through models and probability estimation factors (PEFs).The section presents these as the approach’s main concepts.Source: §I · p. 8
  • PEFs can certify smooth conditional min-entropy of outputs given inputs and classical side information E.The certification is conditional on the sequence of inputs and E.Source: §I · p. 8
  • The section frames probability estimation as a method for certifying randomness against classical side information.Source: §I · p. 8

A. Models and PEFs

The section models each block as a sequence of trial distributions constrained by device physics and the spot-checking schedule. Trial-wise PEFs are then chained to certify randomness for the block.

A. Models and PEFs

  • Each block contains a random number of executed real trials up to 2^k, while later positions are virtual trials filled with * for analysis.The block length determines which positions are real versus virtual.Source: A. Models and PEFs · p. 8
  • A block model is a superset of distributions achievable under verifiable physical constraints, with trial models accounting for whether the block has ended.The experiment constrains devices by quantum mechanics and locality.Source: A. Models and PEFs · p. 8
  • At each real trial, the model combines non-signaling and Tsirelson-bounded outcomes with a position-dependent chance of a uniform spot check; otherwise settings are fixed to 00.The spot-check probability at position j is q_j = 1/(2^k − j + 1).Source: A. Models and PEFs · p. 9
  • A PEF is a non-negative function satisfying an inequality for every distribution in its trial model, and the constant-one function is used for virtual trials.The PEF inequality depends on the positive power β.Source: A. Models and PEFs · p. 9
  • Multiplying trial-wise PEFs yields a block-wise PEF, but the analysis assumes the input distribution is exact; adversarial input bias would require more trials for the same certified randomness.The block PEF uses the same power β, and allowing biased spot-check and setting inputs is not sufficient by itself for randomness amplification.Source: A. Models and PEFs · p. 10

B. Certifying smooth min-entropy

This section bounds the smooth conditional min-entropy of experiment outputs given inputs and classical side information. It uses block-wise PEFs to establish an entropy bound when the experiment succeeds, which can then be composed with an extractor.

B. Certifying smooth min-entropy

  • Conditional min-entropy is defined through the negative base-2 logarithm of the average maximum guessing probability for outputs given inputs and E.The smooth version allows a nearby distribution within a specified total-variation distance.Source: B. Certifying smooth min-entropy · pp. 10–11
  • The certification goal is a lower bound on smooth conditional min-entropy for any joint distribution satisfying the whole-experiment model H.The model applies conditionally for each value of classical side information E.Source: B. Certifying smooth min-entropy · pp. 10–11
  • Multiplying the PEFs across blocks gives a whole-experiment statistic T used to lower-bound smooth conditional min-entropy.The bound replaces trial-wise PEFs with block-wise PEFs.Source: B. Certifying smooth min-entropy · p. 11
  • When T reaches the threshold 1/(p^βϵ_s), the theorem bounds smooth conditional min-entropy conditioned on event Φ.The event Φ is interpreted as experiment success.Source: B. Certifying smooth min-entropy · p. 11
  • On success, the smooth conditional min-entropy bound can be composed with a classical-proof strong extractor to obtain near-uniform random bits.Source: B. Certifying smooth min-entropy · p. 11

II. RANDOMNESS GENERATION

The section aims to define a sound randomness-generation protocol whose performance is guaranteed regardless of how low its success probability is. It previews the extractor, soundness definition, and protocol proof.

II. RANDOMNESS GENERATION

  • The protocol is designed to guarantee performance no matter how low its success probability is.Source: §II · p. 11
  • The extractor determines choices of various parameters used in the protocol.Source: §II · p. 11
  • The section introduces the extractor, formalizes soundness, and presents and proves the randomness-generation protocol.Source: §II · p. 11

A. Classical-proof strong extractors

A classical-proof strong extractor uses a uniformly random seed independent of other variables to extract near-uniform bits from a source. Its guarantee is conditioned on the source having sufficient conditional min-entropy.

A. Classical-proof strong extractors

B. Protocol soundness

The section defines soundness by comparing successful protocol outputs and the reused seed with a uniform distribution, allowing classical side information. It distinguishes this guarantee from completeness, which concerns whether success is achievable.

B. Protocol soundness

  • On success, the protocol outputs fresh bits R and the previously used extraction seed S′, alongside a success flag P.Source: B. Protocol soundness · p. 12
  • Soundness requires the successful outputs and seed to be close to uniform and independent of inputs and classical side information, up to a success-probability-weighted error.Source: B. Protocol soundness · p. 12
  • If success probability exceeds κ and conditional total-variation distance must be at most δ, it suffices to choose soundness error ϵ ≤ δκ.Source: B. Protocol soundness · p. 12
  • Completeness means that some distribution satisfying the model achieves success probability at least η, while soundness guarantees performance regardless of implementation.Source: B. Protocol soundness · p. 12

C. PEF-based randomness-generation protocol

The protocol estimates randomness from blocks using probability-estimation factors, then applies a classical-proof strong extractor to produce output bits. Its soundness follows for the experiment model, with variable-length blocks padded to meet the extractor’s fixed-length requirement.

C. PEF-based randomness-generation protocol

III. CONSTRUCTION OF BLOCK-WISE PEFS

The section formulates block-wise PEF optimization for randomness generation and expansion, then defines a block-count criterion for success under honest-device behavior. It also characterizes the resulting block-wise randomness rate.

III. CONSTRUCTION OF BLOCK-WISE PEFS

  • Randomness expansion optimizes the difference between random bits generated and consumed, while randomness generation maximizes output after a fixed number of blocks.Source: §III · p. 15

A. Formulation of block-wise PEF optimization

  • A feasible block-wise PEF remains valid when block results follow distributions in model C, while unconstrained optimization is optimal at the assumed distribution ν.Source: A. Formulation of block-wise PEF… · pp. 16–17
  • The minimum block count Nexp,b(β) is defined by equating its expected witness contribution to the threshold log2(tmin)/β.The required threshold includes input entropy and entropy and soundness error terms.Source: A. Formulation of block-wise PEF… · p. 17
  • Minimizing Nexp,b(β) over β gives the simplified minimum block count, which is tight to lowest order.Only an asymptotically small increase in blocks is needed in practice to guarantee sufficient success probability.Source: A. Formulation of block-wise PEF… · p. 17
  • For a fixed β, gb(β) is the maximum asymptotic randomness rate per block under the same block distribution ν and model C.Source: A. Formulation of block-wise PEF… · p. 17

B. Simplified and effective block-wise PEF optimization

The section reduces block-wise PEF construction to trial-wise PEFs and presents interpolation as an efficient way to cover all trial positions. It reports near-optimal performance and describes how protocol parameters are commissioned.

B. Simplified and effective block-wise PEF optimization

  • Linear interpolation constructs PEFs for every trial position from optimized PEFs at only three positions, and the resulting trial-wise PEFs perform almost as well as individually optimized ones.Source: B. Simplified and effective block-wise… · p. 17
  • The block-wise rate is computed from per-position rates weighted by the probability that a block reaches each trial position.For trials beyond the block length, the PEF contribution is zero.Source: B. Simplified and effective block-wise… · pp. 17–18
  • 99.99% of the lower bound g′b(β) is achieved by interpolated PEFs using the optimal middle position, jmid,opt = 53,478, for maximum block length 2^17.The optimal middle position depends on the honest-device distribution and PEF power β.Source: B. Simplified and effective block-wise… · p. 20

IV. PROTOCOL DESIGN AND COMMISSIONING

  • Protocol parameters are chosen from anticipated performance; in this demonstration, maximum block length was set before data acquisition, while remaining parameters were set after acquisition but before unblinding.Production-quality implementations should choose all parameters before acquiring data.Source: §IV · p. 20

A. Block-length determination

The authors estimate an honest-device input-conditional output distribution from calibration data and optimize the maximum block length for randomness expansion. Their analysis finds the optimal maximum block length is 2^17 across the tested soundness errors.

A. Block-length determination

  • The optimization minimizes the expected number of trials needed for expansion, using a maximum-likelihood estimate of the input-conditional output distribution from calibration data.The estimate is used to choose block length, not to assert the actual distribution during the experiment.Source: A. Block-length determination · p. 20, Table II · p. 21
  • 2^17 is the optimal maximum block length independent of soundness error, and the minimum required trial count scales linearly with the logarithm of that error.The reported result also finds the optimal PEF power and error-splitting ratio independent of soundness error.Source: A. Block-length determination · p. 21, Table III · p. 22
  • The optimal maximum block length is independent of the fixed inputs used in non-spot-checking trials, but optimal parameters depend on the estimated input-conditional output distribution.Source: A. Block-length determination · p. 21

B. Parameter determination

The analysis parameters were chosen using training data and an estimated trial distribution, then used to set extraction and success thresholds. Under these choices, the expected expansion ratio conditional on success was 1.105.

B. Parameter determination

  • The first 16 unblinded cycles formed a 4,502,276-block training set, while the analysis set contained 56,070,910 blocks.The parameter choices also used prior knowledge about available blocks and cycles with reduced calibration files, which the authors note is unavailable in production-quality implementations.Source: B. Parameter determination · p. 22
  • β = 4.7614×10^-8 and ϵen = 5.6822×10^-7 were optimized for 56,070,910 blocks using the first six training cycles’ estimated distribution.The distribution was inferred by maximum likelihood from calibration trials; its statistical strength was 3.03×10^-6, compared with 7.19×10^-6 for the earlier Table II distribution.Source: B. Parameter determination · p. 22, Table V · p. 24, Table IV · p. 24
  • Wmin = 1,616,998,677 set an estimated success probability of at least 0.9938, using a normal approximation to the output entropy witness.The tail calculation is heuristic because it assumes an approximately normal witness distribution, and somewhat pessimistic because it omits possible early threshold crossing.Source: B. Parameter determination · p. 23
  • 1.105 is the expected expansion ratio conditional on success, with 1,181,264,237 output bits and 1,069,072,364 input bits including extractor seeds.The calculation gives 3,725,074 seed bits and notes that early threshold attainment can produce a higher ratio.Source: B. Parameter determination · p. 23
  • Figure 5 varies the soundness error while holding the desired success probability at 0.9938 to show the expected expansion ratio.The PEF power and entropy error were optimized for each chosen soundness error using the estimated distribution and analysis-block count.Source: Figure 5 · p. 23, B. Parameter determination · p. 23

V. PEF UPDATING DURING THE ANALYSIS

Because the authors anticipated substantial distribution drift, they updated block-wise PEFs for each cycle using recent calibration data. Training-set results and simulations supported the updated approach and its short calibration window.

V. PEF UPDATING DURING THE ANALYSIS

  • Cycle-updated PEFs used at least 22,200,000 recent calibration trials, pooling trials from the preceding cycle when a cycle’s calibration file was too small.The presumed current distribution was estimated by maximum likelihood, then trial-wise PEFs were obtained by linear interpolation; simulations showed close-to-optimal performance with high probability.Source: §V · p. 24
  • Using preceding calibration data to construct block-wise PEFs with power β = 4.7614 × 10−8, simulations found they perform close to optimal for the true distribution with high probability.Source: §V · p. 24
  • On the training set, the empirical rate was 35.6851 bits per block, close to the predicted 36.0558 bits per block.The empirical per-block witness variance was 4.4786×10^8, similar to the predicted 4.6729×10^8.Source: §V · p. 24

VI. ANALYSIS RESULTS

The analysis crossed its success threshold after 49,977,714 blocks, yielding a 1.24 expansion ratio at soundness error 5.7×10^-7. The implementation updated PEFs from calibration data and accumulated an entropy witness until the threshold was reached.

VI. ANALYSIS RESULTS

  • Across 20,000 simulated calibration samples, the witnessed randomness rate per block was almost independent of the sample used to build the PEF.Each sample contained 30,000,000 trials, corresponding to 2 minutes of calibration at 250,000 trials per second.Source: Figure 6 · p. 25
  • Independent MATLAB and Python analysis runs returned consistent results.The secondary run served as a consistency check during training and analysis.Source: §VI · p. 26
  • The implementation accumulated calibration data to a 22,200,000-trial minimum, estimated the distribution, built trial-wise PEFs, and added their log contributions to the running entropy witness.When calibration data in a cycle fell short, the procedure added trials from preceding expansion files and stopped successfully once the witness threshold was exceeded.Source: §VI · p. 26
  • 1.24 was the actual expansion ratio after 49,977,714 blocks and 91.0 hours, yielding 1,181,264,237 bits at soundness error 5.7×10^-7.The run consumed 949,576,566 bits for spot checks and settings choices; after all blocks, the witnessed rate was 32.8028 bits per block, below the predicted 36.0558.Source: §VI · p. 27
  • The cycle-wise calibration estimates were used to predict statistical strength and randomness rate per block for the next cycle.The prediction assumed each estimated distribution remained true for all trials of that next cycle; the analysis tracked a positive correlation between the two quantities.Source: Figure 7 · p. 27, §VI · p. 27
Loading 1912.11158v2…