Dimension-Free Polylogarithmic Quantum Shadow Tomography
Abstract
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( log(M)log(M/δ)/ε2 ), 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.
Related
- Orbital-Rotation Shadow Tomography Reduces the Classical Cost of Quantum-Classical Auxiliary-Field Quantum Monte Carlo
- Optimally Weighted Constrained Shadow Tomography for Reduced Density Matrices
- New gravitational instanton: shadow of an extra dimension
- Pretty good shadow tomography
- Displacement-noise-free gravitational-wave detector using quantum tomography of photon orbital angular momentum states
BibTeX
@misc{jeronimo2026dimensionfree,
title = {{Dimension-Free Polylogarithmic Quantum Shadow Tomography}},
author = {Fernando Granha Jeronimo and Qizhao Huang and Lenny Liu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.06345},
eprint = {2608.06345},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.06345},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Dimension-Free Polylogarithmic Quantum Shadow Tomography
AU - Fernando Granha Jeronimo
AU - Qizhao Huang
AU - Lenny Liu
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2608.06345
UR - https://arxiv.org/abs/2608.06345
AB - 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 E_1,…,E_M, the goal is to estimate all expectation values {Tr(ρE_i)}_i=1^M 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( log(M)log(M/δ)/ε^2 ), 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.
ER -