Classical shadow tomography is widely touted as supplying a family of methods for extracting information from quantum systems with polynomially scaling sample-complexities. In the current era of quantum computers possessing on the order of hundreds of qubits, however, polynomial scaling can nonetheless be prohibitive. Thus, there is a strong practical need for obtaining sample-complexity bounds which are as tight as possible. Here we address this in the case of fermionic (matchgate) shadows. For an arbitrary observable $O$ of Majorana degree $2k$, we improve the previously known sample-complexity bound of $\mathcal{O}(n^{2k}\|O\|_\infty^2)$ to $\mathcal{O}(n^{k}\|O\|_\infty^2)$, which is asymptotically tight. For example, for the estimation of the energy per mode of an open fermionic 50-site Hubbard chain with hopping and on site strenghts respectively given by $t=1$, $V=4$, and for a target additive precision of 0.1, this reduces the number of required shots from $\sim 10^9$ to $\sim 10^5$. That is, the new bound reduces the required number of shots by approximately $99.98\%$.
AI Summary
Matchgate classical shadows estimate fermionic observables with polynomial shot complexity, but existing bounds for general low-degree observables can be much larger than those for individual Majorana monomials. This paper tightens the worst-case variance bounds without changing the measurement protocol.
For a homogeneous degree-$2k$ observable $O$, with $0\leq k\leq n/2$, it proves $\operatorname{Var}(\hat o)\leq 3\|O\|_\infty^2/(2a_{n,k})$, where $a_{n,k}=\binom nk/\binom{2n}{2k}$. For fixed $k$, this replaces the previous $O(n^{2k}\|O\|_\infty^2)$ bound by $O(n^k\|O\|_\infty^2)$, matching the worst-case scaling of a single Majorana monomial. For $O=\sum_{k=1}^K O_{2k}$, a triangle-inequality extension bounds the variance by $\frac32(\sum_k\|O_{2k}\|_\infty/\sqrt{a_{n,k}})^2$.
The proof replaces Haar-random matchgates by a Clifford matchgate 3-design and expresses second moments through survival probabilities under random perfect matchings of Majorana indices. A signed combination of positive unital channels, constructed using Krawtchouk polynomials, beta-prime moments, and Gaussian quadrature, supplies the operator-norm bound.
For energy per mode in a 50-site, 100-mode open Hubbard chain with $t=1$ and $V=4$, the new variance bound is $6542$, versus at least $4.3\times10^7$ from the earlier bound. This compares guarantees, not measured shot requirements. The factor $3/2$ is suspected to be removable; extension to other shadow protocols remains unclear. Measurement-circuit depth remains a separate implementation constraint, particularly on one-dimensional nearest-neighbour hardware.
No sign of AI-generated text
Error found: The Hubbard example's stated variance bounds give approximately 6.54×10^5 versus 4.27×10^9 after multiplication by ε^{-2}, so the abstract's shot figures omit appreciable numerical factors, although its percentage reduction is consistent.
Equation (sc) incorrectly assigns a variance-only, logarithmic-confidence guarantee to the ordinary empirical average without supplying the additional concentration argument or robust estimator needed to justify it.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
Classical shadow tomography is widely touted as supplying a family of methods for extracting information from quantum systems with polynomially scaling sample-complexities. In the current era of quantum computers possessing on the order of hundreds of qubits, however, polynomial scaling can nonetheless be prohibitive. Thus, there is a strong practical need for obtaining sample-complexity bounds which are as tight as possible. Here we address this in the case of fermionic (matchgate) shadows. For an arbitrary observable O of Majorana degree 2k, we improve the previously known sample-complexity bound of O(n2k∥O∥∞2) to O(nk∥O∥∞2), which is asymptotically tight. For example, for the estimation of the energy per mode of an open fermionic 50-site Hubbard chain with hopping and on site strenghts respectively given by t=1, V=4, and for a target additive precision of 0.1, this reduces the number of required shots from ∼109 to ∼105. That is, the new bound reduces the required number of shots by approximately 99.98%.
Matchgate classical shadows estimate fermionic observables with polynomial shot complexity, but existing bounds for general low-degree observables can be much larger than those for individual Majorana monomials. This paper tightens the worst-case variance bounds without changing the measurement protocol.
For a homogeneous degree-2k observable O, with 0≤k≤n/2, it proves Var(o^)≤3∥O∥∞2/(2an,k), where an,k=(kn)/(2k2n). For fixed k, this replaces the previous O(n2k∥O∥∞2) bound by O(nk∥O∥∞2), matching the worst-case scaling of a single Majorana monomial. For O=∑k=1KO2k, a triangle-inequality extension bounds the variance by 23(∑k∥O2k∥∞/an,k)2.
The proof replaces Haar-random matchgates by a Clifford matchgate 3-design and expresses second moments through survival probabilities under random perfect matchings of Majorana indices. A signed combination of positive unital channels, constructed using Krawtchouk polynomials, beta-prime moments, and Gaussian quadrature, supplies the operator-norm bound.
For energy per mode in a 50-site, 100-mode open Hubbard chain with t=1 and V=4, the new variance bound is 6542, versus at least 4.3×107 from the earlier bound. This compares guarantees, not measured shot requirements. The factor 3/2 is suspected to be removable; extension to other shadow protocols remains unclear. Measurement-circuit depth remains a separate implementation constraint, particularly on one-dimensional nearest-neighbour hardware.
We consider the problem of learning expectation values of particle-preserving operators with respect to an unknown η-particle n-mode fermionic state via classical shadows. Our main application is to estimating overlaps with arbitrary Slater determinant states: While it is known that such overlaps can, in the average case, be learnt to a fixed additive precision with a constant number of samples, the best-known worst case bound is O(nlogn); here we improve this to O(ηlogη), achieving a mode-independent sample cost. Our procedure is also computationally efficient, requiring only classical post-processing which for a generic dense orbital runs in time O(nη2). For the task of estimating the expectation value of a general particle-preserving quadratic fermionic observable h, we prove a sample complexity bound of O(η∥h0∥22), where h0 is the traceless component of h; the associated classical post-processing scales as O(n2η). Finally, we discuss implementation of the required randomization: in a first-quantized encoding, approximate unitary designs give circuit depths polylogarithmic in the number of modes, contrasting with linear-depth requirements for nearest-neighbor second-quantized matchgate implementations. On the technical side, our proof reduces the extremal shadow variance to harmonic analysis on the AIII symmetric space U(n)/(U(η)×U(n−η)) and evaluates the resulting integral using techniques from the theories of Jacobi ensembles and orthogonal polynomials, in a calculation which may be of independent interest.
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 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.
Shadow tomography has appeared as a powerful tool for estimating observables on quantum computers from a small number of samples. We show that shadow-tomography-inspired ideas can offer similarly improved sample scaling for estimating observables on tensor network states on classical computers after proper adaptation. We develop strategies for both spin (bosonic) and fermionic systems, tailored to the contraction requirements of tensor networks, and generate scaling improvements of factors of O(N) to O(N3) (where N is system size), depending on the specific task and system type. For the important and difficult task of evaluating the expectation value of long-range interacting Hamiltonians, we achieve the optimal O(1) overall scaling (up to logarithmic factors) for an arbitrarily fixed relative Monte Carlo error in both spin and fermionic systems. Additionally, we show that shadow estimators offer more stable gradients of observables in variational optimization tasks than standard Monte Carlo estimators. We demonstrate practical advantage by simulating systems with long-range interactions, including the 2D long-range Heisenberg model and an ab-initio quantum chemistry Hamiltonian.
Predicting local fermionic correlations is a central task in quantum many-body physics, as these correlations encode many physically relevant local observables. The ubiquitous particle-number symmetry imposes strong structural constraints on quantum states, suggesting that local correlations should be learned with fewer samples than by symmetry-agnostic approaches. However, it has remained unclear whether such a provable advantage exists in collective learning of local correlations. Here, we develop a framework of number-conserving fermionic-shadow tomography based on random orbital rotations. We prove that, for every given order k, we can simultaneously estimate all k-body fermionic correlations of an N-mode η-particle state with a given variance ε2 using only Ok(ηk/ε2) samples, which are independent of the system size N. We further establish a matching information-theoretic lower bound Ωk(ηk/ε2) for any adaptive protocol based on single-copy measurements, showing that the (ηk,ε)-dependence is optimal up to constants depending only on k. Furthermore, numerical studies show a 20-fold query reduction for one-body correlation estimation at N=200, η=20, and ε=10−2, compared with the best alternative including Heisenberg-limited estimation methods. Relative to fermionic Gaussian-unitary shadows, sample costs for the square-lattice Fermi-Hubbard model at N=288 are reduced by factors of 148 for energy density and 161 for spin structure factor estimation. For molecular energy derivatives with respect to atomic coordinates, our method reduces sample requirements by factors of 53 for Cr2 and 18.5 for [Fe2S2]2− at N=128. These results demonstrate the practical advantage of particle-number symmetry for fermionic observable estimation.
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.