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

Batched and Complete U-Statistics for Trace-Polynomial Estimation from Classical Shadows

Xinyu Song

quant-phmath.STSubmitted Aug 24, 2026• Announced Aug 25, 2026• 0 citations
arXivHTMLPDF

Abstract

We study estimation of the trace polynomial $\operatorname{tr} p(PρP)$ from global classical shadows, where $ρ$ 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.

Comments
Main paper: 13 pages, 3 tables, no figures; supplementary material: 10 pages

Related papers

Local and Global Risk Bounds for Quantum Entropy Estimation under Projective-Design Measurements

Xinyu Song

We establish a lower bound for estimating the von Neumann entropy from independent outcomes of any fixed rank-one POVM. A rotation-averaged van Trees argument gives a global minimax risk of at least $(d/n)\log^2\{n/(4d)\}$ when $d\ge C$ and $n\ge Cd$, without a projective-design assumption. We also characterize risk on an operator-norm ball of radius $r$ around the maximally mixed state. We allow an approximate second moment: on the trace-zero Hermitian subspace, the measurement frame may differ by $\varepsilon<1$ from the tight projective frame. A clipped estimator based on canonical dual shadows and the complete U-statistic for purity has risk at most $d^3r^2/n+d^4/n^2+d^6r^6$. Lower bounds under the same frame control yield the local minimax rate $d^3r^2/n+d^4/n^2$ when $n\ge Cd^2$ and $r$ lies in an explicit matching range. For every fixed upper bound on $\varepsilon$, approximation changes only the constants, not the powers of $d,n,r$. At the critical radius $r=n^{-1/2}$, the local risk is asymptotically negligible relative to the global risk when $n\log^2(n/d)\gg d^3$. This separation holds for projective 2-designs, including global Clifford measurements in qubit dimensions, and for their uniformly well-conditioned frame approximations. Finite-sample experiments in dimension four illustrate the critical-radius benchmark and the effect of a nonexact frame.

quant-pharXiv:2609.29485•Aug 26, 2026•0 citations

Spectrum Estimation is Almost as Hard as Tomography

Marco Fanizza, Ryan O'Donnell, Chirag Wadhwa

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 $γ>0$, we prove a sample complexity lower bound of $Ω(d^{2-γ})$ 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.

quant-pharXiv:2607.29680•Aug 3, 2026•0 citations

A Frame-Spread Lower Bound for Quantum Entropy Estimation under Fixed Rank-One Measurements

Xinyu Song

We study estimation of the von Neumann entropy of a $d$-dimensional quantum state from independent outcomes of a fixed rank-one measurement. Let $κ_ν\in[1,d+1]$ denote the normalized trace-zero frame spread; $κ_ν=1$ for exact complex projective $2$-designs. For any fixed rank-one measurement and $n\le c_2d^2/κ_ν$, the minimax mean-squared error is at least $c_1\log^2\{d^2/(κ_νn)\}$. For bounded frame spread and every fixed $0<a<2$, the minimax risk is of order $\log^2 d$ throughout $n\lesssim d^{2-a}$; hence fixed uniform accuracy requires $Ω(d^2)$ observations. Existing tomography bounds give bounded risk from $O(d^3\log^3 d)$ observations for finite equal-weight exact designs and the Haar covariant measurement, while the intermediate minimax regime remains open. The results concern a fixed measurement repeated independently across copies; adaptive and collective protocols, and protocols that reuse common randomness across copies, are not covered.

quant-pharXiv:2610.00270•Statistics & Probability Letters•Aug 26, 2026•0 citations

Real Classical Shadows with Noise

Atharva Hingane, Dax Enshan Koh

The real classical shadows protocol of West et al. replaces the unitary (Clifford) ensemble of the Huang--Kueng--Preskill scheme by the orthogonal (real Clifford) ensemble, and for symmetric observables achieves strictly smaller estimator variances: a factor approaching two for global evolution and an exponential factor $(3/2)^k$ for $k$-local real Pauli observables. Real hardware, however, never implements the ideal evolution. Building on the noisy classical shadows framework of Koh and Grewal, we give a complete theory of the real classical shadows protocol in the presence of a known completely positive trace-preserving noise channel acting after the orthogonal evolution. We derive the noisy global and local orthogonal shadow channels from first principles using the Weingarten calculus of the orthogonal group, prove that each is a depolarizing channel acting on the symmetric (respectively locally symmetric) component of its input, and derive from it the exact single-shot variance in closed form, together with the associated shadow seminorm, two-sided bounds on it, and the resulting sample-complexity guarantees. We prove that the noiseless sample-complexity advantages survive intact under noise. Because the variances are exact rather than bounded, the ratio is controlled by a single dimensionless parameter, which gives a closed-form criterion for when the factor of two is attainable: both the second-moment and the variance ratio reach it exactly when the observable's norm profile grows, and the noise enters that limit only through a factor lying within $2/(d+2)$ of two, so the advantage is uniform in the noise. For rank-one targets it is provably unattainable, saturating strictly below two. The local real-Pauli advantage remains $(3/2)^k$. We treat complex measurement bases through a reality parameter and a transposed-noise scalar, recovering unitary shadows in the appropriate limit.

