Optimal dimension-free copy complexity of shadow tomography

Shadow tomography asks how many copies of an unknown quantum state are needed to estimate the probabilities of $M$ given measurements, without reconstructing the whole state. A 2026 preprint reports that about $\log^2 M/\varepsilon^2$ copies suffice in every dimension. The open question is whether $\log M/\varepsilon^2$ copies, the rate for classical data, are always enough.

Problem

Let $E_1,\dots,E_M$ be known operators on $\mathbb C^d$ with $0\le E_j\le I$, and let $\rho$ be an unknown $d$-dimensional state, available as independent copies. A strategy chooses, knowing the list, one measurement on $\rho^{\otimes N}$ and a rule that turns its outcome into estimates $\hat\mu_1,\dots,\hat\mu_M$. It succeeds if

$$\max_{1\le j\le M}\big|\hat\mu_j-\operatorname{Tr}(\rho E_j)\big|\le\varepsilon .$$

Question. Is there a universal constant $C$ such that, for every dimension $d$, every $M\ge2$, every list $E_1,\dots,E_M$ and every $0<\varepsilon<1/4$, some strategy with $N\le C\log M/\varepsilon^2$ copies succeeds with probability at least $2/3$ for every state $\rho$?

The measurement may act jointly on all copies, and its computational cost is not limited. A negative answer is a lower bound that grows faster than $\log M/\varepsilon^2$ for some family of lists.

Background

In work published in 2018, Aaronson introduced shadow tomography and showed that $\tilde O(\varepsilon^{-4}\log^4M\log d)$ copies suffice, exponentially fewer than full tomography needs [1]. The question arose from his work on private-key quantum money and bears on copy-protected software and quantum advice [1]. He asked whether a number of copies polylogarithmic in $M$ and independent of $d$ is possible, as it is for classical distributions, and whether any lower bound of the form $\omega(\log M)$ holds [1]. When all the $E_j$ commute, measuring their common eigenbasis and averaging gives $O(\log M/\varepsilon^2)$ copies, so the difficulty lies with noncommuting measurements.

What is known

• Lower bound: $\Omega(\min\{d^2,\log M\}/\varepsilon^2)$ copies are needed in the worst case. For classical distributions on $d$ outcomes the bound is $\Omega(\min\{d,\log M\}/\varepsilon^2)$, and it is tight there [1].
• Dimension-dependent upper bounds: $\tilde O(\varepsilon^{-4}\log^4M\log d)$ [1], improved by Bădescu and O'Donnell to $\tilde O(\varepsilon^{-4}\log^2M\log d)$ [2].
• The optimal rate $O(\log M/\varepsilon^2)$ is achieved at high precision: for $\varepsilon\le O(d^{-12})$ by Chen, Li and Liu (2024) [3], and for $\varepsilon=O(1/d)$ by Pelecanos, Spilecki and Wright (2025) [4].
• Jeronimo, Huang and Liu (2026) report a dimension-free strategy with $O(\varepsilon^{-2}\log M\log(M/\delta))$ copies for failure probability $\delta$, which would answer Aaronson's polylogarithmic question; it is an unrefereed preprint [5]. The best dimension-independent bound before it was Sinha's $O(\sqrt M\log M/\varepsilon^2)$ (2025), as cited in [5]. At constant $\delta$ the new bound is $O(\log^2M/\varepsilon^2)$, a factor $\log M$ above the lower bound in large dimension.

What would count as progress

• A strategy using $O(\log M/\varepsilon^2)$ copies in every dimension, or any bound below $\log^2M/\varepsilon^2$, such as $O(\log M\log\log M/\varepsilon^2)$, with a complete proof.
• A lower bound of order $\omega(\log M)/\varepsilon^2$ for an explicit family of noncommuting measurements in growing dimension, which would answer Aaronson's second question.
• The optimal rate in the middle regime $1/d\ll\varepsilon<1/4$, extending [3, 4].

References

1. S. Aaronson, "Shadow tomography of quantum states", Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC), 325–338 (2018). doi:10.1145/3188745.3188802
2. C. Bădescu and R. O'Donnell, "Improved quantum data analysis", Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC), 1398–1411 (2021). doi:10.1145/3406325.3451109
3. S. Chen, J. Li and A. Liu, "Optimal high-precision shadow estimation", preprint (2024). arXiv:2407.13874
4. A. Pelecanos, J. Spilecki and J. Wright, "The debiased Keyl's algorithm: a new unbiased estimator for full state tomography", preprint (2025). arXiv:2510.07788
5. F. G. Jeronimo, Q. Huang and L. Liu, "Dimension-free polylogarithmic quantum shadow tomography", preprint (2026). arXiv:2608.06345

Source

Imported from QIQCOP Zoo op_428e6c37ba03149a, curated by Bikun Li, Qicheng Tang, Changhao Li, Chengkai Zhu, Minbo Gao, Zhong-Xia Shang, Bin Cheng and Naixu Guo. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.