Pretty good shadow tomography

Sabee Grewal, Angelos Pelecanos, Jack Spilecki, Ewin Tang, John Wright

Oct 5, 2026arXiv:2610.06781v1

quant-ph

Scorecard· 15/16

9.0/10 impact

Near-optimal, dimension-free shadow tomography via a genuinely new average-case PGM plus minimax route, resolving a flagship open problem up to one log factor.

Abstract

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.

AI Impact Assessments

(1 model)

Assessment of "Pretty good shadow tomography"

Core Contribution

The paper gives a dimension-free shadow tomography algorithm using O(log(m)·log(m/δ)/ε²) copies. Previous dimension-free bounds scaled polynomially in m (O(√m/ε²)). The best dimension-dependent bound was O(log(m)·√log(d)/ε³). The result nearly closes Aaronson's 2016 problem, leaving a gap of one log(m) factor to the classical O(log(m/δ)/ε²) rate and the Ω(log m/ε²) lower bound. It also shows that no dimension dependence is needed in the offline setting.

The route is conceptually new and has three parts.

Average case: the paper moves to the average-case setting with a known prior and analyzes the pretty good measurement (PGM) plus plug-in estimation. This avoids the Aaronson-style hypothesis-state-update paradigm used by essentially all prior work.

Minimax: Sion's minimax theorem converts the average-case guarantee into a worst-case one, non-constructively. This sidesteps the long-standing difficulty of identifying hard priors for given observables. The idea is borrowed from Harrow–Winter on worst-case state discrimination, but its use here is new.

Decay of the Bad set: the paper shows that although the PGM's error probability on a given state need not decay exponentially, the prior mass of "Bad" states (error above 1/8) does decay as exp(−nε²). The proof compares the integral PGM's output to an auxiliary Bernoulli register.

- Pinsker's inequality bounds the error by a relative entropy.

- The relative entropy is bounded by a data-processing gap Δ_x, using a log-derivative property of the integral PGM.

- The gap is controlled by a telescoping argument based on a Laplace-estimator redundancy bound.

A median or boosting step then amplifies the success probability. The paper also gives a useful negative-results narrative.

The natural PGM decay conjecture is false.

The Barnum–Knill-type bound fails for approximate parameter estimation.

The remaining log(m) factor is an inherent obstacle of the approach: the PGM amplifies over the prior but not over measurement randomness.

Methodological Rigor

This is a pure theory paper, and the proofs are self-contained and appear correct on a careful read.

Lemma 3.2 follows from operator concavity of log and the derivative identity. Lemmas 4.7 and 4.8 are clean. Lemma 4.9 telescopes over the random copy count, which is why the algorithm samples n at random. Lemma 4.10 combines entropic identities with the Mourtada–Gaïffas redundancy bound. The appendix boosting is a standard multiplicative-weights argument.

The reduction through minimax is standard, though it implicitly requires discretizing or compactifying the state and POVM spaces. The paper does not belabor this.

The paper is honest about limitations: the random-n trick and the use of the integral PGM instead of the standard one are acknowledged as possible proof artifacts. The worst-case algorithm is non-constructive, with no efficiency claim; an SDP over POVMs exists in principle but would be enormous.

The disclosure that the proofs were produced by generative AI and then verified and polished by humans is unusual. The proofs are checkable and appear sound, so provenance does not lower rigor. It does raise the question of whether the proofs are fully vetted, but the written arguments are transparent.

Potential Impact

Theory: this is a major advance in quantum learning theory and quantum data analysis. It shows that the cost of non-commutativity is at most a logarithmic factor in the offline setting, answering a central question the introduction poses.

Technique: the average-case-plus-minimax template, together with the Bad-set decay phenomenon, is likely to be reused. Likely uses include:

- tomography variants;

- learning properties of states;

- quantum random access codes;

- multi-hypothesis testing.

Open directions: it also opens clear follow-ups: removing the extra log(m), finding constructive or efficient algorithms, and understanding PGM behavior more generally.

Practical: practical impact is minimal near term. The algorithm is non-constructive and requires entangled measurements across about log(m)/ε² copies. The sample complexity is, however, a meaningful benchmark.

Meta-impact: the paper may be remembered as a documented case of AI-discovered research-level proofs in theoretical computer science and quantum information. This adds attention beyond the technical result.

Timeliness

Shadow tomography has been an active area since 2018, with a recent flurry of progress (COPW26, Sinha, the concurrent Jeronimo–Huang–Liu result). A dimension-free polylog(m) bound is a long-sought milestone. The concurrent independent derivation of the same bound confirms both the importance and the correctness of the target. Because another group reached the same bound, the incremental priority advantage is diluted somewhat, but the cleaner algorithm and proof give this paper separate value.

Strengths

It solves a flagship open problem nearly optimally.

The method is conceptually clean and conceptually new.

The paper is clear about what fails and why, which has pedagogical value.

The proofs are short enough to verify.

The matching lower-bound discussion for the MSE and the identification of the obstruction add insight.

Limitations

A log(m) gap to optimal remains, and the paper itself says the approach appears bottlenecked there.

The result is non-constructive and gives no efficient algorithm.

Entangled measurements across many copies are needed.

The worst-case guarantee does not preserve any online or observable-independent structure. Classical-shadows-style lower bounds are consistent with the result only because the measurement depends on the hard prior.

The proof depends on technical choices: randomized copy count and the integral PGM.

There are no experiments, which is appropriate for the paper type.

The background section is long and somewhat narrative, though readable.

Overall

This is a high-impact theoretical result in quantum learning with a novel proof strategy. It is very likely to be widely cited, and the main techniques are reusable.

Rating:9/ 10

Significance 9Rigor 8.5Novelty 9Clarity 7.5

Generated Oct 6, 2026

Comparison History (0)

No comparisons yet.

Scorecard· 15/16

9.0/10 impact

Near-optimal, dimension-free shadow tomography via a genuinely new average-case PGM plus minimax route, resolving a flagship open problem up to one log factor.