arXiv:2407.13874

Optimal high-precision shadow estimation

Sitan Chen, Jerry Zheng Li, Allen Liu

Published Jul 18, 2024• 0 citations

Abstract

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.

DOI: 10.48550/arxiv.2407.13874

Related papers

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

Senrui Chen, Weiyuan Gong, Sisi Zhou

quant-pharXiv:2602.04952Feb 6, 20260 citations

Dimension-Free Polylogarithmic Quantum Shadow Tomography

Fernando Granha Jeronimo, Qizhao Huang, Lenny Liu

quant-pharXiv:2608.06345Aug 7, 20260 citations

Online Shadow Tomography Matching the Classical Bounds

Sitan Chen, Ryan O'Donnell, Angelos Pelecanos +1 more

quant-pharXiv:2607.29686Aug 3, 20260 citations

Shadow Tomography Against Adversaries

Maryam Aliakbarpour, Vladimir Braverman, Nai-Hui Chia +4 more

quant-pharXiv:2512.05451Dec 8, 20250 citations

Practical fermionic shadows enabled by improved sample-complexity bounds

Maxwell West, Su Yeon Chang, Luke Coffman +2 more

quant-pharXiv:2609.40173Oct 1, 20260 citations

Optimal classical shadow estimation of unitary channels at Heisenberg limit

Entong He, Zihao Li, Noam Scully +2 more

quant-pharXiv:2606.13638Jun 12, 20260 citations

arXiv:2407.13874

Optimal high-precision shadow estimation

Sitan Chen, Jerry Zheng Li, Allen Liu

Published Jul 18, 2024• 0 citations

arXiv HTML PDF

Abstract

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.

DOI: 10.48550/arxiv.2407.13874

Related papers

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.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.04952Feb 6, 20260 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.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.06345Aug 7, 20260 citations

Online Shadow Tomography Matching the Classical Bounds

Sitan Chen, Ryan O'Donnell, Angelos Pelecanos +1 more

In Online Shadow Tomography, we are given copies of an unknown $d$ -dimensional quantum state $ρ$ , an adversary (adaptively) proposes a sequence of bounded observables $A^{(1)},\ldots,A^{(m)}$ , and after each $A^{(t)}$ is given we must estimate $\mathrm{Tr}(A^{(t)}ρ)$ to within $\pm ε$ . This is the direct quantum generalization of the classical problem of Adaptive Data Analysis. Prior results for online Shadow Tomography were suboptimal in all three parameters $m, d, ε$ , lagging behind the best known and classical rates, for which there is some evidence of optimality. In this work, we finally close this gap, giving a pair of algorithms matching the classical rates. Our first algorithm is the first to achieve $o(\log^2 m)$ -dependence together with $\mathrm{poly}(\log(d)/ε)$ ; moreover, it improves all three exponents even in the Offline Shadow Tomography setting. Our second algorithm is known to be optimal among bounds independent of $d$ , and improves the best prior result by a $\sqrt{m} \log m$ factor. The key to our proof is a new framework for quantifying post-measurement damage, based on the quantum Efron-Stein decomposition.In Online Shadow Tomography, we are given copies of an unknown $d$-dimensional quantum state $ρ$, an adversary (adaptively) proposes a sequence of bounded observables $A^{(1)},\ldots,A^{(m)}$, and after each $A^{(t)}$ is given we must estimate $\mathrm{Tr}(A^{(t)}ρ)$ to within $\pm ε$. This is the direct quantum generalization of the classical problem of Adaptive Data Analysis. Prior results for online Shadow Tomography were suboptimal in all three parameters $m, d, ε$, lagging behind the best known and classical rates, for which there is some evidence of optimality. In this work, we finally close this gap, giving a pair of algorithms matching the classical rates. Our first algorithm is the first to achieve $o(\log^2 m)$-dependence together with $\mathrm{poly}(\log(d)/ε)$; moreover, it improves all three exponents even in the Offline Shadow Tomography setting. Our second algorithm is known to be optimal among bounds independent of $d$, and improves the best prior result by a $\sqrt{m} \log m$ factor. The key to our proof is a new framework for quantifying post-measurement damage, based on the quantum Efron-Stein decomposition.

