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.
The ability of quantum computers to directly manipulate and analyze quantum states stored in quantum memory allows them to learn about aspects of our physical world that would otherwise be invisible given a modest number of measurements. Here we investigate a new learning resource, which could be available to quantum computers in the future—measurements on the unknown state accompanied by its complex conjugate ρ ⊗ ρ ∗ . For a certain shadow tomography task, we surprisingly find that measurements on only copies of ρ ⊗ ρ ∗ can be exponentially more powerful than measurements on ρ ⊗ K , even for large K . This expands the class of provable exponential advantages using only a constant overhead quantum memory, or minimal quantum memory, and we provide a number of examples where the state ρ ∗ is naturally available in both computational and physical applications. In addition, we precisely quantify the power of classical shadows on single copies under a generalized Clifford ensemble and give a class of quantities that can be efficiently learned. The learning task we study in both the single copy and quantum memory settings is physically natural and corresponds to real-space observables with a limit of bosonic modes, where it achieves an exponential improvement in detecting certain signals under a noisy background. We quantify a new and powerful resource in quantum learning, and we believe the advantage may find applications in improving quantum simulation, learning from quantum sensors, and uncovering new physical phenomena. Published by the American Physical Society 2024
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.
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.
Inferring nonlinear features of quantum states is fundamentally important across quantum information science, but remains challenging due to the intrinsic linearity of quantum mechanics. It is widely recognized that quantum memory and coherent operations help avoid exponential sample complexity, by mapping nonlinear properties onto linear observables over multiple copies of the target state. In this work, we prove that such a conversion is not only sufficient but also necessary. Specifically, we prove that the estimation of
tr(ρkO) for a broad class of observables
O is exponentially hard for any protocol restricted to
(k−1)-replica joint measurements, whereas access to one additional replica reduces the complexity to a constant. These results establish, for the first time, an exponential separation between
(k−1)- and
k-replica protocols for any integer
k>2, thereby introducing a fine-grained hierarchy of replica-based quantum advantage and resolving an open question in the literature. The technical core is a general indistinguishability principle showing that any ensemble constructed from large Haar random states via tensor products and mixtures is hard to distinguish from its average. Leveraging this principle, we further prove that
k-replica joint measurements are also necessary for distinguishing rank-
k density matrices from rank-
(k−1) ones. Overall, our work delineates sharp boundaries on the power of joint measurements, highlighting resource-complexity trade-offs in quantum learning theory and deepening the understanding of quantum mechanics' intrinsic linearity.
In recent years there has been significant interest in understanding the statistical complexity of learning from quantum data under the constraint that one can only make unentangled measurements. While a key challenge in establishing tight lower bounds in this setting is to deal with the fact that the measurements can be chosen in an adaptive fashion, a recurring theme has been that adaptivity offers little advantage over more straightforward, nonadaptive protocols. In this note, we offer a counterpoint to this. We show that for the basic task of shadow tomography, protocols that use adaptively chosen two-copy measurements can be exponentially more sample-efficient than any protocol that uses nonadaptive two-copy measurements.