Improved Quantum Algorithms for Rényi Entropies Estimation

Abstract

Entropy estimation of discrete probability distributions is a fundamental problem in statistical inference and quantum property estimation. In this paper, we study the problem of estimating Rényi entropy H_α(p) for any distribution p = (p_i)_i=1ⁿ given its purified quantum query-access. For non-integer α> 1, our algorithm estimates H_α(p) to within additive error ε using only 𝒪̃(n^{max{1/2,1−1/α}}/ε) queries, which improves the best known upper bound for dependence on both n and 1/ε. For 0<α<1, our algorithm has query complexity 𝒪̃(n^1/(2α)/ε^{max{1,1/(2α)}}), which improves the dependence on 1/ε of the current best upper bound without incresing its n dependence. Our approach adapts the multi-level estimation framework to relative approximation of the power sums and leverage binary search to remove the requirement of prior knowledge of them. We also strengthen the precision-dependent lower bound to Ω(1/ε^{max{1,1/(2α)}}) for 0<α<1, which identifies the optimal precision dependence of our algorithm.

Sharp Data-Processing Region for Quantum Conditional Rényi Entropies
Milad M. Goodarzi, Yucheng Bao, Marco Tomamichel
arXiv25 Sep 2026PreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
Real-Space Renormalization of Stabilizer Rényi Entropies in Spin Chains
Sonja Gombar, Petar Mali, Slobodan Radošević +3
arXiv15 Sep 2026PreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
Rényi and Tsallis information entropies for a harmonic position-dependent mass
Dorcas A. Addo, Daniel Sabi-Takou, Eugene Adjei +1
arXiv16 Sep 2026PreprintCC BY-NC-ND 4.0Full textMathematical physics Applied physics & instrumentationarXiv
Exact holographic superfluid at the Bogomolny point: transport, large charge, and Rényi entropies
Siqing Yu
arXiv29 Oct 2026PreprintCC BY 4.0Full textCondensed matter Gravitation & general relativityarXiv
Multi-Indexed Schatten Quasi- and Anti-Norms and Additivity of Conditional Rényi Entropies
Jan Kochanowski
arXiv2 Oct 2026PreprintCC BY-NC-SA 4.0Full textAnalysis & PDEs Mathematical physicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{xiong2026improved,
  title = {{Improved Quantum Algorithms for Rényi Entropies Estimation}},
  author = {Zongxing Xiong and Chengshen Gao and Lvzhou Li},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.19936},
  eprint = {2610.19936},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.19936},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Improved Quantum Algorithms for Rényi Entropies Estimation
AU  - Zongxing Xiong
AU  - Chengshen Gao
AU  - Lvzhou Li
PY  - 2026
DA  - 2026/10/14
PB  - arXiv
DO  - 10.48550/arxiv.2610.19936
UR  - https://arxiv.org/abs/2610.19936
AB  - Entropy estimation of discrete probability distributions is a fundamental problem in statistical inference and quantum property estimation. In this paper, we study the problem of estimating Rényi entropy H_α(p) for any distribution p = (p_i)_i=1^n given its purified quantum query-access. For non-integer α> 1, our algorithm estimates H_α(p) to within additive error ε using only 𝒪̃(n^max{1/2,1−1/α}/ε) queries, which improves the best known upper bound for dependence on both n and 1/ε. For 0<α<1, our algorithm has query complexity 𝒪̃(n^1/(2α)/ε^max{1,1/(2α)}), which improves the dependence on 1/ε of the current best upper bound without incresing its n dependence. Our approach adapts the multi-level estimation framework to relative approximation of the power sums and leverage binary search to remove the requirement of prior knowledge of them. We also strengthen the precision-dependent lower bound to Ω(1/ε^max{1,1/(2α)}) for 0<α<1, which identifies the optimal precision dependence of our algorithm.
ER  -

Abstract

Related

Cite