Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.40173

Practical fermionic shadows enabled by improved sample-complexity bounds

Maxwell West, Su Yeon Chang, Luke Coffman, Martin Larocca, M. Cerezo

quant-phSubmitted Sep 30, 2026• Announced Oct 1, 2026• 3 citations
arXivHTMLPDF

Abstract

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.

Related papers

Particle-preserving fermionic shadows with mode-independent sample complexity

Maxwell West, M. Cerezo, Martin Larocca

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 $\mathcal{O}(\sqrt n \log n)$; here we improve this to $\mathcal{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 $\mathcal{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 $\mathcal{O}(η\|h_0\|_2^2)$, where $h_0$ is the traceless component of $h$; the associated classical post-processing scales as $\mathcal{O}(n^2η)$. 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(η)\times 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.

quant-pharXiv:2606.27254•Jun 26, 2026•10 citations

Instance-optimal high-precision shadow tomography with few-copy measurements: A metrological approach

Senrui Chen, Weiyuan Gong, Sisi Zhou

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 $\{O_i\}_{i=1}^m$, the goal is to estimate expectation values $\{\mathrm{tr}(O_iρ)\}_{i=1}^m$ to accuracy $ε$ in $L_p$-norm, using possibly adaptive measurements that act on $O(\mathrm{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 $\tildeΘ(Γ_p/ε^2)$, where $Γ_p$ is a function of $\{O_i\}_{i=1}^m$ 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_\infty$-norm error. Concretely, we first analyze a simpler oblivious variant where the goal is to estimate an observable of the form $\sum_{i=1}^m α_i O_i$ with $\|α\|_q = 1$ (where $q$ is dual to $p$) revealed after the measurement. For single-copy measurements, we obtain a sample complexity of $Θ(Γ^{\mathrm{ob}}_p/ε^2)$. We then show $\tildeΘ(Γ_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, $Γ^{\mathrm{ob}}_\infty = Γ_\infty$. 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.

quant-pharXiv:2602.04952•Feb 6, 2026•10 citations

Optimal high-precision shadow estimation

Sitan Chen, Jerry Zheng Li, Allen Liu

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\in\mathbb{N}$ and $ε\le O(d^{-12})$, measures $O(\log(m)/ε^2)$ copies of an unknown mixed state $ρ\in\mathbb{C}^{d\times 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 $ε\le O(d^{-1/2})$. Our algorithm draws upon representation-theoretic tools recently developed in the context of full state tomography.

arXiv:2407.13874•Jul 18, 2024•15 citations

Shadow tomography for classical tensor network simulations

Jiace Sun, Garnet Kin-Lic Chan

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(N^{3})$ (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.

quant-pharXiv:2606.29133•Jun 30, 2026•0 citations

Provably Efficient Learning of Fermionic Correlations under Particle-Number Symmetry

Yuki Koizumi, Kaito Wada, Toshinori P. Takama +1 more

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 $\varepsilon^2$ using only $O_k(η^k/\varepsilon^2)$ samples, which are independent of the system size $N$. We further establish a matching information-theoretic lower bound $Ω_k(η^k/\varepsilon^2)$ for any adaptive protocol based on single-copy measurements, showing that the $(η^k,\varepsilon)$-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 $\varepsilon=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 $\mathrm{Cr}_2$ and $18.5$ for $[\mathrm{Fe}_2\mathrm{S}_2]^{2-}$ at $N=128$. These results demonstrate the practical advantage of particle-number symmetry for fermionic observable estimation.

quant-pharXiv:2606.30601•Jun 30, 2026•5 citations

Dimension-Free Polylogarithmic Quantum Shadow Tomography

Fernando Granha Jeronimo, Qizhao Huang, Lenny Liu

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 $E_1,\ldots,E_M$, the goal is to estimate all expectation values $\{\text{Tr}(ρE_i)\}_{i=1}^M$ to additive accuracy $\varepsilon$ 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\left( \frac{\log(M)\log(M/δ)}{\varepsilon^2} \right), \] 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.

quant-pharXiv:2608.06345•Aug 7, 2026•6 citations
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 OOO of Majorana degree 2k2k2k, we improve the previously known sample-complexity bound of O(n2k∥O∥∞2)\mathcal{O}(n^{2k}\|O\|_\infty^2)O(n2k∥O∥∞2​) to O(nk∥O∥∞2)\mathcal{O}(n^{k}\|O\|_\infty^2)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=1t=1t=1, V=4V=4V=4, and for a target additive precision of 0.1, this reduces the number of required shots from ∼109\sim 10^9∼109 to ∼105\sim 10^5∼105. That is, the new bound reduces the required number of shots by approximately 99.98%99.98\%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-2k2k2k observable OOO, with 0≤k≤n/20\leq k\leq n/20≤k≤n/2, it proves Var⁡(o^)≤3∥O∥∞2/(2an,k)\operatorname{Var}(\hat o)\leq 3\|O\|_\infty^2/(2a_{n,k})Var(o^)≤3∥O∥∞2​/(2an,k​), where an,k=(nk)/(2n2k)a_{n,k}=\binom nk/\binom{2n}{2k}an,k​=(kn​)/(2k2n​). For fixed kkk, this replaces the previous O(n2k∥O∥∞2)O(n^{2k}\|O\|_\infty^2)O(n2k∥O∥∞2​) bound by O(nk∥O∥∞2)O(n^k\|O\|_\infty^2)O(nk∥O∥∞2​), matching the worst-case scaling of a single Majorana monomial. For O=∑k=1KO2kO=\sum_{k=1}^K O_{2k}O=∑k=1K​O2k​, a triangle-inequality extension bounds the variance by 32(∑k∥O2k∥∞/an,k)2\frac32(\sum_k\|O_{2k}\|_\infty/\sqrt{a_{n,k}})^223​(∑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=1t=1t=1 and V=4V=4V=4, the new variance bound is 654265426542, versus at least 4.3×1074.3\times10^74.3×107 from the earlier bound. This compares guarantees, not measured shot requirements. The factor 3/23/23/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 nnn-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(nlog⁡n)\mathcal{O}(\sqrt n \log n)O(n​logn); here we improve this to O(ηlog⁡η)\mathcal{O}(η\logη)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)\mathcal{O}(nη^2)O(nη2). For the task of estimating the expectation value of a general particle-preserving quadratic fermionic observable hhh, we prove a sample complexity bound of O(η∥h0∥22)\mathcal{O}(η\|h_0\|_2^2)O(η∥h0​∥22​), where h0h_0h0​ is the traceless component of hhh; the associated classical post-processing scales as O(n2η)\mathcal{O}(n^2η)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−η))U(n)/(U(η)\times U(n-η))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 ddd-dimensional quantum state ρρρ and a known set of observables {Oi}i=1m\{O_i\}_{i=1}^m{Oi​}i=1m​, the goal is to estimate expectation values {tr(Oiρ)}i=1m\{\mathrm{tr}(O_iρ)\}_{i=1}^m{tr(Oi​ρ)}i=1m​ to accuracy εεε in LpL_pLp​-norm, using possibly adaptive measurements that act on O(polylog(d))O(\mathrm{polylog}(d))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)\tildeΘ(Γ_p/ε^2)Θ~(Γp​/ε2), where ΓpΓ_pΓp​ is a function of {Oi}i=1m\{O_i\}_{i=1}^m{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∞L_\inftyL∞​-norm error. Concretely, we first analyze a simpler oblivious variant where the goal is to estimate an observable of the form ∑i=1mαiOi\sum_{i=1}^m α_i O_i∑i=1m​αi​Oi​ with ∥α∥q=1\|α\|_q = 1∥α∥q​=1 (where qqq is dual to ppp) revealed after the measurement. For single-copy measurements, we obtain a sample complexity of Θ(Γpob/ε2)Θ(Γ^{\mathrm{ob}}_p/ε^2)Θ(Γpob​/ε2). We then show Θ~(Γp/ε2)\tildeΘ(Γ_p/ε^2)Θ~(Γ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=Γ∞Γ^{\mathrm{ob}}_\infty = Γ_\inftyΓ∞ob​=Γ∞​. In both cases, allowing ccc-copy measurements improves the sample complexity by at most Ω(1/c)Ω(1/c)Ω(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∈Nm\in\mathbb{N}m∈N and ε≤O(d−12)ε\le O(d^{-12})ε≤O(d−12), measures O(log⁡(m)/ε2)O(\log(m)/ε^2)O(log(m)/ε2) copies of an unknown mixed state ρ∈Cd×dρ\in\mathbb{C}^{d\times d}ρ∈Cd×d and outputs a classical description of ρρρ which can then be used to estimate any collection of mmm observables to within additive accuracy εεε. Previously, even for the simpler task of shadow tomography -- where the mmm observables are known in advance -- the best known rates either scaled benignly but suboptimally in all of m,d,εm, d, εm,d,ε, or scaled optimally in ε,mε, mε,m but had additional polynomial factors in ddd for general observables. Intriguingly, we also show via dimensionality reduction, that we can rescale εεε and ddd to reduce to the regime where ε≤O(d−1/2)ε\le O(d^{-1/2})ε≤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)O(N)O(N) to O(N3)O(N^{3})O(N3) (where NNN 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)O(1)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 kkk, we can simultaneously estimate all kkk-body fermionic correlations of an NNN-mode ηηη-particle state with a given variance ε2\varepsilon^2ε2 using only Ok(ηk/ε2)O_k(η^k/\varepsilon^2)Ok​(ηk/ε2) samples, which are independent of the system size NNN. We further establish a matching information-theoretic lower bound Ωk(ηk/ε2)Ω_k(η^k/\varepsilon^2)Ωk​(ηk/ε2) for any adaptive protocol based on single-copy measurements, showing that the (ηk,ε)(η^k,\varepsilon)(ηk,ε)-dependence is optimal up to constants depending only on kkk. Furthermore, numerical studies show a 20-fold query reduction for one-body correlation estimation at N=200N=200N=200, η=20η=20η=20, and ε=10−2\varepsilon=10^{-2}ε=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=288N=288N=288 are reduced by factors of 148148148 for energy density and 161161161 for spin structure factor estimation. For molecular energy derivatives with respect to atomic coordinates, our method reduces sample requirements by factors of 535353 for Cr2\mathrm{Cr}_2Cr2​ and 18.518.518.5 for [Fe2S2]2−[\mathrm{Fe}_2\mathrm{S}_2]^{2-}[Fe2​S2​]2− at N=128N=128N=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 ddd-dimensional quantum state ρρρ and a known collection of observables E1,…,EME_1,\ldots,E_ME1​,…,EM​, the goal is to estimate all expectation values {Tr(ρEi)}i=1M\{\text{Tr}(ρE_i)\}_{i=1}^M{Tr(ρEi​)}i=1M​ to additive accuracy ε\varepsilonε with probability at least 1−δ1-δ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 MMM, 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(log⁡(M)log⁡(M/δ)ε2), O\left( \frac{\log(M)\log(M/δ)}{\varepsilon^2} \right), 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.