Towards Minimax Estimation of High-Order Functionals by Quantum Arguments

Jul 16, 2026

A quantum-computing-based approach addresses minimax estimation of high-order functionals for both classical discrete distributions and quantum mixed states. For large α, two estimators target Fα(P)=Σ pi^α and Fα(ρ)=tr(ρα), linking them to Rényi and Tsallis entropies. Both achieve the minimax optimal L2 rate α n−1 over α≲n≲α3−o(1), with support size or dimension far exceeding sample size. Sample complexity improves to n≈α versus previous O(α2) bounds, using a unified quantum-primitives framework that runs in linear time.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages42

Reading Time1 h 46 min

Introduction

Main results

Techniques

Related work

Discussion

Overview

Sample complexity

Time efficiency

Preliminaries

Basic notations

Quantum computing

Hadamard test

Quantum query algorithms with block-encoding

Quantum singular value transformation

Quantum samplizer

Upper Bounds

Generalized SWAP test for block-encodings

Lower Bounds

Sample complexity lower bounds

MSE lower bounds

arXiv :2607 .07540v1 [ quant-ph] 8 Jul 2026 Towards Minimax Estimation of High-Order Functionals by Quantum Arguments Qisheng Wang∗ Abstract We propose a novel approach to the minimax estimation of high-order functionals from the perspective of quantum computing. Specifically, for any real number α ≫ 1, we present two estimators, one for the classical functional Fα (P) = Ppαi of a discrete distribution P and the other for the quantum functional Fα (ρ) = tr(ρα ) of a mixed state ρ . These functionals have close connections with the R´enyi entropy and the Tsallis entropy. We show that both estimators achieve the minimax optimal L2 rate αn−1 in the range α ≲ n ≲ α3−o(1), where the support size S of P or the dimension of ρ can be much larger than the number of samples n. As a result, both estimators achieve the optimal sample complexity n ≍ α, 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. ∗ Qisheng Wang is with the School of Computer Science, Shanghai Jiao Tong University, Shanghai 200240, China (e-mail: [QishengWang1994@gmail.com](QishengWang1994@gmail.com)). Contents 1 Introduction 1 1.1 Main results ......................................... 3 1.2 Techniques ......................................... 4 1.2.1 Relate classical functionals to quantum functionals ............... 4 1.2.2 The construction of our estimator ........................ 5 1.2.3 Lower bounds .................................... 9 1.3 Related work ........................................ 10 1.4 Discussion .......................................... 10 2 Overview 10 2.1 Sample complexity ..................................... 12 2.2 Time efficiency ....................................... 12 3 Preliminaries 13 3.1 Basic notations ....................................... 13 3.2 Quantum computing .................................... 14 3.3 Hadamard test ....................................... 15 3.4 Quantum query algorithms with block-encoding ..................... 16 3.5 Quantum singular value transformation ......................... 16 3.6 Quantum samplizer ..................................... 17 4 Upper Bounds 18 4.1 Generalized SWAP test for block-encodings ....................... 18 4.2 Subroutines with queries .................................. 19 4.3 Samplization ........................................ 20 4.4 A baby estimator ...................................... 21 4.5 Final estimator ....................................... 25 5 Lower Bounds 27 5.1 Sample complexity lower bounds ............................. 27 5.2 MSE lower bounds ..................................... 30 References 31 A Proof of Lemma 3.3 39 1 Introduction Classical functional estimation. Given n samples drawn from an unknown discrete probability distribution P = (p1 , p2 ,..., pS ) of alphabet size S, the estimation of the functionals of the distribution P of the form S F (P) =Xf(pi) (1) i=1 has been extensively investigated in the literature. This fundamental problem has strong applications in entropy estimation. For example, when f (x) = −x ln(x), the functional becomes the Shannon entropy H(P) = −Ppi ln(pi) [Sha48a, Sha48b], and its estimation has been thoroughly studied in a series of works [Pan03, BDKR05 , Pan04 , VV11a, VV11b, VV17 , JVHW15 , JVHW17 , WY16] . In particular, f (x) = xα with parameter α gives a family of information measures of the form S Fα(P) := Xpαi . (2) i=1 This type of infor

FAQs

What two types of functionals are estimated in this work?

The paper estimates the classical high-order functional Fα(P)=Σ pi^α for a discrete distribution P and the quantum analogue Fα(ρ)=tr(ρα) for a mixed state ρ.

In what parameter range do the proposed estimators achieve the minimax optimal rate?

They achieve the minimax optimal L2 rate α n−1 in the range α≲n≲α3−o(1).

How does the method improve upon previous sample complexity bounds?

The estimators reduce sample complexity to n≈α, improving earlier best upper bounds of order O(α2) for both classical and quantum functionals.

Jul 16, 2026

Upload by Evangeline