arXiv:2410.13559 · IEEE Transactions on Information Theory

On Estimating the Trace of Quantum State Powers

Yupan Liu, Qisheng Wang

Published Apr 14, 2026• 0 citations

Abstract

We investigate the computational complexity of estimating the trace of quantum state powers tr(ρq) for annqubit mixed quantum state ρ, given its state-preparation circuit of size poly(n). This quantity is closely related to and often interchangeable with the Tsallis entropy Sq(ρ) = 1—tr(ρq)/q—1, whereq= 1 corresponds to the von Neumann entropy. For any non-integerq≥ 1 + Ω(1), we provide a quantum estimator for Sq(ρ) with time complexity poly(n), exponentially improving the prior best results of exp(n)due to Acharya, Issa, Shende, and Wagner (ISIT 2019), Wang, Guan, Liu, Zhang, and Ying (TIT 2024)| Wang, Zhang, and Li (TIT 2024), and Wang and Zhang (TIT 2025). Our speedup is achieved by introducing efficiently computableuniform approximationsof positive power functions into quantum singular value transformation. Our quantum algorithm reveals a sharp phase transition between the case ofq= 1 and constantq> 1 in the computational complexity of the Quantumq-Tsallis Entropy Difference Problem (TsallisQEDq), particularly deciding whether the difference Sq(ρ0)−Sq(ρ1) is at least 0.001 or at most −0.001: • For any 1 + Ω (1) ≤q≤ 2, TsallisQEDqis BQP-complete, which implies that Purity Estimation is also BQP-complete. • For any 1≤q≤1+1/n— 1, TsallisQED q is QSZK-hard, leading to hardness of approximating the von Neumann entropy because Sq(ρ) ≤ S (ρ), as long as BQPQSZK. The hardness results are derived from reductions based on new inequalities for the quantumq-Jensen–(Shannon–)Tsallis divergence with 1 ≤q≤ 2, which are of independent interest.

DOI: 10.1109/tit.2026.3683891

Related papers

On Estimating the Trace of Quantum State Powers

Yupan Liu, Qisheng Wang

Society for Industrial and Applied Mathematics eBooksJan 1, 20253 citations

Computational hardness of estimating quantum entropies via binary entropy bounds

Yupan Liu

quant-pharXiv:2601.03734Leibniz international proceedings in informaticsJan 8, 20260 citations

On estimating operator norm distance, with optimal trace distance estimation when one state is pure

Yupan Liu, Qisheng Wang, Zhan Yu

quant-pharXiv:2607.03905Leibniz international proceedings in informaticsJul 7, 20260 citations

Time-Efficient Quantum Entropy Estimator via Samplizer

Qisheng Wang, Zhicheng Zhang

IEEE Transactions on Information TheoryJun 9, 20256 citations

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

Kean Chen, Qisheng Wang

quant-pharXiv:2608.18070Aug 19, 20260 citations

A Unified Complexity Framework for Quantum Property Testing

Qisheng Wang

quant-pharXiv:2608.02600Aug 4, 20260 citations

arXiv:2410.13559 · IEEE Transactions on Information Theory

On Estimating the Trace of Quantum State Powers

Yupan Liu, Qisheng Wang

Published Apr 14, 2026• 0 citations

arXiv HTML PDF

Abstract

DOI: 10.1109/tit.2026.3683891

Related papers

On Estimating the Trace of Quantum State Powers

Yupan Liu, Qisheng Wang

