Dimension-Free Polylogarithmic Quantum Shadow Tomography from Sequential Pretty-Good Measurements

Abstract:\textit{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 $\{\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 (STOC'18) 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 give a quantum protocol for shadow tomography with sample complexity \[ O\left( \frac{1}{\varepsilon^2} \frac{(\log (m/\delta))^4} {(\log\log (m/\delta))^3} \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 from Sinha (STOC'25). 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 and updates the priori distribution over the finite ensemble according to the measurement outcomes. A refined tail analysis of the resulting estimation error yields simultaneous accuracy guarantees for all observables.

arXiv:2608.06345 [quant-ph]

(or arXiv:2608.06345v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2608.06345 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.