PaperlayerView exact revision on arXiv

Source-linked AI summary

Device-independent randomness expansion against quantum side information

Wen-Zhao Liu, Ming-Han Li, Sammy Ragy, Si-Ran Zhao, Bing Bai, Yang Liu, Peter J. Brown, Jun Zhang, Roger Colbeck, Jingyun Fan, Qiang Zhang, Jian-Wei Pan

arXiv:1912.11159v2quant-ph

TL;DR

Device-independent randomness expansion must overcome the limited tightness of existing security bounds and the randomness consumed by prior experiments. This work develops tighter entropy-accumulation bounds and a spot-checking protocol, achieving certified net randomness with a soundness error of 3.09 × 10^-12.

  • Problem

    Existing device-independent randomness experiments consumed more randomness than they generated, leaving randomness expansion elusive and technically challenging.

  • Method

    The paper combines tighter entropy accumulation with a device-independent spot-checking protocol and convex optimization of the accumulated-entropy bound.

  • Results

    2.57 × 10^8 net bits were certified with a soundness error of 3.09 × 10^-12, and the output streams passed the NIST statistical test suite.

  • Takeaways & Limitations

    The experiment establishes device-independent randomness expansion against quantum adversaries under the protocol’s security assumptions.

Abstract

from arXiv · show

The ability to produce random numbers that are unknown to any outside party is crucial for many applications. Device-independent randomness generation does not require trusted devices and therefore provides strong guarantees of the security of the output, but it comes at the price of requiring the violation of a Bell inequality for implementation. A further challenge is to make the bounds in the security proofs tight enough to allow randomness expansion with contemporary technology. Although randomness has been generated in recent experiments, the amount of randomness consumed in doing so has been too high to certify expansion based on existing theory. Here we present an experiment that demonstrates device-independent randomness expansion. By developing a Bell test setup with a single-photon detection efficiency of around $84\%$ and by using a spot-checking protocol, we achieve a net gain of $2.57\times10^8$ certified bits with a soundness error $3.09\times10^{-12}$. The experiment ran for $19.2$ h, which corresponds to an average rate of randomness generation of $13,527$ bits per second. By developing the entropy accumulation theorem, we establish security against quantum adversaries. We anticipate that this work will lead to further improvements that push device-independence towards commercial viability.

A. Security definition

The paper defines security by requiring soundness against an adversary holding quantum side information and completeness for an honest implementation. A seeded extractor converts conditional smooth min-entropy into output that is nearly uniform and independent of the adversary.

  • Security definition: Completeness requires an honest implementation whose probability of not aborting is at least 1 − ϵC.
  • Security definition: Soundness bounds the distance between the protocol output and an ideal uniform output independent of the adversary’s information.The adversary’s marginal remains unchanged in the idealized comparison.
  • Extraction and unpredictability: A seeded extractor uses the raw output and random seed to produce randomness that is almost indistinguishable from uniform.The output length is roughly determined by the smooth min-entropy conditioned on Eve’s side information.
  • Security definition: The smooth min-entropy quantifies unpredictability against quantum side information through a guessing-probability interpretation.The paper bounds this quantity for the device-independent protocol using the entropy accumulation theorem.

B. Theoretical details about the protocol

The protocol uses spot-checking to test a CHSH violation on randomly selected rounds while generating output on the remaining rounds. Its security relies on protected devices, trusted classical processing and initial randomness, together with quantum theory and entropy accumulation.

  • Protocol operation: The protocol counts lost CHSH test rounds and aborts when their number exceeds nγ(1 −(ωexp −δ)).The CHSH score is computed from binary inputs X,Y and outputs A,B, with a win when A⊕B = X·Y.
  • Entropy accumulation: The entropy accumulation theorem converts an observed CHSH score into a lower bound on accumulated entropy, including finite-statistics corrections.The bound uses an affine lower bound on single-round von Neumann entropy and explicit correction functions.
  • Randomness accounting: The protocol consumes input randomness for test-round selection and CHSH inputs, while extractor seeding is not counted as consumed.The expected input randomness contains Hbin(γ) from test selection and 2γ from CHSH input selection.
  • Protocol assumptions: Security assumes a secure laboratory, a trusted classical computer, initial trusted randomness, and validity of quantum theory.Shielding prevents device communication and removes the need to close the locality loophole in the experiment.

3. Extraction

