Dimension-Free Polylogarithmic Quantum Shadow Tomography from Sequential Pretty-Good Measurements
Shadow Tomography is a fundamental problem in quantum information theory. Given multiple copies of an unknown $d$-dimensional quantum state $\rho$ and a known collection of observables ${E_1,\ldots,E_M}$, the goal is to estimate all expectation values $\{\text{Tr}(\rho E_i)\}_{i=1}^M$ to additive accuracy $\varepsilon$ with probability at least $1-\delta$. 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\left( \frac{\log(M)\log(M/\delta)}{\varepsilon^2} \right), \] 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.