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

Optimal strategies for shadow tomography with limited resources

Zhen-Peng Xu, Qi Ye, Jie Wang, Gereon Koßmann, Andreas Winter, René Schwonnek

quant-phSubmitted Aug 9, 2026• Announced Aug 11, 2026• 3 citations
arXivHTMLPDF

Abstract

Shadow tomography addresses the task of efficiently predicting many expectation values of an unknown quantum state from randomized measurements on comparatively few copies. Existing analyses promise large scaling advantages, but the optimal strategies realizing these guarantees are not always known, and the required measurements are potentially challenging to implement on current hardware. We address this gap for Pauli observables by computing optimal sample-complexity parameters and constructing optimal measurement strategies under realistic resource constraints. We focus on memoryless protocols, where each copy is measured only once, and on measurements with bounded interaction range. Our approach reduces the problem to the analysis of graph parameters of the frustration graph encoding the Pauli anticommutation relations. We provide efficient numerical methods for the general case and analytically prove that Clifford measurements are optimal in many situations. This includes all perfect graphs, all single-qubit, all two-qubit measurement scenarios, and more. Applied to Hamiltonian energy estimation, our framework yields constructive strategies and improved variance bounds for molecular benchmarks.

Comments
5+14 pages, comments are highly welcome

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.

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

Triply efficient shadow tomography

Robbie King, David Gosset, Robin Kothari +1 more

Given copies of a quantum state ρ, a shadow tomography protocol aims to learn all expectation values from a fixed set of observables, to within a given precision ε. We say that a shadow tomography protocol is triply efficient if it is sample- and time-efficient, and only employs measurements that entangle a constant number of copies of ρ at a time. The classical shadows protocol based on random single-copy measurements is triply efficient for the set of local Pauli observables. This and other protocols based on random singlecopy Clifford measurements can be understood as arising from fractional colorings of a graph G that encodes the commutation structure of the set of observables. Here we describe a framework for two-copy shadow tomography that uses an initial round of Bell measurements to reduce to a fractional coloring problem in an induced subgraph of G with bounded clique number. This coloring problem can be addressed using techniques from graph theory known as chi-boundedness. Using this framework we give the first triply efficient shadow tomography scheme for the set of local fermionic observables, which arise in a broad class of interacting fermionic systems in physics and chemistry. We also give a triply efficient scheme for the set of all n-qubit Pauli observables. Our protocols for these tasks use two-copy measurements, which is necessary: sample- efficient schemes are provably impossible using only single-copy measurements. Finally, we give a shadow tomography protocol that compresses an n-qubit quantum state into a poly(n )-sized classical representation, from which one can extract the expected value of any of the 4n Pauli observables in poly(n ) time, up to a small constant error.

Society for Industrial and Applied Mathematics eBooks•Jan 1, 2025•11 citations

Triply Efficient Shadow Tomography

Robbie King, David Gosset, Robin Kothari +1 more

We investigate the problem of efficiently estimating expectation values of large sets of observables from copies of an unknown many-body quantum state. This task, known as shadow tomography, is crucial for quantum simulation and quantum chemistry, where the relevant observables often include k -body fermionic or k -local Pauli operators. A key goal is to achieve sample efficiency, computational efficiency, and few-copy measurements. We introduce the notion of triply efficient shadow tomography to formalize these requirements. Prior work has shown that single-copy measurements suffice for k -local Pauli operators with constant k . However, we prove that for k -body fermionic observables and the full set of n -qubit Pauli operators, single-copy protocols fail to achieve sample-efficient tomography. We then present new protocols based on measuring two copies of the state at a time that overcome these lower bounds, providing a triply efficient protocol.

arXiv:2404.19211•PRX Quantum•Feb 27, 2025•54 citations

Variance reduction methods in the estimation of Pauli sums

Søren Fuglede Jørgensen, Rafael Emilio Barfknecht, Patrick Ettenhuber +1 more

