Quadratic quantum sample lower bounds for entropy, trace distance, and fidelity estimation
Let denote the dimension of the quantum states, and assume the precision parameter satisfies 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
Uniformity testing for classical distributions has sample complexity , while classical entropy and total variation distance estimation exhibit a near-quadratic increase; in the quantum setting, mixedness testing has sample complexity . The conjecture asserts an analogous quadratic blowup for the three listed estimation tasks.
References
- Kean Chen, Qisheng Wang and Zhicheng Zhang, “A List of Complexity Bounds for Property Testing by Quantum Sample-to-Query Lifting”, arXiv:2512.01971 (2025).
Progress summary
An unverified August 2026 preprint claims that entropy can be estimated with fewer than the conjectured quadratic number of samples, while the trace-distance and general fidelity cases remain unresolved.
The conjecture asserts sample lower bounds for constant-precision estimation of von Neumann entropy, trace distance, and fidelity. A December 2025 source presented all three as open problems.
Known results
- An August 2026 paper claims lower bounds of roughly for all three tasks at constant , leaving polylogarithmic slack.
- For fidelity with a known rank- reference state, an August 2026 preprint claims , but this is not unrestricted fidelity estimation.
August 2026 entropy counterexample claim
An August 2026 preprint claims a von Neumann entropy estimator using samples, which would refute the entropy component. The claim is unverified; no corresponding result was found for trace distance or unrestricted fidelity.
Current status (as of September 2026): The full conjecture is not verified; entropy is challenged by an unverified subquadratic claim, while trace distance and unrestricted fidelity remain open.
Solutions 0
No solutions have been posted yet.