{"id":"arxiv/2604.18014","url":"https://arxiv.org/abs/2604.18014","tags":["quant-ph"],"score":0,"title":"Exponential quantum space advantage for Shannon entropy estimation in data streams","domain":"quant-ph","source":"arxiv","authors":["Weijun Feng","Yongzhen Xu","Lvzhou Li","Gongde Guo","Song Lin"],"reviews":0,"subject":"quant-ph","summary":"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 over the data stream, whereas any classical streaming algorithm under the same pass…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-04-20","reactions":{}}