Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.22983

Quantum Tsallis Entropy Estimation: Near-Optimal Bounds and High-Precision Improvements

Chengshen Gao, Zongxing Xiong, Lvzhou Li

quant-phSubmitted Oct 16, 2026• Announced Oct 19, 2026• 0 citations
arXivHTMLPDF

Abstract

Estimating statistical properties of probability distributions is a fundamental problem in statistics and theoretical computer science. We develop quantum algorithms for estimating the $q$-Tsallis entropy $\mathrm{H}_q^{\mathrm{Tsa}}(P) =\frac{\sum_{i=1}^n p_i^q-1}{1-q}$ when $0<q<1$, given purified quantum query access to a distribution $P$ on $[n]$. When $0<q\leq \frac{1}{2}$, we provide a quantum algorithm with query complexity $\widetilde{O}\rbra{\left(\frac{n}{\varepsilon}\right)^{\frac{1}{2q}}}$, which is optimal up to polylogarithmic factors. When $\frac{1}{2}<q<1$, we introduce a two-stage simultaneous probability estimation procedure, yielding a quantum algorithm with query complexity $\widetilde{O}\left(\frac{n^{\frac12+\frac{1}{2q}}}{\varepsilon^{\frac{1}{2q}}}+\frac{n^{1-q}}{\varepsilon}\right)$, which improves the result given by Chen et al. (ICALP 2026) when $\varepsilon=O\rbra{n^{1-2q}}$.

AI Summary

The paper studies additive-error estimation of the classical $q$-Tsallis entropy, $H_q(P)=(\sum_i p_i^q-1)/(1-q)$, for $0<q<1$, given purified quantum query access to a distribution on $n$ outcomes. The challenge is controlling contributions from small probabilities, where the derivative of $p^q$ diverges. For fixed $0<q\leq1/2$, it gives an estimator using $\widetilde O((n/\varepsilon)^{1/(2q)})$ oracle queries with success probability at least $2/3$, matching the cited lower bound up to polylogarithmic factors. The construction adapts an existing multilevel QSVT framework: uniform rather than distribution-weighted initialization permits local polynomial approximations of positive powers, while singular-value discriminators separate probability scales and amplitude estimation combines their contributions. For fixed $1/2<q<1$, the query bound is $\widetilde O(n^{1/2+1/(2q)}\varepsilon^{-1/(2q)}+n^{1-q}/\varepsilon)$. A two-stage simultaneous probability-estimation procedure first groups coordinates by magnitude, then refines them to errors scaling as $\sqrt{p_i}/T$ above a cutoff $T^{-2}$. A floored classical reference vector supports a first-order expansion of the power sum. Weighted squared-error control bounds the expansion bias, and quantum mean estimation evaluates the remaining correction with variance $O(n^{2-2q})$. The latter bound improves the cited previous estimator in the high-precision regime $\varepsilon=O(n^{1-2q})$, but retains a $\sqrt n$ gap in its first term relative to the known lower bound. Dependence on $q$ is absorbed into constants; applications of the probability-estimation primitive to other functionals remain open.

Little sign of AI-generated textAI use disclosed
The authors acknowledge the use of OpenAI's language models in developing Theorem~\ref{the: Two-stage multidimensional amplitude estimation}, as well as in editing and improving the presentation of the manuscript.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Improved Quantum Algorithms for Rényi Entropies Estimation

Zongxing Xiong, Chengshen Gao, Lvzhou Li

Entropy estimation of discrete probability distributions is a fundamental problem in statistical inference and quantum property estimation. In this paper, we study the problem of estimating Rényi entropy $H_α(\mathbf{p})$ for any distribution $\mathbf{p} = (p_i)_{i=1}^n$ given its purified quantum query-access. For non-integer $α> 1$, our algorithm estimates $H_α(\mathbf{p})$ to within additive error $ε$ using only $\widetilde{\mathcal{O}}\big(n^{\max\{1/2,1-1/α\}}/ε\big)$ queries, which improves the best known upper bound for dependence on both $n$ and $1/ε$. For $0<α<1$, our algorithm has query complexity $\widetilde{\mathcal{O}}\big(n^{1/(2α)}/ε^{\max\{1,1/(2α)\}}\big)$, which improves the dependence on $1/ε$ of the current best upper bound without incresing its $n$ dependence. Our approach adapts the multi-level estimation framework to relative approximation of the power sums and leverage binary search to remove the requirement of prior knowledge of them. We also strengthen the precision-dependent lower bound to $Ω\big(1/ε^{\max\{1,1/(2α)\}}\big)$ for $0<α<1$, which identifies the optimal precision dependence of our algorithm.

