Instance-optimal high-precision shadow tomography with few-copy measurements: A metrological approach

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 \{O_i\}_i=1^m, the goal is to estimate expectation values \{tr\(O_iρ\)\}_i=1^m to accuracy ε in L_p-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/ε²\), where Γ_p is a function of \{O_i\}_i=1^m 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_infty-norm error. Concretely, we first analyze a simpler oblivious variant where the goal is to estimate an observable of the form sum_i=1^m α_i O_i with \|α\|_q = 1 (where q is dual to p) revealed after the measurement. For single-copy measurements, we obtain a sample complexity of Θ\(Γ^ob_p/ε²\). We then show Θ\(Γ_p/ε²\) 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_infty = Γ_infty. 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.