Submit progress

on Optimal sample complexity of shadow tomography

The statement

Given $m$ bounded observables $O_1,\ldots,O_m$ on a $d$ -dimensional system and copies of an unknown state $\rho$ , estimate each $\operatorname{Tr}(O_i\rho)$ to additive error $\varepsilon$ . Can the quantum sample complexity match the classical rate $O(\log(m)/\varepsilon^2)$ , or is there a provable separation? The 2024 source cites an upper bound $O(\log^2(m)\log(d)/\varepsilon^4)$ . See the cited papers for normalization and success-probability conventions.

What gets accepted

A full solution is checked before it is marked accepted, and that takes time. Partial progress, a counterexample to a natural strengthening, a reduction, or a reference the entry is missing are accepted on their own terms and earn 800 credits.

Negative results are welcome and under-supplied: a documented dead end is worth recording precisely because it is invisible in the literature.