Breaking the Multiplicative Overhead in Quantum Entropy Estimation
Abstract
The von Neumann, Tsallis, and Rényi entropies are fundamental measures of quantum information. A common estimation strategy multiplies the worst-case costs of spectral transformation and statistical readout, leaving gaps to query lower bounds. We reduce this overhead with multi-level algorithms that use local normalization and precision allocation, while variable-time estimation accounts for the probability of reaching expensive spectral tests. With controlled purified access and its inverse, we obtain bounds for additive error ε, rank upper bound R, and fixed order α. Tsallis entropy estimation has near-optimal rank-independent query complexity Õ(ε−1/(α−1)) for 1<α<2, when the allowed dimension and rank accommodate the lower-bound instances, and Õ(1/ε) for α≥2, where Õ suppresses logarithmic factors. The first saves a factor 1/ε; the second extends known integer-order scaling to noninteger orders. We also improve the von Neumann entropy bound from Õ(R/ε2) to Õ(R/ε) and obtain Õ(R/ε) for noninteger Rényi orders 1<α<3, with further bounds at other orders. Our functional-estimation theorem replaces the global product by a sum of local costs weighted by function magnitudes and spectral masses. We further estimate fixed logarithmic moments and entropy variance using Õ(R/ε) queries, providing efficient access to fluctuation parameters that enter finite-blocklength quantum compression and pure-state entanglement conversion. More broadly, our framework extends beyond entropy to a broad class of density-matrix functionals, offering a systematic approach toward optimal query complexity in quantum spectral estimation.
Related
- Reliable Entropy Estimation from Observed Statistics for Device-Independent Quantum Cryptography
- Quantum Tsallis Entropy Estimation: Near-Optimal Bounds and High-Precision Improvements
- A Frame-Spread Lower Bound for Quantum Entropy Estimation under Fixed Rank-One Measurements
- Local and Global Risk Bounds for Quantum Entropy Estimation under Projective-Design Measurements
- Quantum circuit compilation with constant overhead
BibTeX
@misc{huang2026breaking,
title = {{Breaking the Multiplicative Overhead in Quantum Entropy Estimation}},
author = {Junxiang Huang and Chenyang Li and Lu-Fan Zhang and Yusen Wu and Yukun Zhang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.40179},
eprint = {2609.40179},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.40179},
}
RIS
TY - UNPB
TI - Breaking the Multiplicative Overhead in Quantum Entropy Estimation
AU - Junxiang Huang
AU - Chenyang Li
AU - Lu-Fan Zhang
AU - Yusen Wu
AU - Yukun Zhang
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.40179
UR - https://arxiv.org/abs/2609.40179
AB - The von Neumann, Tsallis, and Rényi entropies are fundamental measures of quantum information. A common estimation strategy multiplies the worst-case costs of spectral transformation and statistical readout, leaving gaps to query lower bounds. We reduce this overhead with multi-level algorithms that use local normalization and precision allocation, while variable-time estimation accounts for the probability of reaching expensive spectral tests. With controlled purified access and its inverse, we obtain bounds for additive error ε, rank upper bound R, and fixed order α. Tsallis entropy estimation has near-optimal rank-independent query complexity Õ(ε^−1/(α−1)) for 1<α<2, when the allowed dimension and rank accommodate the lower-bound instances, and Õ(1/ε) for α≥2, where Õ suppresses logarithmic factors. The first saves a factor 1/ε; the second extends known integer-order scaling to noninteger orders. We also improve the von Neumann entropy bound from Õ(R/ε^2) to Õ(R/ε) and obtain Õ(R/ε) for noninteger Rényi orders 1<α<3, with further bounds at other orders. Our functional-estimation theorem replaces the global product by a sum of local costs weighted by function magnitudes and spectral masses. We further estimate fixed logarithmic moments and entropy variance using Õ(R/ε) queries, providing efficient access to fluctuation parameters that enter finite-blocklength quantum compression and pure-state entanglement conversion. More broadly, our framework extends beyond entropy to a broad class of density-matrix functionals, offering a systematic approach toward optimal query complexity in quantum spectral estimation.
ER -