We study estimation of the trace polynomial $\operatorname{tr} p(P\rho P)$ from global classical shadows, where $\rho$ is an unknown quantum state and $P$ is a fixed projector. Disjoint batching and complete U-statistics yield unbiased estimators of the same trace moments, but assign different sample-size factors to the degenerate terms in their Hoeffding decompositions. Under the global Clifford protocol, exact degree-two variance formulas show that, on a null projected block of rank $s$, the quadratic degenerate term has order $s^2/N$ under batching and $s^2/N^2$ under complete symmetrization. For a logarithmic-degree polynomial used in entropy approximation, the quadratic coefficient raises the batched variance to at least order $s^2N\log^2N$ at the classical entropy cutoff. For complete U-statistics, we derive a cross-degree covariance identity and an exact variance decomposition for polynomial estimators. We also bound every Hoeffding order at a fixed degree and obtain a growing-dimensional risk bound for a small-spectrum entropy functional. The higher-order bounds retain a polynomial dependence on the ambient dimension and therefore do not cover logarithmically increasing degrees. Monte Carlo experiments confirm the degree-two formulas, and exact calculations illustrate the entropy risks.
We provide limit theory for the trace of the squared sample correlation matrix $\mathbf R$, constructed from $n$ observations of a $p$-dimensional random vector with iid components. If the entries have finite fourth moment and $p$ and $n$ grow proportionally, it is known that $\operatorname{tr}({\mathbf R}^2)$ satisfies a central limit theorem (CLT) and the centering and scaling sequences are universal in the sense that they do not depend on the entry distribution. Under symmetry and regular variation assumption with index $\alpha$ and any growth rate of the dimension, we prove that the universal CLT remains valid for $\alpha>3$. For $\alpha<3$, we identify a critical dimension growth at which the fluctuations of $\operatorname{tr}({\mathbf R}^2)$ become non-Gaussian. Moreover, if the dimension $p$ grows faster and $\alpha\le 3$ we establish a non-universal CLT with norming sequences depending on the value of $\alpha$. Our findings are illustrated in a simulation study.
Let $\widehat R$ be the Pearson sample correlation matrix formed from $n$ independent Gaussian observations in $p$ dimensions, and write $m=n-1\ge p$. Under the null correlation $R=I_p$, the classical independent beta product, exact cumulants, and full Fourier inversion yield, along every sequence $p\to\infty$ with $m\ge p$, a uniform first Edgeworth expansion for $\log\det\widehat R$, centered by its exact mean and scaled by its exact standard deviation. The expansion identifies the exact finite dimensional skewness correction and gives the sharp Kolmogorov equivalent $A_{m,p}/\{6\sqrt{2\pi}V_{m,p}^{3/2}\}$, where $V_{m,p}$ is the exact variance and $A_{m,p}$ is the absolute third cumulant. This equivalent unifies the square, fixed gap, growing gap, proportional, and dilute regimes; in the square regime the error has order $(\log p)^{-3/2}$ with an exact constant. For every positive definite population correlation matrix $R$, we prove a uniform finite sample Berry-Esseen bound that explicitly tracks population dependence. All theoretical results have exact or proved equivalent Lean 4 formulations whose declarations and dependencies are kernel checked.
We study the sample complexity of estimating and testing fundamental unitarily invariant properties of unknown quantum states; namely, the tasks of spectrum estimation, von Neumann entropy estimation, and rank-testing. For $d$-dimensional states, and for every $\gamma>0$, we prove a sample complexity lower bound of $\Omega(d^{2-\gamma})$ for spectrum estimation to constant sorted total-variation error, entropy estimation to constant additive error, and rank-testing to constant trace distance. Our hard instances are constructed from sandwiched products of Haar-random projectors, suitably normalized using a novel technique that lets us derive explicit expressions for high-order tensor moments of the resultant states. These moments can be expressed as symmetric functions of Jucys--Murphy elements of the symmetric group algebra. To show that two such mixtures are indistinguishable, we analyze the log-likelihood ratio and perform moment-matching, i.e., we set its low-order Jucys--Murphy components to zero. Indistinguishability is then obtained by bounding an $f$-divergence through the high-order components; the non-zero high-order terms and concentration of functions of Haar-random unitaries also imply separations in typical spectra, entropies, and ranks, proving all our lower bounds.
Marco Fanizza, R. O'Donnell, Chirag Wadhwa· 3 citations
Exhaustive moment fitting in this constant-dimensional space produces a proper mixture and, together with the dimension-free moment characterization of Gaussian mixtures, achieves the optimal Hellinger rate in polynomial arithmetic time for every fixed $k$.
Implicit trace estimation aims to approximate the trace of a matrix or linear operator accessible only through matrix-vector or operator-vector products. In the matrix setting, the Girard-Hutchinson estimator typically requires $\mathcal{O}(\varepsilon^{-2})$ products to achieve accuracy $\varepsilon$, while the variance-reduced Hutch++ algorithm reduces this sample complexity to $\mathcal{O}(\varepsilon^{-1})$ for positive semidefinite matrices. We develop infinite-dimensional analogues of these estimators for positive trace-class operators on separable Hilbert spaces. The idealized estimators use Gaussian random elements whose covariance is determined by the target operator, leading to unbiased operator versions of Girard-Hutchinson and Hutch++. We prove high-probability error bounds analogous to the finite-dimensional matrix results; in particular, idealized infHutch++ achieves $\mathcal{O}(\varepsilon^{-1})$ sample complexity. For practical computation, we introduce truncated implementations that restrict the random samples to finite-dimensional subspaces; for fixed sample budget, we show that truncated infHutch++ converges in distribution to its idealized counterpart as the truncation dimension tends to infinity. Numerical experiments with integral operators, density-of-states approximations, and spectral filtering for a radial Dirac operator show that these truncated estimators can achieve accuracy comparable to the ContHutch++ algorithm by Zvonek, Horning&Townsend while using lower-degree function representations and smaller internal discretizations in chebfun.
Zvonimir Bujanović, Luka Grubišić, Daniel Kressner et al.· 0 citations
For a centered, variance-one random variable $X$ with finite fourth moment, let $x$ be the vector of square-free degree-$d$ monomials in $n$ independent copies of $X$. At the critical scale $d^2/n \to \lambda \in (0,\infty)$, the normalized squared length of $x$ converges to the lognormal variable $R = \exp(\sqrt{\lambda v}\, Z - \lambda v/2)$, where $v = \mathbb{E} X^4 - 1$ and $Z$ is standard normal. If $\binom{n}{d}/N \to c \in (0,\infty)$, the sample covariance of $N$ independent copies of $x$ has an almost-sure limiting spectral law: the free compound-Poisson law with rate $1/c$ and jump distribution $\operatorname{Law}(cR)$. It reduces to Marchenko-Pastur when $\lambda v = 0$. The proof shows that subtracting the contribution of the sample length leaves vanishing quadratic-form fluctuations, even when $\mathbb{E} X^3 \neq 0$; length and direction need not be independent.
Xiaohui Xie· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
