CS Paper Radar

Nearly Sample-Optimal Estimators for Quantum Rényi and Tsallis Entropies

Kean Chen, Qisheng Wang

cs.IT quant-ph ·submitted 2026-08-18 17:56 UTC · v1

Abstract

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

Comment
32 pages, 1 table, 4 algorithms

Closest papers

Nearest neighbours by meaning across the whole index.

Settling the Sample Complexity of Rényi Entropy Estimation

cs.IT cs.DSmath.ST ·2026-10-07 ·Qisheng Wang
theory similarity 0.83
Abstract · 23 pages, 1 table

Rényi entropy estimation has been comprehensively investigated by Acharya, Orlitsky, Suresh and Tyagi (SODA 2015; IEEE Trans. Inf. Theory 2017) and consequent works, whereas only the sample complexity of Rényi entropy estimation of integer order has been settled. In this paper, we settle the sample complexity of Rényi entropy estimation of noninteger order, thereby completing the complexity picture of Rényi entropy estimation. Specifically, we show that for any noninteger $α> 0$, it is sufficient and necessary to use \[ Θ\!\left(\frac{d^{\max\{1/α,1\}}}{\varepsilon^{1/α}\log(d)} + \frac{d^{|1-1/α|}}{\varepsilon^2}\right) \] samples to estimate the Rényi entropy of order $α$ of an unknown discrete distribution over an alphabet of size $d$ to within additive error $\varepsilon$. For the upper bound, we reduce the bias using a refined polynomial approximation estimator for large probabilities. For the lower bound, we employ a different hard instance equipped with a new moment matching construction. The constructive moment matching has constant bounded high-order moments, while attaining a fixed ratio between the $α$-th moments, which is of independent interest.

0.20

Optimal Min-Entropy Estimation with High Probability

cs.IT math.STquant-ph ·2026-11-17 ·Qisheng Wang
similarity 0.73
Abstract · 9 pages

Min-entropy plays a fundamental role in assessing the unpredictability of randomness sources. In particular, NIST SP 800-90B specifies min-entropy estimation as a key procedure for entropy sources used in cryptographic random bit generators, illustrating the practical importance of reliable min-entropy estimation. In this paper, we settle the sample complexity of min-entropy estimation with high probability in both the classical and quantum cases. Specifically, for min-entropy estimation with additive error $\varepsilon$ and probability at least $1-δ$, the sample complexity is $Θ(d\log(d/δ)/\varepsilon^2)$ for classical distributions on $d$ symbols and $Θ((d^2+d\log(1/δ))/\varepsilon^2)$ for quantum states on a $d$-dimensional Hilbert space. Our results admit short and simple proofs.

0.38

Optimal Rényi and Logarithmic Additive Functional Entropy Estimation

cs.IT cs.CCeess.SPmath.ST ·2026-10-20 ·Arman Adibi, Piotr Krysta
theory similarity 0.72
Abstract

We characterize the minimax sample complexity of estimating Rényi entropy from independent samples on an alphabet of size at most $k$, when the known order $α>1$ may vary with $k$. For every fixed additive accuracy $\varepsilon\in(0,1/2)$ and success probability $2/3$, we prove matching bounds with constants independent of $k$ and $α$. For $1<α<\log k$, the rate is $Θ_\varepsilon(αk^{1-1/α}X_α(k,\varepsilon))$, where a monotone scalar inequality defines $X_α$ at noninteger orders. The bounds remain uniform as the order approaches one or an integer, or grows with the alphabet. Integer orders below $\log k$ have rate $Θ_\varepsilon(αk^{1-1/α})$; orders at least $\log k$ and min-entropy have rate $Θ_\varepsilon(k\log k)$. We extend the analysis to logarithms of positive additive functionals. For every fixed continuous $f$ satisfying $f(0)=0$, $f(x)>0$ for $x>0$, and $f(x)\sim ax^r$ at zero, with $a>0$ and $r>1$, estimating $-β^{-1}\log\sum_i f(p_i)$ at fixed accuracy, for fixed $β>0$, has sample complexity $Θ(k^{1-1/r})$ for integer $r$ and $Θ(k/\log k)$ otherwise. A replication reduction preserves the sampling experiment and transfers the rates for powers. Smooth flat functions show that regularity alone does not determine the complexity. The upper bound combines polynomial approximation, Gamma count statistics, and an independent pilot, with a global affine correction near order one. The lower bound uses interpolation to construct positive mean-one priors and controls their distinguishability and entropy separation after normalization. Exact count-variance identities and weighted approximation duality connect the two arguments.

0.17

Matrix Samplers and Quantum-Proof Extractors: Their Correspondence and Almost-Optimal Constructions

cs.CC quant-ph ·2026-10-27 ·Kuan Cheng, Ruiyang Wu
similarity 0.65
Abstract

