EUVIMEDEUVIMED entdecken
Crossref

A Quantum Algorithm Framework for Discrete Probability Distributions With Applications to Rényi Entropy Estimation

Xinzhao Wang, Shengyu Zhang, Tongyang Li

IEEE Transactions on Information Theory · 2024-05 · 70 (5) · 3399-3426

DOI: 10.1109/tit.2024.3382037 ↗

Kurz gefasst

Fachartikel in der Zeitschrift IEEE Transactions on Information Theory, 2024-05. Verfasst von Xinzhao Wang und 2 weiteren Autor:innen. Die Arbeit wurde bisher 10-mal zitiert (Crossref) und nennt 54 Literaturangaben. Gefördert von: startup fund from Peking University, Advanced Institute of Information Technology, Peking University.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Estimating statistical properties is fundamental in statistics and computer science. In this paper, we propose a unified quantum algorithm framework for estimating properties of discrete probability distributions, with estimating Rényi entropies as specific examples. In particular, given a quantum oracle that prepares an n-dimensional quantum state $\sum _{i=1}^{n}\sqrt {p_{i}}|i \rangle $ , for $\alpha >1$ and $0 , our algorithm framework estimates $\alpha $ -Rényi entropy $H_{\alpha }(p)$ to within additive error $\epsilon $ with probability at least 2/3 using $\widetilde {\mathcal {O}}\left({n^{1-\frac {1}{2\alpha }}/\epsilon + \sqrt {n}/\epsilon ^{1+\frac {1}{2\alpha }}}\right)$ and $\widetilde {\mathcal {O}}\left({n^{\frac {1}{2\alpha }}/\epsilon ^{1+\frac {1}{2\alpha }}}\right)$ queries, respectively. This improves the best known dependence in $\epsilon $ as well as the joint dependence between n and $1/\epsilon $ . Technically, our quantum algorithms combine quantum singular value transformation, quantum annealing, and variable-time amplitude estimation. We believe that our algorithm framework is of general interest and has wide applications.

Förderung

  • startup fund from Peking University
  • Advanced Institute of Information Technology, Peking University

Zitieren

APA

Wang, X., Zhang, S., & Li, T. (2024). A Quantum Algorithm Framework for Discrete Probability Distributions With Applications to Rényi Entropy Estimation. IEEE Transactions on Information Theory, 70(5), 3399-3426. https://doi.org/10.1109/tit.2024.3382037

Vancouver

Wang X, Zhang S, Li T. A Quantum Algorithm Framework for Discrete Probability Distributions With Applications to Rényi Entropy Estimation. IEEE Transactions on Information Theory. 2024;70(5):3399-3426. doi:10.1109/tit.2024.3382037

BibTeX
@article{Wang2024,
  author = {Wang, Xinzhao and Zhang, Shengyu and Li, Tongyang},
  title = {A Quantum Algorithm Framework for Discrete Probability Distributions With Applications to Rényi Entropy Estimation},
  journal = {IEEE Transactions on Information Theory},
  year = {2024},
  volume = {70},
  number = {5},
  pages = {3399--3426},
  doi = {10.1109/tit.2024.3382037}
}
Kostenlos starten →