A Lower Bound Framework for Quantum Functional Estimation

Abstract

We develop a unified framework for proving lower bounds for estimating functionals of $d$-dimensional quantum states: \[ \mathcal L_ϕ(ρ)=\frac1d\sum_{i=1}^dϕ(dλ_i(ρ)). \] The framework combines a Haar-random moment encoding process with moment matching and best polynomial approximation. A master theorem is provided to derive sample complexity lower bounds for estimating ${\mathcal{L}}_{\varphi }$ from the properties of $\varphi$. Using this framework, we resolve several open problems by establishing nearly tight lower bounds for a wide range of quantum property testing problems, including Uhlmann fidelity estimation, trace distance estimation, von Neumann/Rényi/Tsallis entropy estimation, spectrum estimation, and rank testing. Moreover, by quantum sample-to-query lifting, these sample lower bounds also imply quantum query lower bounds. These sample/query lower bounds imply the optimality of more than 20 quantum algorithms since 2015.

33 pages, 1 table. Title changed, polylog factors improved, more applications added: Renyi entropy, Tsallis entropy, rank testing, Hellinger distance