Exponential quantum space advantage for Shannon entropy estimation in data streams
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914491286945792 |
|---|---|
| author | Feng, Weijun Xu, Yongzhen Li, Lvzhou Guo, Gongde Lin, Song |
| author_facet | Feng, Weijun Xu, Yongzhen Li, Lvzhou Guo, Gongde Lin, Song |
| contents | Near-term quantum devices with limited qubits motivate the study of space-bounded quantum computation in the data stream model. We show that Shannon entropy estimation exhibits an exponential separation between quantum and classical space complexity in this setting. Technically, we develop a two-stage quantum streaming algorithm based on a quantum procedure with an explicitly constructed oracle derived from the streaming input. This algorithm achieves logarithmic space complexity in the accuracy parameter, whereas any classical streaming algorithm requires polynomial space. In sharp contrast, existing results for Shannon entropy estimation in the quantum query model achieve only a quadratic speedup. Our work establishes a natural problem with practical applications in computer networking that admits an exponential quantum space advantage, revealing a fundamental gap between quantum query complexity and streaming space complexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_18014 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Exponential quantum space advantage for Shannon entropy estimation in data streams Feng, Weijun Xu, Yongzhen Li, Lvzhou Guo, Gongde Lin, Song Quantum Physics Near-term quantum devices with limited qubits motivate the study of space-bounded quantum computation in the data stream model. We show that Shannon entropy estimation exhibits an exponential separation between quantum and classical space complexity in this setting. Technically, we develop a two-stage quantum streaming algorithm based on a quantum procedure with an explicitly constructed oracle derived from the streaming input. This algorithm achieves logarithmic space complexity in the accuracy parameter, whereas any classical streaming algorithm requires polynomial space. In sharp contrast, existing results for Shannon entropy estimation in the quantum query model achieve only a quadratic speedup. Our work establishes a natural problem with practical applications in computer networking that admits an exponential quantum space advantage, revealing a fundamental gap between quantum query complexity and streaming space complexity. |
| title | Exponential quantum space advantage for Shannon entropy estimation in data streams |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2604.18014 |