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:2605.03685 · Leibniz international proceedings in informatics

Quantum Multi-Level Estimation of Functionals of Discrete Distributions

Kean Chen, Minbo Gao, Tongyang Li, Qisheng Wang, Xinzhao Wang

quant-phcs.CCcs.DScs.ITSubmitted May 5, 2026• Announced May 6, 2026• 0 citations
arXivHTMLPDF

Abstract

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

Journal reference
Proceedings of the 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026), 58:1-58:23, 2026
DOI
10.4230/LIPIcs.ICALP.2026.58
Comments
32 pages

Related papers

Towards Minimax Estimation of High-Order Functionals by Quantum Arguments

Qisheng Wang

We propose a novel approach to the minimax estimation of high-order functionals from the perspective of quantum computing. Specifically, for any real number $α\gg 1$, we present two estimators, one for the classical functional $\mathrm{F}_α(P) = \sum_{i=1}^S p_i^α$ of a discrete distribution $P$ and the other for the quantum functional $\mathrm{F}_α(ρ) = \operatorname{tr}(ρ^α)$ of a mixed state $ρ$. These functionals have close connections with the Rényi entropy and the Tsallis entropy. We show that both estimators achieve the minimax optimal $L_2$ rate $α\mathsf{n}^{-1}$ in the range $α\lesssim \mathsf{n} \lesssim α^{3-o(1)}$, where the support size $S$ of $P$ or the dimension of $ρ$ can be much larger than the number of samples $\mathsf{n}$. As a result, both estimators achieve the \textit{optimal} sample complexity $\mathsf{n} \asymp α$, improving upon the prior best upper bounds $O(α^2)$ established by Jiao, Venkat, Han, and Weissman (IEEE Trans. Inf. Theory 2017) for classical functionals and Chen and Wang (COLT 2025) for quantum functionals. Our estimators are constructed under a unified framework using quantum primitives and run in linear time on a quantum computer. This work reveals an unexpected path from quantum computing to statistics, suggesting a conceptually new methodology for functional estimation. It adds to the growing list of quantum proofs for classical theorems.

quant-pharXiv:2607.07540•Jul 9, 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

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

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

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.

quant-pharXiv:2601.03734•Leibniz international proceedings in informatics•Jan 8, 2026•0 citations
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.
We propose a novel approach to the minimax estimation of high-order functionals from the perspective of quantum computing. Specifically, for any real number α≫1α\gg 1α≫1, we present two estimators, one for the classical functional Fα(P)=∑i=1Spiα\mathrm{F}_α(P) = \sum_{i=1}^S p_i^αFα​(P)=∑i=1S​piα​ of a discrete distribution PPP and the other for the quantum functional Fα(ρ)=tr⁡(ρα)\mathrm{F}_α(ρ) = \operatorname{tr}(ρ^α)Fα​(ρ)=tr(ρα) of a mixed state ρρρ. These functionals have close connections with the Rényi entropy and the Tsallis entropy. We show that both estimators achieve the minimax optimal L2L_2L2​ rate αn−1α\mathsf{n}^{-1}αn−1 in the range α≲n≲α3−o(1)α\lesssim \mathsf{n} \lesssim α^{3-o(1)}α≲n≲α3−o(1), where the support size SSS of PPP or the dimension of ρρρ can be much larger than the number of samples n\mathsf{n}n. As a result, both estimators achieve the \textit{optimal} sample complexity n≍α\mathsf{n} \asymp αn≍α, improving upon the prior best upper bounds O(α2)O(α^2)O(α2) established by Jiao, Venkat, Han, and Weissman (IEEE Trans. Inf. Theory 2017) for classical functionals and Chen and Wang (COLT 2025) for quantum functionals. Our estimators are constructed under a unified framework using quantum primitives and run in linear time on a quantum computer. This work reveals an unexpected path from quantum computing to statistics, suggesting a conceptually new methodology for functional estimation. It adds to the growing list of quantum proofs for classical theorems.
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.
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.
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}}$.
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).
We investigate the computational hardness of estimating the quantum ααα-Rényi entropy SαR(ρ)=ln⁡Tr(ρα)1−α{\rm S}^{\tt R}_α(ρ) = \frac{\ln {\rm Tr}(ρ^α)}{1-α}SαR​(ρ)=1−αlnTr(ρα)​ and the quantum qqq-Tsallis entropy SqT(ρ)=1−Tr(ρq)q−1{\rm S}^{\tt T}_q(ρ) = \frac{1-{\rm Tr}(ρ^q)}{q-1}SqT​(ρ)=q−11−Tr(ρq)​, both of which converge to the von Neumann entropy as the order approaches 111. The promise problems Quantum ααα-Rényi Entropy Approximation (RényiQEAα_αα​) and Quantum qqq-Tsallis Entropy Approximation (TsallisQEAq_qq​) ask whether $ {\rm S}^ {\tt R}_α(ρ)$ or SqT(ρ){\rm S}^{\tt T}_q(ρ)SqT​(ρ), is at least τ1τ_1τ1​ or at most τ2τ_2τ2​, where τ1−τ2τ_1 - τ_2τ1​−τ2​ is typically a positive constant. Previous hardness results cover only the von Neumann entropy (order 111) and some cases of the quantum qqq-Tsallis entropy, while existing approaches do not readily extend to other orders. We establish that for all positive real ααα and qqq, and also for α=∞α=\inftyα=∞, the rank-222 variants Rank2RényiQEAα_αα​ and Rank2TsallisQEAq_qq​ 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α> 0α>0 or α=∞α=\inftyα=∞, and for all real orders 0<q≤10 < q \leq 10<q≤1, LowRankRényiQEAα_αα​ and LowRankTsallisQEAq_qq​ are BQP-complete, where both are restricted versions of RényiQEAα_αα​ and TsallisQEAq_qq​ with ρρρ of polynomial rank. - For all real order q>1q>1q>1, TsallisQEAq_qq​ is BQP-complete. Our hardness results stem from reductions based on new inequalities relating the ααα-Rényi or qqq-Tsallis binary entropies of different orders. These reductions differ substantially from previous approaches, and the inequalities are of independent interest.