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:2610.06781

Pretty good shadow tomography

Sabee Grewal, Angelos Pelecanos, Jack Spilecki, Ewin Tang, John Wright

quant-phSubmitted Oct 5, 2026• Announced Oct 6, 2026• 1 citation
arXivHTMLPDF

Abstract

We give a shadow tomography algorithm that uses $O(\log(m) \log(m/δ) / \varepsilon^2)$ copies of the input state. Specifically, given a quantum state $ρ$ and observables $O_1,\ldots,O_m$, the algorithm outputs estimates of $\mathrm{tr}(O_iρ)$ for all $i\in[m]$ that are all accurate to within $\pm\varepsilon$, except with probability at most $δ$. The key idea is to work in the average-case setting: for a random state drawn from a known prior, a pretty good measurement on $O(\log(m)/\varepsilon^2)$ copies gives a constant-error guarantee on all but a small fraction of the prior. Boosting this guarantee gives an average-case shadow tomography algorithm, and the minimax principle then (non-constructively) implies the existence of a measurement with the same worst-case guarantee. We also identify an obstruction to further improvement with this approach. While pretty good measurements amplify success over the randomness of the prior, they do not amplify success over the randomness of measurement. This issue appears to be inherent, and gives rise to the remaining $\log(m)$ factor separating the complexity of the quantum problem from its classical counterpart.

AI Summary

Shadow tomography asks how many copies of an unknown quantum state $\rho$ are needed to estimate $m$ bounded observables simultaneously to additive error $\varepsilon$, with total failure probability at most $\delta$. The paper establishes a copy bound of $O(\log(m)\log(m/\delta)/\varepsilon^2)$, independent of the Hilbert-space dimension $d$. For constant failure probability, this is $O(\log^2(m)/\varepsilon^2)$, compared with the previously known dimension-dependent bound $O(\log(m)\sqrt{\log(d)}/\varepsilon^3)$ and dimension-free bound $O(\sqrt m/\varepsilon^2)$. The argument first treats states drawn from an arbitrary known prior. An integral pretty good measurement, applied to a randomized number of copies, estimates each observable with constant conditional error on all but an exponentially small fraction of the prior. The proof relates prediction error to relative-entropy loss when auxiliary Bernoulli measurement outcomes are discarded, then bounds this loss through data processing and a telescoping information argument. Reweighting the prior and taking coordinatewise medians amplifies the guarantee. Minimax then yields a measurement with the same worst-case copy complexity. The worst-case construction is nonconstructive, and the result does not establish computational or experimental efficiency. A factor of $\log m$ remains above the classical sample bound. Counterexamples show that ordinary PGM prediction errors need not decay exponentially, obstructing a direct route to closing this gap; whether randomizing the copy count is necessary remains unclear. Concurrent work is reported to attain the same bound using related techniques.

Almost certainly largely AI-generatedAI use disclosed
The main result was developed through heavy interaction with generative A.I.\ models, with the proofs generated by the models themselves; the analysis presented here was modified to add conceptual clarity.

Error found: The abstract omits the bounded-observable assumption required for its dimension-independent additive-error copy bound. The asserted polynomial-decay tensor-product counterexample underlying the PGM obstruction discussion is not constructed or proved in the supplied text. The randomized integral-PGM lemma's proof requires k = ceil(48/ε²), rather than its stated ceil(12/ε²), when extended to general norm-one observables by the paper's reduction.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
32 pages, comments welcome

Related papers

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

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

quant-pharXiv:2512.05451•Dec 8, 2025•2 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.

quant-pharXiv:2607.29686•Aug 3, 2026•4 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

Dimension Independent and Computationally Efficient Shadow Tomography

Pulkit Sinha

We describe a new shadow tomography algorithm that uses n =Θ(√ m log m /є 2 ) samples, for m measurements and additive error є, which is independent of the dimension of the quantum state being learned. This stands in contrast to all previously known algorithms that improve upon the naive approach. The sample complexity also has optimal dependence on є. Due to its dimension independent nature, this algorithm has the best known sample complexity in the regime m = o (log 2 d ) (when є is chosen independently from d ). Additionally, this algorithm is efficient in various aspects, including quantum memory usage (possibly even O (1)), gate complexity, classical computation, all of which are also do not have any dimension dependence. This algorithm is also robust against qubit measurement noise, by which we mean that the qubit measurement errors can only affect the accuracy of the estimates, and small noise leads to small additive error in the estimates. Apart from this, the algorithm can be modified to also be implementable as a read-once quantum circuit with low quantum memory usage, i.e., it will hold only one copy of ρ in memory, and discard it before asking for a new one, with the additional quantum memory needed being O ( m log n ) qubits. Our approach builds on the idea of using noisy measurements, but instead of focusing on gentleness in trace distance, we focus on the gentleness in shadows, i.e., we show that the noisy measurements do not significantly perturb the expected values. To work with this, we think of noisy measurements as measuring a noisy encoding of the quantity we are trying to noisily measure. In our case, these are the observables corresponding to sample means of the m POVMs. We see that the product state structure of the samples is effectively maintained (with possibly some additional randomness) even after the creation and tracing out of the specific noisy encodings we work with.

