Exponential quantum space advantage for Shannon entropy estimation in data streams

Weijun Feng, Yongzhen Xu, Lvzhou Li +2

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…