We describe a new shadow tomography algorithm that uses n =Θ(√ m log m /є 2 ) samples, for m measurements and additive error є, which is independent of the dimension of the quantum state being learned. This stands in contrast to all previously known algorithms that improve upon the naive approach. The sample complexity also has optimal dependence on є. Due to its dimension independent nature, this algorithm has the best known sample complexity in the regime m = o (log 2 d ) (when є is chosen independently from d ). Additionally, this algorithm is efficient in various aspects, including quantum memory usage (possibly even O (1)), gate complexity, classical computation, all of which are also do not have any dimension dependence. This algorithm is also robust against qubit measurement noise, by which we mean that the qubit measurement errors can only affect the accuracy of the estimates, and small noise leads to small additive error in the estimates. Apart from this, the algorithm can be modified to also be implementable as a read-once quantum circuit with low quantum memory usage, i.e., it will hold only one copy of ρ in memory, and discard it before asking for a new one, with the additional quantum memory needed being O ( m log n ) qubits. Our approach builds on the idea of using noisy measurements, but instead of focusing on gentleness in trace distance, we focus on the gentleness in shadows, i.e., we show that the noisy measurements do not significantly perturb the expected values. To work with this, we think of noisy measurements as measuring a noisy encoding of the quantity we are trying to noisily measure. In our case, these are the observables corresponding to sample means of the m POVMs. We see that the product state structure of the samples is effectively maintained (with possibly some additional randomness) even after the creation and tracing out of the specific noisy encodings we work with.
We describe a new shadow tomography algorithm that uses n =Θ(√ m log m /є 2 ) samples, for m measurements and additive error є, which is independent of the dimension of the quantum state being learned. This stands in contrast to all previously known algorithms that improve upon the naive approach. The sample complexity also has optimal dependence on є. Due to its dimension independent nature, this algorithm has the best known sample complexity in the regime m = o (log 2 d ) (when є is chosen independently from d ). Additionally, this algorithm is efficient in various aspects, including quantum memory usage (possibly even O (1)), gate complexity, classical computation, all of which are also do not have any dimension dependence. This algorithm is also robust against qubit measurement noise, by which we mean that the qubit measurement errors can only affect the accuracy of the estimates, and small noise leads to small additive error in the estimates. Apart from this, the algorithm can be modified to also be implementable as a read-once quantum circuit with low quantum memory usage, i.e., it will hold only one copy of ρ in memory, and discard it before asking for a new one, with the additional quantum memory needed being O ( m log n ) qubits. Our approach builds on the idea of using noisy measurements, but instead of focusing on gentleness in trace distance, we focus on the gentleness in shadows, i.e., we show that the noisy measurements do not significantly perturb the expected values. To work with this, we think of noisy measurements as measuring a noisy encoding of the quantity we are trying to noisily measure. In our case, these are the observables corresponding to sample means of the m POVMs. We see that the product state structure of the samples is effectively maintained (with possibly some additional randomness) even after the creation and tracing out of the specific noisy encodings we work with.
We study the sample complexity of shadow tomography in the high-precision regime under realistic measurement constraints. Given an unknown d-dimensional quantum state ρ and a known set of observables {Oi}i=1m, the goal is to estimate expectation values {tr(Oiρ)}i=1m to accuracy ε in Lp-norm, using possibly adaptive measurements that act on O(polylog(d)) number of copies of ρ at a time. We focus on the regime where ε is below an instance-dependent threshold.
Our main contribution is an instance-optimal characterization of the sample complexity as Θ~(Γp/ε2), where Γp is a function of {Oi}i=1m defined via an optimization formula involving the inverse Fisher information matrix. Previously, tight bounds were known only in special cases, e.g. Pauli shadow tomography with L∞-norm error. Concretely, we first analyze a simpler oblivious variant where the goal is to estimate an observable of the form ∑i=1mαiOi with ∥α∥q=1 (where q is dual to p) revealed after the measurement. For single-copy measurements, we obtain a sample complexity of Θ(Γpob/ε2). We then show Θ~(Γp/ε2) is necessary and sufficient for the original problem, with the lower bound applying to unbiased, bounded estimators. Our upper bounds rely on a two-step algorithm combining coarse tomography with local estimation. Notably, Γ∞ob=Γ∞. In both cases, allowing c-copy measurements improves the sample complexity by at most Ω(1/c).
Our results establish a quantitative correspondence between quantum learning and metrology, unifying asymptotic metrological limits with finite-sample learning guarantees.
Shadow Tomography is a fundamental problem in quantum information theory. Given multiple copies of an unknown d-dimensional quantum state ρ and a known collection of observables E1,…,EM, the goal is to estimate all expectation values {Tr(ρEi)}i=1M to additive accuracy ε with probability at least 1−δ.
An elusive open question from the seminal shadow tomography work of Aaronson is whether this task admits a dimension-independent sample complexity with only polylogarithmic dependence on M, as suggested by the best-known lower bounds. In this work, we propose two different quantum protocols for shadow tomography with the best sample complexity O(ε2log(M)log(M/δ)), which is polylogarithmic in the number of observables and independent of the dimension of the unknown state, thereby answering Aaronson's original question while also providing an exponential improvement in the prior best dimension independent sample complexity of shadow tomography from Sinha (STOC 2025) and, more recently, Chen, O'Donnell, Pelecanos, and Wright.
Our approach first reduces the general shadow tomography problem to a finite-ensemble estimation problem via a minimax argument. We then develop an observable-independent protocol that repeatedly applies the pretty-good measurement while updating the prior distribution over the finite ensemble according to the measurement outcomes. A tail analysis of the resulting estimation error yields simultaneous accuracy guarantees for all observables and a cubic-logarithmic upper bound. We also introduce a refined recovery-label measurement for the same finite ensemble, which yields the bound in our main theorem.
We study the problems of quantum tomography and shadow tomography using measurements performed on individual, identical copies of an unknown d -dimensional state. We first revisit known lower bounds [ 23 ] on quantum tomography with accuracy ε in trace distance, when the measurement choices are independent of previously observed outcomes, i.e., they are nonadaptive. We give a succinct proof of these results through the χ 2 -divergence between suitable distributions. Unlike prior work, we do not require that the measurements be given by rank-one operators. This leads to stronger lower bounds when the learner uses measurements with a constant number of outcomes (e.g., two-outcome measurements). In particular, this rigorously establishes the optimality of the folklore “Pauli tomography” algorithm in terms of its sample complexity. We also derive novel bounds of Ω(r2d/ϵ2) and Ω(r2d2/ϵ2) for learning rank r states using arbitrary and constant-outcome measurements, respectively, in the nonadaptive case. In addition to the sample complexity, a resource of practical significance for learning quantum states is the number of unique measurement settings required (i.e., the number of different measurements used by an algorithm, each possibly with an arbitrary number of outcomes). Motivated by this consideration, we employ concentration of measure of χ 2 -divergence of suitable distributions to extend our lower bounds to the case where the learner performs possibly adaptive measurements from a fixed set of exp(O(d)) possible measurements. This implies in particular that adaptivity does not give us any advantage using single-copy measurements that are efficiently implementable. We also obtain a similar bound in the case where the goal is to predict the expectation values of a given sequence of observables, a task known as shadow tomography. Finally, in the case of adaptive, single-copy measurements implementable with polynomial-size circuits, we prove that a straightforward strategy based on computing sample means of the given observables is optimal.
We introduce a technique to estimate error-mitigated expectation values on noisy quantum computers. Our technique performs shadow tomography on a logical state to produce a memory-efficient classical reconstruction of the noisy density matrix. Using efficient classical post-processing, one can mitigate errors by projecting a general nonlinear function of the noisy density matrix into the codespace. The subspace expansion and virtual distillation can be viewed as special cases of the new framekwork. We show our method is favorable in the quantum and classical resources overhead. Relative to subspace expansion which requires O(2N) samples to estimate a logical Pauli observable with [[N,k]] error correction code, our technique requires only O(4k) samples. Relative to virtual distillation, our technique can compute powers of the density matrix without additional copies of quantum states or quantum memory. We present numerical evidence using logical states encoded with up to sixty physical qubits and show fast convergence to error-free expectation values with only 105 samples under 1% depolarizing noise.
We study single-copy shadow tomography in the adversarial robust setting, where the goal is to learn the expectation values of M observables O1,…,OM with ε accuracy, but γ-fraction of the outcomes can be arbitrarily corrupted by an adversary. We show that all non-adaptive shadow tomography algorithms must incur an error of ε=Ω~(γmin{M,d}) for some choice of observables, even with unlimited copies. Unfortunately, the classical shadows algorithm by [HKP20] and naive algorithms that directly measure each observable suffer even more. We design an algorithm that achieves an error of ε=O~(γmaxi∈[M]∥Oi∥HS), which nearly matches our worst-case error lower bound for M≥d and guarantees better accuracy when the observables have stronger structure. Remarkably, the algorithm only needs n=γ21log(M/δ) copies to achieve that error with probability at least 1−δ, matching the sample complexity of the classical shadows algorithm that achieves the same error without corrupted measurement outcomes. Our algorithm is conceptually simple and easy to implement. Classical simulation for fidelity estimation shows that our algorithm enjoys much stronger robustness than [HKP20] under adversarial noise. Finally, based on a reduction from full-state tomography to shadow tomography, we prove that for rank r states, both the near-optimal asymptotic error of ε=O~(γr) and copy complexity O~(dr2/ε2)=O~(dr/γ2) can be achieved for adversarially robust state tomography, closing the large gap in [ABCL25] where optimal error can only be achieved using pseudo-polynomial number of copies in d.
We give the first tight sample complexity bounds for shadow tomography and classical shadows in the regime where the target error is below some sufficiently small inverse polynomial in the dimension of the Hilbert space. Formally we give a protocol that, given any m∈N and ε≤O(d−12), measures O(log(m)/ε2) copies of an unknown mixed state ρ∈Cd×d and outputs a classical description of ρ which can then be used to estimate any collection of m observables to within additive accuracy ε. Previously, even for the simpler task of shadow tomography -- where the m observables are known in advance -- the best known rates either scaled benignly but suboptimally in all of m,d,ε, or scaled optimally in ε,m but had additional polynomial factors in d for general observables. Intriguingly, we also show via dimensionality reduction, that we can rescale ε and d to reduce to the regime where ε≤O(d−1/2). Our algorithm draws upon representation-theoretic tools recently developed in the context of full state tomography.