2026/02/04 by Senrui Chen, Weiyuan Gong, Sisi Zhou · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Markov Chains and Monte Carlo Methods #Quantum Information and Cryptography #Quantum Mechanics and Applications #cs.IT #cs.LG #math.IT #quant-ph
paper · pdf · doi:10.48550/arxiv.2602.04952
published as Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1115-1185, 2026 · 67 pages
arxiv created 2026/02/04 · openalex publication_date 2026/02/04 · openalex created_date 2026/02/07 · openalex updated_date 2026/07/28 · arxiv updated 2026/08/04
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 αi Oi with ‖α‖q = 1 (where q is dual to p) revealed after the measurement. For single-copy measurements, we obtain a sample complexity of Θ(Γobp/ε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.