Quantum information · Theory (AI-assisted)

Optimal Min-Entropy Estimation with High Probability

Qisheng Wang

arXiv:2611.23116v1 ↗PDF ↗Submitted 17 November 2026

Question
Min-entropy, \(-\log\max_ip_i\), measures how hard the most likely outcome of a source is to guess, and it fixes how many nearly uniform bits a randomness extractor can produce. Certification of entropy sources for cryptographic random number generators (NIST SP 800-90B) requires estimating it from samples. How many samples are needed to estimate the min-entropy of an unknown distribution on \(d\) symbols, or of an unknown \(d\)-dimensional quantum state, to additive error \(\varepsilon\) with failure probability at most \(\delta\)? The upper and lower bounds known before did not match in either case.
Result
Both cases are settled. For distributions the answer is \(\Theta(d\log(d/\delta)/\varepsilon^2)\) samples, achieved by taking the empirical frequency of the most common symbol; the new part is a matching lower bound. For quantum states it is \(\Theta((d^2+d\log(1/\delta))/\varepsilon^2)\) copies, achieved by weak Schur sampling and the length of the first row of the measured Young diagram, with a matching lower bound. In the quantum case the dependence on \(\delta\) adds to the \(d^2\) term rather than multiplying it, so the standard median trick, which gives \(d^2\log(1/\delta)/\varepsilon^2\), is not optimal. Each proof takes about a page.

The paper in detail

A source with \(k\) bits of min-entropy yields \(k-2\log_2(1/\eta)\) bits within distance \(\eta\) of uniform through universal hashing, so min-entropy, not Shannon entropy, decides how much randomness can be extracted. Standards for random number generators therefore require an estimate of it. The question is a sample complexity: how many independent samples of an unknown distribution \(p\) on \(d\) symbols, or copies of an unknown state \(\rho\) with min-entropy \(-\log\|\rho\|_\infty\), are needed for an estimate within \(\varepsilon\) with probability \(1-\delta\). Before this paper the classical upper bound \(O(d\log(d/\delta)/\varepsilon^2)\) faced a lower bound \(\Omega(d\log d)\); in the quantum case \(O(d^2\log(1/\delta)/\varepsilon^2)\) faced \(\Omega(d/\varepsilon+d\log d)\).

The classical estimator is the obvious one: take the largest empirical frequency. An additive error \(\varepsilon\) on \(-\log p_\star\) needs relative error about \(\varepsilon/2\) on \(p_\star\), and \(p_\star\) can be as small as \(1/d\); estimating a probability of order \(1/d\) to relative accuracy \(\varepsilon\) takes about \(d/\varepsilon^2\) samples, and a union bound over the \(d\) symbols that might overshoot adds the \(\log(d/\delta)\). The lower bound shows that the union bound is not wasteful: a distribution with one slightly heavy symbol at an unknown position is hard to tell from the uniform one, and averaging over the \(d\) possible positions makes the factor \(\log(d/\delta)\) unavoidable.

For quantum states the estimator is weak Schur sampling: by Schur–Weyl duality, \(\rho^{\otimes m}\) decomposes into blocks labelled by Young diagrams with \(m\) boxes, and measuring which block the state is in yields a diagram \(\Lambda\). Its first row \(\Lambda_1\) has the same law as the longest nondecreasing subsequence of \(m\) letters drawn from the spectrum, so \(\Lambda_1/m\) estimates the largest eigenvalue with a bias of at most \(2\sqrt{2m}/m\). Making that bias smaller than \(\varepsilon p_1\) costs \(d^2/\varepsilon^2\) copies regardless of \(\delta\); fluctuations then cost only \(d\log(1/\delta)/\varepsilon^2\). The lower bound uses a state with one slightly heavy eigenvector in a Haar-random direction, which is hard to tell from the maximally mixed state with fewer than \(d^2/\varepsilon^2\) copies, and adds the classical bound for the \(\delta\) term.

Natural next questions are the corresponding bounds when samples are correlated, as for physical noise sources with memory, the high-probability sample complexity of the other Rényi entropies of non-integer order, and the cost of quantum min-entropy estimation when each copy must be measured separately.

