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

arXiv:2111.11139

Sublinear quantum algorithms for estimating von Neumann entropy

Tom Gur, Min-Hsiu Hsieh, Sathyawageeswar Subramanian

Published Nov 22, 2021• 10 citations
arXivHTMLPDF

Abstract

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: $\quad\bullet$ an $\widetilde{\mathcal{O}}\left( n^{\frac{1+η}{2γ^2}}\right)$-query quantum algorithm that outputs a $γ$-multiplicative approximation of the Shannon entropy $H(\mathbf{p})$ of a classical probability distribution $\mathbf{p} = (p_1,\ldots,p_n)$; $\quad\bullet$ an $\widetilde{\mathcal{O}}\left( n^{\frac12+\frac{1+η}{2γ^2}}\right)$-query quantum algorithm that outputs a $γ$-multiplicative approximation of the von Neumann entropy $S(ρ)$ of a density matrix $ρ\in\mathbb{C}^{n\times 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 $Ω\left(n^{\frac{1}{3γ^2}}\right)$ 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.

DOI
10.48550/arxiv.2111.11139

Related papers

Quantum Tsallis Entropy Estimation: Near-Optimal Bounds and High-Precision Improvements

Chengshen Gao, Zongxing Xiong, Lvzhou Li

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 $\mathrm{H}_q^{\mathrm{Tsa}}(P) =\frac{\sum_{i=1}^n p_i^q-1}{1-q}$ when $0<q<1$, given purified quantum query access to a distribution $P$ on $[n]$. When $0<q\leq \frac{1}{2}$, 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 $\frac{1}{2}<q<1$, we introduce a two-stage simultaneous probability estimation procedure, yielding a quantum algorithm with query complexity $\widetilde{O}\left(\frac{n^{\frac12+\frac{1}{2q}}}{\varepsilon^{\frac{1}{2q}}}+\frac{n^{1-q}}{\varepsilon}\right)$, which improves the result given by Chen et al. (ICALP 2026) when $\varepsilon=O\rbra{n^{1-2q}}$.

quant-pharXiv:2610.22983•Oct 19, 2026•0 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

Improved Quantum Algorithms for Rényi Entropies Estimation

Zongxing Xiong, Chengshen Gao, Lvzhou Li

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_α(\mathbf{p})$ for any distribution $\mathbf{p} = (p_i)_{i=1}^n$ given its purified quantum query-access. For non-integer $α> 1$, our algorithm estimates $H_α(\mathbf{p})$ to within additive error $ε$ using only $\widetilde{\mathcal{O}}\big(n^{\max\{1/2,1-1/α\}}/ε\big)$ queries, which improves the best known upper bound for dependence on both $n$ and $1/ε$. For $0<α<1$, our algorithm has query complexity $\widetilde{\mathcal{O}}\big(n^{1/(2α)}/ε^{\max\{1,1/(2α)\}}\big)$, 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 $Ω\big(1/ε^{\max\{1,1/(2α)\}}\big)$ for $0<α<1$, which identifies the optimal precision dependence of our algorithm.

quant-pharXiv:2610.19936•Oct 15, 2026•0 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.

quant-pharXiv:2608.02600•Aug 4, 2026•0 citations

Quantum algorithm for estimating α -Renyi entropies of quantum states

Sathyawageeswar Subramanian, Min-Hsiu Hsieh

We describe a quantum algorithm to estimate the $\ensuremath{\alpha}$-Renyi entropy of an unknown density matrix $\ensuremath{\rho}\ensuremath{\in}{\mathbb{C}}^{d\ifmmode\times\else\texttimes\fi{}d}$ for $\ensuremath{\alpha}\ensuremath{\ne}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 $\ensuremath{\alpha}$-Renyi entropy to additive precision $\ensuremath{\epsilon}$, using an expected total number $O(\frac{1}{{(x\ensuremath{\epsilon})}^{2}})$ of independent applications of a quantum circuit which coherently queries the input unitary $O(\frac{1}{\ensuremath{\delta}}log\frac{d}{\ensuremath{\epsilon}})$ times, in each case measuring a single output qubit. Here $\ensuremath{\delta}$ is a lower cutoff on the smallest eigenvalue of $\ensuremath{\rho}$ and $x=\frac{1}{d}\mathrm{Tr}({\ensuremath{\rho}}^{\ensuremath{\alpha}})$. The expected number of measurements made in this method can be compared to results in the sample complexity model that generally require $\mathrm{\ensuremath{\Theta}}(\frac{{d}^{2}}{{\ensuremath{\epsilon}}^{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$.

arXiv:1908.05251•Physical Review A•Aug 24, 2021•46 citations

Optimal von Neumann Entropy Estimation

Ziyun Chen, Minbo Gao, Qisheng Wang

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.

quant-pharXiv:2608.11151•Aug 12, 2026•0 citations
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γ>1γ>1 of the Shannon entropy of probability distributions and the von Neumann entropy of mixed quantum states. Our main results are: ∙\quad\bullet∙ an O~(n1+η2γ2)\widetilde{\mathcal{O}}\left( n^{\frac{1+η}{2γ^2}}\right)O(n2γ21+η​)-query quantum algorithm that outputs a γγγ-multiplicative approximation of the Shannon entropy H(p)H(\mathbf{p})H(p) of a classical probability distribution p=(p1,…,pn)\mathbf{p} = (p_1,\ldots,p_n)p=(p1​,…,pn​); ∙\quad\bullet∙ an O~(n12+1+η2γ2)\widetilde{\mathcal{O}}\left( n^{\frac12+\frac{1+η}{2γ^2}}\right)O(n21​+2γ21+η​)-query quantum algorithm that outputs a γγγ-multiplicative approximation of the von Neumann entropy S(ρ)S(ρ)S(ρ) of a density matrix ρ∈Cn×nρ\in\mathbb{C}^{n\times n}ρ∈Cn×n. In both cases, the input is assumed to have entropy bounded away from zero by a quantity determined by the parameter η>0η>0η>0, since, as we prove, no polynomial query algorithm can multiplicatively approximate the entropy of distributions with arbitrarily low entropy. In addition, we provide Ω(n13γ2)Ω\left(n^{\frac{1}{3γ^2}}\right)Ω(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.
Estimating statistical properties of probability distributions is a fundamental problem in statistics and theoretical computer science. We develop quantum algorithms for estimating the qqq-Tsallis entropy HqTsa(P)=∑i=1npiq−11−q\mathrm{H}_q^{\mathrm{Tsa}}(P) =\frac{\sum_{i=1}^n p_i^q-1}{1-q}HqTsa​(P)=1−q∑i=1n​piq​−1​ when 0<q<10<q<10<q<1, given purified quantum query access to a distribution PPP on [n][n][n]. When 0<q≤120<q\leq \frac{1}{2}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 12<q<1\frac{1}{2}<q<121​<q<1, we introduce a two-stage simultaneous probability estimation procedure, yielding a quantum algorithm with query complexity O~(n12+12qε12q+n1−qε)\widetilde{O}\left(\frac{n^{\frac12+\frac{1}{2q}}}{\varepsilon^{\frac{1}{2q}}}+\frac{n^{1-q}}{\varepsilon}\right)O(ε2q1​n21​+2q1​​+εn1−q​), which improves the result given by Chen et al. (ICALP 2026) when $\varepsilon=O\rbra{n^{1-2q}}$.
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.
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)H_α(\mathbf{p})Hα​(p) for any distribution p=(pi)i=1n\mathbf{p} = (p_i)_{i=1}^np=(pi​)i=1n​ given its purified quantum query-access. For non-integer α>1α> 1α>1, our algorithm estimates Hα(p)H_α(\mathbf{p})Hα​(p) to within additive error εεε using only O~(nmax⁡{1/2,1−1/α}/ε)\widetilde{\mathcal{O}}\big(n^{\max\{1/2,1-1/α\}}/ε\big)O(nmax{1/2,1−1/α}/ε) queries, which improves the best known upper bound for dependence on both nnn and 1/ε1/ε1/ε. For 0<α<10<α<10<α<1, our algorithm has query complexity O~(n1/(2α)/εmax⁡{1,1/(2α)})\widetilde{\mathcal{O}}\big(n^{1/(2α)}/ε^{\max\{1,1/(2α)\}}\big)O(n1/(2α)/εmax{1,1/(2α)}), which improves the dependence on 1/ε1/ε1/ε of the current best upper bound without incresing its nnn 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α)})Ω\big(1/ε^{\max\{1,1/(2α)\}}\big)Ω(1/εmax{1,1/(2α)}) for 0<α<10<α<10<α<1, which identifies the optimal precision dependence of our algorithm.
We develop a unified framework for analyzing the complexity of quantum property testing through functionals of the form Lφ(ρ)=tr⁡(φ(dρ))/d\mathcal{L}_φ(ρ) = \operatorname{tr}(φ(dρ))/dLφ​(ρ)=tr(φ(dρ))/d, where ρρρ is an unknown ddd-dimensional quantum state and φφφ is a given function. A master theorem is established that derives sample complexity lower bounds for estimating Lφ(ρ)\mathcal{L}_φ(ρ)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 Θ ⁣(d2εlog⁡2(d)max⁡{1,εlog⁡2(d)}+log⁡2(d)ε2), Θ\!\left(\frac{d^2}{\varepsilon\log^2(d)\max\{1, \varepsilon\log^2(d)\}} + \frac{\log^2(d)}{\varepsilon^2}\right), Θ(εlog2(d)max{1,εlog2(d)}d2​+ε2log2(d)​), and the sample complexity of spectrum estimation is Θ ⁣(d2ε2log⁡2(d)max⁡{1,ε2log⁡2(d)}). Θ\!\left(\frac{d^2}{\varepsilon^2\log^2(d)\max\{1, \varepsilon^2\log^2(d)\}}\right). Θ(ε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.
We describe a quantum algorithm to estimate the $\ensuremath{\alpha}$-Renyi entropy of an unknown density matrix $\ensuremath{\rho}\ensuremath{\in}{\mathbb{C}}^{d\ifmmode\times\else\texttimes\fi{}d}$ for $\ensuremath{\alpha}\ensuremath{\ne}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 $\ensuremath{\alpha}$-Renyi entropy to additive precision $\ensuremath{\epsilon}$, using an expected total number $O(\frac{1}{{(x\ensuremath{\epsilon})}^{2}})$ of independent applications of a quantum circuit which coherently queries the input unitary $O(\frac{1}{\ensuremath{\delta}}log\frac{d}{\ensuremath{\epsilon}})$ times, in each case measuring a single output qubit. Here $\ensuremath{\delta}$ is a lower cutoff on the smallest eigenvalue of $\ensuremath{\rho}$ and $x=\frac{1}{d}\mathrm{Tr}({\ensuremath{\rho}}^{\ensuremath{\alpha}})$. The expected number of measurements made in this method can be compared to results in the sample complexity model that generally require $\mathrm{\ensuremath{\Theta}}(\frac{{d}^{2}}{{\ensuremath{\epsilon}}^{2}})$ samples. Furthermore, we also show that multiplicative approximations can be obtained by iteratively using additive approximations, with an overhead logarithmic in the dimension ddd.
We show that the von Neumann entropy of an unknown ddd-dimensional quantum state ρρρ can be estimated to within additive error ε\varepsilonε using Θ ⁣(d2εlog⁡2(d)(1+εlog⁡2(d))+log⁡2(d)ε2) Θ\!\left(\frac{d^2}{\varepsilon\log^2(d)(1+\varepsilon\log^2(d))} + \frac{\log^2(d)}{\varepsilon^2}\right) Θ(εlog2(d)(1+εlog2(d))d2​+ε2log2(d)​) 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.