Pretty good shadow tomography
Abstract
We give a shadow tomography algorithm that uses O(log(m) log(m/δ) / ε2) copies of the input state. Specifically, given a quantum state ρ and observables O1,…,Om, the algorithm outputs estimates of tr(Oiρ) for all i∈[m] that are all accurate to within ±ε, except with probability at most δ. The key idea is to work in the average-case setting: for a random state drawn from a known prior, a pretty good measurement on O(log(m)/ε2) copies gives a constant-error guarantee on all but a small fraction of the prior. Boosting this guarantee gives an average-case shadow tomography algorithm, and the minimax principle then (non-constructively) implies the existence of a measurement with the same worst-case guarantee. We also identify an obstruction to further improvement with this approach. While pretty good measurements amplify success over the randomness of the prior, they do not amplify success over the randomness of measurement. This issue appears to be inherent, and gives rise to the remaining log(m) factor separating the complexity of the quantum problem from its classical counterpart.
Related
- Pretty good quantum state transfer via transcendental edge weights
- The marginal is pretty good
- Quantum simultaneous decoding via pretty-good measurements of tilted states
- Shadow bootstrapping: Nearly minimal-setting pure-state tomography with shallow Clifford measurements
- Optimally Weighted Constrained Shadow Tomography for Reduced Density Matrices
BibTeX
@misc{grewal2026pretty,
title = {{Pretty good shadow tomography}},
author = {Sabee Grewal and Angelos Pelecanos and Jack Spilecki and Ewin Tang and John Wright},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.06781},
eprint = {2610.06781},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.06781},
}
RIS
TY - UNPB
TI - Pretty good shadow tomography
AU - Sabee Grewal
AU - Angelos Pelecanos
AU - Jack Spilecki
AU - Ewin Tang
AU - John Wright
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.06781
UR - https://arxiv.org/abs/2610.06781
AB - We give a shadow tomography algorithm that uses O(log(m) log(m/δ) / ε^2) copies of the input state. Specifically, given a quantum state ρ and observables O_1,…,O_m, the algorithm outputs estimates of tr(O_iρ) for all i∈[m] that are all accurate to within ±ε, except with probability at most δ. The key idea is to work in the average-case setting: for a random state drawn from a known prior, a pretty good measurement on O(log(m)/ε^2) copies gives a constant-error guarantee on all but a small fraction of the prior. Boosting this guarantee gives an average-case shadow tomography algorithm, and the minimax principle then (non-constructively) implies the existence of a measurement with the same worst-case guarantee. We also identify an obstruction to further improvement with this approach. While pretty good measurements amplify success over the randomness of the prior, they do not amplify success over the randomness of measurement. This issue appears to be inherent, and gives rise to the remaining log(m) factor separating the complexity of the quantum problem from its classical counterpart.
ER -