Curator's Take
This article shows how quantum‑algorithmic ideas can shave the sample complexity for estimating high‑order Rényi‑type functionals from quadratic in α down to linear, a breakthrough that closes a long‑standing gap between known upper bounds and minimax optimal rates. By delivering a unified estimator that works for both classical distributions and mixed quantum states and runs in linear time on a quantum processor, the work demonstrates a concrete statistical advantage of quantum primitives beyond speed‑ups for simulation. The result not only tightens theoretical limits but also points to practical gains in tasks such as entropy estimation for massive alphabets or high‑dimensional quantum systems where data are scarce.
— Mark Eatherly
Summary
We propose a novel approach to the minimax estimation of high-order functionals from the perspective of quantum computing. Specifically, for any real number $α\gg 1$, we present two estimators, one for the classical functional $\mathrm{F}_α(P) = \sum_{i=1}^S p_i^α$ of a discrete distribution $P$ and the other for the quantum functional $\mathrm{F}_α(ρ) = \operatorname{tr}(ρ^α)$ of a mixed state $ρ$. These functionals have close connections with the Rényi entropy and the Tsallis entropy. We show that both estimators achieve the minimax optimal $L_2$ rate $α\mathsf{n}^{-1}$ in the range $α\lesssim \mathsf{n} \lesssim α^{3-o(1)}$, where the support size $S$ of $P$ or the dimension of $ρ$ can be much larger than the number of samples $\mathsf{n}$. As a result, both estimators achieve the \textit{optimal} sample complexity $\mathsf{n} \asymp α$, improving upon the prior best upper bounds $O(α^2)$ established by Jiao, Venkat, Han, and Weissman (IEEE Trans. Inf. Theory 2017) for classical functionals and Chen and Wang (COLT 2025) for quantum functionals. Our estimators are constructed under a unified framework using quantum primitives and run in linear time on a quantum computer. This work reveals an unexpected path from quantum computing to statistics, suggesting a conceptually new methodology for functional estimation. It adds to the growing list of quantum proofs for classical theorems.