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 \tildeΘ(Γ_p/ε^2), 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/ε^2). We then show \tildeΘ(Γ_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}\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.