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).
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 ε,
For 0<α<1, the sample complexity is O(d1+1/α/ε1/α+d1/α−1/ε2) for Rényi entropy and O(d1+1/α/ε1/α+d2−2α/ε2) for Tsallis entropy. In particular, for 0<α≤1/2, the sample complexity for both entropies is O(d1+1/α/ε1/α).
For non-integer α>1, the sample complexity is 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).
We investigate the computational hardness of estimating the quantum α-Rényi entropy SαR(ρ)=1−αlnTr(ρα) and the quantum q-Tsallis entropy SqT(ρ)=q−11−Tr(ρq), both of which converge to the von Neumann entropy as the order approaches 1. The promise problems Quantum α-Rényi Entropy Approximation (RényiQEAα) and Quantum q-Tsallis Entropy Approximation (TsallisQEAq) ask whether $ {\rm S}^ {\tt R}_α(ρ)$ or SqT(ρ), is at least τ1 or at most τ2, where τ1−τ2 is typically a positive constant. Previous hardness results cover only the von Neumann entropy (order 1) and some cases of the quantum q-Tsallis entropy, while existing approaches do not readily extend to other orders.
We establish that for all positive real α and q, and also for α=∞, the rank-2 variants Rank2RényiQEAα and Rank2TsallisQEAq are BQP-hard. Combined with prior (rank-dependent) quantum query algorithms in Wang, Guan, Liu, Zhang, and Ying (TIT 2024), Wang, Zhang, and Li (TIT 2024), and Liu and Wang (SODA 2025), as well as the one derived from O'Donnell and Wright (STOC 2016), our results imply:
- For all real orders α>0 or α=∞, and for all real orders 0<q≤1, LowRankRényiQEAα and LowRankTsallisQEAq are BQP-complete, where both are restricted versions of RényiQEAα and TsallisQEAq with ρ of polynomial rank.
- For all real order q>1, TsallisQEAq is BQP-complete.
Our hardness results stem from reductions based on new inequalities relating the α-Rényi or q-Tsallis binary entropies of different orders. These reductions differ substantially from previous approaches, and the inequalities are of independent interest.
Entropy is a measure of the randomness of a system. Estimating the entropy of a quantum state is a basic problem in quantum information. In this paper, we introduce a time-efficient quantum approach to estimating the von Neumann entropy S(ρ) and Rényi entropy Sα(ρ) of an N-dimensional quantum state ρ, given access to independent samples of ρ. Specifically, we provide the following: 1. A quantum estimator for S(ρ) with time complexity O~(N2), improving the prior best time complexity O~(N6) by Acharya, Issa, Shende, and Wagner (2020) and Bavarian, Mehraba, and Wright (2016). 2. A quantum estimator for Sα(ρ) with time complexity O~(N4/α−2) for 0<α<1 and O~(N4−2/α) for α>1, improving the prior best time complexity O~(N6/α) for 0<α<1 and O~(N6) for α>1 by Acharya, Issa, Shende, and Wagner (2020), though at a cost of a slightly larger sample complexity. Moreover, these estimators are naturally extensible to the low-rank case. We also provide a sample lower bound for estimating Sα(ρ). Technically, our method is quite different from the previous ones that are based on weak Schur sampling and Young diagrams. At the heart of our construction, is a novel tool called samplizer, which can "samplize" a quantum query algorithm to a quantum algorithm with similar behavior using only samples of quantum states; this suggests a unified framework for estimating quantum entropies. Specifically, when a quantum oracle U block-encodes a mixed quantum state ρ, any quantum query algorithm using Q queries to U can be samplized to a δ-close (in the diamond norm) quantum algorithm using Θ~(Q2/δ) samples of ρ. Moreover, this samplization is proven to be optimal, up to a polylogarithmic factor.
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) for any distribution p=(pi)i=1n given its purified quantum query-access. For non-integer α>1, our algorithm estimates Hα(p) to within additive error ε using only O(nmax{1/2,1−1/α}/ε) queries, which improves the best known upper bound for dependence on both n and 1/ε. For 0<α<1, our algorithm has query complexity O(n1/(2α)/εmax{1,1/(2α)}), 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 Ω(1/εmax{1,1/(2α)}) for 0<α<1, which identifies the optimal precision dependence of our algorithm.
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, we present two estimators, one for the classical functional Fα(P)=∑i=1Spiα of a discrete distribution P and the other for the quantum functional 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 L2 rate αn−1 in the range α≲n≲α3−o(1), where the support size S of P or the dimension of ρ can be much larger than the number of samples n. As a result, both estimators achieve the \textit{optimal} sample complexity n≍α, 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.
Entropy is a measure of the randomness of a system. Estimating the entropy of a quantum state is a basic problem in quantum information. In this paper, we introduce a time-efficient quantum approach to estimating the von Neumann entropyS(ρ) and Rényi entropySα(ρ) of anN-dimensional quantum state ρ, given access to independent samples of ρ. Specifically, we provide the following quantum estimators. • A quantum estimator forS(ρ) with time complexity Õ (N2),1improving the prior best time complexity Õ(N6) by Acharya, Issa, Shende, and Wagner (2020) and Bavarian, Mehraba, and Wright (2016). • A quantum estimator forSα(ρ) with time complexity Õ (N4/α−2) for 0N4−2/α) for α > 1, improving the prior best time complexity Õ(N6/α) for 0N6) for α > 1 by Acharya, Issa, Shende, and Wagner (2020), though at a cost of a slightly larger sample complexity. Moreover, these estimators are naturally extensible to the low-rank case. We also provide a sample lower bound Ω(max{N/ε,N1/α−1/ε1/α}) for estimatingSα(ρ). Technically, our method is quite different from the previous ones that are based on weak Schur sampling and Young diagrams. At the heart of our construction, is a novel tool calledsamplizer, which can “samplize” a quantum query algorithm to a quantum algorithm with similar behavior using only samples of quantum states; this suggests a new framework for estimating quantum entropies. Specifically, when a quantum oracleUblockencodes a mixed quantum state ρ, any quantum query algorithm usingQqueries toUcan be samplized to a δ-close (in the diamond norm) quantum algorithm using Θ(Q2/δ) samples of ρ. Moreover, this samplization is proven to be optimal, up to a polylogarithmic factor.
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 HqTsa(P)=1−q∑i=1npiq−1 when 0<q<1, given purified quantum query access to a distribution P on [n]. When 0<q≤21, 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 21<q<1, we introduce a two-stage simultaneous probability estimation procedure, yielding a quantum algorithm with query complexity O(ε2q1n21+2q1+εn1−q), which improves the result given by Chen et al. (ICALP 2026) when $\varepsilon=O\rbra{n^{1-2q}}$.