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 quantum estimators. - A quantum estimator for S(ρ) with time complexity Õ(N²), improving the prior best time complexity Õ(N⁶) by Acharya, Issa, Shende, and Wagner (2020) and Bavarian, Mehraba, and Wright (2016). - A quantum estimator for S_α(ρ) with time complexity Õ(N^{4/α-2}) for 0 < α < 1 and Õ(N^{4-2/α}) for α > 1, improving the prior best time complexity Õ(N^{6/α}) for 0 < α < 1 and Õ(N⁶) 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/ε, N^{1/α-1}/ε^{1/α}}) 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 Θ~(Q²/δ) 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 entropy S(ρ) and Rényi entropy S_α(ρ) of an N-dimensional quantum state ρ, given access to independent samples of ρ. Specifically, we provide the following quantum estimators. - A quantum estimator for S(ρ) with time complexity Õ(N²), improving the prior best time complexity Õ(N⁶) by Acharya, Issa, Shende, and Wagner (2020) and Bavarian, Mehraba, and Wright (2016). - A quantum estimator for S_α(ρ) with time complexity Õ(N^{4/α-2}) for 0 < α < 1 and Õ(N^{4-2/α}) for α > 1, improving the prior best time complexity Õ(N^{6/α}) for 0 < α < 1 and Õ(N⁶) 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/ε, N^{1/α-1}/ε^{1/α}}) 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 Θ~(Q²/δ) samples of ρ. Moreover, this samplization is proven to be optimal, up to a polylogarithmic factor.

Sep 23, 20240 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 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 $\tilde O(N^2)$ , improving the prior best time complexity $\tilde O(N^6)$ by Acharya, Issa, Shende, and Wagner (2020) and Bavarian, Mehraba, and Wright (2016). 2. A quantum estimator for $S_α(ρ)$ with time complexity $\tilde O(N^{4/α-2})$ for $0<α<1$ and $\tilde O(N^{4-2/α})$ for $α>1$ , improving the prior best time complexity $\tilde O(N^{6/α})$ for $0<α<1$ and $\tilde O(N^6)$ 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 $\tildeΘ(Q^2/δ)$ 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 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 $\tilde O(N^2)$, improving the prior best time complexity $\tilde O(N^6)$ by Acharya, Issa, Shende, and Wagner (2020) and Bavarian, Mehraba, and Wright (2016). 2. A quantum estimator for $S_α(ρ)$ with time complexity $\tilde O(N^{4/α-2})$ for $0<α<1$ and $\tilde O(N^{4-2/α})$ for $α>1$, improving the prior best time complexity $\tilde O(N^{6/α})$ for $0<α<1$ and $\tilde O(N^6)$ 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 $\tildeΘ(Q^2/δ)$ samples of $ρ$. Moreover, this samplization is proven to be optimal, up to a polylogarithmic factor.

arXiv:2401.09947Leibniz international proceedings in informaticsJan 1, 20243 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

Estimating Quantum Entropy

Jayadev Acharya, Ibrahim Issa, Nirmal V. Shende +1 more

The entropy of a quantum system is a measure of its randomness, and has applications in measuring quantum entanglement. We study the problem of estimating the von Neumann entropy, S(ρ), and Rényi entropy, Sα(ρ) of an unknown mixed quantum state ρ in d dimensions, given access to independent copies of ρ. We provide algorithms with copy complexity O(d2/α) for estimating Sα(ρ) for α2) for estimating S(ρ), and Sα(ρ) for non-integral α > 1. These bounds are at least quadratic in d, which is the order dependence on the number of copies required for estimating the entire state ρ. For integral α > 1, on the other hand, we provide an algorithm for estimating Sα(ρ) with a sub-quadratic copy complexity of O(d2-2/α), and we show the optimality of the algorithms by providing a matching lower bound.The entropy of a quantum system is a measure of its randomness, and has applications in measuring quantum entanglement. We study the problem of estimating the von Neumann entropy, S(ρ), and Rényi entropy, Sα(ρ) of an unknown mixed quantum state ρ in d dimensions, given access to independent copies of ρ. We provide algorithms with copy complexity O(d2/α) for estimating Sα(ρ) for α2) for estimating S(ρ), and Sα(ρ) for non-integral α > 1. These bounds are at least quadratic in d, which is the order dependence on the number of copies required for estimating the entire state ρ. For integral α > 1, on the other hand, we provide an algorithm for estimating Sα(ρ) with a sub-quadratic copy complexity of O(d2-2/α), and we show the optimality of the algorithms by providing a matching lower bound.

IEEE Journal on Selected Areas in Information TheoryAug 1, 202036 citations

Quantum algorithm for estimating α -Renyi entropies of quantum states

S Subramanian, Min-Hsiu Hsieh

We describe a quantum algorithm to estimate the α-Renyi entropy of an unknown density matrix ρ∈Cd×d for α≠1 by combining the recent technique of quantum singular value transformations with the method of estimating normalized traces in the one clean qubit model. We consider an oracular input model where the input state is prepared via a quantum oracle that outputs a purified version of the state, assumed to be nonsingular. Our method outputs an estimate of the α-Renyi entropy to additive precision ϵ, using an expected total number O(1(xϵ)2) of independent applications of a quantum circuit which coherently queries the input unitary O(1δlogdϵ) times, in each case measuring a single output qubit. Here δ is a lower cutoff on the smallest eigenvalue of ρ and x=1dTr(ρα). The expected number of measurements made in this method can be compared to results in the sample complexity model that generally require Θ(d2ϵ2) samples. Furthermore, we also show that multiplicative approximations can be obtained by iteratively using additive approximations, with an overhead logarithmic in the dimension d.We describe a quantum algorithm to estimate the α-Renyi entropy of an unknown density matrix ρ∈Cd×d for α≠1 by combining the recent technique of quantum singular value transformations with the method of estimating normalized traces in the one clean qubit model. We consider an oracular input model where the input state is prepared via a quantum oracle that outputs a purified version of the state, assumed to be nonsingular. Our method outputs an estimate of the α-Renyi entropy to additive precision ϵ, using an expected total number O(1(xϵ)2) of independent applications of a quantum circuit which coherently queries the input unitary O(1δlogdϵ) times, in each case measuring a single output qubit. Here δ is a lower cutoff on the smallest eigenvalue of ρ and x=1dTr(ρα). The expected number of measurements made in this method can be compared to results in the sample complexity model that generally require Θ(d2ϵ2) samples. Furthermore, we also show that multiplicative approximations can be obtained by iteratively using additive approximations, with an overhead logarithmic in the dimension d.

Aug 1, 20210 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

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

\tilde O(N^2)

, improving the prior best time complexity

\tilde O(N^6)

by Acharya, Issa, Shende, and Wagner (2020) and Bavarian, Mehraba, and Wright (2016). 2. A quantum estimator for

S_α(ρ)

with time complexity

\tilde O(N^{4/α-2})

for

0<α<1

and

\tilde O(N^{4-2/α})

for

α>1

, improving the prior best time complexity

\tilde O(N^{6/α})

for

0<α<1

and

\tilde O(N^6)

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

\tildeΘ(Q^2/δ)

samples of

ρ

. Moreover, this samplization is proven to be optimal, up to a polylogarithmic factor.

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.