quant-pharXiv:2607.29686Aug 3, 20260 citations

Shadow Tomography Against Adversaries

Maryam Aliakbarpour, Vladimir Braverman, Nai-Hui Chia +4 more

We study single-copy shadow tomography in the adversarial robust setting, where the goal is to learn the expectation values of $M$ observables $O_1, \ldots, O_M$ with $\varepsilon$ 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 $\varepsilon=\tildeΩ(γ\min\{\sqrt{M}, \sqrt{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 $\varepsilon=\tilde{O}(γ\max_{i\in[M]}\|O_i\|_{HS})$ , which nearly matches our worst-case error lower bound for $M\ge d$ and guarantees better accuracy when the observables have stronger structure. Remarkably, the algorithm only needs $n=\frac{1}{γ^2}\log(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 $\varepsilon=\tilde{O}(γ\sqrt{r})$ and copy complexity $\tilde{O}(dr^2/\varepsilon^2)=\tilde{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 study single-copy shadow tomography in the adversarial robust setting, where the goal is to learn the expectation values of $M$ observables $O_1, \ldots, O_M$ with $\varepsilon$ 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 $\varepsilon=\tildeΩ(γ\min\{\sqrt{M}, \sqrt{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 $\varepsilon=\tilde{O}(γ\max_{i\in[M]}\|O_i\|_{HS})$, which nearly matches our worst-case error lower bound for $M\ge d$ and guarantees better accuracy when the observables have stronger structure. Remarkably, the algorithm only needs $n=\frac{1}{γ^2}\log(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 $\varepsilon=\tilde{O}(γ\sqrt{r})$ and copy complexity $\tilde{O}(dr^2/\varepsilon^2)=\tilde{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$.

quant-pharXiv:2512.05451Dec 8, 20250 citations

Practical fermionic shadows enabled by improved sample-complexity bounds

Maxwell West, Su Yeon Chang, Luke Coffman +2 more

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\%$ .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\%$.

quant-pharXiv:2609.40173Oct 1, 20260 citations

Optimal classical shadow estimation of unitary channels at Heisenberg limit

Entong He, Zihao Li, Noam Scully +2 more

Full tomography of an unknown quantum evolution is resource-intensive and often unnecessary when the goal is only to predict selected properties. This motivates the study of classical shadow estimation of unitary channels (CSEU), a task in which one queries an unknown $d$ -dimensional unitary $U$ and stores classical data that can later be used to predict expectation values $\mathrm{tr}[O UρU^\dagger]$ for arbitrary input states $ρ$ and observables $O$ . Here we propose a parallel and non-adaptive CSEU protocol that uses $\mathcal{O}(\min\{d\varepsilon^{-2},d^{3/2}\varepsilon^{-1}\})$ queries to $U$ when the observables have constant effective size. This achieves Heisenberg scaling with respect to the additive error $\varepsilon$ and is query-optimal, as we prove a matching lower bound $Ω(\min\{d\varepsilon^{-2},d^{3/2}\varepsilon^{-1}\})$ for the query complexity, which remains valid even when stronger access to the unknown unitary is available. Our CSEU protocol is a versatile primitive with applications to several quantum learning tasks. In particular, it yields a near-optimal algorithm for learning an arbitrary Hamiltonian from its real-time evolution in the high-precision regime and recovers the best-known bounds for several tasks in a unified way.Full tomography of an unknown quantum evolution is resource-intensive and often unnecessary when the goal is only to predict selected properties. This motivates the study of classical shadow estimation of unitary channels (CSEU), a task in which one queries an unknown $d$-dimensional unitary $U$ and stores classical data that can later be used to predict expectation values $\mathrm{tr}[O UρU^\dagger]$ for arbitrary input states $ρ$ and observables $O$. Here we propose a parallel and non-adaptive CSEU protocol that uses $\mathcal{O}(\min\{d\varepsilon^{-2},d^{3/2}\varepsilon^{-1}\})$ queries to $U$ when the observables have constant effective size. This achieves Heisenberg scaling with respect to the additive error $\varepsilon$ and is query-optimal, as we prove a matching lower bound $Ω(\min\{d\varepsilon^{-2},d^{3/2}\varepsilon^{-1}\})$ for the query complexity, which remains valid even when stronger access to the unknown unitary is available. Our CSEU protocol is a versatile primitive with applications to several quantum learning tasks. In particular, it yields a near-optimal algorithm for learning an arbitrary Hamiltonian from its real-time evolution in the high-precision regime and recovers the best-known bounds for several tasks in a unified way.

quant-pharXiv:2606.13638Jun 12, 20260 citations

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.

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

ε

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.

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.

In Online Shadow Tomography, we are given copies of an unknown

d

-dimensional quantum state

ρ

, an adversary (adaptively) proposes a sequence of bounded observables

A^{(1)},\ldots,A^{(m)}

, and after each

A^{(t)}

is given we must estimate

\mathrm{Tr}(A^{(t)}ρ)

to within

\pm ε

. This is the direct quantum generalization of the classical problem of Adaptive Data Analysis. Prior results for online Shadow Tomography were suboptimal in all three parameters

m, d, ε

, lagging behind the best known and classical rates, for which there is some evidence of optimality. In this work, we finally close this gap, giving a pair of algorithms matching the classical rates. Our first algorithm is the first to achieve

o(\log^2 m)

-dependence together with

\mathrm{poly}(\log(d)/ε)

; moreover, it improves all three exponents even in the Offline Shadow Tomography setting. Our second algorithm is known to be optimal among bounds independent of

d

, and improves the best prior result by a

\sqrt{m} \log m

factor. The key to our proof is a new framework for quantifying post-measurement damage, based on the quantum Efron-Stein decomposition.

We study single-copy shadow tomography in the adversarial robust setting, where the goal is to learn the expectation values of

M

observables

O_1, \ldots, O_M

with

\varepsilon

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

\varepsilon=\tildeΩ(γ\min\{\sqrt{M}, \sqrt{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

\varepsilon=\tilde{O}(γ\max_{i\in[M]}\|O_i\|_{HS})

, which nearly matches our worst-case error lower bound for

M\ge d

and guarantees better accuracy when the observables have stronger structure. Remarkably, the algorithm only needs

n=\frac{1}{γ^2}\log(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

\varepsilon=\tilde{O}(γ\sqrt{r})

and copy complexity

\tilde{O}(dr^2/\varepsilon^2)=\tilde{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

O

of Majorana degree

2k

, we improve the previously known sample-complexity bound of

\mathcal{O}(n^{2k}\|O\|_\infty^2)

\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

\sim 10^5

. That is, the new bound reduces the required number of shots by approximately

99.98\%

d

-dimensional unitary

U

and stores classical data that can later be used to predict expectation values

\mathrm{tr}[O UρU^\dagger]

for arbitrary input states

ρ

and observables

O

. Here we propose a parallel and non-adaptive CSEU protocol that uses

\mathcal{O}(\min\{d\varepsilon^{-2},d^{3/2}\varepsilon^{-1}\})

queries to

U

when the observables have constant effective size. This achieves Heisenberg scaling with respect to the additive error

\varepsilon

and is query-optimal, as we prove a matching lower bound

Ω(\min\{d\varepsilon^{-2},d^{3/2}\varepsilon^{-1}\})

for the query complexity, which remains valid even when stronger access to the unknown unitary is available. Our CSEU protocol is a versatile primitive with applications to several quantum learning tasks. In particular, it yields a near-optimal algorithm for learning an arbitrary Hamiltonian from its real-time evolution in the high-precision regime and recovers the best-known bounds for several tasks in a unified way.