Accurately estimating expectation values of quantum observables with as few measurements as possible is crucial to many quantum computing applications. We introduce a framework that covers many of existing measurement strategies and introduce heuristics that can be used to enhance randomized schemes, including those based on Pauli grouping with inverse probability weighting and variants of the classical shadow algorithm. We show how to maximize information gain from such schemes, while carefully optimizing the distribution of possible measurements, and show that simple grouping algorithms can get close to, and in some cases exceed, state-of-the-art accuracy for unbiased estimation of expectation values on a standard quantum chemistry benchmark. We show how these randomized methods may be compared to more recent measurement schemes, such as shadow grouping, derandomized shadow, and overlapped grouping measurement, we show how the same strategies can be used to augment these schemes, and we demonstrate that we can reduce measurement costs by up to a factor of two by allowing Clifford measurement circuits for otherwise Clifford-less methods.

quant-pharXiv:2603.20029•Mar 23, 2026•0 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

Optimal Tradeoffs for Estimating Pauli Observables

Sitan Chen, Weiyuan Gong, Qi Ye

We revisit the problem of Pauli shadow tomography: given copies of an unknown n-qubit quantum state$\rho$, estimate Tr$(P\rho)$for some set of Pauli operators$F$to within additive error$\epsilon$. This has been a popular testbed for exploring the advantage of protocols with quantum memory over those without: with enough memory to measure two copies at a time, one can use Bell sampling to estimate$\vert \text{Tr}(P\rho)$for all$P$using$O(n/\epsilon^{4})$copies, but with$k\leq n$qubits of memory,$\Omega(2^{(n-k)/3})$copies are needed. These results leave open several natural questions. How does this picture change in the physically relevant setting where one only needs to estimate a certain subset of Paulis? What is the optimal dependence on$\epsilon ?$What is the optimal tradeoff between quantum memory and sample complexity? We answer all of these questions: •For any subset$A$of Paulis and any family of measurement strategies, we completely characterize the optimal sample complexity, up to$\log\vert A\vert$factors. •We show any protocol that makes poly$(n)$-copy measure-ments must make$\Omega(1/\epsilon^{4})$measurements. •For any protocol that makes poly$(n)$-copy measurements and only has$k < n$qubits of memory, we show that$\tilde{\Theta}(\min\{2^{n}/\epsilon^{2},2^{n-k}/\epsilon^{4}\})$copies are necessary and sufficient. The protocols we propose can also estimate the actual values$\text{Tr}(P\rho)$, rather than just their absolute values as in prior work. Additionally, as a byproduct of our techniques, we establish tight bounds for the task of purity testing and show that it exhibits an intriguing phase transition not present in the memory-sample tradeoff for Pauli shadow tomography.

