Towards Minimax Estimation of High-Order Functionals by Quantum Arguments

We propose a novel approach to the minimax estimation of high-order functionals from the perspective of quantum computing.

Specifically, for any real number $\alpha \gg 1$, we present two estimators, one for the classical functional $\mathrm{F}_\alpha(P) = \sum_{i=1}^S p_i^\alpha$ of a discrete distribution $P$ and the other for the quantum functional $\mathrm{F}_\alpha(\rho) = \operatorname{tr}(\rho^\alpha)$ of a mixed state $\rho$.

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 $\alpha \mathsf{n}^{-1}$ in the range $\alpha \lesssim \mathsf{n} \lesssim \alpha^{3-o(1)}$, where the support size $S$ of $P$ or the dimension of $\rho$ 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 \alpha$, improving upon the prior best upper bounds $O(\alpha^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.