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:2610.19936

Improved Quantum Algorithms for Rényi Entropies Estimation

Zongxing Xiong, Chengshen Gao, Lvzhou Li

quant-phSubmitted Oct 14, 2026• Announced Oct 15, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

Comments
Improved Rényi entropy estimator for integer $α$ to be added

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

A Quantum Algorithm Framework for Discrete Probability Distributions With Applications to Rényi Entropy Estimation

Xinzhao Wang, Shengyu Zhang, Tongyang Li

Estimating statistical properties is fundamental in statistics and computer science. In this paper, we propose a unified quantum algorithm framework for estimating properties of discrete probability distributions, with estimating Rényi entropies as specific examples. In particular, given a quantum oracle that prepares ann-dimensional quantum state Σni=1√pi|i⟩, for α > 1 and 0Hα(p) to within additive error ϵ with probability at least 2/3 using Õ(n1-1/2α/ϵ + √n/ϵ1+ 1/2α) and Õ(n1/2α/ϵ1+ 1/2α) queries, respectively. This improves the best known dependence in ϵ as well as the joint dependence betweennand 1/ϵ. Technically, our quantum algorithms combine quantum singular value transformation, quantum annealing, and variable-time amplitude estimation. We believe that our algorithm framework is of general interest and has wide applications.

arXiv:2212.01571•IEEE Transactions on Information Theory•Mar 26, 2024•7 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

Quantum Multi-Level Estimation of Functionals of Discrete Distributions

Kean Chen, Minbo Gao, Tongyang Li +2 more

We propose a quantum multi-level estimation framework for a functional $\sum_{i=1}^n f(p_i)$ of a discrete distribution $(p_i)_{i=1}^n$. We partition the values $p_i$ into logarithmically many intervals whose length decays exponentially. For each interval, we perform non-destructive singular value discrimination to isolate the relevant $p_i$, enabling adaptive estimation of the partial sum over this interval. Unlike previous variable-time approaches, our method avoids high control overhead and requires only constant extra ancilla qubits. As an application, we present efficient quantum estimators for the $q$-Tsallis entropy of discrete distributions. Specifically: (i) For $q > 1$, we obtain a near-optimal quantum algorithm with query complexity $\tildeΘ(1/\varepsilon^{\max\{1/(2(q-1)), 1\}})$, improving the prior best $O(1/\varepsilon^{1+1/(q-1)})$ due to Liu and Wang (SODA 2025; IEEE Trans. Inf. Theory 2026). (ii) For $0 < q < 1$, we obtain a quantum algorithm with query complexity $\tilde{O}(n^{1/q-1/2}/\varepsilon^{1/q})$, exhibiting a quantum speedup over the near-optimal classical estimators due to Jiao, Venkat, Han, and Weissman (IEEE Trans. Inf. Theory 2017). Our results achieve, to our knowledge, the first near-optimal quantum estimators for parameterized $q$-entropy for non-integer $q$.

quant-pharXiv:2605.03685•Leibniz international proceedings in informatics•May 6, 2026•0 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•0 citations

Towards Optimal Quantum Estimators for State Frame Potential

Jinge Bao, Wang Fang, Yoshifumi Nakata +1 more

The state frame potential is a standard diagnostic of how closely a quantum state ensemble approximates Haar randomness. In this work, we study the problem of estimating the state frame potential of order $t$ to within additive error $\varepsilon$ under three progressively weaker access models: (i) query access to a multi-state-preparation oracle, (ii) general sample access, and (iii) single-copy sample access. In the query model, we establish a near-optimal query complexity of $\widetildeΘ(\sqrt{t}/\varepsilon)$, yielding a quadratic improvement in the dependence on $t$ over the previous best result of Nakata, Takeuchi, Kliesch, and Darmawan (PRX Quantum 2025). In the general sample model, we establish the optimal sample complexity $Θ(t/\varepsilon^2)$. In the single-copy sample model, we present a store-and-estimate approach whose sample complexity depends on the Rényi entropy of the ensemble weights. As an application, we use the single-copy algorithm to assess the randomness of projected state ensembles, where the entropy term becomes the observational Rényi entropy associated with measuring one subsystem.

