Imagine you're a food inspector and your job is to measure how unpredictable a dice is — not whether its average roll is fair, but whether its most-likely face is suspiciously dominant. You don't get to look inside the die; you can only roll it and count outcomes. The question is: how many rolls do you need before you can confidently say 'the worst-case predictability of this die is X, within ±ε, and I'm right 99% of the time'? This paper gives the exact answer — not just an upper bound, but a matching lower bound — for both ordinary dice (classical distributions) and quantum dice (density matrices). That's the full picture. The committed claim: the sample complexity of min-entropy estimation to additive error ε with confidence 1−δ is Θ(d·log(d/δ)/ε²) for classical distributions over d symbols, and Θ((d²+d·log(1/δ))/ε²) for quantum states on d-dimensional Hilbert spaces. Both bounds are tight — upper and lower match up to constants. The classical result resolves an open question that has lingered since the NIST SP 800-90B standard made min-entropy estimation a mandatory step in certifying cryptographic random number generators. The quantum result settles the analogous question for quantum entropy sources. To understand why this matters, you need to know the ladder. Min-entropy is the hardest entropy measure to estimate because it depends on the single largest probability mass — the worst case, not the average. Prior work established that estimating Shannon entropy over d symbols requires Θ(d/log d) samples, and Rényi entropies of integer order have been studied extensively. But min-entropy (the ∞-Rényi entropy) had resisted tight characterization, especially in the high-probability regime where you need the estimate to hold with probability 1−δ for small δ. The best previous classical upper bound was O(d·log(d/δ)/ε²) from distribution-learning arguments, but no matching lower bound existed. For quantum states, the picture was even less complete: tomography-based approaches give O(d²/ε²) but the dependence on δ was not nailed down. This paper closes both gaps simultaneously. The proof architecture is what makes this paper distinctive: it's short (9 pages) and elementary. The classical upper bound reduces min-entropy estimation to distribution learning in ℓ∞ norm — if you can learn the full distribution well enough in max-entry error, you can read off min-entropy. The lower bound uses a carefully constructed pair of distributions that differ in min-entropy by ε but require many samples to distinguish. For the quantum case, the upper bound uses quantum state tomography in operator norm, while the lower bound leverages quantum state discrimination arguments. No heavy machinery — no information-theoretic meta-theorems, no involved coupling arguments. The simplicity of the proofs is itself a contribution: it suggests the community was overthinking the problem. Integrity is strong for this type of result. These are mathematical proofs, not simulations — the bounds are proved, not empirically estimated. There is no cherry-picking risk because the claims are existential (matching upper and lower bounds). The only caveat is that the constant factors hidden inside the Θ notation are not optimized, which matters if you're writing a NIST implementation with a specific sample budget. But for the theoretical question — what is the right scaling? — this is definitive. The practical implication flows directly into cryptographic certification. NIST SP 800-90B requires entropy source testing, and min-entropy is the core quantity. This paper tells NIST exactly how many samples are necessary and sufficient to certify a source to a given confidence level. If your source has d=256 output symbols and you want ε=0.1 error at 99.9% confidence, you now know the sample count scales as Θ(256·log(256000)/0.01) — roughly on the order of millions of samples, which is feasible but not trivial. For quantum random number generators, the d² scaling is more punishing: a d=64 quantum source requires on the order of 4096/ε² samples, making high-confidence certification of high-dimensional quantum sources expensive. The successor experiment this paper didn't run is the constant-factor optimization: what are the actual leading constants, and can they be made small enough for practical deployment? The honest read is option (c) — this is a theory paper that settles the scaling question cleanly, and constant-factor optimization is a different kind of work (algorithmic engineering, not proof technique) that the author is likely leaving to implementers or a follow-up.
The analogy
You're a food inspector measuring how biased a die is — not the average roll, but whether the most-likely face is too dominant. How many rolls do you need before you can say 'the worst-case predictability is X ± ε' and be right 99% of the time? This paper gives the exact answer for both regular dice and quantum dice.
Dice inspector
Rolling a die N times to bound the probability of its most-likely face within ±ε at confidence 1−δ
Min-entropy estimator
Drawing N samples from a d-symbol source to bound min-entropy within ±ε at confidence 1−δ
Honest assessment
This is a clean, definitive theoretical result that closes two open problems in a single 9-page paper. The proofs are elementary, the claims are tight, and the implications for NIST cryptographic certification are concrete. What it doesn't do is hand you deployable code or optimized constants — that's the next step. If you work on randomness certification, entropy estimation, or quantum information, this is a paper you'll cite. If you're a practitioner waiting for a sample-size calculator, you'll need the follow-up.
What Is CLAIMS?
80
/ 100
BedrockNews applies a structured analytical framework called CLAIMS to academic papers and technical research releases.
How CLAIMS worksClaim
5/5
Ladder
4/5
Architecture
4/5
Integrity
5/5
Milestone
3/5
Successor
3/5
What is this paper actually committing to?
Genuine resolution: tight Θ bounds for min-entropy estimation in both classical and quantum settings, closing an open problem relevant to NIST SP 800-90B. Not incremental — this is the final answer on scaling.
The field fight
Can min-entropy — the hardest entropy functional to estimate — be characterized as tightly as Shannon entropy and Rényi entropies?
Side A
Min-entropy estimation is fundamentally harder than other entropies and resists tight bounds due to worst-case dependence on the max probability
Held by: Prior complexity-theoretic literature, NIST working groups
Side B
Simple reductions to distribution learning / tomography suffice, and matching lower bounds are achievable with elementary techniques
Held by: This paper
Milestone tracker
Unlocks: Exact sample budget formulas for NIST SP 800-90B entropy source certification, both classical and quantum RNGs
Current
Θ
tight scaling
This paper
Next
O(c·d·log(d/δ)/ε²)
explicit constant c
NIST-deployable bound
~1-2 years for constant optimization and practical algorithm design
Verified Facts (5)
Min-entropy estimation sample complexity: Θ(d·log(d/δ)/ε²) for classical distributions on d symbols
Min-entropy estimation sample complexity: Θ((d²+d·log(1/δ))/ε²) for quantum states on d-dimensional Hilbert space
NIST SP 800-90B specifies min-entropy estimation as a key procedure for entropy sources used in cryptographic random bit generators
Paper is 9 pages
Categories: cs.IT, math.ST, quant-ph
Practical Implications (3)
NIST SP 800-90B implementers now know the exact sample scaling needed for min-entropy certification — no over- or under-sampling
Quantum RNG certification requires d² samples, confirming that high-dimensional quantum sources are quadratically more expensive to certify than classical ones
The elementary proof techniques suggest that similar tight bounds for related entropy measures may be achievable with the same approach
More latest news
Read all