TRANSMISSION // 2611.23116v1

How many samples reveal a source’s worst-case randomness?

Source published

A new theoretical analysis gives matching sample requirements for estimating min-entropy in classical distributions and quantum states, with confidence levels made explicit.

AI-generated conceptual illustration for How many samples reveal a source’s worst-case randomness?
AI-generated conceptual illustration; not documentary evidence.

Randomness is only useful when its predictability can be assessed. Qisheng Wang’s preprint studies how many observations are needed to estimate min-entropy reliably, both for ordinary probability distributions and for quantum states.

Min-entropy asks a deliberately cautious question: how likely is the single most predictable outcome? For a classical source, it is determined by the probability of the most common result. A source with a highly likely outcome has low min-entropy; one whose outcomes are less concentrated has higher min-entropy. This worst-case perspective makes min-entropy useful in analyzing randomness and cryptographic random-bit generators. NIST SP 800-90B includes min-entropy estimation in its guidance for assessing entropy sources.

But an estimate is only useful if we know how much data it needs. Qisheng Wang’s preprint, “Optimal Min-Entropy Estimation with High Probability,” asks for the sample complexity: how many observations are needed to estimate min-entropy within a chosen additive error, while succeeding with probability at least 1 − δ? The paper treats both classical distributions over d possible outcomes and quantum states in a d-dimensional space.

Two kinds of source, two estimators

For the classical case, imagine recording repeated outputs from a source with d possible symbols. The paper’s estimator counts how often each symbol appears, identifies the most frequent one, and uses its observed frequency to estimate min-entropy. The analysis establishes how many independent samples suffice, and proves a matching lower bound: in general, an estimator cannot succeed with substantially fewer samples.

For the quantum case, the unknown state is accessed through independent copies. The proposed method uses weak Schur sampling, a collective measurement whose outcome contains information about the state’s spectrum—roughly, the distribution of its eigenvalues. The estimator uses the largest part of that outcome to estimate the state’s largest eigenvalue, which determines quantum min-entropy. Again, the paper proves both an upper bound on the samples needed and a lower bound showing that the dependence is unavoidable in general.

The main results are expressed using Θ, meaning that the required number of samples is bounded above and below by constant multiples of the stated quantities. For classical distributions, the complexity is Θ(d log(d/δ) / ε²). For quantum states, it is Θ((d² + d log(1/δ)) / ε²). Here ε is the allowed additive error and δ is the probability of failure. Smaller error tolerances require more samples; demanding greater confidence—smaller δ—also increases the requirement.

What the comparison says

The results show different dimension-dependence in the two mathematical settings: the classical expression scales linearly with d, while the quantum expression includes a d² term. In the quantum bound, the confidence-dependent term grows with d log(1/δ), rather than multiplying the entire dimension-squared term by log(1/δ). The paper describes this as improving on simply applying a median-based confidence amplification to an earlier quantum estimator. For a fixed, constant failure probability, its quantum result also confirms the optimality of the earlier estimator’s dimension-squared dependence.

These are theoretical sample-complexity statements, not a report of laboratory trials or a demonstration that a particular random-number generator is secure. They say how the number of samples must scale in the stated estimation problems; they do not, on their own, verify that a real device produces independent samples or meets a cryptographic standard.

What remains uncertain

The work’s contribution is a pair of mathematical bounds and relatively short proofs. Applying them in practice still involves the details of the source, the available measurements, and the assumptions behind the sampling model. In particular, the quantum analysis concerns copies of an unknown state and a specified measurement procedure; it is not a universal prescription for every experimental setup.

The source provided here is an arXiv preprint, not evidence of peer review or independent replication. The paper also refers to recent related work, so its account of what was previously known should be read as the author’s framing rather than a comprehensive field assessment. Its central claims are formal bounds within defined models, not empirical validation of cryptographic systems.

Automatically matched by shared topic keywords. These links do not imply that the sources agree or establish a consensus.