A quantum-proof strong extractor turns the protocol’s raw output into nearly uniform bits while preserving the extractor seed as reusable randomness. The experiment implements this extraction with large Toeplitz-matrix computations accelerated by FFTs.

  • Extraction: A quantum-proof strong extractor outputs nearly uniform randomness from a string with sufficient min-entropy against quantum side information.The extractor’s strong property keeps the seed random and uncorrelated with the output and adversary’s information.
  • Toeplitz extraction: The experiment uses binary Toeplitz matrices as quantum-proof strong extractors, with the random matrix specified by its first row and column.Binary Toeplitz matrices form a two-universal hash family.
  • Implementation: FFT-based multiplication reduces Toeplitz extraction time complexity from O(m^2) to O(m log m), enabling processing of the large output data.The computation is split into blocks to reduce memory requirements.
  • Implementation: The implementation extracts approximately 6.496 × 10^9 bits from a 3.17 × 10^12-bit output string using Toeplitz hashing.The computation used the Viking research cluster and required around 249 hours across 32 cores.

4. Error parameters

The paper separates completeness and soundness errors and bounds them using concentration inequalities, entropy accumulation, and extractor parameters. These bounds quantify both honest-protocol aborts and adversarial deviations from ideal randomness.

  • Completeness error: For an honest implementation, the completeness error bounds the probability that statistical fluctuations cause the protocol to abort.The score registers follow a binomial distribution, enabling a binomial concentration bound.
  • Soundness error: The device-independent error accounts for the possibility of lucky adversarial strategies and depends on the probability that the protocol does not abort.Replacing the unknown pass probability with ϵEAT preserves a valid entropy lower bound in the relevant cases.
  • Soundness error: The soundness error also includes smoothing and extractor errors, with the extractor contribution set to ϵEXT = 10^-5 ϵh in the calculations.The smoothing parameter has the larger impact on both soundness and certifiable smooth min-entropy.

6. Entropy Accumulation

The paper refines entropy accumulation by retaining score-dependent information in the error terms, producing tighter entropy bounds that make device-independent randomness expansion experimentally accessible.

  • The construction represents protocol rounds as sequential EAT channels satisfying finite-dimensional classical-output and conditional-independence constraints.The channel collection captures sequential device interactions, with the residual system carrying the evolving quantum state.
  • The framework defines achievable score distributions and min-tradeoff functions to lower-bound worst-case single-round von Neumann entropy.Rate functions are defined over score distributions achievable by the channel set, while affine rate functions extend to all probability distributions over X.
  • The refined entropy-accumulation analysis improves rates by using score-dependent rate bounds instead of statistics-independent worst-case simplifications.The method defines Δ(f, p) as the difference between a rate function and a min-tradeoff function, preserving information about the observed distribution.
  • The modified theorem applies to sequential EAT channels and bounds the entropy of accepted protocol outputs against quantum side information.The framework models each round as a channel producing systems A, B, X, and a residual quantum system, while allowing an adversary-held system E.
  • The Δ(f, p) term both contributes positively to the final entropy and constrains error-term optimization near the observed score distribution.Choosing min-tradeoff functions tangent to convex rate functions makes Δ grow when candidate distributions move far from the tangent point.

8. Non-local games and convexity

The section reformulates the entropy-accumulation analysis for CHSH protocols and establishes convexity properties that make the spot-checking optimization tractable.

  • CHSH specialization: The notation is adapted from general entropy accumulation to CHSH by replacing the score, output, and input registers with U, AB, and XY.The CHSH protocol uses a binary test-round score U and joint outputs and inputs.
  • Convexity results: The achievable score distributions from no-signalling channels form a convex set.Convexity follows because no-signalling output distributions are convex and the score is a deterministic function of the outputs and inputs.
  • Convexity results: The optimal conditional-entropy rate rateopt(q) is convex over the achievable score distributions.This convexity is established by combining compatible channels and states through a flagged mixture.
  • Convexity results: The resulting infimum for a device-independent spot-checking protocol is a convex optimization problem.The corollary combines convexity of the achievable distributions, rate functions, and the spot-checking construction.
  • CHSH entropy bound: For CHSH, tangent min-tradeoff functions are optimized over their tangent point and α before entropy extraction is applied.The CHSH rate function is defined from the winning probability, while spot-checking adds a no-test outcome and an optimized parameter c⊥.
  • CHSH entropy bound: Changing the abort condition can yield a similar entropy expression, but one alternative gives worse error parameters.The stated alternative abort rule uses c⊥ = gt(δ1), whereas a two-sided rule can recover the same expression.

1. Determination of single photon efficiency

The experiment characterizes single-photon heralding efficiency from coincidence and single-detection rates, with optical-efficiency components tabulated for the experiments.

  • Efficiency definition: Single-photon heralding efficiency is defined as ηA = C/NB and ηB = C/NA for Alice and Bob.C denotes two-photon coincidence events, while NA and NB denote single-photon detection events.
  • Efficiency characterization: Table II characterizes the optical-efficiency contributions used to determine the experimental efficiencies.The listed components include coupling into single-mode fibre and optical transmittance losses.

2. Quantum state and measurement bases