We investigate the computational complexity of estimating the trace of quantum state powers tr(ρq ) for an n-qubit mixed quantum state ρ, given its state-preparation circuit of size poly(n ). This quantity is closely related to and often interchangeable with the Tsallis entropywhere q = 1 corresponds to the von Neumann entropy. For any non-integer q ≥ 1 + Ω(1), we provide a quantum estimator for Sq (ρ ) with time complexity poly(n), exponentially improving the prior best results of exp(n ) due to Acharya, Issa, Shende, and Wagner (ISIT 2019), Wang, Guan, Liu, Zhang, and Ying (TIT 2024), Wang, Zhang, and Li (TIT 2024), and Wang and Zhang (ESA 2024). Our speedup is achieved by introducing efficiently computable uniform approximations of positive power functions into quantum singular value transformation.We investigate the computational complexity of estimating the trace of quantum state powers tr(ρq ) for an n-qubit mixed quantum state ρ, given its state-preparation circuit of size poly(n ). This quantity is closely related to and often interchangeable with the Tsallis entropywhere q = 1 corresponds to the von Neumann entropy. For any non-integer q ≥ 1 + Ω(1), we provide a quantum estimator for Sq (ρ ) with time complexity poly(n), exponentially improving the prior best results of exp(n ) due to Acharya, Issa, Shende, and Wagner (ISIT 2019), Wang, Guan, Liu, Zhang, and Ying (TIT 2024), Wang, Zhang, and Li (TIT 2024), and Wang and Zhang (ESA 2024). Our speedup is achieved by introducing efficiently computable uniform approximations of positive power functions into quantum singular value transformation.

Society for Industrial and Applied Mathematics eBooksJan 1, 20253 citations

Computational hardness of estimating quantum entropies via binary entropy bounds

Yupan Liu

We investigate the computational hardness of estimating the quantum $α$ -Rényi entropy ${\rm S}^{\tt R}_α(ρ) = \frac{\ln {\rm Tr}(ρ^α)}{1-α}$ and the quantum $q$ -Tsallis entropy ${\rm S}^{\tt T}_q(ρ) = \frac{1-{\rm Tr}(ρ^q)}{q-1}$ , 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 (TsallisQEA $_q$ ) ask whether $ {\rm S}^ {\tt R}_α(ρ)$ or ${\rm S}^{\tt T}_q(ρ)$ , 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 $α=\infty$ , the rank- $2$ variants Rank2RényiQEA $_α$ and Rank2TsallisQEA $_q$ 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 $α=\infty$ , and for all real orders $0 < q \leq 1$ , LowRankRényiQEA $_α$ and LowRankTsallisQEA $_q$ are BQP-complete, where both are restricted versions of RényiQEA $_α$ and TsallisQEA $_q$ with $ρ$ of polynomial rank. - For all real order $q>1$ , TsallisQEA $_q$ 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 investigate the computational hardness of estimating the quantum $α$-Rényi entropy ${\rm S}^{\tt R}_α(ρ) = \frac{\ln {\rm Tr}(ρ^α)}{1-α}$ and the quantum $q$-Tsallis entropy ${\rm S}^{\tt T}_q(ρ) = \frac{1-{\rm Tr}(ρ^q)}{q-1}$, 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 (TsallisQEA$_q$) ask whether $ {\rm S}^ {\tt R}_α(ρ)$ or ${\rm S}^{\tt T}_q(ρ)$, 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 $α=\infty$, the rank-$2$ variants Rank2RényiQEA$_α$ and Rank2TsallisQEA$_q$ 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 $α=\infty$, and for all real orders $0 < q \leq 1$, LowRankRényiQEA$_α$ and LowRankTsallisQEA$_q$ are BQP-complete, where both are restricted versions of RényiQEA$_α$ and TsallisQEA$_q$ with $ρ$ of polynomial rank. - For all real order $q>1$, TsallisQEA$_q$ 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.

quant-pharXiv:2601.03734Leibniz international proceedings in informaticsJan 8, 20260 citations

On estimating operator norm distance, with optimal trace distance estimation when one state is pure

Yupan Liu, Qisheng Wang, Zhan Yu

