We study coherent classical shadows protocols for an unknown $d$-dimensional quantum state of rank at most $r$, allowing an arbitrary joint measurement on all available copies. For observables with operator norm at most one and centered squared Frobenius norm at most $F$, we study the minumum number of copies $T$ needed for the protocol to successed with propbability $1 - δ$. We prove a lower bound on $T$, that depends both on $δ$ and the number $M$ of post-measurement observables. Denoting $\ell=\max\{\log(2M),\log(1/δ)\}$, we show that $T=Ω\left(\min\left\{\frac{\sqrt{rF\ell}}{\varepsilon},\frac{(F\ell)^{2/3}}{\varepsilon^{4/3}}\right\}+\frac{\ell}{\varepsilon^2}\right)$ under the mild assumption $\log(2M)\lesssim d\min\{r,F\}$. The lower bound nearly matches the known upper bound and matches the conjectural strengthening of the known upper bound.
The proof is inspired by the framework of the proof of the lower bound for Boolean Hidden Matching. We develop a Gaussian-lift noise kernel that transfers forward and reverse Gaussian hypercontractivity to the Grassmannian, allowing us to bound the distinguishing advantage in an auxiliary game with a revealed query observable. We use Schur--Weyl structure and posterior moment bounds to control arbitrary coherent measurements on the source side.
AI Summary
The paper studies the sample complexity of coherent classical shadows for an unknown $d$-dimensional state of rank at most $r$: an arbitrary joint measurement on $T$ copies must produce classical data supporting later expectation-value queries. Observables satisfy $\|O\|_{\mathrm{op}}\leq1$ and $\|O-(\operatorname{Tr}O/d)I\|_F^2\leq F$, and all $M$ estimates must have error at most $\varepsilon$ with probability at least $1-\delta$.
Writing $\ell=\max\{\log(2M),\log(1/\delta)\}$, the main result is $T=\Omega\!\left(\min\left\{\sqrt{rF\ell}/\varepsilon,(F\ell)^{2/3}/\varepsilon^{4/3}\right\}+\ell/\varepsilon^2\right)$, for $1\leq F\leq d$, sufficiently small $\varepsilon$, $\delta\leq1/3$, and $\log(2M)\lesssim d\min\{r,F\}$. This matches known upper bounds for one observable at constant confidence and throughout the rank-sensitive regime. For pure states, it removes a logarithmic loss in the previous single-observable lower bound.
The proof reduces estimation to distinguishing a hidden sign from correlations between a measured random projector state and a subsequently revealed observable. A Gaussian-lift noise kernel transfers forward and reverse Gaussian hypercontractivity to the Grassmannian. Schur–Weyl decomposition bounds posterior moments for arbitrary coherent measurements; affinity bounds handle high confidence, while hiding a planted query among Haar-random decoys gives the multiple-observable dependence through Fano’s inequality.
A factor $\ell^{1/3}$ remains between known upper and lower bounds in the saturated geometric regime; a matching upper bound is conjectured. Larger observable lists receive a capped logarithmic dependence. Tradeoffs under limited measurement coherence remain open.
Likely largely AI-generatedAI use disclosed
ChatGPT 5.6 and 6 were used in drafting and proofreading the manuscript, however, the exposition was iteratively and heavily edited by the author.
Error found: The abstract omits the essential restriction F≤d: beyond d the observable class is unchanged, but its claimed lower bound grows without bound even though full tomography gives a finite-copy protocol.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
Comments
Comments welcome. 82 pages. Apologies for the length; the noise kernel part of the paper might be moved to a separate paper in the future
We study coherent classical shadows protocols for an unknown d-dimensional quantum state of rank at most r, allowing an arbitrary joint measurement on all available copies. For observables with operator norm at most one and centered squared Frobenius norm at most F, we study the minumum number of copies T needed for the protocol to successed with propbability 1−δ. We prove a lower bound on T, that depends both on δ and the number M of post-measurement observables. Denoting ℓ=max{log(2M),log(1/δ)}, we show that T=Ω(min{εrFℓ,ε4/3(Fℓ)2/3}+ε2ℓ) under the mild assumption log(2M)≲dmin{r,F}. The lower bound nearly matches the known upper bound and matches the conjectural strengthening of the known upper bound.
The proof is inspired by the framework of the proof of the lower bound for Boolean Hidden Matching. We develop a Gaussian-lift noise kernel that transfers forward and reverse Gaussian hypercontractivity to the Grassmannian, allowing us to bound the distinguishing advantage in an auxiliary game with a revealed query observable. We use Schur--Weyl structure and posterior moment bounds to control arbitrary coherent measurements on the source side.
The paper studies the sample complexity of coherent classical shadows for an unknown d-dimensional state of rank at most r: an arbitrary joint measurement on T copies must produce classical data supporting later expectation-value queries. Observables satisfy ∥O∥op≤1 and ∥O−(TrO/d)I∥F2≤F, and all M estimates must have error at most ε with probability at least 1−δ.
Writing ℓ=max{log(2M),log(1/δ)}, the main result is T=Ω(min{rFℓ/ε,(Fℓ)2/3/ε4/3}+ℓ/ε2), for 1≤F≤d, sufficiently small ε, δ≤1/3, and log(2M)≲dmin{r,F}. This matches known upper bounds for one observable at constant confidence and throughout the rank-sensitive regime. For pure states, it removes a logarithmic loss in the previous single-observable lower bound.
The proof reduces estimation to distinguishing a hidden sign from correlations between a measured random projector state and a subsequently revealed observable. A Gaussian-lift noise kernel transfers forward and reverse Gaussian hypercontractivity to the Grassmannian. Schur–Weyl decomposition bounds posterior moments for arbitrary coherent measurements; affinity bounds handle high confidence, while hiding a planted query among Haar-random decoys gives the multiple-observable dependence through Fano’s inequality.
A factor ℓ1/3 remains between known upper and lower bounds in the saturated geometric regime; a matching upper bound is conjectured. Larger observable lists receive a capped logarithmic dependence. Tradeoffs under limited measurement coherence remain open.
We determine the optimal sample complexity of low-rank quantum state tomography when each measurement may act jointly on at most t samples. For sufficiently small ε, estimating an unknown state on Cd of rank at most r to trace norm error ε with constant success probability requires, and is achievable with, Θ(ε2drmax{1,tr}) samples. The lower bound allows the protocol to choose each joint measurement adaptively using all previous classical outcomes; the matching upper bound is nonadaptive. Thus joint measurements on at most t samples improve the complexity of algorithms making single-sample measurements by at most a factor t. Further, measuring order r2 samples jointly is necessary and sufficient to attain the unrestricted collective rate.
For the lower bound, we vary the support of a state with fixed uniform spectrum and bound the Fisher information trace of every joint measurement on t samples. The adaptive Fisher chain rule and the van Trees inequality then give the trace norm lower bound. For the upper bound, we construct and analyze a nonadaptive tomography protocol based on a Gaussian joint measurement. An explicit second moment identity and a conditional Gaussian law outside the state's support give a rank-dependent error analysis, yielding the matching rate.
We study the sample complexity of the classical shadows task: what is the fewest number of copies of an unknown state you need to measure to predict expected values with respect to some class of observables? Large joint measurements are likely required in order to minimize sample complexity, but previous joint measurement protocols only work when the unknown state is pure. We present the first joint measurement protocol for classical shadows whose sample complexity scales with the rank of the unknown state. In particular we prove O(rB/ε2) samples suffice, where r is the rank of the state, B is a bound on the squared Frobenius norm of the observables, and ε is the target accuracy. In the low-rank regime, this is a nearly quadratic advantage over traditional approaches that use single-copy measurements. We present several intermediate results that may be of independent interest: a solution to a new formulation of classical shadows that captures functions of non-identical input states; a generalization of a ``nice'' Schur basis used for optimal qubit purification and quantum majority vote; and a measurement strategy that allows us to use local symmetries in the Schur basis to avoid intractable Weingarten calculations in the analysis.
We study the number of copies needed to estimate the root Uhlmann fidelity between an unknown quantum state and a classically known reference, under collective measurements. If the unknown state has rank at most s, we give an estimator using O(s2/ε2) copies, uniformly in the ambient dimension and reference rank. The estimator applies a random-purification channel and a covariant pure-state measurement, then rescales the observed amplitude before evaluating a weighted nuclear norm. Combined with the lower bound established independently in our first version and in concurrent work of Wang, this determines the worst-case complexity under rank bounds r,s as min{r,s}2/ε2 up to logarithmic factors in the smaller rank.
The same estimator gives the upper bound O(r(trσ)2/ε2) for a rank-r reference σ. We combine spectral truncation with lower bounds obtained by embedding hard instances for the maximally mixed reference into spectral subspaces. For spectra λi∝i−α with fixed 1<α≤2, as ε↓0 with r≥Cαε−2/(α−1), the bounds determine the complexity as Θα(ε−4/(α−1)). In particular, inverse-square spectra have accuracy exponent four. The lower-bound construction uses exact moment matching and an explicitly computable Schur measure.
We prove that learning an unknown mixed fermionic Gaussian state on m modes to trace distance ε requires Ω(m3/ε2) copies when measurements act on one copy at a time, even with arbitrary POVMs, fresh ancillas and classical adaptivity, but without quantum memory between copies. The bound holds for 0<ε≤1/3600 and separates this model from the known collective rate Θ(m2/ε2). It follows from a uniform single-copy Fisher-information budget and a dimension-independent comparison between trace distance and Gaussian parameters. On covariance matrices of operator norm at most 1−c, we prove a Frobenius-to-trace-norm continuity bound with constant [2c(2−c)]−1/2; matchgate shadows then attain O(m3/(cε2)) copies. This also gives explicit error certificates for thermal free-fermion states. For a class of mixed passive bosonic Gaussian states with total mean photon number at most one, a reduction to bounded-block qudit tomography gives a single-copy lower bound Ω(m3/(ε2log(m/ε))), versus collective complexity Θ(m2/ε2). These separations answer the mixed-state measurement-resource question posed by Chen et al. A two-mode example has optimal two-copy Fisher trace 5, versus the separable ceiling 4. An IBM replication gave a pre-registered witness lower bound 4.12 at one-sided 95% shot-noise confidence; its interpretation assumes the prescribed preparations and a common measurement channel and does not bound preparation systematics.
We study the sample complexity of shadow tomography in the high-precision regime under realistic measurement constraints. Given an unknown d-dimensional quantum state ρ and a known set of observables {Oi}i=1m, the goal is to estimate expectation values {tr(Oiρ)}i=1m to accuracy ε in Lp-norm, using possibly adaptive measurements that act on O(polylog(d)) number of copies of ρ at a time. We focus on the regime where ε is below an instance-dependent threshold.
Our main contribution is an instance-optimal characterization of the sample complexity as Θ~(Γp/ε2), where Γp is a function of {Oi}i=1m defined via an optimization formula involving the inverse Fisher information matrix. Previously, tight bounds were known only in special cases, e.g. Pauli shadow tomography with L∞-norm error. Concretely, we first analyze a simpler oblivious variant where the goal is to estimate an observable of the form ∑i=1mαiOi with ∥α∥q=1 (where q is dual to p) revealed after the measurement. For single-copy measurements, we obtain a sample complexity of Θ(Γpob/ε2). We then show Θ~(Γp/ε2) is necessary and sufficient for the original problem, with the lower bound applying to unbiased, bounded estimators. Our upper bounds rely on a two-step algorithm combining coarse tomography with local estimation. Notably, Γ∞ob=Γ∞. In both cases, allowing c-copy measurements improves the sample complexity by at most Ω(1/c).
Our results establish a quantitative correspondence between quantum learning and metrology, unifying asymptotic metrological limits with finite-sample learning guarantees.
Shadow Tomography is a fundamental problem in quantum information theory. Given multiple copies of an unknown d-dimensional quantum state ρ and a known collection of observables E1,…,EM, the goal is to estimate all expectation values {Tr(ρEi)}i=1M to additive accuracy ε with probability at least 1−δ.
An elusive open question from the seminal shadow tomography work of Aaronson is whether this task admits a dimension-independent sample complexity with only polylogarithmic dependence on M, as suggested by the best-known lower bounds. In this work, we propose two different quantum protocols for shadow tomography with the best sample complexity O(ε2log(M)log(M/δ)), which is polylogarithmic in the number of observables and independent of the dimension of the unknown state, thereby answering Aaronson's original question while also providing an exponential improvement in the prior best dimension independent sample complexity of shadow tomography from Sinha (STOC 2025) and, more recently, Chen, O'Donnell, Pelecanos, and Wright.
Our approach first reduces the general shadow tomography problem to a finite-ensemble estimation problem via a minimax argument. We then develop an observable-independent protocol that repeatedly applies the pretty-good measurement while updating the prior distribution over the finite ensemble according to the measurement outcomes. A tail analysis of the resulting estimation error yields simultaneous accuracy guarantees for all observables and a cubic-logarithmic upper bound. We also introduce a refined recovery-label measurement for the same finite ensemble, which yields the bound in our main theorem.