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.
AI Summary
The paper studies additive estimation of Rényi entropy $H_\alpha(\mathbf p)$ for an unknown distribution on $n$ outcomes, given purified quantum query access, including inverse and controlled preparation oracles. For fixed $\alpha\ne1$, this requires relative estimation of the power sum $P_\alpha=\sum_i p_i^\alpha$, rather than the additive estimation sufficient for Tsallis entropy.
For fixed non-integer $\alpha>1$, it gives query complexity $\widetilde O(n^{\max\{1/2,1-1/\alpha\}}/\epsilon)$, replacing the previous bound $\widetilde O(n^{1-1/(2\alpha)}/\epsilon+\sqrt n/\epsilon^{1+1/(2\alpha)})$. For $0<\alpha<1$, the bound is $\widetilde O(n^{1/(2\alpha)}/\epsilon^{\max\{1,1/(2\alpha)\}})$, improving precision dependence without increasing the dimensional exponent. Tildes suppress polylogarithmic factors, including failure-probability dependence.
The algorithms adapt an existing multilevel estimation framework: geometric probability intervals are isolated using non-destructive singular-value discrimination, local power-function polynomials are implemented through QSVT, and amplitude estimation measures each contribution. Above order one, the analysis exploits a power-sum upper bound; below order one, uniform label initialization avoids negative-power approximation. Geometric search removes the need to know the power-sum scale beforehand.
A two-oracle hybrid argument, perturbing a distribution with one heavy outcome and a uniform light tail, combines with previous results to yield the lower bound $\Omega(n^{1/(2\alpha)-o(1)}+n^{1/(2\alpha)-1/2}/\epsilon^{\max\{1,1/(2\alpha)\}})$ below order one. This matches the precision exponent but leaves a gap in joint dimension–precision dependence. Above order one, dimensional optimality is established only for $1<\alpha<2$ at constant accuracy, up to subpolynomial factors. The results concern query complexity for fixed orders; preparation-oracle construction costs are excluded.
Little sign of AI-generated textUnclear writing
Error found: Algorithm 3 requests polynomial and discriminator precisions outside the invoked lemmas’ domains at sufficiently fine levels, requiring an explicit zero-polynomial/skip rule or equivalent parameter handling.
The α<1 entropy-error proof incorrectly uses α−1 instead of 1−α in its accuracy parameter and absolute-error denominator, although its pseudocode uses the correct sign.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
Comments
Improved Rényi entropy estimator for integer $α$ to be added
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) for any distribution p=(pi)i=1n given its purified quantum query-access. For non-integer α>1, our algorithm estimates Hα(p) to within additive error ε using only O(nmax{1/2,1−1/α}/ε) queries, which improves the best known upper bound for dependence on both n and 1/ε. For 0<α<1, our algorithm has query complexity O(n1/(2α)/εmax{1,1/(2α)}), 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 Ω(1/εmax{1,1/(2α)}) for 0<α<1, which identifies the optimal precision dependence of our algorithm.
The paper studies additive estimation of Rényi entropy Hα(p) for an unknown distribution on n outcomes, given purified quantum query access, including inverse and controlled preparation oracles. For fixed α=1, this requires relative estimation of the power sum Pα=∑ipiα, rather than the additive estimation sufficient for Tsallis entropy.
For fixed non-integer α>1, it gives query complexity O(nmax{1/2,1−1/α}/ϵ), replacing the previous bound O(n1−1/(2α)/ϵ+n/ϵ1+1/(2α)). For 0<α<1, the bound is O(n1/(2α)/ϵmax{1,1/(2α)}), improving precision dependence without increasing the dimensional exponent. Tildes suppress polylogarithmic factors, including failure-probability dependence.
The algorithms adapt an existing multilevel estimation framework: geometric probability intervals are isolated using non-destructive singular-value discrimination, local power-function polynomials are implemented through QSVT, and amplitude estimation measures each contribution. Above order one, the analysis exploits a power-sum upper bound; below order one, uniform label initialization avoids negative-power approximation. Geometric search removes the need to know the power-sum scale beforehand.
A two-oracle hybrid argument, perturbing a distribution with one heavy outcome and a uniform light tail, combines with previous results to yield the lower bound Ω(n1/(2α)−o(1)+n1/(2α)−1/2/ϵmax{1,1/(2α)}) below order one. This matches the precision exponent but leaves a gap in joint dimension–precision dependence. Above order one, dimensional optimality is established only for 1<α<2 at constant accuracy, up to subpolynomial factors. The results concern query complexity for fixed orders; preparation-oracle construction costs are excluded.
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 HqTsa(P)=1−q∑i=1npiq−1 when 0<q<1, given purified quantum query access to a distribution P on [n]. When 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 21<q<1, we introduce a two-stage simultaneous probability estimation procedure, yielding a quantum algorithm with query complexity O(ε2q1n21+2q1+εn1−q), which improves the result given by Chen et al. (ICALP 2026) when $\varepsilon=O\rbra{n^{1-2q}}$.
Estimation of Shannon and Rényi entropies of unknown discrete distributions is a fundamental problem in statistical property testing. In this paper, we give the first quantum algorithms for estimating α-Rényi entropies (Shannon entropy being 1-Rényi entropy). In particular, we demonstrate a quadratic quantum speedup for Shannon entropy estimation and a generic quantum speedup for α-Rényi entropy estimation for all α ≥ 0 values, including tight bounds for the Shannon entropy, the Hartley entropy (α = 0), and the collision entropy (α = 2). We also provide quantum upper bounds for estimating min-entropy (α = +∞) as well as the Kullback-Leibler divergence. We complement our results with quantum lower bounds on α-Rényi entropy estimation for all α ≥ 0 values. Our approach is inspired by the pioneering work of Bravyi, Harrow, and Hassidim (BHH); however, with many new technical ingredients: 1) we improve the error dependence of the BHH framework by a fine-tuned error analysis together with Montanaro's approach to estimating the expected output of quantum subroutines for α = 0, 1; 2) we develop a procedure, similar to cooling schedules in simulated annealing, for general α ≥ 0, and 3) in the cases of integer α ≥ 2 and α = +∞, we reduce the entropy estimation problem to the α-distinctness and [log n]-distinctness problems, respectively.
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 ε, rank upper bound R, and fixed order α. Tsallis entropy estimation has near-optimal rank-independent query complexity O(ε−1/(α−1)) for 1<α<2, when the allowed dimension and rank accommodate the lower-bound instances, and O(1/ε) for α≥2, where O suppresses logarithmic factors. The first saves a factor 1/ε; the second extends known integer-order scaling to noninteger orders. We also improve the von Neumann entropy bound from O(R/ε2) to O(R/ε) and obtain O(R/ε) 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 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) of a discrete distribution (pi)i=1n. We partition the values pi into logarithmically many intervals whose length decays exponentially. For each interval, we perform non-destructive singular value discrimination to isolate the relevant pi, 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 Θ~(1/εmax{1/(2(q−1)),1}), improving the prior best O(1/ε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 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 q-entropy for non-integer q.
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.
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 ε,
1. For 0<α<1, the sample complexity is O(d1+1/α/ε1/α+d1/α−1/ε2) for Rényi entropy and O(d1+1/α/ε1/α+d2−2α/ε2) for Tsallis entropy. In particular, for 0<α≤1/2, the sample complexity for both entropies is O(d1+1/α/ε1/α).
2. For non-integer α>1, the sample complexity is 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).