quant-pharXiv:2610.19936•Oct 15, 2026•0 citations

Nearly Sample-Optimal Estimators for Quantum Rényi and Tsallis Entropies

Kean Chen, Qisheng Wang

In this paper, we provide estimators for quantum Rényi and Tsallis entropies with nearly optimal sample complexity. Specifically, for order $α$, dimension $d$, and additive error $\varepsilon$, 1. For $0 < α< 1$, the sample complexity is $O(d^{1+1/α}/\varepsilon^{1/α} + d^{1/α-1}/\varepsilon^{2})$ for Rényi entropy and $O(d^{1+1/α}/\varepsilon^{1/α} + d^{2-2α}/\varepsilon^2)$ for Tsallis entropy. In particular, for $0 < α\leq 1/2$, the sample complexity for both entropies is $O(d^{1+1/α}/\varepsilon^{1/α})$. 2. For non-integer $α> 1$, the sample complexity is $O(d^2/\varepsilon^{1/α} + d^{1-1/α}/\varepsilon^2)$ for Rényi entropy. Our upper bounds improve the quantum Rényi entropy estimators due to Acharya, Issa, Shende, and Wagner (2017) and the quantum Tsallis entropy estimators due to Chen, Liu, and Wang (2026), and match the lower bounds recently established by Wang (2026).

quant-pharXiv:2608.18070•Aug 19, 2026•4 citations

Information-Theoretic Lower Bounds for Approximating Monomials via Optimal Quantum Tsallis Entropy Estimation

Qisheng Wang

This paper reveals a conceptually new connection from information theory to approximation theory via quantum algorithms for entropy estimation. Specifically, we provide an information-theoretic lower bound $Ω(\sqrt{n})$ on the approximate degree of the monomial $x^n$, compared to the analytic lower bounds shown in Newman and Rivlin (Aequ. Math. 1976) via Fourier analysis and in Sachdeva and Vishnoi (Found. Trends Theor. Comput. Sci. 2014) via the Markov brothers' inequality. This is done by relating the polynomial approximation of monomials to quantum Tsallis entropy estimation. This further implies a quantum algorithm that estimates to within additive error $\varepsilon$ the Tsallis entropy of integer order $q \geq 2$ of an unknown probability distribution $p$ or an unknown quantum state $ρ$, using $\widetilde Θ(\frac{1}{\sqrt{q}\varepsilon})$ queries to the quantum oracle that produces a sample from $p$ or prepares a copy of $ρ$, improving the prior best $O(\frac{1}{\varepsilon})$ via the Shift test due to Ekert, Alves, Oi, Horodecki, Horodecki and Kwek (Phys. Rev. Lett. 2002). To the best of our knowledge, this is the first quantum entropy estimator with optimal query complexity (up to polylogarithmic factors) for all parameters simultaneously.

arXiv:2509.03496•Sep 3, 2025•5 citations

Towards Minimax Estimation of High-Order Functionals by Quantum Arguments

Qisheng Wang

We propose a novel approach to the minimax estimation of high-order functionals from the perspective of quantum computing. Specifically, for any real number $α\gg 1$, we present two estimators, one for the classical functional $\mathrm{F}_α(P) = \sum_{i=1}^S p_i^α$ of a discrete distribution $P$ and the other for the quantum functional $\mathrm{F}_α(ρ) = \operatorname{tr}(ρ^α)$ of a mixed state $ρ$. These functionals have close connections with the Rényi entropy and the Tsallis entropy. We show that both estimators achieve the minimax optimal $L_2$ rate $α\mathsf{n}^{-1}$ in the range $α\lesssim \mathsf{n} \lesssim α^{3-o(1)}$, where the support size $S$ of $P$ or the dimension of $ρ$ can be much larger than the number of samples $\mathsf{n}$. As a result, both estimators achieve the \textit{optimal} sample complexity $\mathsf{n} \asymp α$, improving upon the prior best upper bounds $O(α^2)$ established by Jiao, Venkat, Han, and Weissman (IEEE Trans. Inf. Theory 2017) for classical functionals and Chen and Wang (COLT 2025) for quantum functionals. Our estimators are constructed under a unified framework using quantum primitives and run in linear time on a quantum computer. This work reveals an unexpected path from quantum computing to statistics, suggesting a conceptually new methodology for functional estimation. It adds to the growing list of quantum proofs for classical theorems.

