Near optimal quantum algorithm for estimating Shannon entropy
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914297167216640 |
|---|---|
| author | Shin, Myeongjin Jeong, Kabgyun |
| author_facet | Shin, Myeongjin Jeong, Kabgyun |
| contents | We present a near-optimal quantum algorithm, up to logarithmic factors, for estimating the Shannon entropy in the quantum probability oracle model. Our approach combines the singular value separation algorithm with quantum amplitude amplification, followed by the application of quantum singular value transformation. On the lower bound side, we construct probability distributions encoded via Hamming weights in the oracle, establishing a tight query lower bound up to logarithmic factors. Consequently, our results show that the tight query complexity for estimating the Shannon entropy within $ε$-additive error is given by $\tildeΘ\left(\tfrac{\sqrt{n}}ε\right)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_07452 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Near optimal quantum algorithm for estimating Shannon entropy Shin, Myeongjin Jeong, Kabgyun Quantum Physics We present a near-optimal quantum algorithm, up to logarithmic factors, for estimating the Shannon entropy in the quantum probability oracle model. Our approach combines the singular value separation algorithm with quantum amplitude amplification, followed by the application of quantum singular value transformation. On the lower bound side, we construct probability distributions encoded via Hamming weights in the oracle, establishing a tight query lower bound up to logarithmic factors. Consequently, our results show that the tight query complexity for estimating the Shannon entropy within $ε$-additive error is given by $\tildeΘ\left(\tfrac{\sqrt{n}}ε\right)$. |
| title | Near optimal quantum algorithm for estimating Shannon entropy |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2509.07452 |