Transferable methods

  1. Chernoff bounds with a union bound, matched by a hidden-spike lower bound

    The upper bound needs each symbol's empirical frequency to stay below \((1+\varepsilon/2)p_\star\) and the true maximum's frequency to stay above \((1-\varepsilon/2)p_\star\). A multiplicative Chernoff bound for each, a union bound over symbols, and \(p_\star\ge1/d\) give the sample size. The lower bound turns any good estimator into a test between the uniform distribution and a mixture of spiked ones, and a second-moment computation shows that the test fails unless the sample is as large as the upper bound.

    With \(\hat p=\max_iN_i/m\), the Chernoff–Hoeffding bounds \(\Pr[X>(1+\varepsilon)\mathbb EX]\le e^{-\varepsilon^2\mathbb EX/3}\) and \(\Pr[X<(1-\varepsilon)\mathbb EX]\le e^{-\varepsilon^2\mathbb EX/2}\), applied to the counts, give \[\Pr\Bigl[|\hat p-p_\star|>\tfrac{\varepsilon}{2}p_\star\Bigr]\le e^{-\varepsilon^2mp_\star/8}+d\,e^{-\varepsilon^2mp_\star/12}\le(d+1)\,e^{-m\varepsilon^2/(12d)},\] using \(p_\star\ge1/d\). Editorial step: on the complementary event \(|\ln\hat p-\ln p_\star|\le-\ln(1-\varepsilon/2)\le\varepsilon\) for \(\varepsilon<1\), so \(m=\lceil(12d/\varepsilon^2)\ln((d+1)/\delta)\rceil\) suffices.

    For the lower bound let \(q^{(j)}\) put mass \((1+4\varepsilon)/d\) on symbol \(j\) and spread the rest evenly, so its min-entropy is \(\ln(1+4\varepsilon)>2\varepsilon\) below that of the uniform \(u\). An estimator with failure probability \(\delta\) separates \(u^{\otimes m}\) from \(P=\tfrac1d\sum_j(q^{(j)})^{\otimes m}\), and Cauchy–Schwarz gives \(\mathbb E_u[P^2]\ge(1-\delta)^2/(d^{2m}\delta)\). Expanding the square over pairs of positions, \[\mathbb E_u[P^2]=\frac{1}{d^{2m+1}}\Bigl(1+\frac{16\varepsilon^2}{d-1}\Bigr)^m+\frac{d-1}{d^{2m+1}}\Bigl(1-\frac{16\varepsilon^2}{(d-1)^2}\Bigr)^m\le\frac1{d^{2m}}\Bigl(1+\frac{e^{16m\varepsilon^2/(d-1)}-1}{d}\Bigr),\] which forces \(m\ge\frac{d-1}{16\varepsilon^2}\ln\bigl(1+d(1-3\delta+\delta^2)/\delta\bigr)\). The factor \(1/d\) in front of the exponential comes from the unknown position, and it is why \(\log(d/\delta)\) rather than \(\log(1/\delta)\) appears.

    Editorial check: summing \(P(\mathbf x)^2\) over all \(d^m\) sequences reproduces the exact expression for three \((d,m)\) pairs to \(10^{-16}\). In simulation with \(d=20\), \(\varepsilon=0.2\), \(\delta=0.05\), the empirical estimator at \(m=36{,}242\) never failed; at a sixteenth of that it failed 17% of the time on the uniform distribution and essentially never on one with \(p_\star=0.3\), confirming that near-uniform sources are the hard case, as the lower-bound construction assumes. The inequality \(\ln(1+4\varepsilon)>2\varepsilon\) used in the construction holds only for \(\varepsilon<0.628\).

    How to reuse it

    Planting a small perturbation at a random one of \(d\) locations and bounding the second moment of the likelihood ratio is a general way to prove \(\log(d/\delta)\) lower bounds in the high-probability regime, for testing support size, identity or the largest probability. When it matches a union bound, the union bound was optimal.

  2. Weak Schur sampling and the longest increasing subsequence

    The spectrum of an unknown state can be estimated without learning its eigenbasis by measuring the permutation symmetry of many copies. The outcome is a Young diagram whose rows estimate the ordered eigenvalues. Greene's theorem identifies the first row with the longest nondecreasing subsequence of a random word, a classical object whose mean and concentration are known; its bias fixes the \(d^2\) term and its fluctuations the \(d\log(1/\delta)\) term.

    By Schur–Weyl duality \((\mathbb C^d)^{\otimes m}\cong\bigoplus_{\lambda}\mathcal P_\lambda\otimes\mathcal Q^d_\lambda\) over Young diagrams \(\lambda\) with \(m\) boxes and at most \(d\) rows, and the projective measurement onto these blocks returns \(\lambda\) with probability \(\dim(\mathcal P_\lambda)\,s_\lambda(p_1,\dots,p_d)\), a Schur polynomial in the eigenvalues. The first row \(\Lambda_1\) has the law of the longest nondecreasing subsequence of \(W_1,\dots,W_m\) drawn independently with \(\Pr[W=j]=p_j\). Hence \[mp_1\le\mu=\mathbb E\Lambda_1\le mp_1+2\sqrt{2m},\qquad\Pr\bigl[|\Lambda_1-\mu|\ge t\bigr]\le2\exp\Bigl(-\frac{t^2}{2(\mu+t/3)}\Bigr).\]

    Editorial derivation of Theorem 3.2: an error \(\varepsilon p_1/2\) in \(\Lambda_1/m\) is avoided if the bias \(2\sqrt{2m}\) is at most \(\varepsilon mp_1/4\) and the fluctuation is at most another \(\varepsilon mp_1/4\). The first condition is \(m\ge128/(\varepsilon^2p_1^2)\), at most \(128d^2/\varepsilon^2\) since \(p_1\ge1/d\). For the second, \(\mu+\varepsilon mp_1/12\le\tfrac43mp_1\), so the exponent is at least \(3\varepsilon^2mp_1/128\ge3\varepsilon^2m/(128d)\), and failure probability \(\delta\) needs \(m\gtrsim(d/\varepsilon^2)\log(2/\delta)\). The two costs add, which is the source of \(d^2+d\log(1/\delta)\). For the matching lower bound, \(\rho_v=\mathbb I/d+\frac{4\varepsilon}{d-1}(\ket v\bra v-\mathbb I/d)\) with Haar-random \(v\) has the spectrum of the classical spike, and a lemma the paper cites bounds the trace distance from \((\mathbb I/d)^{\otimes m}\) by \(\sqrt{R/(1-R)}\) with \(R=32m\varepsilon^2/(d-1)^2\).

    Editorial check: simulated longest nondecreasing subsequences for the uniform spectrum with \((d,m)=(4,400),(10,1000),(10,4000)\) have means 124, 149 and 499, between \(mp_1\) and \(mp_1+2\sqrt{2m}\) (157, 189, 579). Requiring \(\sqrt{R/(1-R)}\ge1/3\) gives \(R\ge1/10\), that is \(m\ge(d-1)^2/(320\varepsilon^2)\); the paper states the weaker \((d-1)^2/(512\varepsilon^2)\), which also holds.

    How to reuse it

    Spectrum estimation through Young diagrams applies to any spectral quantity: the bias of the row lengths sets a state-independent \(d^2\) cost, and concentration of increasing-subsequence statistics sets the confidence cost. Separating the two is what shows that boosting by repetition and taking medians is wasteful in the high-confidence regime.