arXiv:2404.19105•Annual Symposium on Foundations of Computer Science•Oct 27, 2024•48 citations
Shadow tomography addresses the task of efficiently predicting many expectation values of an unknown quantum state from randomized measurements on comparatively few copies. Existing analyses promise large scaling advantages, but the optimal strategies realizing these guarantees are not always known, and the required measurements are potentially challenging to implement on current hardware. We address this gap for Pauli observables by computing optimal sample-complexity parameters and constructing optimal measurement strategies under realistic resource constraints. We focus on memoryless protocols, where each copy is measured only once, and on measurements with bounded interaction range. Our approach reduces the problem to the analysis of graph parameters of the frustration graph encoding the Pauli anticommutation relations. We provide efficient numerical methods for the general case and analytically prove that Clifford measurements are optimal in many situations. This includes all perfect graphs, all single-qubit, all two-qubit measurement scenarios, and more. Applied to Hamiltonian energy estimation, our framework yields constructive strategies and improved variance bounds for molecular benchmarks.
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.
Given copies of a quantum state ρ, a shadow tomography protocol aims to learn all expectation values from a fixed set of observables, to within a given precision ε. We say that a shadow tomography protocol is triply efficient if it is sample- and time-efficient, and only employs measurements that entangle a constant number of copies of ρ at a time. The classical shadows protocol based on random single-copy measurements is triply efficient for the set of local Pauli observables. This and other protocols based on random singlecopy Clifford measurements can be understood as arising from fractional colorings of a graph G that encodes the commutation structure of the set of observables. Here we describe a framework for two-copy shadow tomography that uses an initial round of Bell measurements to reduce to a fractional coloring problem in an induced subgraph of G with bounded clique number. This coloring problem can be addressed using techniques from graph theory known as chi-boundedness. Using this framework we give the first triply efficient shadow tomography scheme for the set of local fermionic observables, which arise in a broad class of interacting fermionic systems in physics and chemistry. We also give a triply efficient scheme for the set of all n-qubit Pauli observables. Our protocols for these tasks use two-copy measurements, which is necessary: sample- efficient schemes are provably impossible using only single-copy measurements. Finally, we give a shadow tomography protocol that compresses an n-qubit quantum state into a poly(n )-sized classical representation, from which one can extract the expected value of any of the 4n Pauli observables in poly(n ) time, up to a small constant error.
We investigate the problem of efficiently estimating expectation values of large sets of observables from copies of an unknown many-body quantum state. This task, known as shadow tomography, is crucial for quantum simulation and quantum chemistry, where the relevant observables often include k -body fermionic or k -local Pauli operators. A key goal is to achieve sample efficiency, computational efficiency, and few-copy measurements. We introduce the notion of triply efficient shadow tomography to formalize these requirements. Prior work has shown that single-copy measurements suffice for k -local Pauli operators with constant k . However, we prove that for k -body fermionic observables and the full set of n -qubit Pauli operators, single-copy protocols fail to achieve sample-efficient tomography. We then present new protocols based on measuring two copies of the state at a time that overcome these lower bounds, providing a triply efficient protocol.
Accurately estimating expectation values of quantum observables with as few measurements as possible is crucial to many quantum computing applications. We introduce a framework that covers many of existing measurement strategies and introduce heuristics that can be used to enhance randomized schemes, including those based on Pauli grouping with inverse probability weighting and variants of the classical shadow algorithm. We show how to maximize information gain from such schemes, while carefully optimizing the distribution of possible measurements, and show that simple grouping algorithms can get close to, and in some cases exceed, state-of-the-art accuracy for unbiased estimation of expectation values on a standard quantum chemistry benchmark. We show how these randomized methods may be compared to more recent measurement schemes, such as shadow grouping, derandomized shadow, and overlapped grouping measurement, we show how the same strategies can be used to augment these schemes, and we demonstrate that we can reduce measurement costs by up to a factor of two by allowing Clifford measurement circuits for otherwise Clifford-less methods.
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 revisit the problem of Pauli shadow tomography: given copies of an unknown n-qubit quantum stateρ\rhoρ, estimate Tr(Pρ)(P\rho)(Pρ)for some set of Pauli operatorsFFFto within additive errorϵ\epsilonϵ. This has been a popular testbed for exploring the advantage of protocols with quantum memory over those without: with enough memory to measure two copies at a time, one can use Bell sampling to estimate∣Tr(Pρ)\vert \text{Tr}(P\rho)∣Tr(Pρ)for allPPPusingO(n/ϵ4)O(n/\epsilon^{4})O(n/ϵ4)copies, but withk≤nk\leq nk≤nqubits of memory,Ω(2(n−k)/3)\Omega(2^{(n-k)/3})Ω(2(n−k)/3)copies are needed. These results leave open several natural questions. How does this picture change in the physically relevant setting where one only needs to estimate a certain subset of Paulis? What is the optimal dependence onϵ?\epsilon ?ϵ?What is the optimal tradeoff between quantum memory and sample complexity? We answer all of these questions: •For any subsetAAAof Paulis and any family of measurement strategies, we completely characterize the optimal sample complexity, up tolog⁡∣A∣\log\vert A\vertlog∣A∣factors. •We show any protocol that makes poly(n)(n)(n)-copy measure-ments must makeΩ(1/ϵ4)\Omega(1/\epsilon^{4})Ω(1/ϵ4)measurements. •For any protocol that makes poly(n)(n)(n)-copy measurements and only hask<nk < nk<nqubits of memory, we show thatΘ~(min⁡{2n/ϵ2,2n−k/ϵ4})\tilde{\Theta}(\min\{2^{n}/\epsilon^{2},2^{n-k}/\epsilon^{4}\})Θ~(min{2n/ϵ2,2n−k/ϵ4})copies are necessary and sufficient. The protocols we propose can also estimate the actual valuesTr(Pρ)\text{Tr}(P\rho)Tr(Pρ), rather than just their absolute values as in prior work. Additionally, as a byproduct of our techniques, we establish tight bounds for the task of purity testing and show that it exhibits an intriguing phase transition not present in the memory-sample tradeoff for Pauli shadow tomography.