We establish an equivalence between matrix samplers and quantum-proof randomness extractors. The classical sampler-extractor equivalence is established by a seminal work of Zuckerman (Random Structures & Algorithms, 1997). Using this equivalence, we construct explicit strong matrix samplers with optimal randomness overhead and near-optimal sample complexity via constructing quantum-proof extractors. Specifically for matrix dimension $D$, accuracy $\varepsilon$ and failure probability $δ\leq\varepsilon$, our matrix sampler uses $$ m+O_α(\log(D/δ))\text{ random bits and } O_α\!\left(\varepsilon^{-2-α}\log^{1+α}(D/δ)\right)\text{ samples}, $$ for any constant $α>0$. Compared with the matrix sampler of Xun and Zuckerman (CCC 2025), our construction has improvements in two aspects. Under optimal random seed length, we can replace the $\operatorname{poly} D$ dependence in the number of samples by $O(\log^{1+α} D)$. Under the same scale of sample size, we can remove their $\log\log D$ factor in the length of the random seed. Our underlying strong quantum-proof extractor has output length $n-O_α(a+\log(1/η))$ and seed length at most $(1+α)\log a+(2+α)\log(1/η)+O_α(1)$ for $n$-bit sources with conditional min-entropy $n-a$ and error $η$. We also obtain strong quantum-proof extractors for every constant entropy rate, for any error as small as $2^{-Ω(n)}$, having optimal seed length $O(\log(n/η))$ and output length $Ω(n)$, improving previous constructions.

0.09

Optimal von Neumann Entropy Estimation

cs.IT quant-ph ·2026-08-11 ·Ziyun Chen, Minbo Gao, Qisheng Wang
theoryhighly cited similarity 0.62
Abstract · 22 pages, 1 table, 1 algorithm. Improved the sample complexity to optimal

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.

0.49

Finite attainment and efficient computation of regularized quantum channel relative entropy

cs.IT quant-ph ·2026-11-02 ·Yiwei Xu, Kun Fang
similarity 0.62
Abstract · comments are welcome

Quantum channel relative entropy can be nonadditive, making its regularization essential for asymptotic analysis. We study when the regularized value is attained at finite blocklength and how efficiently it can be approximated. For the first question, we establish a sharp dichotomy: the regularized value is either attained already at the single-copy level, implying additivity at every blocklength, or is never attained at any finite blocklength. Notably, a simple two-copy additivity test distinguishes between these alternatives for qubit channels and for channel pairs in arbitrary dimensions admitting an interior optimizer. We further show that both the interiority condition and finite nonattainment are generic, holding for almost every channel pair. For the second question, we establish explicit convergence rates for approximating the regularized channel relative entropy. For fixed channel dimensions, $\widetilde O(\varepsilon^{-3/2})$ channel copies suffice to approximate the regularized value to additive accuracy $\varepsilon$. Alternatively, a semidefinite hierarchy achieves the same accuracy at level $\widetilde O(\varepsilon^{-2})$, yielding a certified polynomial-time approximation. Together, these results reveal the intriguing structure and generic behavior of regularized channel relative entropy, sharpening our understanding of both its analytical and computational aspects.

0.21

Information Complexity of Inner Product and Matrix Multiplication via Shannon-to-Min-Entropy Conversion

cs.IT cs.CC ·2026-11-02 ·Xiaohong Cai, Mingyang Zhu
theoryhot direction similarity 0.61
Abstract · 38 pages, including appendices

We determine the information complexity of matrix multiplication over finite fields under independent uniform inputs, up to a universal additive constant. The binary inner-product case resolves the open question of Braverman, Garg, Pankratov, and Weinstein on the optimal dependence of information complexity on the error probability. For inputs in $\mathbb F_2^m$ and error at most $\varepsilon\in[0,1/2]$, the information complexity with output at Bob lies between $(1-2\varepsilon)m-c_0$ and $(1-2\varepsilon)m$, where $c_0<4.772$ is a universal constant. For independent uniform matrices $X\in\mathbb F_q^{t\times m}$ and $Y\in\mathbb F_q^{s\times m}$, where $t\le s$, computing $XY^{\mathsf T}$ with output at Bob and error at most $\varepsilon\in[0,1]$ has information complexity $(1-q^{ts}\varepsilon/(q^{ts}-1))^+mt\log_2q$, up to an additive gap of less than $9.544$ bits. This gap is independent of the matrix dimensions, field size, and error. At zero error, the information complexity is exactly $mt\log_2q$. The information lower bounds for both inner product and matrix multiplication follow from a new Shannon-to-min-entropy theorem for convolution on discrete groups. Let $Q_1,\ldots,Q_k$ be the finitely supported distributions of independent random variables taking values in a discrete group, and let $s$ be the largest support size. We show that if $k\ge\lceil\lfloor\log_2s\rfloor\ln2\rceil$, then the min-entropy of their ordered product is at least the average Shannon entropy of the $Q_i$ minus $c_0$ bits. This holds for arbitrary discrete groups, including infinite and noncommutative groups, even when the input distributions differ. The leading coefficient of the logarithmic threshold is optimal.

0.38

Optimal spectrum estimation

cs.CC quant-phcs.DS ·2026-09-24 ·Ainesh Bakshi, Apoorv Vikram Singh, Xinyu Tan
theoryhighly cited similarity 0.61
Abstract · 37 pages

We prove that the spectrum of an unknown $d$-dimensional quantum state can be estimated to error $\varepsilon$ in total variation distance using \[ O\!\left(d^2\min\left\{ \frac{1}{(\varepsilon\log d)^4},\; \frac{1}{(\varepsilon\log d)^2} \right\}\right) \] copies. This matches the recent lower bound of Wang. When restricted to unentangled measurements, we give an algorithm with an additional factor of $d$ in copy complexity, which we conjecture to be optimal. We develop a framework for recovering the small eigenvalues of a quantum state by matching Chebyshev moments. We bound the variance of each Chebyshev moment estimate in terms of scalar derivatives of the corresponding polynomial, using classical and quantum Efron--Stein decompositions. Different rescalings of the Chebyshev polynomials balance approximation error and variance, yielding two regimes in our copy complexity bound.

0.35