quant-pharXiv:2608.18935•Aug 20, 2026•0 citations

Finite-Sample Selected Covariance Spectra in Classical Shadows

Masahito Hayashi

Classical shadows use a single measurement snapshot to estimate many observables. These estimates are jointly distributed, and their covariance is not determined by their expectation values or individual variances. It also differs from physical correlations between observables because it depends on the measurement and reconstruction protocol. We study the covariance matrix for a fixed set of shadow estimates and its spectrum. For general shadow protocols, we give a finite-sample operator-norm bound for the empirical covariance computed using the sample mean. This bound also controls the eigenvalues and isolated spectral subspaces of the covariance matrix. For local product shadow protocols with fixed local dimension, observables supported on a bounded number of sites lead to bounds that do not depend on the total system size, provided that the number of selected observables and the relevant local reconstruction factors remain bounded. For biased local Pauli shadows, we obtain explicit finite-sample bounds and an exact covariance formula determined by Pauli compatibility and local basis probabilities. A comparison with global Clifford shadows shows that dimension-independent covariance estimation depends on the measurement protocol and does not follow from the general theory alone.

quant-pharXiv:2606.00527•Jun 2, 2026•0 citations

Optimal von Neumann Entropy Estimation

Ziyun Chen, Minbo Gao, Qisheng Wang

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.

