How Many Copies Does Pretty Good Shadow Tomography Need to Estimate Observables?

The copy count is dimension-free and polylogarithmic in m

The central result is a sample-complexity bound: O(log(m) log(m/δ) / ε²) copies of the input state ρ suffice to output estimates of tr(O_i ρ) for every i in [m] that are all accurate to within ±ε, except with probability at most δ. The bound depends on the number of observables m, the accuracy ε, and the failure probability δ — but not on the dimension d of the state.

That dimension-free property is the headline. The paper states that this is the first dimension-free shadow tomography algorithm with only polylogarithmic dependence on m. Before this work, the best dimension-free bound was O(√m / ε²) copies, attributed to COPW26, which itself improved an earlier O(√m log(m) / ε²) bound of Sinha. The new bound replaces √m with log²(m), a qualitative change in how the cost scales with the number of observables.

Non-commuting observables block naive sample reuse

The difficulty the paper addresses is the cost of non-commutativity. When ρ is a classical distribution, the same samples can be reused to estimate every observable, requiring only O(log(m/δ) / ε²) samples, where the log(m) comes from a union bound. For a general quantum state, measuring one observable can disturb the state and prevent measuring the rest.

The paper quantifies the naive alternatives: a straightforward algorithm uses O(m log(m/δ) / ε²) copies, while running full tomography requires O(d² / ε²) copies. Shadow tomography sits between these, and the question is how far the quantum cost can be pushed toward the classical O(log(m/δ) / ε²) baseline. The paper notes that no lower bound stronger than Ω(log(m/δ) / ε²) is known, so the exact gap remains open.

The algorithm solves the average case before the worst case

The key idea is to depart from prior work and study shadow tomography in the average case, where the input state is drawn from a known prior. Formally, the unknown state is promised to belong to a known family F = {ρ_1, …, ρ_ℓ} with a known prior p = (p_1, …, p_ℓ); the input ρ = ρ_x is obtained by drawing x ∼ p. The algorithm must succeed with probability at least 1 − δ over both the random choice of ρ from the prior and the randomness of the measurement.

Working in the average case gives access to tools defined with respect to a prior — most importantly the pretty good measurement (PGM), a canonical measurement first designed for quantum state discrimination. The paper proves an average-case theorem: there is an algorithm for the average-case shadow tomography problem that consumes O(log(m) log(m/δ) / ε²) copies of the input state.

The mechanism is described in the abstract: for a random state drawn from a known prior, a pretty good measurement on O(log(m) / ε²) copies gives a constant-error guarantee on all but a small fraction of the prior. Boosting this guarantee yields the average-case algorithm.

The minimax principle converts the average-case bound

The worst-case result follows from the average-case theorem by Sion's minimax theorem, which generalizes the classical minimax theorem of von Neumann. The paper's proof of its main theorem is stated as a direct consequence: apply the average-case theorem for every prior, then apply the minimax theorem.

This step is fundamentally non-constructive. The minimax theorem only tells us that an algorithm exists; it does not give an explicit description of one. The paper notes that the minimax measurement can in principle be found constructively by solving a semidefinite program over POVMs, but that this does not give an especially illuminating algorithm.

The paper frames this non-constructiveness as a possible strength. A major obstacle to designing shadow tomography algorithms is that we do not understand what a hard instance looks like for a given set of observables. The average-case formulation avoids identifying the hardest prior: the algorithm is proved to work for every prior, and the minimax theorem converts those guarantees into a worst-case guarantee without ever identifying which prior is hardest.

An inherent obstruction leaves one log(m) factor

The paper also identifies 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 the measurement. The paper states that this issue appears to be inherent, and that it gives rise to the remaining log(m) factor separating the complexity of the quantum problem from its classical counterpart.

This is the paper's own explanation of why the approach appears bottlenecked at log²(m). It is a statement about the limits of this method, not a proven lower bound on shadow tomography itself — the paper separately notes that no lower bound stronger than Ω(log(m/δ) / ε²) is known.

Where the new bound wins against prior algorithms

With constant δ, the paper summarizes the best-known bounds for shadow tomography as three regimes. First, O(log(m) / ε²) copies suffice in the high-precision regime ε ≲ 1/d. Second, O(log(m) √log(d) / ε³) copies suffice, which for ε ≳ 1/d gives the best known bound when √log(d) / ε ≲ log(m). Third, O(log²(m) / ε²) copies suffice by this work, which for ε ≳ 1/d gives the best known bound when √log(d) / ε ≳ log(m).

The comparison is therefore regime-dependent rather than a uniform improvement. The new algorithm's advantage appears in the regime where the dimension-dependent term √log(d) / ε grows relative to log(m), and its defining feature is the complete absence of d from the copy count.

Variance bounds do not settle the shadow tomography rate

The paper distinguishes its problem from a statistical formulation of the cost of non-commutativity. In that formulation, given observables O_1, …, O_m and n copies of ρ, one computes unbiased estimators and asks how the total variance scales as C/n + o(1/n). Results there indicate the cost of non-commutativity is at most a factor of 2: the variance can be as large as m for commuting observables but is at most 2m for non-commuting observables. This factor of two was first described by Nagaoka and Hayashi in the single-copy setting and later extended to multi-copy settings, and it matches the gap between the Quantum Cramér–Rao bound and the Holevo–Cramér–Rao bound.

The paper argues these formulations are substantially different. Shadow tomography demands control of higher moments, because the desired log(m) scaling comes from demonstrating an exponential tail on the estimator distribution. Even though the cost of non-commutativity is a constant factor for variances, it need not be the same for shadow tomography — so the factor-of-two variance result does not bound the shadow tomography copy count.

Read the result as a regime-specific improvement

The most decision-relevant reading is a comparison across regimes, not a single number. If your setting has many observables m and a dimension-dependent term √log(d) / ε that is large relative to log(m), this algorithm's O(log²(m) / ε²) copies is the best known bound and it carries no d dependence at all. If instead ε ≲ 1/d, the O(log(m) / ε²) high-precision bound is better, and if √log(d) / ε ≲ log(m), the O(log(m) √log(d) / ε³) bound is better.

Two boundaries qualify that reading. The worst-case algorithm is non-constructive: the minimax step establishes existence, and an explicit algorithm would require solving a semidefinite program over POVMs. And the paper's own obstruction — that pretty good measurements amplify over prior randomness but not over measurement randomness — is presented as the reason this approach stops at log²(m), so the remaining log(m) gap to the classical O(log(m/δ) / ε²) baseline is not closed here. The paper also discloses that the main result was developed through heavy interaction with generative A.I. models, with the proofs generated by the models themselves.

Sources used in this answer