Source: Section 2.1 (Theorem 2.1, Proposition 2.2), Section 2.2 (Theorem 2.4), Section 3.1 (Definition 3.1, Proposition 3.3, Theorem 3.2), Section 3.2 (Lemma 3.5, Theorem 3.4). Based on the linked paper version. Derivations marked as editorial, and suggested uses in other problems, are editorial guidance rather than results of the paper.

Context & limitations

Why it matters. The result closes a question with direct use in certifying entropy sources and gives the high-probability regime, which is the one a certification standard needs, rather than constant failure probability. It also corrects the record: an earlier claimed sample complexity of \(\Theta(d/\log d)\) was mistaken, and the recent upper bound of Adibi and Krysta is now shown to be optimal. Tight high-probability bounds were previously known for only a handful of testing and estimation problems.

Limitations. Samples are assumed independent and identically distributed; physical entropy sources can have memory, which is outside the model. The constants are explicit but large (12 and 128 in the upper bounds), and the lower-bound construction needs \(\varepsilon\) small enough that \(\ln(1+4\varepsilon)>2\varepsilon\), about \(\varepsilon<0.63\), which does not affect the asymptotic statements. The quantum estimator measures all copies collectively, which requires entangling operations across copies; the bound for measurements made copy by copy is not addressed. The author states that large language models were used to explore proof strategies, and that the author distilled the arguments into the proofs presented and wrote the manuscript.

Description based on the full arXiv HTML of v1 (the whole paper), read 2026-11-20. Editorial checks: the exact second moment of Eq. (5) agrees with brute-force enumeration for \((d,m)=(3,4),(4,5),(5,4)\) to \(10^{-16}\) and lies below the stated exponential bound; for \(d=20\), \(\varepsilon=0.2\), \(\delta=0.05\) the empirical estimator at the Theorem 2.1 sample size \(m=36{,}242\) never failed in 2000 trials, for both a uniform and a spiked distribution, and at \(m/16\) and \(m/64\) it failed 17% and 96% of the time on the uniform distribution but almost never on the spiked one; simulated longest nondecreasing subsequences for uniform spectra stay within the bias bound \(mp_1+2\sqrt{2m}\); and the constant in the quantum lower bound, where requiring a trace distance of at least \(1/3\) gives \(m\ge(d-1)^2/(320\varepsilon^2)\), stronger than the stated \(512\).