quant-pharXiv:2607.07540•Jul 9, 2026•1 citation

Quantum Multi-Level Estimation of Functionals of Discrete Distributions

Kean Chen, Minbo Gao, Tongyang Li +2 more

We propose a quantum multi-level estimation framework for a functional $\sum_{i=1}^n f(p_i)$ of a discrete distribution $(p_i)_{i=1}^n$. We partition the values $p_i$ into logarithmically many intervals whose length decays exponentially. For each interval, we perform non-destructive singular value discrimination to isolate the relevant $p_i$, enabling adaptive estimation of the partial sum over this interval. Unlike previous variable-time approaches, our method avoids high control overhead and requires only constant extra ancilla qubits. As an application, we present efficient quantum estimators for the $q$-Tsallis entropy of discrete distributions. Specifically: (i) For $q > 1$, we obtain a near-optimal quantum algorithm with query complexity $\tildeΘ(1/\varepsilon^{\max\{1/(2(q-1)), 1\}})$, improving the prior best $O(1/\varepsilon^{1+1/(q-1)})$ due to Liu and Wang (SODA 2025; IEEE Trans. Inf. Theory 2026). (ii) For $0 < q < 1$, we obtain a quantum algorithm with query complexity $\tilde{O}(n^{1/q-1/2}/\varepsilon^{1/q})$, exhibiting a quantum speedup over the near-optimal classical estimators due to Jiao, Venkat, Han, and Weissman (IEEE Trans. Inf. Theory 2017). Our results achieve, to our knowledge, the first near-optimal quantum estimators for parameterized $q$-entropy for non-integer $q$.

quant-pharXiv:2605.03685•Leibniz international proceedings in informatics•May 6, 2026•2 citations

Sublinear quantum algorithms for estimating von Neumann entropy

Tom Gur, Min-Hsiu Hsieh, Sathyawageeswar Subramanian

Entropy is a fundamental property of both classical and quantum systems, spanning myriad theoretical and practical applications in physics and computer science. We study the problem of obtaining estimates to within a multiplicative factor $γ>1$ of the Shannon entropy of probability distributions and the von Neumann entropy of mixed quantum states. Our main results are: $\quad\bullet$ an $\widetilde{\mathcal{O}}\left( n^{\frac{1+η}{2γ^2}}\right)$-query quantum algorithm that outputs a $γ$-multiplicative approximation of the Shannon entropy $H(\mathbf{p})$ of a classical probability distribution $\mathbf{p} = (p_1,\ldots,p_n)$; $\quad\bullet$ an $\widetilde{\mathcal{O}}\left( n^{\frac12+\frac{1+η}{2γ^2}}\right)$-query quantum algorithm that outputs a $γ$-multiplicative approximation of the von Neumann entropy $S(ρ)$ of a density matrix $ρ\in\mathbb{C}^{n\times n}$. In both cases, the input is assumed to have entropy bounded away from zero by a quantity determined by the parameter $η>0$, since, as we prove, no polynomial query algorithm can multiplicatively approximate the entropy of distributions with arbitrarily low entropy. In addition, we provide $Ω\left(n^{\frac{1}{3γ^2}}\right)$ lower bounds on the query complexity of $γ$-multiplicative estimation of Shannon and von Neumann entropies. We work with the quantum purified query access model, which can handle both classical probability distributions and mixed quantum states, and is the most general input model considered in the literature.