We investigate the computational complexity of estimating the operator norm distance ${\rm T}_{\infty}(ρ_0,ρ_1)$ , defined via the operator norm $\|A\|_{\infty} = σ_{\max}(A)$ , given ${\rm poly}(n)$ -size state-preparation circuits of $n$ -qubit quantum states $ρ_0$ and $ρ_1$ . We provide efficient quantum estimators for the operator norm distance whose complexity is independent of the rank (and thus the dimension) of the states: 1. When one state is pure, we establish an optimal quantum estimator using $Θ(1/ε)$ queries to the state-preparation circuits. Consequently, for constant additive error, say $ε=1/5$ , our estimator runs in ${\rm poly}(n)$ time. Since the operator norm distance ${\rm T}_{\infty}(|ψ\rangle\!\langleψ|,ρ)$ is exactly half of the trace distance ${\rm T}(|ψ\rangle\!\langleψ|,ρ)$ , our result also gives rank-independent query complexity for estimating both quantities, whereas the approaches due to van Apeldoorn, Cornelissen, Gily{é}n, and Nannicini (SODA 2023) and Wang and Zhang (TIT 2024) have query complexity scaling at least linearly with ${\rm rank}(ρ)$ , which can be $\exp(n)$ in general. 2. For general quantum states, we also provide a quantum estimator using $\widetilde{O}(1/ε^{3/2})$ queries to the state-preparation circuits, which shows that the corresponding promise problem is ${\sf BQP}$ -complete and improves the ${\sf QMA}$ upper bound sketched by Liu and Wang (ESA 2025). Together with an $Ω(1/ε)$ quantum query complexity lower bound, this leaves only square-root room for improvement. The key intuition behind our estimators is that, when one state is pure, the pure state $|ψ\rangle$ has overlap at least $1/2$ with the top unit eigenvector of $|ψ\rangle\!\langleψ|-ρ$ , reflecting a structural feature specific to the operator norm distance.We investigate the computational complexity of estimating the operator norm distance ${\rm T}_{\infty}(ρ_0,ρ_1)$, defined via the operator norm $\|A\|_{\infty} = σ_{\max}(A)$, given ${\rm poly}(n)$-size state-preparation circuits of $n$-qubit quantum states $ρ_0$ and $ρ_1$. We provide efficient quantum estimators for the operator norm distance whose complexity is independent of the rank (and thus the dimension) of the states: 1. When one state is pure, we establish an optimal quantum estimator using $Θ(1/ε)$ queries to the state-preparation circuits. Consequently, for constant additive error, say $ε=1/5$, our estimator runs in ${\rm poly}(n)$ time. Since the operator norm distance ${\rm T}_{\infty}(|ψ\rangle\!\langleψ|,ρ)$ is exactly half of the trace distance ${\rm T}(|ψ\rangle\!\langleψ|,ρ)$, our result also gives rank-independent query complexity for estimating both quantities, whereas the approaches due to van Apeldoorn, Cornelissen, Gily{é}n, and Nannicini (SODA 2023) and Wang and Zhang (TIT 2024) have query complexity scaling at least linearly with ${\rm rank}(ρ)$, which can be $\exp(n)$ in general. 2. For general quantum states, we also provide a quantum estimator using $\widetilde{O}(1/ε^{3/2})$ queries to the state-preparation circuits, which shows that the corresponding promise problem is ${\sf BQP}$-complete and improves the ${\sf QMA}$ upper bound sketched by Liu and Wang (ESA 2025). Together with an $Ω(1/ε)$ quantum query complexity lower bound, this leaves only square-root room for improvement. The key intuition behind our estimators is that, when one state is pure, the pure state $|ψ\rangle$ has overlap at least $1/2$ with the top unit eigenvector of $|ψ\rangle\!\langleψ|-ρ$, reflecting a structural feature specific to the operator norm distance.

quant-pharXiv:2607.03905Leibniz international proceedings in informaticsJul 7, 20260 citations

Time-Efficient Quantum Entropy Estimator via Samplizer

Qisheng Wang, Zhicheng Zhang

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.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.

IEEE Transactions on Information TheoryJun 9, 20256 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).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.18070Aug 19, 20260 citations

A Unified Complexity Framework for Quantum Property Testing

Qisheng Wang

