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