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

arXiv:2602.04952v2 Announce Type: replace-cross Abstract: We study the sample complexity of shadow tomography in the high-precision regime under realistic measurement constraints. Given an unknown d-dimensional quantum state rho and a known set of observables {O_i}{i=1}^m, the goal is to estimate expectation values {tr(O_irho)}{i=1}^m to accuracy epsilon in L_p-norm, using possibly adaptive measurements that act on O(polylog(d)) number of copies of rho at a time. We focus on the regime where epsilon is below an instance-dependent threshold. Our main contribution is an instance-optimal characterization of the sample complexity as ilde{Theta}(Gamma_p/epsilon^2), where Gamma_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 alpha_i O_i with |alpha|_q = 1 (where q is dual to p) revealed after the measurement. For single-copy measurements, we obtain a sample complexity of Theta(Gamma^{ob}_p/epsilon^2). We then show ilde{Theta}(Gamma_p/epsilon^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, Gamma^{ob}_infty = Gamma_infty. In both cases, allowing c-copy measurements improves the sample complexity by at most Omega(1/c). Our results establish a quantitative correspondence between quantum learning and metrology, unifying asymptotic metrological limits with finite-sample learning guarantees.

Source: arXiv cs.LG | 2026-09-29