Optimal dimension-free copy complexity of shadow tomography
- Field
- Topics
Problem
Can list-dependent shadow tomography always achieve dimension-free copy complexity \(O(\log M/\varepsilon^2)\)?
Let \(0\leq E_1,\ldots,E_M\leq I_d\) be a known list of effects and let \(\rho\) be an unknown \(d\)-dimensional state supplied as independent copies. Does a universal constant \(C\) exist such that, for every \(d\), \(M\geq2\), and \(0<\varepsilon<1/4\), a collective measurement on
The list is fixed before measurement, and no computational-efficiency requirement is imposed. Equation (1) concerns list-dependent shadow tomography rather than measurement-independent classical shadows.
Source
The question is explicitly posed or retained as open in the cited primary literature [Aaronson18][Jeronimo26]. The statement is rewritten here to make its hypotheses and success criterion self-contained.
Progress
For known classical functions, empirical estimation and a union bound use \(O(\!\left(\log M/\varepsilon^2\right))\) samples independently of the sample-space size. The same bound holds for commuting effects by measuring their common eigenbasis; the unresolved case is noncommuting.
Aaronson’s shadow-tomography work established a worst-case lower bound of order
\begin{equation} \Omega\!\left(\frac{\min\{d^2,\log M\}}{\varepsilon^2}\right). \tag{2} \end{equation}The displayed definitions, constraints, and target bounds are recorded in Eqs. (2).
For sufficiently large dimension, this matches the proposed target. It is not a lower bound of \(\log M/\varepsilon^2\) for every fixed small \(d\). [Aaronson18]
Chen, Li, and Liu proved the optimal logarithmic rate in a high-precision regime. Subsequent work by Pelecanos, Spilecki, and Wright expands the regime where that rate is achievable. These dimension-dependent precision conditions do not settle all \(d\) and \(\varepsilon\) simultaneously. [Chen24], [Pelecanos25]
The critical update is Jeronimo, Huang, and Liu, arXiv:2608.06345v2, revised September 14, 2026. The revision reports
\begin{equation} N=O\!\left(\frac{\log M\,\log(M/\delta)}{\varepsilon^2}\right). \tag{3} \end{equation}The displayed definitions, constraints, and target bounds are recorded in Eqs. (3).
At failure probability \(\delta=1/3\), this becomes \(O(\varepsilon^{-2}\log^2 M)\). The earlier version’s fourth-power logarithm is no longer the latest reported bound. The theorem also answers the older question of whether dimension-free polylogarithmic shadow tomography exists. [Jeronimo26]
Comment
At constant failure probability, the latest reported bounds leave the worst-case gap
The result is currently available as a recent preprint. The open question is stated as an explicit optimization target, not attributed as a newly named conjecture to those authors.
The displayed definitions, constraints, and target bounds are recorded in Eqs. (4).
References
- [Aaronson18]
- S. Aaronson, Shadow Tomography of Quantum States, arXiv:1711.01053; STOC (2018). Paper.arXiv
- [Jeronimo26]
- F. Granha Jeronimo, Q. Huang, and L. Liu, Dimension-Free Polylogarithmic Quantum Shadow Tomography from Sequential Pretty-Good Measurements, arXiv:2608.06345v2, revised September 14, 2026. The HTML manuscript uses the shorter title Dimension-Free Polylogarithmic Quantum Shadow Tomography. See Definition 1.1, Theorem 1.2, and Section 1.2. Versioned record; versioned full text.arXivlink
- [Chen24]
- S. Chen, J. Li, and A. Liu, Optimal high-precision shadow estimation, arXiv:2407.13874 (2024). Paper.arXiv
- [Pelecanos25]
- A. Pelecanos, J. Spilecki, and J. Wright, The debiased Keyl’s algorithm: a new unbiased estimator for full state tomography, arXiv:2510.07788 (2025). The improvement to the high-precision regime is also discussed in Section 1.2 of [Jeronimo26]. Paper.arXiv