arXiv:2411.01420•ACM Symposium on Theory of Computing (STOC)•Jun 15, 2025•4 citations

Post-processing optimization and optimal bounds for non-adaptive shadow tomography

Andrea Caprotti, Joshua Morris, Borivoje Dakić

Informationally overcomplete POVMs are known to outperform minimally complete measurements in many tomography and estimation tasks, and they also leave a purely classical freedom in shadow tomography: the same observable admits infinitely many unbiased linear reconstructions from identical measurement data. We formulate the choice of reconstruction coefficients as a convex minimax problem and give an algorithm with guaranteed convergence that returns the tightest state-independent variance bound achievable by post-processing for a fixed POVM and observable. Numerical examples show that the resulting estimators can dramatically reduce sampling complexity relative to standard (canonical) reconstructions, and can even improve the qualitative scaling with system size for structured noncommuting targets.

quant-pharXiv:2601.16266•Jan 26, 2026•1 citation
We give a shadow tomography algorithm that uses O(log⁡(m)log⁡(m/δ)/ε2)O(\log(m) \log(m/δ) / \varepsilon^2)O(log(m)log(m/δ)/ε2) copies of the input state. Specifically, given a quantum state ρρρ and observables O1,…,OmO_1,\ldots,O_mO1​,…,Om​, the algorithm outputs estimates of tr(Oiρ)\mathrm{tr}(O_iρ)tr(Oi​ρ) for all i∈[m]i\in[m]i∈[m] that are all accurate to within ±ε\pm\varepsilon±ε, except with probability at most δδδ. The key idea is to work in the average-case setting: for a random state drawn from a known prior, a pretty good measurement on O(log⁡(m)/ε2)O(\log(m)/\varepsilon^2)O(log(m)/ε2) copies gives a constant-error guarantee on all but a small fraction of the prior. Boosting this guarantee gives an average-case shadow tomography algorithm, and the minimax principle then (non-constructively) implies the existence of a measurement with the same worst-case guarantee.
We also identify an obstruction to further improvement with this approach. While pretty good measurements amplify success over the randomness of the prior, they do not amplify success over the randomness of measurement. This issue appears to be inherent, and gives rise to the remaining log⁡(m)\log(m)log(m) factor separating the complexity of the quantum problem from its classical counterpart.
Shadow tomography asks how many copies of an unknown quantum state ρ\rhoρ are needed to estimate mmm bounded observables simultaneously to additive error ε\varepsilonε, with total failure probability at most δ\deltaδ. The paper establishes a copy bound of O(log⁡(m)log⁡(m/δ)/ε2)O(\log(m)\log(m/\delta)/\varepsilon^2)O(log(m)log(m/δ)/ε2), independent of the Hilbert-space dimension ddd. For constant failure probability, this is O(log⁡2(m)/ε2)O(\log^2(m)/\varepsilon^2)O(log2(m)/ε2), compared with the previously known dimension-dependent bound O(log⁡(m)log⁡(d)/ε3)O(\log(m)\sqrt{\log(d)}/\varepsilon^3)O(log(m)log(d)​/ε3) and dimension-free bound O(m/ε2)O(\sqrt m/\varepsilon^2)O(m​/ε2).
The argument first treats states drawn from an arbitrary known prior. An integral pretty good measurement, applied to a randomized number of copies, estimates each observable with constant conditional error on all but an exponentially small fraction of the prior. The proof relates prediction error to relative-entropy loss when auxiliary Bernoulli measurement outcomes are discarded, then bounds this loss through data processing and a telescoping information argument. Reweighting the prior and taking coordinatewise medians amplifies the guarantee. Minimax then yields a measurement with the same worst-case copy complexity.
The worst-case construction is nonconstructive, and the result does not establish computational or experimental efficiency. A factor of log⁡m\log mlogm remains above the classical sample bound. Counterexamples show that ordinary PGM prediction errors need not decay exponentially, obstructing a direct route to closing this gap; whether randomizing the copy count is necessary remains unclear. Concurrent work is reported to attain the same bound using related techniques.
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.
We study single-copy shadow tomography in the adversarial robust setting, where the goal is to learn the expectation values of MMM observables O1,…,OMO_1, \ldots, O_MO1​,…,OM​ 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 ε=Ω~(γmin⁡{M,d})\varepsilon=\tildeΩ(γ\min\{\sqrt{M}, \sqrt{d}\})ε=Ω~(γmin{M​,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 ε=O~(γmax⁡i∈[M]∥Oi∥HS)\varepsilon=\tilde{O}(γ\max_{i\in[M]}\|O_i\|_{HS})ε=O~(γmaxi∈[M]​∥Oi​∥HS​), which nearly matches our worst-case error lower bound for M≥dM\ge dM≥d and guarantees better accuracy when the observables have stronger structure. Remarkably, the algorithm only needs n=1γ2log⁡(M/δ)n=\frac{1}{γ^2}\log(M/δ)n=γ21​log(M/δ) copies to achieve that error with probability at least 1−δ1-δ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 rrr states, both the near-optimal asymptotic error of ε=O~(γr)\varepsilon=\tilde{O}(γ\sqrt{r})ε=O~(γr​) and copy complexity O~(dr2/ε2)=O~(dr/γ2)\tilde{O}(dr^2/\varepsilon^2)=\tilde{O}(dr/γ^2)O~(dr2/ε2)=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 ddd.
In Online Shadow Tomography, we are given copies of an unknown ddd-dimensional quantum state ρρρ, an adversary (adaptively) proposes a sequence of bounded observables A(1),…,A(m)A^{(1)},\ldots,A^{(m)}A(1),…,A(m), and after each A(t)A^{(t)}A(t) is given we must estimate Tr(A(t)ρ)\mathrm{Tr}(A^{(t)}ρ)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,εm, d, ε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⁡2m)o(\log^2 m)o(log2m)-dependence together with poly(log⁡(d)/ε)\mathrm{poly}(\log(d)/ε)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 ddd, and improves the best prior result by a mlog⁡m\sqrt{m} \log mm​logm factor. The key to our proof is a new framework for quantifying post-measurement damage, based on the quantum Efron-Stein decomposition.
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 describe a new shadow tomography algorithm that uses n =Θ(√ m log m /є 2 ) samples, for m measurements and additive error є, which is independent of the dimension of the quantum state being learned. This stands in contrast to all previously known algorithms that improve upon the naive approach. The sample complexity also has optimal dependence on є. Due to its dimension independent nature, this algorithm has the best known sample complexity in the regime m = o (log 2 d ) (when є is chosen independently from d ). Additionally, this algorithm is efficient in various aspects, including quantum memory usage (possibly even O (1)), gate complexity, classical computation, all of which are also do not have any dimension dependence. This algorithm is also robust against qubit measurement noise, by which we mean that the qubit measurement errors can only affect the accuracy of the estimates, and small noise leads to small additive error in the estimates. Apart from this, the algorithm can be modified to also be implementable as a read-once quantum circuit with low quantum memory usage, i.e., it will hold only one copy of ρ in memory, and discard it before asking for a new one, with the additional quantum memory needed being O ( m log n ) qubits. Our approach builds on the idea of using noisy measurements, but instead of focusing on gentleness in trace distance, we focus on the gentleness in shadows, i.e., we show that the noisy measurements do not significantly perturb the expected values. To work with this, we think of noisy measurements as measuring a noisy encoding of the quantity we are trying to noisily measure. In our case, these are the observables corresponding to sample means of the m POVMs. We see that the product state structure of the samples is effectively maintained (with possibly some additional randomness) even after the creation and tracing out of the specific noisy encodings we work with.
Informationally overcomplete POVMs are known to outperform minimally complete measurements in many tomography and estimation tasks, and they also leave a purely classical freedom in shadow tomography: the same observable admits infinitely many unbiased linear reconstructions from identical measurement data. We formulate the choice of reconstruction coefficients as a convex minimax problem and give an algorithm with guaranteed convergence that returns the tightest state-independent variance bound achievable by post-processing for a fixed POVM and observable. Numerical examples show that the resulting estimators can dramatically reduce sampling complexity relative to standard (canonical) reconstructions, and can even improve the qualitative scaling with system size for structured noncommuting targets.