We show that the von Neumann entropy of an unknown $d$-dimensional quantum state $ρ$ can be estimated to within additive error $\varepsilon$ using \[ Θ\!\left(\frac{d^2}{\varepsilon\log^2(d)(1+\varepsilon\log^2(d))} + \frac{\log^2(d)}{\varepsilon^2}\right) \] samples of $ρ$, matching the lower bound due to Wang (2026). Our estimator is based on a high-degree approximation polynomial and the main technical challenge is bounding its variance despite the large polynomial degree. We overcome this using a quantum Hoeffding decomposition, which preserves cancellations between different polynomial terms and reduces the analysis to derivative bounds for the approximation polynomial.
Comments
22 pages, 1 table, 1 algorithm. Improved the sample complexity to optimal
We show that the von Neumann entropy of an unknown d-dimensional quantum state ρ can be estimated to within additive error ε using [ Θ!\left(\frac{d^2}{\varepsilon\log^2(d)(1+\varepsilon\log^2(d))} + \frac{\log^2(d)}{\varepsilon^2}\right) ] samples of ρ, matching the lower bound due to Wang (2026). Our estimator is based on a high-degree approximation polynomial and the main technical challenge is bounding its variance despite the large polynomial degree. We overcome this using a quantum Hoeffding decomposition, which preserves cancellations between different polynomial terms and reduces the analysis to derivative bounds for the approximation polynomial.
We prove that the spectrum of an unknown d-dimensional quantum state can be estimated to error ε in total variation distance using O(d2min{(εlogd)41,(εlogd)21}) copies. This matches the recent lower bound of Wang. When restricted to unentangled measurements, we give an algorithm with an additional factor of d in copy complexity, which we conjecture to be optimal.
We develop a framework for recovering the small eigenvalues of a quantum state by matching Chebyshev moments. We bound the variance of each Chebyshev moment estimate in terms of scalar derivatives of the corresponding polynomial, using classical and quantum Efron--Stein decompositions. Different rescalings of the Chebyshev polynomials balance approximation error and variance, yielding two regimes in our copy complexity bound.
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: ∙ an O(n2γ21+η)-query quantum algorithm that outputs a γ-multiplicative approximation of the Shannon entropy H(p) of a classical probability distribution p=(p1,…,pn); ∙ an O(n21+2γ21+η)-query quantum algorithm that outputs a γ-multiplicative approximation of the von Neumann entropy S(ρ) of a density matrix ρ∈Cn×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 Ω(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.
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 ε,
1. 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/α).
2. 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).
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) on the approximate degree of the monomial xn, 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 ε the Tsallis entropy of integer order q≥2 of an unknown probability distribution p or an unknown quantum state ρ, using Θ(qε1) queries to the quantum oracle that produces a sample from p or prepares a copy of ρ, improving the prior best 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 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.
We develop a unified framework for analyzing the complexity of quantum property testing through functionals of the form Lφ(ρ)=tr(φ(dρ))/d, where ρ is an unknown d-dimensional quantum state and φ is a given function. A master theorem is established that derives sample complexity lower bounds for estimating Lφ(ρ) from properties of φ, combining Haar-random moment encoding with moment matching and best polynomial approximation. Corresponding query complexity lower bounds follow from quantum sample-to-query lifting.
The framework yields (nearly) tight bounds for a broad class of problems, including entropy estimation (von Neumann, Rényi, and Tsallis), closeness estimation (trace distance and Uhlmann fidelity), spectrum estimation, rank testing (operator rank, Schmidt rank, and matrix product states). In particular, combined with known upper bounds, we show that the sample complexity of von Neumann entropy estimation is Θ(εlog2(d)max{1,εlog2(d)}d2+ε2log2(d)), and the sample complexity of spectrum estimation is Θ(ε2log2(d)max{1,ε2log2(d)}d2). In summary, our results resolve several open problems and establish the optimality of 37 quantum algorithms since 2015, up to constant or polylogarithmic factors.