MathDB

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

Let dd denote the dimension of the quantum states, and assume the precision parameter satisfies ε=Θ(1)\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

Ω(d2).\Omega(d^2).

Uniformity testing for classical distributions has sample complexity Θ(d)\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 Θ(d)\Theta(d). The conjecture asserts an analogous quadratic blowup for the three listed estimation tasks.

References

Primary source

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).

property-testingquantum-informationsample-complexity
Posted · edited

Progress summary

Refreshed
Claimed progress

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 4d244d^24 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 4d2/log⁡4d44d^2/\log^4 d4 for all three tasks at constant 4ε44\varepsilon4, leaving polylogarithmic slack.
  • For fidelity with a known rank-rr reference state, an August 2026 preprint claims Θ~(r2/ε2)0˘002\widetilde{\Theta}(r^2/\varepsilon^2)\u0002, but this is not unrestricted fidelity estimation.

August 2026 entropy counterexample claim

An August 2026 preprint claims a von Neumann entropy estimator using Oε(d2log⁡2(log⁡d)/log⁡2d)=oε(d2)O_\varepsilon(d^2\log^2(\log d)/\log^2 d)=o_\varepsilon(d^2) 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.

Sources

Solutions 0

No solutions have been posted yet.