Quadratic quantum sample lower bounds for entropy, trace distance, and fidelity estimation

Let $d$ denote the dimension of the quantum states, and assume the precision parameter satisfies $\varepsilon=\Theta(1)$ for a sufficiently small constant. The quantum sample complexities concern estimating von Neumann entropy, trace distance, and fidelity.

Quadratic sample-complexity conjecture. The quantum sample complexities of von Neumann entropy estimation, trace distance estimation, and fidelity estimation are

$$\Omega(d^2).$$

Uniformity testing for classical distributions has sample complexity $\Theta(\sqrt{d})$, while classical entropy and total variation distance estimation exhibit a near-quadratic increase; in the quantum setting, mixedness testing has sample complexity $\Theta(d)$. The conjecture asserts an analogous quadratic blowup for the three listed estimation tasks.