quant-pharXiv:2608.11151•Aug 12, 2026•0 citations
We study estimation of the trace polynomial tr⁡p(PρP)\operatorname{tr} p(PρP)trp(PρP) from global classical shadows, where ρρρ is an unknown quantum state and PPP 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 sss, the quadratic degenerate term has order s2/Ns^2/Ns2/N under batching and s2/N2s^2/N^2s2/N2 under complete symmetrization. For a logarithmic-degree polynomial used in entropy approximation, the quadratic coefficient raises the batched variance to at least order s2Nlog⁡2Ns^2N\log^2Ns2Nlog2N 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 establish a lower bound for estimating the von Neumann entropy from independent outcomes of any fixed rank-one POVM. A rotation-averaged van Trees argument gives a global minimax risk of at least (d/n)log⁡2{n/(4d)}(d/n)\log^2\{n/(4d)\}(d/n)log2{n/(4d)} when d≥Cd\ge Cd≥C and n≥Cdn\ge Cdn≥Cd, without a projective-design assumption. We also characterize risk on an operator-norm ball of radius rrr around the maximally mixed state. We allow an approximate second moment: on the trace-zero Hermitian subspace, the measurement frame may differ by ε<1\varepsilon<1ε<1 from the tight projective frame. A clipped estimator based on canonical dual shadows and the complete U-statistic for purity has risk at most d3r2/n+d4/n2+d6r6d^3r^2/n+d^4/n^2+d^6r^6d3r2/n+d4/n2+d6r6. Lower bounds under the same frame control yield the local minimax rate d3r2/n+d4/n2d^3r^2/n+d^4/n^2d3r2/n+d4/n2 when n≥Cd2n\ge Cd^2n≥Cd2 and rrr lies in an explicit matching range. For every fixed upper bound on ε\varepsilonε, approximation changes only the constants, not the powers of d,n,rd,n,rd,n,r. At the critical radius r=n−1/2r=n^{-1/2}r=n−1/2, the local risk is asymptotically negligible relative to the global risk when nlog⁡2(n/d)≫d3n\log^2(n/d)\gg d^3nlog2(n/d)≫d3. This separation holds for projective 2-designs, including global Clifford measurements in qubit dimensions, and for their uniformly well-conditioned frame approximations. Finite-sample experiments in dimension four illustrate the critical-radius benchmark and the effect of a nonexact frame.
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 ddd-dimensional states, and for every γ>0γ>0γ>0, we prove a sample complexity lower bound of Ω(d2−γ)Ω(d^{2-γ})Ω(d2−γ) 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 fff-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.
We study estimation of the von Neumann entropy of a ddd-dimensional quantum state from independent outcomes of a fixed rank-one measurement. Let κν∈[1,d+1]κ_ν\in[1,d+1]κν​∈[1,d+1] denote the normalized trace-zero frame spread; κν=1κ_ν=1κν​=1 for exact complex projective 222-designs. For any fixed rank-one measurement and n≤c2d2/κνn\le c_2d^2/κ_νn≤c2​d2/κν​, the minimax mean-squared error is at least c1log⁡2{d2/(κνn)}c_1\log^2\{d^2/(κ_νn)\}c1​log2{d2/(κν​n)}. For bounded frame spread and every fixed 0<a<20<a<20<a<2, the minimax risk is of order log⁡2d\log^2 dlog2d throughout n≲d2−an\lesssim d^{2-a}n≲d2−a; hence fixed uniform accuracy requires Ω(d2)Ω(d^2)Ω(d2) observations. Existing tomography bounds give bounded risk from O(d3log⁡3d)O(d^3\log^3 d)O(d3log3d) observations for finite equal-weight exact designs and the Haar covariant measurement, while the intermediate minimax regime remains open. The results concern a fixed measurement repeated independently across copies; adaptive and collective protocols, and protocols that reuse common randomness across copies, are not covered.
The real classical shadows protocol of West et al. replaces the unitary (Clifford) ensemble of the Huang--Kueng--Preskill scheme by the orthogonal (real Clifford) ensemble, and for symmetric observables achieves strictly smaller estimator variances: a factor approaching two for global evolution and an exponential factor (3/2)k(3/2)^k(3/2)k for kkk-local real Pauli observables. Real hardware, however, never implements the ideal evolution. Building on the noisy classical shadows framework of Koh and Grewal, we give a complete theory of the real classical shadows protocol in the presence of a known completely positive trace-preserving noise channel acting after the orthogonal evolution. We derive the noisy global and local orthogonal shadow channels from first principles using the Weingarten calculus of the orthogonal group, prove that each is a depolarizing channel acting on the symmetric (respectively locally symmetric) component of its input, and derive from it the exact single-shot variance in closed form, together with the associated shadow seminorm, two-sided bounds on it, and the resulting sample-complexity guarantees. We prove that the noiseless sample-complexity advantages survive intact under noise. Because the variances are exact rather than bounded, the ratio is controlled by a single dimensionless parameter, which gives a closed-form criterion for when the factor of two is attainable: both the second-moment and the variance ratio reach it exactly when the observable's norm profile grows, and the noise enters that limit only through a factor lying within 2/(d+2)2/(d+2)2/(d+2) of two, so the advantage is uniform in the noise. For rank-one targets it is provably unattainable, saturating strictly below two. The local real-Pauli advantage remains (3/2)k(3/2)^k(3/2)k. We treat complex measurement bases through a reality parameter and a transposed-noise scalar, recovering unitary shadows in the appropriate limit.
Classical shadows use a single measurement snapshot to estimate many observables. These estimates are jointly distributed, and their covariance is not determined by their expectation values or individual variances. It also differs from physical correlations between observables because it depends on the measurement and reconstruction protocol. We study the covariance matrix for a fixed set of shadow estimates and its spectrum. For general shadow protocols, we give a finite-sample operator-norm bound for the empirical covariance computed using the sample mean. This bound also controls the eigenvalues and isolated spectral subspaces of the covariance matrix. For local product shadow protocols with fixed local dimension, observables supported on a bounded number of sites lead to bounds that do not depend on the total system size, provided that the number of selected observables and the relevant local reconstruction factors remain bounded. For biased local Pauli shadows, we obtain explicit finite-sample bounds and an exact covariance formula determined by Pauli compatibility and local basis probabilities. A comparison with global Clifford shadows shows that dimension-independent covariance estimation depends on the measurement protocol and does not follow from the general theory alone.
We show that the von Neumann entropy of an unknown ddd-dimensional quantum state ρρρ can be estimated to within additive error ε\varepsilonε using Θ ⁣(d2εlog⁡2(d)(1+εlog⁡2(d))+log⁡2(d)ε2) Θ\!\left(\frac{d^2}{\varepsilon\log^2(d)(1+\varepsilon\log^2(d))} + \frac{\log^2(d)}{\varepsilon^2}\right) Θ(εlog2(d)(1+εlog2(d))d2​+ε2log2(d)​) 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.