quant-pharXiv:2608.24711•Aug 26, 2026•0 citations
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.
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}}$.
Estimating statistical properties is fundamental in statistics and computer science. In this paper, we propose a unified quantum algorithm framework for estimating properties of discrete probability distributions, with estimating Rényi entropies as specific examples. In particular, given a quantum oracle that prepares ann-dimensional quantum state Σni=1√pi|i⟩, for α > 1 and 0Hα(p) to within additive error ϵ with probability at least 2/3 using Õ(n1-1/2α/ϵ + √n/ϵ1+ 1/2α) and Õ(n1/2α/ϵ1+ 1/2α) queries, respectively. This improves the best known dependence in ϵ as well as the joint dependence betweennand 1/ϵ. Technically, our quantum algorithms combine quantum singular value transformation, quantum annealing, and variable-time amplitude estimation. We believe that our algorithm framework is of general interest and has wide applications.
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.
We propose a quantum multi-level estimation framework for a functional ∑i=1nf(pi)\sum_{i=1}^n f(p_i)∑i=1n​f(pi​) of a discrete distribution (pi)i=1n(p_i)_{i=1}^n(pi​)i=1n​. We partition the values pip_ipi​ into logarithmically many intervals whose length decays exponentially. For each interval, we perform non-destructive singular value discrimination to isolate the relevant pip_ipi​, enabling adaptive estimation of the partial sum over this interval. Unlike previous variable-time approaches, our method avoids high control overhead and requires only constant extra ancilla qubits. As an application, we present efficient quantum estimators for the qqq-Tsallis entropy of discrete distributions. Specifically: (i) For q>1q > 1q>1, we obtain a near-optimal quantum algorithm with query complexity Θ~(1/εmax⁡{1/(2(q−1)),1})\tildeΘ(1/\varepsilon^{\max\{1/(2(q-1)), 1\}})Θ~(1/εmax{1/(2(q−1)),1}), improving the prior best O(1/ε1+1/(q−1))O(1/\varepsilon^{1+1/(q-1)})O(1/ε1+1/(q−1)) due to Liu and Wang (SODA 2025; IEEE Trans. Inf. Theory 2026). (ii) For 0<q<10 < q < 10<q<1, we obtain a quantum algorithm with query complexity O~(n1/q−1/2/ε1/q)\tilde{O}(n^{1/q-1/2}/\varepsilon^{1/q})O~(n1/q−1/2/ε1/q), exhibiting a quantum speedup over the near-optimal classical estimators due to Jiao, Venkat, Han, and Weissman (IEEE Trans. Inf. Theory 2017). Our results achieve, to our knowledge, the first near-optimal quantum estimators for parameterized qqq-entropy for non-integer qqq.
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 state frame potential is a standard diagnostic of how closely a quantum state ensemble approximates Haar randomness. In this work, we study the problem of estimating the state frame potential of order ttt to within additive error ε\varepsilonε under three progressively weaker access models: (i) query access to a multi-state-preparation oracle, (ii) general sample access, and (iii) single-copy sample access. In the query model, we establish a near-optimal query complexity of Θ~(t/ε)\widetildeΘ(\sqrt{t}/\varepsilon)Θ(t​/ε), yielding a quadratic improvement in the dependence on ttt over the previous best result of Nakata, Takeuchi, Kliesch, and Darmawan (PRX Quantum 2025). In the general sample model, we establish the optimal sample complexity Θ(t/ε2)Θ(t/\varepsilon^2)Θ(t/ε2). In the single-copy sample model, we present a store-and-estimate approach whose sample complexity depends on the Rényi entropy of the ensemble weights. As an application, we use the single-copy algorithm to assess the randomness of projected state ensembles, where the entropy term becomes the observational Rényi entropy associated with measuring one subsystem.