The main experiment uses a non-maximally entangled two-photon state with optimized measurement bases and reports high measured visibility and state fidelity.

  • State and bases: The target state is cos(α)|HV⟩ + sin(α)|VH⟩ with α = 27.76°, and the mean photon number is optimized to 0.52 for the CHSH score.Alice’s bases are A1 = −82.30° and A2 = −118.72°, while Bob’s are B1 = 7.70° and B2 = −28.72°.
  • State characterization: At mean photon number µ = 0.0034, measured visibility reaches 99.4% in the horizontal/vertical basis and 98.5% in the diagonal/anti-diagonal basis.The visibility measurements use basis sets selected for minimum and maximum coincidence.
  • State characterization: The reconstructed non-maximally entangled state has 99.06% fidelity.The reported imperfections are attributed to multi-photon components, imperfect optical elements, and imperfect spatial or spectral mode matching.
  • Space-like configuration: The space-like experiment uses the same analysis method and tests, with its parameters and comparison reported in Table III.Table III concerns the quantum states and measurement bases used in the experiment.

3. Spacetime configuration of the experiment

The space-like configuration separates Alice’s and Bob’s stations and times the source, setting, and measurement events to ensure the required spacetime separation.

  • Timing budget: The source generates entangled photon pairs in TE = 10 ns, while QRNG, delay, Pockels-cell, and detector intervals determine the setting and measurement timing.The detailed timing parameters include QRNG generation, QRNG-to-Pockels-cell delay, Pockels-cell readiness, and SNSPD signal output.
  • Spacetime constraints: The setting-generation events lie outside the future light cone of the entanglement-creation event at the source.This is the spacetime condition shown for Alice’s and Bob’s random input-setting events.
  • Station geometry: The arrangement places Alice and Bob 93 ± 1 m and 90 ± 1 m from the source, with effective optical lengths of 130 m and 118 m, respectively.The stations are positioned on opposite sides of the source.
  • Spacetime constraints: The timing configuration ensures space-like separation between each measurement event and the distant setting event, and between setting choices and photon-pair emission.The pair-generation interval is TE = 10 ns, and the measurement interval is TA,B M = 100 ns.

1. Parameter determination

The protocol parameters were selected to witness randomness expansion under two expected CHSH scores, with testing probabilities chosen near the expansion-rate optima. The main experiment used ϵS = 3.09 × 10−12, ϵC = 1 × 10−6, and 1.3824 × 10^11 rounds.

  • 1. Parameter determination: 1.3824 × 10^11 rounds were used in the main experiment, exceeding the 8.951 × 10^10 rounds estimated to witness expansion.The experiment ran for 19.2 hours, while the space-like experiment used 3.168 × 10^12 rounds over 220 hours.
  • 1. Parameter determination: The expected CHSH scores were ωexp = 0.750809 for the space-like experiment and ωexp = 0.752487 for the main experiment.These values were used to determine the minimum rounds and optimized testing probabilities.
  • 1. Parameter determination: The chosen testing probabilities were γ = 1.194 × 10−4 and γ = 3.264 × 10−4 for the two experiments, with expansion rate changing slowly around the optimum.The figure compares expected and actual round counts for ωexp = 0.750809 and ωexp = 0.752487.
  • 1. Parameter determination: The expansion-rate analysis compares expected minimum rounds with actual rounds and uses a threshold to identify when expansion is witnessed.The parameter table defines nmin as the minimum expected rounds required for expansion at each expected score and optimized γ.

2. Experimental results

The experiments measured CHSH scores above the classical threshold, extracted genuinely quantum-certified random bits, and obtained positive net output that passed the NIST test suite. The main experiment produced 2.57 × 10^8 net bits after 19.2 hours.

  • 2. Experimental results: The measured CHSH scores were 0.750805 for the space-like experiment and 0.752484 for the main experiment.The main experiment collected data continuously for 19.2 hours, whereas the space-like setup required periodic recalibration because environmental effects reduced visibility.
  • 2. Experimental results: 2.57 × 10^8 net bits were obtained in the main experiment after subtracting consumed randomness, alongside 2.63 × 10^8 net bits in the space-like experiment.The extracted streams contained 9.350 × 10^8 and 6.496 × 10^9 genuinely quantum-certified bits, respectively, with uniformity within 3.09 × 10−12.
  • 2. Experimental results: The measured CHSH violation was monitored over time, with recalibration intervals shown for the space-like experiment.The main experiment had no calibration break during its 19.2-hour data collection, while the space-like experiment used recalibration based on observed CHSH scores.
  • 2. Experimental results: Both random-bit streams passed the NIST statistical test suite after being divided into 1 Mbit sections.The tests were applied to the 6.496 × 10^9-bit and 9.350 × 10^8-bit outputs.
Loading 1912.11159v2…