Track the frontier, from condensed matter to cosmology.
Search papers, labs, and topics across Lattice.
This paper introduces a shadow tomography algorithm achieving $O(\log(m) \log(m/δ) / \varepsilon^2)$ copies for estimating expectation values of $m$ observables on a quantum state $\rho$ to within $\pm\varepsilon$ accuracy with probability $1-\delta$. The core innovation lies in leveraging average-case analysis, where a "pretty good measurement" on $O(\log(m)/\varepsilon^2)$ copies provides a constant-error guarantee for a significant portion of a known prior state distribution. This average-case guarantee is then boosted to a worst-case bound, though an inherent limitation in amplifying measurement randomness prevents achieving a $\log(m)$ factor improvement over classical complexity.
A novel shadow tomography algorithm achieves near-optimal sample complexity by exploiting average-case guarantees, but an inherent measurement bottleneck limits further improvement.
We give a shadow tomography algorithm that uses $O(\log(m) \log(m/δ) / \varepsilon^2)$ copies of the input state. Specifically, given a quantum state $ρ$ and observables $O_1,\ldots,O_m$, the algorithm outputs estimates of $\mathrm{tr}(O_iρ)$ for all $i\in[m]$ that are all accurate to within $\pm\varepsilon$, 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)/\varepsilon^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.