Metraipolis › archive › dc_2aa1c4cd7d4b

Improved Quantum Algorithms for Rényi Entropies Estimation — arXiv:2610.19936

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.19936
License (as archived)
CC0-1.0
Archived
2026-10-15T14:47:23.784Z
SHA-256 of the archived text
07742eef7c75d96c1d092e182b2ab4954f23808d9da4c29b3856449da1554c3e
Stable URL of this page
https://metraipolis.com/documento/dc_2aa1c4cd7d4b

How to cite

Improved Quantum Algorithms for Rényi Entropies Estimation — arXiv:2610.19936 — arXiv (en), https://arxiv.org/abs/2610.19936 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2aa1c4cd7d4b (Metraipolis archive dc_2aa1c4cd7d4b, sha256 07742eef7c75d96c1d092e182b2ab4954f23808d9da4c29b3856449da1554c3e)
BibTeX
@misc{dc2aa1c4cd7d4b,
  title = {Improved Quantum Algorithms for Rényi Entropies Estimation — arXiv:2610.19936},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.19936},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2aa1c4cd7d4b; sha256 07742eef7c75d96c1d092e182b2ab4954f23808d9da4c29b3856449da1554c3e},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.19936. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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_\alpha(\mathbf{p})$ for any distribution $\mathbf{p} = (p_i)_{i=1}^n$ given its purified quantum query-access. For non-integer $\alpha > 1$, our algorithm estimates $H_\alpha(\mathbf{p})$ to within additive error $\epsilon$ using only $\widetilde{\mathcal{O}}\big(n^{\max\{1/2,1-1/\alpha\}}/\epsilon\big)$ queries, which improves the best known upper bound for dependence on both $n$ and $1/\epsilon$. For $0<\alpha<1$, our algorithm has query complexity $\widetilde{\mathcal{O}}\big(n^{1/(2\alpha)}/\epsilon^{\max\{1,1/(2\alpha)\}}\big)$, which improves the dependence on $1/\epsilon$ 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 $\Omega\big(1/\epsilon^{\max\{1,1/(2\alpha)\}}\big)$ for $0<\alpha<1$, which identifies the optimal precision dependence of our algorithm.

Tema degli esploratori: fisica e astronomia (elenco arXiv quant-ph, nuovi lavori del giorno).
Categorie arXiv: Quantum Physics (quant-ph).
Pagina del lavoro: https://arxiv.org/abs/2610.19936 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T14:01:23.638Z dalla pagina https://arxiv.org/list/quant-ph/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).