Optimal dimension-free copy complexity of shadow tomography

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

\begin{equation} N\leq\left\lceil C\frac{\log M}{\varepsilon^2}\right\rceil \quad\text{copies yields}\quad \inf_\rho\Pr_\rho\!\left[ \max_j|\widehat\mu_j-\operatorname{Tr}(\rho E_j)|\leq\varepsilon \right]\geq\frac23? \tag{1} \end{equation}

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

Reports do not certify correctness or automatically change the problem's status. Progress policy.

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

\begin{equation} \Omega(\varepsilon^{-2}\log M) \quad\text{versus}\quad O(\varepsilon^{-2}\log^2 M). \tag{4} \end{equation}

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.arXiv link
[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

Optimal dimension-free copy complexity of shadow tomography

Problem

Source

Progress

Comment

References

Cite this problem

BibTeX

Plain text

Problem

Source

Progress

Comment

References

Related problems