We develop a unified framework for analyzing the complexity of quantum property testing through functionals of the form $\mathcal{L}_φ(ρ) = \operatorname{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 $\mathcal{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 $Θ\!\left(\frac{d^2}{\varepsilon\log^2(d)\max\{1, \varepsilon\log^2(d)\}} + \frac{\log^2(d)}{\varepsilon^2}\right),$ and the sample complexity of spectrum estimation is $Θ\!\left(\frac{d^2}{\varepsilon^2\log^2(d)\max\{1, \varepsilon^2\log^2(d)\}}\right).$ In summary, our results resolve several open problems and establish the optimality of 37 quantum algorithms since 2015, up to constant or polylogarithmic factors.We develop a unified framework for analyzing the complexity of quantum property testing through functionals of the form $\mathcal{L}_φ(ρ) = \operatorname{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 $\mathcal{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 \[ Θ\!\left(\frac{d^2}{\varepsilon\log^2(d)\max\{1, \varepsilon\log^2(d)\}} + \frac{\log^2(d)}{\varepsilon^2}\right), \] and the sample complexity of spectrum estimation is \[ Θ\!\left(\frac{d^2}{\varepsilon^2\log^2(d)\max\{1, \varepsilon^2\log^2(d)\}}\right). \] In summary, our results resolve several open problems and establish the optimality of 37 quantum algorithms since 2015, up to constant or polylogarithmic factors.

quant-pharXiv:2608.02600Aug 4, 20260 citations

We investigate the computational hardness of estimating the quantum

α

-Rényi entropy

{\rm S}^{\tt R}_α(ρ) = \frac{\ln {\rm Tr}(ρ^α)}{1-α}

and the quantum

q

-Tsallis entropy

{\rm S}^{\tt T}_q(ρ) = \frac{1-{\rm Tr}(ρ^q)}{q-1}

, 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 (TsallisQEA

_q

) ask whether $ {\rm S}^ {\tt R}_α(ρ)$ or

{\rm S}^{\tt T}_q(ρ)

, 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

α=\infty

, the rank-

2

variants Rank2RényiQEA

_α

and Rank2TsallisQEA

_q

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

α=\infty

, and for all real orders

0 < q \leq 1

, LowRankRényiQEA

_α

and LowRankTsallisQEA

_q

are BQP-complete, where both are restricted versions of RényiQEA

_α

and TsallisQEA

_q

with

ρ

of polynomial rank. - For all real order

q>1

, TsallisQEA

_q

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 investigate the computational complexity of estimating the operator norm distance

{\rm T}_{\infty}(ρ_0,ρ_1)

, defined via the operator norm

\|A\|_{\infty} = σ_{\max}(A)

, given

{\rm poly}(n)

-size state-preparation circuits of

n

-qubit quantum states

ρ_0

and

ρ_1

. We provide efficient quantum estimators for the operator norm distance whose complexity is independent of the rank (and thus the dimension) of the states: 1. When one state is pure, we establish an optimal quantum estimator using

Θ(1/ε)

queries to the state-preparation circuits. Consequently, for constant additive error, say

ε=1/5

, our estimator runs in

{\rm poly}(n)

time. Since the operator norm distance

{\rm T}_{\infty}(|ψ\rangle\!\langleψ|,ρ)

is exactly half of the trace distance

{\rm T}(|ψ\rangle\!\langleψ|,ρ)

, our result also gives rank-independent query complexity for estimating both quantities, whereas the approaches due to van Apeldoorn, Cornelissen, Gily{é}n, and Nannicini (SODA 2023) and Wang and Zhang (TIT 2024) have query complexity scaling at least linearly with

{\rm rank}(ρ)

, which can be

\exp(n)

in general. 2. For general quantum states, we also provide a quantum estimator using

\widetilde{O}(1/ε^{3/2})

queries to the state-preparation circuits, which shows that the corresponding promise problem is

{\sf BQP}

-complete and improves the

{\sf QMA}

upper bound sketched by Liu and Wang (ESA 2025). Together with an

Ω(1/ε)

quantum query complexity lower bound, this leaves only square-root room for improvement. The key intuition behind our estimators is that, when one state is pure, the pure state

|ψ\rangle

has overlap at least

1/2

with the top unit eigenvector of

|ψ\rangle\!\langleψ|-ρ

, reflecting a structural feature specific to the operator norm distance.

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).

We develop a unified framework for analyzing the complexity of quantum property testing through functionals of the form

\mathcal{L}_φ(ρ) = \operatorname{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

\mathcal{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

Θ\!\left(\frac{d^2}{\varepsilon\log^2(d)\max\{1, \varepsilon\log^2(d)\}} + \frac{\log^2(d)}{\varepsilon^2}\right),

and the sample complexity of spectrum estimation is

Θ\!\left(\frac{d^2}{\varepsilon^2\log^2(d)\max\{1, \varepsilon^2\log^2(d)\}}\right).

In summary, our results resolve several open problems and establish the optimality of 37 quantum algorithms since 2015, up to constant or polylogarithmic factors.