We investigate the problem of efficiently estimating expectation values of large sets of observables from copies of an unknown many-body quantum state. This task, known as shadow tomography, is crucial for quantum simulation and quantum chemistry, where the relevant observables often include k -body fermionic or k -local Pauli operators. A key goal is to achieve sample efficiency, computational efficiency, and few-copy measurements. We introduce the notion of triply efficient shadow tomography to formalize these requirements. Prior work has shown that single-copy measurements suffice for k -local Pauli operators with constant k . However, we prove that for k -body fermionic observables and the full set of n -qubit Pauli operators, single-copy protocols fail to achieve sample-efficient tomography. We then present new protocols based on measuring two copies of the state at a time that overcome these lower bounds, providing a triply efficient protocol.
Given copies of a quantum state ρ, a shadow tomography protocol aims to learn all expectation values from a fixed set of observables, to within a given precision ε. We say that a shadow tomography protocol is triply efficient if it is sample- and time-efficient, and only employs measurements that entangle a constant number of copies of ρ at a time. The classical shadows protocol based on random single-copy measurements is triply efficient for the set of local Pauli observables. This and other protocols based on random singlecopy Clifford measurements can be understood as arising from fractional colorings of a graph G that encodes the commutation structure of the set of observables. Here we describe a framework for two-copy shadow tomography that uses an initial round of Bell measurements to reduce to a fractional coloring problem in an induced subgraph of G with bounded clique number. This coloring problem can be addressed using techniques from graph theory known as chi-boundedness. Using this framework we give the first triply efficient shadow tomography scheme for the set of local fermionic observables, which arise in a broad class of interacting fermionic systems in physics and chemistry. We also give a triply efficient scheme for the set of all n-qubit Pauli observables. Our protocols for these tasks use two-copy measurements, which is necessary: sample- efficient schemes are provably impossible using only single-copy measurements. Finally, we give a shadow tomography protocol that compresses an n-qubit quantum state into a poly(n )-sized classical representation, from which one can extract the expected value of any of the 4n Pauli observables in poly(n ) time, up to a small constant error.
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.
Shadow tomography addresses the task of efficiently predicting many expectation values of an unknown quantum state from randomized measurements on comparatively few copies. Existing analyses promise large scaling advantages, but the optimal strategies realizing these guarantees are not always known, and the required measurements are potentially challenging to implement on current hardware. We address this gap for Pauli observables by computing optimal sample-complexity parameters and constructing optimal measurement strategies under realistic resource constraints. We focus on memoryless protocols, where each copy is measured only once, and on measurements with bounded interaction range. Our approach reduces the problem to the analysis of graph parameters of the frustration graph encoding the Pauli anticommutation relations. We provide efficient numerical methods for the general case and analytically prove that Clifford measurements are optimal in many situations. This includes all perfect graphs, all single-qubit, all two-qubit measurement scenarios, and more. Applied to Hamiltonian energy estimation, our framework yields constructive strategies and improved variance bounds for molecular benchmarks.
Shadow tomography protocols have recently emerged as powerful tools for efficient quantum state learning, aiming to reconstruct expectation values of observables with considerably fewer resources than traditional quantum state tomography. For the particular case of estimating Pauli observables, entangling two-copy measurement schemes can offer an exponential improvement in sample complexity over any single-copy strategy conceivable [1, Huang, Kueng, Preskill, PRL (2021)]. A recent refinement of these ideas by King et al. [2, King, Gosset, Kothari, Babbush, SODA (2025)] does not only achieve polynomial sample complexity, but also maintains reasonable computational demands and utilizes joint measurements on only a small constant number of state copies. This 'triple efficiency' is achievable for any subset of
n-qubit Pauli observables, whereas single-copy strategies can only be efficient if the Pauli observables in question have advantageous structure. In this work, we complement existing theoretical performance guarantees with the empirical evaluation of triply efficient shadow tomography using classical, noise-free simulations. Our findings indicate that the empirical sample complexity aligns closely with theoretical predictions for stabilizer states and, notably, demonstrates slightly improved scaling for random Gibbs states compared to established theoretical bounds. In addition, we improve a central subroutine in the triply-efficient shadow protocol by leveraging insights from a refined quantum and quantum-inspired convex optimization algorithm [3, Henze et al. arXiv:2502.15426 (2025)] [Henze et al. arXiv:2502.15426 (2025)]. To summarize, our empirical sample complexity studies of triply efficient shadow tomography not only confirm existing theoretical scaling behavior, but also showcase that the actual constants involved are comparatively benign. Hence, this protocol has the potential to also be very sample-efficient in practice.
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.
Quantum shadow tomography based on the classical shadow representation provides an efficient way to estimate properties of an unknown quantum state without performing a full quantum state tomography. In scenarios where estimating the expectation values for only certain classes of observables is required, obtaining information about the entire density matrix is unnecessary. We propose a partial quantum shadow tomography protocol that estimates a subset of density matrix elements relevant to the expectation values of structured observables. Specifically, we identify specific subsets of the tomographically complete set
Cl(2)⊗n and a simple pseudo-inverse of the associated channel, which can be used to estimate all elements of the density matrix with the same active order. By restricting the protocol to smaller subsets of single-qubit Pauli measurements, it becomes experimentally more efficient. We demonstrate the advantage over unitary designs, such as the Clifford, full Pauli basis, and methods utilizing mutually unbiased bases, by analytically deriving error bounds and numerically evaluating the protocol on structured operators. We experimentally demonstrate the partial shadow estimation scheme for a wide class of two-qubit states (pure, entangled, and mixed) in the nuclear magnetic resonance (NMR) platform. The full density matrix, reconstructed experimentally by combining different partial estimators, achieves fidelities around 99%.