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

• URL: http://arxiv.org/abs/2608.18070v1
• Date: Tue, 18 Aug 2026 17:56:22 GMT
• Title: Nearly Sample-Optimal Estimators for Quantum Rényi and Tsallis Entropies
• Abstract summary: We provide estimators for quantum Rényi and Tsallis entropies with nearly optimal sample complexity.<n>For $0 1$, the sample complexity is $O(d1+1//varepsilon1/ + d1/-1/varepsilon2)$ for Rényi entropy and $O(d1+1//varepsilon1/)$ for Tsallis entropy.
• Score: 14.968127458030251
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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).

Related papers

• Tight Sample Bounds for Renyi and Min-Entropy Estimation [4.866431869728017]
  Estimating entropy from samples is fundamental in information theory and property testing.<n>We prove that min-entropy estimation to constant additive accuracy has sample complexity $(klog k)$.
  arXiv  Detail & Related papers  (2026-07-18T21:01:38Z)
• Computational hardness of estimating quantum entropies via binary entropy bounds [0.2538209532048867]
  We investigate the computational hardness of estimating the quantum $$-Rényi entropy $rm Stt T_q()$.<n>We establish that for all positive real orders, the rank-$2$ variants Rank2RényiQEA$_$ and Rank2TsallisQEA$_q$ are $sf BQP$-hard.<n>Our results stem from reductions based on new inequalities relating $$-Rényi or $q$-Tsallis binary entropies of different orders.
  arXiv  Detail & Related papers  (2026-01-07T09:25:07Z)
• Inverse-free quantum state estimation with Heisenberg scaling [4.191671741497842]
  We present an inverse-free pure quantum state estimation protocol that achieves Heisenberg scaling.<n>Our result implies a query upper bound $O(mind3/2/varepsilon,1/varepsilon2)$ for inverse-free amplitude estimation.
  arXiv  Detail & Related papers  (2025-10-29T17:48:46Z)
• Information-Theoretic Lower Bounds for Approximating Monomials via Optimal Quantum Tsallis Entropy Estimation [13.491187998442596]
  This paper reveals a conceptually new connection from information theory to approximation theory via quantum algorithms for entropy estimation.<n>We provide an information-theoretic lower bound $Omega(sqrtn)$ on the approximate degree of the monomial $xn$, compared to the analytic lower bounds shown in Newman and Rivlin.<n>This is the first quantum entropy estimator with optimal query complexity (up to polylogarithmic factors) for all parameters simultaneously.
  arXiv  Detail & Related papers  (2025-09-03T17:25:28Z)
• Improved Sample Upper and Lower Bounds for Trace Estimation of Quantum State Powers [9.136389487369117]
  We significantly improve the sample complexity of estimating $operatornametr(rhoq)$ in both the upper and lower bounds.<n>Our upper bounds are obtained by (non-plug-in) quantum estimators based on weak Schur sampling.
  arXiv  Detail & Related papers  (2025-05-14T17:06:33Z)
• Coresets for Multiple $\ell_p$ Regression [47.790126028106734]
  We construct coresets of size $tilde O(varepsilon-2d)$ for $p2$ and $tilde O(varepsilon-pdp/2)$ for $p>2$. For $1p2$, every matrix has a subset of $tilde O(varepsilon-1k)$ rows which spans a $(varepsilon-1k)$-approximately optimal $k$-dimensional subspace for $ell_p$ subspace approximation
  arXiv  Detail & Related papers  (2024-06-04T15:50:42Z)
• Optimal bounds for $\ell_p$ sensitivity sampling via $\ell_2$ augmentation [56.403488578703865]
  We show that by augmenting the $ell_p$ sensitivities by $ell$ sensitivities, we obtain better bounds on optimal linear $tilde O(varepsilon-2mu2 d)$ sampling complexity. We also obtain an $tilde O(varepsilon-2mu2 d)$ sensitivity sampling bound for logistic regression.
  arXiv  Detail & Related papers  (2024-06-01T07:03:40Z)
• Efficient Sampling of Stochastic Differential Equations with Positive Semi-Definite Models [91.22420505636006]
  This paper deals with the problem of efficient sampling from a differential equation, given the drift function and the diffusion matrix. It is possible to obtain independent and identically distributed (i.i.d.) samples at precision $varepsilon$ with a cost that is $m2 d log (1/varepsilon)$ Our results suggest that as the true solution gets smoother, we can circumvent the curse of dimensionality without requiring any sort of convexity.
  arXiv  Detail & Related papers  (2023-03-30T02:50:49Z)
• Fast Rates for Maximum Entropy Exploration [52.946307632704645]
  We address the challenge of exploration in reinforcement learning (RL) when the agent operates in an unknown environment with sparse or no rewards. We study the maximum entropy exploration problem two different types. For visitation entropy, we propose a game-theoretic algorithm that has $widetildemathcalO(H3S2A/varepsilon2)$ sample complexity. For the trajectory entropy, we propose a simple algorithm that has a sample of complexity of order $widetildemathcalO(mathrmpoly(S,
  arXiv  Detail & Related papers  (2023-03-14T16:51:14Z)
• Estimation of Entropy in Constant Space with Improved Sample Complexity [14.718968517824756]
  We give a new constant memory scheme that reduces the sample complexity to $(k/epsilon2)cdot textpolylog (1/epsilon)$. We conjecture that this is optimal up to $textpolylog (1/epsilon)$ factors.
  arXiv  Detail & Related papers  (2022-05-19T18:51:28Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
  arXiv  Detail & Related papers  (2022-03-17T23:52:08Z)
• Learning low-degree functions from a logarithmic number of random queries [77.34726150561087]
  We prove that for any integer $ninmathbbN$, $din1,ldots,n$ and any $varepsilon,deltain(0,1)$, a bounded function $f:-1,1nto[-1,1]$ of degree at most $d$ can be learned.
  arXiv  Detail & Related papers  (2021-09-21T13:19:04Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.