Near optimal quantum algorithm for estimating Shannon entropy

2025/09/09 by Myeongjin Shin, Shin, Myeongjin, Kabgyun Jeong +1 · 2 citations
Computer Science · Physics and Astronomy · #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #Quantum Physics (quant-ph)

paper · pdf · doi:10.48550/arxiv.2509.07452

openalex publication_date 2025/09/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 Θ(\tfrac√(n)ε).

Citations

• Amplitude amplification and estimation require inverses
• Distributional property testing in a quantum world
• Minimax rates of entropy estimation on large alphabets via best polynomial approximation
• Quantum Lower Bounds by Polynomials

Cited by

• Exponential quantum space advantage for Shannon entropy estimation in data streams
• A List of Complexity Bounds for Property Testing by Quantum Sample-to-Query Lifting

Related

• Exponential quantum space advantage for Shannon entropy estimation in data streams
• Entropy lower bounds of quantum decision tree complexity
• Information-Theoretic Lower Bounds for Approximating Monomials via Optimal Quantum Tsallis Entropy Estimation
• Sublinear quantum algorithms for estimating von Neumann entropy
• Quantum algorithm for approximating the expected value of a random-exist quantified oracle