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

IEEE Transactions on Information Theory

Time-Efficient Quantum Entropy Estimator via Samplizer

Qisheng Wang, Zhicheng Zhang

Published Jun 9, 2025• 29 citations
Publisher

Abstract

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.

DOI
10.1109/tit.2025.3576137

Related papers

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 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, 2024•0 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.

arXiv:2401.09947•Leibniz international proceedings in informatics•Jan 1, 2024•15 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

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.

IEEE Journal on Selected Areas in Information Theory•Aug 1, 2020•69 citations

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

arXiv:2410.13559•IEEE Transactions on Information Theory•Apr 14, 2026•13 citations

Breaking the Multiplicative Overhead in Quantum Entropy Estimation

Junxiang Huang, Chenyang Li, Lu-Fan Zhang +2 more

The von Neumann, Tsallis, and Rényi entropies are fundamental measures of quantum information. A common estimation strategy multiplies the worst-case costs of spectral transformation and statistical readout, leaving gaps to query lower bounds. We reduce this overhead with multi-level algorithms that use local normalization and precision allocation, while variable-time estimation accounts for the probability of reaching expensive spectral tests. With controlled purified access and its inverse, we obtain bounds for additive error $\varepsilon$, rank upper bound $R$, and fixed order $α$. Tsallis entropy estimation has near-optimal rank-independent query complexity $\widetilde O(\varepsilon^{-1/(α-1)})$ for $1<α<2$, when the allowed dimension and rank accommodate the lower-bound instances, and $\widetilde O(1/\varepsilon)$ for $α\ge2$, where $\widetilde O$ suppresses logarithmic factors. The first saves a factor $1/\varepsilon$; the second extends known integer-order scaling to noninteger orders. We also improve the von Neumann entropy bound from $\widetilde O(R/\varepsilon^2)$ to $\widetilde O(R/\varepsilon)$ and obtain $\widetilde O(R/\varepsilon)$ for noninteger Rényi orders $1<α<3$, with further bounds at other orders. Our functional-estimation theorem replaces the global product by a sum of local costs weighted by function magnitudes and spectral masses. We further estimate fixed logarithmic moments and entropy variance using $\widetilde O(R/\varepsilon)$ queries, providing efficient access to fluctuation parameters that enter finite-blocklength quantum compression and pure-state entanglement conversion. More broadly, our framework extends beyond entropy to a broad class of density-matrix functionals, offering a systematic approach toward optimal query complexity in quantum spectral estimation.

quant-pharXiv:2609.40179•Oct 1, 2026•0 citations
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 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(ρ)S(ρ)S(ρ) and Rényi entropy Sα(ρ)S_α(ρ)Sα​(ρ) of an NNN-dimensional quantum state ρρρ, given access to independent samples of ρρρ. Specifically, we provide the following: 1. A quantum estimator for S(ρ)S(ρ)S(ρ) with time complexity O~(N2)\tilde O(N^2)O~(N2), improving the prior best time complexity O~(N6)\tilde O(N^6)O~(N6) by Acharya, Issa, Shende, and Wagner (2020) and Bavarian, Mehraba, and Wright (2016). 2. A quantum estimator for Sα(ρ)S_α(ρ)Sα​(ρ) with time complexity O~(N4/α−2)\tilde O(N^{4/α-2})O~(N4/α−2) for 0<α<10<α<10<α<1 and O~(N4−2/α)\tilde O(N^{4-2/α})O~(N4−2/α) for α>1α>1α>1, improving the prior best time complexity O~(N6/α)\tilde O(N^{6/α})O~(N6/α) for 0<α<10<α<10<α<1 and O~(N6)\tilde O(N^6)O~(N6) for α>1α>1α>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α(ρ)S_α(ρ)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 UUU block-encodes a mixed quantum state ρρρ, any quantum query algorithm using QQQ queries to UUU can be samplized to a δδδ-close (in the diamond norm) quantum algorithm using Θ~(Q2/δ)\tildeΘ(Q^2/δ)Θ~(Q2/δ) 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 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).
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.
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.
The von Neumann, Tsallis, and Rényi entropies are fundamental measures of quantum information. A common estimation strategy multiplies the worst-case costs of spectral transformation and statistical readout, leaving gaps to query lower bounds. We reduce this overhead with multi-level algorithms that use local normalization and precision allocation, while variable-time estimation accounts for the probability of reaching expensive spectral tests. With controlled purified access and its inverse, we obtain bounds for additive error ε\varepsilonε, rank upper bound RRR, and fixed order ααα. Tsallis entropy estimation has near-optimal rank-independent query complexity O~(ε−1/(α−1))\widetilde O(\varepsilon^{-1/(α-1)})O(ε−1/(α−1)) for 1<α<21<α<21<α<2, when the allowed dimension and rank accommodate the lower-bound instances, and O~(1/ε)\widetilde O(1/\varepsilon)O(1/ε) for α≥2α\ge2α≥2, where O~\widetilde OO suppresses logarithmic factors. The first saves a factor 1/ε1/\varepsilon1/ε; the second extends known integer-order scaling to noninteger orders. We also improve the von Neumann entropy bound from O~(R/ε2)\widetilde O(R/\varepsilon^2)O(R/ε2) to O~(R/ε)\widetilde O(R/\varepsilon)O(R/ε) and obtain O~(R/ε)\widetilde O(R/\varepsilon)O(R/ε) for noninteger Rényi orders 1<α<31<α<31<α<3, with further bounds at other orders. Our functional-estimation theorem replaces the global product by a sum of local costs weighted by function magnitudes and spectral masses. We further estimate fixed logarithmic moments and entropy variance using O~(R/ε)\widetilde O(R/\varepsilon)O(R/ε) queries, providing efficient access to fluctuation parameters that enter finite-blocklength quantum compression and pure-state entanglement conversion. More broadly, our framework extends beyond entropy to a broad class of density-matrix functionals, offering a systematic approach toward optimal query complexity in quantum spectral estimation.