arXiv:2111.11139•Nov 22, 2021•44 citations
Estimating statistical properties of probability distributions is a fundamental problem in statistics and theoretical computer science. We develop quantum algorithms for estimating the qqq-Tsallis entropy HqTsa(P)=∑i=1npiq−11−q\mathrm{H}_q^{\mathrm{Tsa}}(P) =\frac{\sum_{i=1}^n p_i^q-1}{1-q}HqTsa​(P)=1−q∑i=1n​piq​−1​ when 0<q<10<q<10<q<1, given purified quantum query access to a distribution PPP on [n][n][n]. When 0<q≤120<q\leq \frac{1}{2}0<q≤21​, we provide a quantum algorithm with query complexity O~\rbra(nε)12q\widetilde{O}\rbra{\left(\frac{n}{\varepsilon}\right)^{\frac{1}{2q}}}O\rbra(εn​)2q1​, which is optimal up to polylogarithmic factors. When 12<q<1\frac{1}{2}<q<121​<q<1, we introduce a two-stage simultaneous probability estimation procedure, yielding a quantum algorithm with query complexity O~(n12+12qε12q+n1−qε)\widetilde{O}\left(\frac{n^{\frac12+\frac{1}{2q}}}{\varepsilon^{\frac{1}{2q}}}+\frac{n^{1-q}}{\varepsilon}\right)O(ε2q1​n21​+2q1​​+εn1−q​), which improves the result given by Chen et al. (ICALP 2026) when ε=O\rbran1−2q\varepsilon=O\rbra{n^{1-2q}}ε=O\rbran1−2q.
The paper studies additive-error estimation of the classical qqq-Tsallis entropy, Hq(P)=(∑ipiq−1)/(1−q)H_q(P)=(\sum_i p_i^q-1)/(1-q)Hq​(P)=(∑i​piq​−1)/(1−q), for 0<q<10<q<10<q<1, given purified quantum query access to a distribution on nnn outcomes. The challenge is controlling contributions from small probabilities, where the derivative of pqp^qpq diverges.
For fixed 0<q≤1/20<q\leq1/20<q≤1/2, it gives an estimator using O~((n/ε)1/(2q))\widetilde O((n/\varepsilon)^{1/(2q)})O((n/ε)1/(2q)) oracle queries with success probability at least 2/32/32/3, matching the cited lower bound up to polylogarithmic factors. The construction adapts an existing multilevel QSVT framework: uniform rather than distribution-weighted initialization permits local polynomial approximations of positive powers, while singular-value discriminators separate probability scales and amplitude estimation combines their contributions.
For fixed 1/2<q<11/2<q<11/2<q<1, the query bound is O~(n1/2+1/(2q)ε−1/(2q)+n1−q/ε)\widetilde O(n^{1/2+1/(2q)}\varepsilon^{-1/(2q)}+n^{1-q}/\varepsilon)O(n1/2+1/(2q)ε−1/(2q)+n1−q/ε). A two-stage simultaneous probability-estimation procedure first groups coordinates by magnitude, then refines them to errors scaling as pi/T\sqrt{p_i}/Tpi​​/T above a cutoff T−2T^{-2}T−2. A floored classical reference vector supports a first-order expansion of the power sum. Weighted squared-error control bounds the expansion bias, and quantum mean estimation evaluates the remaining correction with variance O(n2−2q)O(n^{2-2q})O(n2−2q).
The latter bound improves the cited previous estimator in the high-precision regime ε=O(n1−2q)\varepsilon=O(n^{1-2q})ε=O(n1−2q), but retains a n\sqrt nn​ gap in its first term relative to the known lower bound. Dependence on qqq is absorbed into constants; applications of the probability-estimation primitive to other functionals remain open.
Entropy estimation of discrete probability distributions is a fundamental problem in statistical inference and quantum property estimation. In this paper, we study the problem of estimating Rényi entropy Hα(p)H_α(\mathbf{p})Hα​(p) for any distribution p=(pi)i=1n\mathbf{p} = (p_i)_{i=1}^np=(pi​)i=1n​ given its purified quantum query-access. For non-integer α>1α> 1α>1, our algorithm estimates Hα(p)H_α(\mathbf{p})Hα​(p) to within additive error εεε using only O~(nmax⁡{1/2,1−1/α}/ε)\widetilde{\mathcal{O}}\big(n^{\max\{1/2,1-1/α\}}/ε\big)O(nmax{1/2,1−1/α}/ε) queries, which improves the best known upper bound for dependence on both nnn and 1/ε1/ε1/ε. For 0<α<10<α<10<α<1, our algorithm has query complexity O~(n1/(2α)/εmax⁡{1,1/(2α)})\widetilde{\mathcal{O}}\big(n^{1/(2α)}/ε^{\max\{1,1/(2α)\}}\big)O(n1/(2α)/εmax{1,1/(2α)}), which improves the dependence on 1/ε1/ε1/ε of the current best upper bound without incresing its nnn dependence. Our approach adapts the multi-level estimation framework to relative approximation of the power sums and leverage binary search to remove the requirement of prior knowledge of them. We also strengthen the precision-dependent lower bound to Ω(1/εmax⁡{1,1/(2α)})Ω\big(1/ε^{\max\{1,1/(2α)\}}\big)Ω(1/εmax{1,1/(2α)}) for 0<α<10<α<10<α<1, which identifies the optimal precision dependence of our algorithm.
In this paper, we provide estimators for quantum Rényi and Tsallis entropies with nearly optimal sample complexity. Specifically, for order ααα, dimension ddd, and additive error ε\varepsilonε, 1. For 0<α<10 < α< 10<α<1, the sample complexity is O(d1+1/α/ε1/α+d1/α−1/ε2)O(d^{1+1/α}/\varepsilon^{1/α} + d^{1/α-1}/\varepsilon^{2})O(d1+1/α/ε1/α+d1/α−1/ε2) for Rényi entropy and O(d1+1/α/ε1/α+d2−2α/ε2)O(d^{1+1/α}/\varepsilon^{1/α} + d^{2-2α}/\varepsilon^2)O(d1+1/α/ε1/α+d2−2α/ε2) for Tsallis entropy. In particular, for 0<α≤1/20 < α\leq 1/20<α≤1/2, the sample complexity for both entropies is O(d1+1/α/ε1/α)O(d^{1+1/α}/\varepsilon^{1/α})O(d1+1/α/ε1/α). 2. For non-integer α>1α> 1α>1, the sample complexity is O(d2/ε1/α+d1−1/α/ε2)O(d^2/\varepsilon^{1/α} + d^{1-1/α}/\varepsilon^2)O(d2/ε1/α+d1−1/α/ε2) for Rényi entropy. Our upper bounds improve the quantum Rényi entropy estimators due to Acharya, Issa, Shende, and Wagner (2017) and the quantum Tsallis entropy estimators due to Chen, Liu, and Wang (2026), and match the lower bounds recently established by Wang (2026).
This paper reveals a conceptually new connection from information theory to approximation theory via quantum algorithms for entropy estimation. Specifically, we provide an information-theoretic lower bound Ω(n)Ω(\sqrt{n})Ω(n​) on the approximate degree of the monomial xnx^nxn, compared to the analytic lower bounds shown in Newman and Rivlin (Aequ. Math. 1976) via Fourier analysis and in Sachdeva and Vishnoi (Found. Trends Theor. Comput. Sci. 2014) via the Markov brothers' inequality. This is done by relating the polynomial approximation of monomials to quantum Tsallis entropy estimation. This further implies a quantum algorithm that estimates to within additive error ε\varepsilonε the Tsallis entropy of integer order q≥2q \geq 2q≥2 of an unknown probability distribution ppp or an unknown quantum state ρρρ, using Θ~(1qε)\widetilde Θ(\frac{1}{\sqrt{q}\varepsilon})Θ(q​ε1​) queries to the quantum oracle that produces a sample from ppp or prepares a copy of ρρρ, improving the prior best O(1ε)O(\frac{1}{\varepsilon})O(ε1​) via the Shift test due to Ekert, Alves, Oi, Horodecki, Horodecki and Kwek (Phys. Rev. Lett. 2002). To the best of our knowledge, this is the first quantum entropy estimator with optimal query complexity (up to polylogarithmic factors) for all parameters simultaneously.
We propose a novel approach to the minimax estimation of high-order functionals from the perspective of quantum computing. Specifically, for any real number α≫1α\gg 1α≫1, we present two estimators, one for the classical functional Fα(P)=∑i=1Spiα\mathrm{F}_α(P) = \sum_{i=1}^S p_i^αFα​(P)=∑i=1S​piα​ of a discrete distribution PPP and the other for the quantum functional Fα(ρ)=tr⁡(ρα)\mathrm{F}_α(ρ) = \operatorname{tr}(ρ^α)Fα​(ρ)=tr(ρα) of a mixed state ρρρ. These functionals have close connections with the Rényi entropy and the Tsallis entropy. We show that both estimators achieve the minimax optimal L2L_2L2​ rate αn−1α\mathsf{n}^{-1}αn−1 in the range α≲n≲α3−o(1)α\lesssim \mathsf{n} \lesssim α^{3-o(1)}α≲n≲α3−o(1), where the support size SSS of PPP or the dimension of ρρρ can be much larger than the number of samples n\mathsf{n}n. As a result, both estimators achieve the \textit{optimal} sample complexity n≍α\mathsf{n} \asymp αn≍α, improving upon the prior best upper bounds O(α2)O(α^2)O(α2) established by Jiao, Venkat, Han, and Weissman (IEEE Trans. Inf. Theory 2017) for classical functionals and Chen and Wang (COLT 2025) for quantum functionals. Our estimators are constructed under a unified framework using quantum primitives and run in linear time on a quantum computer. This work reveals an unexpected path from quantum computing to statistics, suggesting a conceptually new methodology for functional estimation. It adds to the growing list of quantum proofs for classical theorems.
We propose a quantum multi-level estimation framework for a functional ∑i=1nf(pi)\sum_{i=1}^n f(p_i)∑i=1n​f(pi​) of a discrete distribution (pi)i=1n(p_i)_{i=1}^n(pi​)i=1n​. We partition the values pip_ipi​ into logarithmically many intervals whose length decays exponentially. For each interval, we perform non-destructive singular value discrimination to isolate the relevant pip_ipi​, enabling adaptive estimation of the partial sum over this interval. Unlike previous variable-time approaches, our method avoids high control overhead and requires only constant extra ancilla qubits. As an application, we present efficient quantum estimators for the qqq-Tsallis entropy of discrete distributions. Specifically: (i) For q>1q > 1q>1, we obtain a near-optimal quantum algorithm with query complexity Θ~(1/εmax⁡{1/(2(q−1)),1})\tildeΘ(1/\varepsilon^{\max\{1/(2(q-1)), 1\}})Θ~(1/εmax{1/(2(q−1)),1}), improving the prior best O(1/ε1+1/(q−1))O(1/\varepsilon^{1+1/(q-1)})O(1/ε1+1/(q−1)) due to Liu and Wang (SODA 2025; IEEE Trans. Inf. Theory 2026). (ii) For 0<q<10 < q < 10<q<1, we obtain a quantum algorithm with query complexity O~(n1/q−1/2/ε1/q)\tilde{O}(n^{1/q-1/2}/\varepsilon^{1/q})O~(n1/q−1/2/ε1/q), exhibiting a quantum speedup over the near-optimal classical estimators due to Jiao, Venkat, Han, and Weissman (IEEE Trans. Inf. Theory 2017). Our results achieve, to our knowledge, the first near-optimal quantum estimators for parameterized qqq-entropy for non-integer qqq.
Entropy is a fundamental property of both classical and quantum systems, spanning myriad theoretical and practical applications in physics and computer science. We study the problem of obtaining estimates to within a multiplicative factor γ>1γ>1γ>1 of the Shannon entropy of probability distributions and the von Neumann entropy of mixed quantum states. Our main results are: ∙\quad\bullet∙ an O~(n1+η2γ2)\widetilde{\mathcal{O}}\left( n^{\frac{1+η}{2γ^2}}\right)O(n2γ21+η​)-query quantum algorithm that outputs a γγγ-multiplicative approximation of the Shannon entropy H(p)H(\mathbf{p})H(p) of a classical probability distribution p=(p1,…,pn)\mathbf{p} = (p_1,\ldots,p_n)p=(p1​,…,pn​); ∙\quad\bullet∙ an O~(n12+1+η2γ2)\widetilde{\mathcal{O}}\left( n^{\frac12+\frac{1+η}{2γ^2}}\right)O(n21​+2γ21+η​)-query quantum algorithm that outputs a γγγ-multiplicative approximation of the von Neumann entropy S(ρ)S(ρ)S(ρ) of a density matrix ρ∈Cn×nρ\in\mathbb{C}^{n\times n}ρ∈Cn×n. In both cases, the input is assumed to have entropy bounded away from zero by a quantity determined by the parameter η>0η>0η>0, since, as we prove, no polynomial query algorithm can multiplicatively approximate the entropy of distributions with arbitrarily low entropy. In addition, we provide Ω(n13γ2)Ω\left(n^{\frac{1}{3γ^2}}\right)Ω(n3γ21​) lower bounds on the query complexity of γγγ-multiplicative estimation of Shannon and von Neumann entropies. We work with the quantum purified query access model, which can handle both classical probability distributions and mixed quantum states, and is the most general input model considered in the literature.