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

Adaptivity can help exponentially for shadow tomography

Sitan Chen, Weiyuan Gong, Zhihan Zhang

Published Dec 26, 2024• 14 citations
arXivHTMLPDF

Abstract

In recent years there has been significant interest in understanding the statistical complexity of learning from quantum data under the constraint that one can only make unentangled measurements. While a key challenge in establishing tight lower bounds in this setting is to deal with the fact that the measurements can be chosen in an adaptive fashion, a recurring theme has been that adaptivity offers little advantage over more straightforward, nonadaptive protocols. In this note, we offer a counterpoint to this. We show that for the basic task of shadow tomography, protocols that use adaptively chosen two-copy measurements can be exponentially more sample-efficient than any protocol that uses nonadaptive two-copy measurements.

DOI
10.48550/arxiv.2412.19022

Related papers

Lower Bounds for Learning Quantum States with Single-Copy Measurements

Angus Lowe, Ashwin Nayak

We study the problems of quantum tomography and shadow tomography using measurements performed on individual, identical copies of an unknown d -dimensional state. We first revisit known lower bounds [ 23 ] on quantum tomography with accuracy ε in trace distance, when the measurement choices are independent of previously observed outcomes, i.e., they are nonadaptive. We give a succinct proof of these results through the χ 2 -divergence between suitable distributions. Unlike prior work, we do not require that the measurements be given by rank-one operators. This leads to stronger lower bounds when the learner uses measurements with a constant number of outcomes (e.g., two-outcome measurements). In particular, this rigorously establishes the optimality of the folklore “Pauli tomography” algorithm in terms of its sample complexity. We also derive novel bounds of \(\Omega (r^2 d/\epsilon ^2)\) and \(\Omega (r^2 d^2/\epsilon ^2)\) for learning rank r states using arbitrary and constant-outcome measurements, respectively, in the nonadaptive case. In addition to the sample complexity, a resource of practical significance for learning quantum states is the number of unique measurement settings required (i.e., the number of different measurements used by an algorithm, each possibly with an arbitrary number of outcomes). Motivated by this consideration, we employ concentration of measure of χ 2 -divergence of suitable distributions to extend our lower bounds to the case where the learner performs possibly adaptive measurements from a fixed set of \(\exp (O(d))\) possible measurements. This implies in particular that adaptivity does not give us any advantage using single-copy measurements that are efficiently implementable. We also obtain a similar bound in the case where the goal is to predict the expectation values of a given sequence of observables, a task known as shadow tomography. Finally, in the case of adaptive, single-copy measurements implementable with polynomial-size circuits, we prove that a straightforward strategy based on computing sample means of the given observables is optimal.

arXiv:2207.14438•ACM Transactions on Computation Theory•Feb 13, 2025•35 citations

Adaptive Local Measurements For Quantum Learning Can Exponentially Outperform Nonadaptive Global Measurements

Alireza Goldar, Zhen Qin, Zhihui Zhu +2 more

Can measurements chosen adaptively, in response to earlier outcomes, be exponentially more informative than measurements fixed in advance? In many quantum settings, adaptivity helps at most polynomially; known exponential advantages require coherent measurements across copies or restricted measurements. We show an exponential advantage measuring one copy at a time, with no quantum memory kept between state copies, even when the nonadaptive learner may perform arbitrary global measurements on each copy. We construct explicit families of multi-qubit states in which a scalar parameter is encoded in one of exponentially many candidate observables, with an auxiliary marker indicating which one. An adaptive protocol identifies the relevant observable and then measures it using only single-qubit measurements and one round of adaptation. At fixed accuracy, it needs logarithmically many copies as the qubit count grows, whereas every nonadaptive protocol needs exponentially many. The same mechanism yields an exponential gap in local asymptotic minimax mean squared error constants, tight up to the exponential base. The states are separable and classical in label-dependent product bases; no entanglement or other nonclassical correlations are required. The gap comes from measurement incompatibility: the candidate observables cannot be measured jointly, so a fixed measurement must divide its information budget among them, while adaptivity selects the informative one. Accordingly, the separation disappears when the candidate observables commute, and cannot occur with fully observed classical samples. Measurement incompatibility thus emerges as a resource for quantum learning, distinct from entanglement and quantum memory, that classical feedback alone can exploit.

quant-pharXiv:2610.38922•Oct 30, 2026•0 citations

When Does Adaptivity Help for Quantum State Learning?

Sitan Chen, Brice Huang, Jerry Zheng Li +2 more

We consider the classic question of state tomography: given copies of an unknown quantum state $\rho \in \mathbb{C}^{d \times d}$, output $\widehat{\rho}$ which is close to $\rho$ in some sense, e.g. trace distance or fidelity. When one is allowed to make coherent measurements entangled across all copies, $\Theta\left(d^{2} / \varepsilon^{2}\right)$ copies are necessary and sufficient to get trace distance $\varepsilon$ [18], [29]. Unfortunately, the protocols achieving this rate incur large quantum memory overheads that preclude implementation on near-term devices. On the other hand, the best known protocol using incoherent (single-copy) measurements uses $O\left(d^{3} / \varepsilon^{2}\right)$ copies [24], and multiple papers have posed it as an open question to understand whether or not this rate is tight [6], [18]. In this work, we fully resolve this question, by showing that any protocol using incoherent measurements, even if they are chosen adaptively, requires $\Omega\left(d^{3} / \varepsilon^{2}\right)$ copies, matching the upper bound of [24]. We do so by a new proof technique which directly bounds the “tilt” of the posterior distribution after measurements, which yields a surprisingly short proof of our lower bound, and which we believe may be of independent interest. While this implies that adaptivity does not help for tomography with respect to trace distance, we show that it actually does help for tomography with respect to infidelity. We give an adaptive algorithm that outputs a state which is $\gamma$-close in infidelity to $\rho$ using only $\widetilde{O}\left(d^{3} / \gamma\right)$ copies, which is optimal for incoherent measurements. In contrast, it is known [18] that any nonadaptive algorithm requires $\Omega\left(d^{3} / \gamma^{2}\right)$ copies. While it is folklore that in 2 dimensions, one can achieve a scaling of $O(1 / \gamma)$, to the best of our knowledge, our algorithm is the first to achieve the optimal rate in all dimensions.

arXiv:2206.05265•Annual Symposium on Foundations of Computer Science•Nov 6, 2023•64 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

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

An infinite hierarchy of multi-copy quantum learning tasks

Jan Nöller, Viet T. Tran, Mariami Gachechiladze +1 more

Learning properties of quantum states from measurement data is a fundamental challenge in quantum information. The sample complexity of such tasks depends crucially on the measurement primitive. While shadow tomography achieves sample-efficient learning by allowing entangling measurements across many copies, it requires prohibitively deep circuits. At the other extreme, two-copy measurements already yield exponential advantages over single-copy strategies in tasks such as Pauli tomography. In this work we show that such sharp separations extend far beyond the two-copy regime: for every prime c we construct explicit learning tasks of degree c, which are exponentially hard with (c - 1)-copy measurements but efficiently solvable with c-copy measurements. Our protocols are not only sample-efficient but also realizable with shallow circuits. Extending further, we show that such finite-degree tasks exist for all square-free integers c, pointing toward a general principle underlying their existence. Together, our results reveal an infinite hierarchy of multi-copy learning problems, uncovering new phase transitions in sample complexity and underscoring the role of reliable quantum memory as a key resource for exponential quantum advantage.

arXiv:2510.08070•Oct 9, 2025•10 citations
In recent years there has been significant interest in understanding the statistical complexity of learning from quantum data under the constraint that one can only make unentangled measurements. While a key challenge in establishing tight lower bounds in this setting is to deal with the fact that the measurements can be chosen in an adaptive fashion, a recurring theme has been that adaptivity offers little advantage over more straightforward, nonadaptive protocols. In this note, we offer a counterpoint to this. We show that for the basic task of shadow tomography, protocols that use adaptively chosen two-copy measurements can be exponentially more sample-efficient than any protocol that uses nonadaptive two-copy measurements.
We study the problems of quantum tomography and shadow tomography using measurements performed on individual, identical copies of an unknown d -dimensional state. We first revisit known lower bounds [ 23 ] on quantum tomography with accuracy ε in trace distance, when the measurement choices are independent of previously observed outcomes, i.e., they are nonadaptive. We give a succinct proof of these results through the χ 2 -divergence between suitable distributions. Unlike prior work, we do not require that the measurements be given by rank-one operators. This leads to stronger lower bounds when the learner uses measurements with a constant number of outcomes (e.g., two-outcome measurements). In particular, this rigorously establishes the optimality of the folklore “Pauli tomography” algorithm in terms of its sample complexity. We also derive novel bounds of Ω(r2d/ϵ2)\Omega (r^2 d/\epsilon ^2)Ω(r2d/ϵ2) and Ω(r2d2/ϵ2)\Omega (r^2 d^2/\epsilon ^2)Ω(r2d2/ϵ2) for learning rank r states using arbitrary and constant-outcome measurements, respectively, in the nonadaptive case. In addition to the sample complexity, a resource of practical significance for learning quantum states is the number of unique measurement settings required (i.e., the number of different measurements used by an algorithm, each possibly with an arbitrary number of outcomes). Motivated by this consideration, we employ concentration of measure of χ 2 -divergence of suitable distributions to extend our lower bounds to the case where the learner performs possibly adaptive measurements from a fixed set of exp⁡(O(d))\exp (O(d))exp(O(d)) possible measurements. This implies in particular that adaptivity does not give us any advantage using single-copy measurements that are efficiently implementable. We also obtain a similar bound in the case where the goal is to predict the expectation values of a given sequence of observables, a task known as shadow tomography. Finally, in the case of adaptive, single-copy measurements implementable with polynomial-size circuits, we prove that a straightforward strategy based on computing sample means of the given observables is optimal.
Can measurements chosen adaptively, in response to earlier outcomes, be exponentially more informative than measurements fixed in advance? In many quantum settings, adaptivity helps at most polynomially; known exponential advantages require coherent measurements across copies or restricted measurements. We show an exponential advantage measuring one copy at a time, with no quantum memory kept between state copies, even when the nonadaptive learner may perform arbitrary global measurements on each copy. We construct explicit families of multi-qubit states in which a scalar parameter is encoded in one of exponentially many candidate observables, with an auxiliary marker indicating which one. An adaptive protocol identifies the relevant observable and then measures it using only single-qubit measurements and one round of adaptation. At fixed accuracy, it needs logarithmically many copies as the qubit count grows, whereas every nonadaptive protocol needs exponentially many. The same mechanism yields an exponential gap in local asymptotic minimax mean squared error constants, tight up to the exponential base. The states are separable and classical in label-dependent product bases; no entanglement or other nonclassical correlations are required. The gap comes from measurement incompatibility: the candidate observables cannot be measured jointly, so a fixed measurement must divide its information budget among them, while adaptivity selects the informative one. Accordingly, the separation disappears when the candidate observables commute, and cannot occur with fully observed classical samples. Measurement incompatibility thus emerges as a resource for quantum learning, distinct from entanglement and quantum memory, that classical feedback alone can exploit.
We consider the classic question of state tomography: given copies of an unknown quantum state ρ∈Cd×d\rho \in \mathbb{C}^{d \times d}ρ∈Cd×d, output ρ^\widehat{\rho}ρ​ which is close to ρ\rhoρ in some sense, e.g. trace distance or fidelity. When one is allowed to make coherent measurements entangled across all copies, Θ(d2/ε2)\Theta\left(d^{2} / \varepsilon^{2}\right)Θ(d2/ε2) copies are necessary and sufficient to get trace distance ε\varepsilonε [18], [29]. Unfortunately, the protocols achieving this rate incur large quantum memory overheads that preclude implementation on near-term devices. On the other hand, the best known protocol using incoherent (single-copy) measurements uses O(d3/ε2)O\left(d^{3} / \varepsilon^{2}\right)O(d3/ε2) copies [24], and multiple papers have posed it as an open question to understand whether or not this rate is tight [6], [18]. In this work, we fully resolve this question, by showing that any protocol using incoherent measurements, even if they are chosen adaptively, requires Ω(d3/ε2)\Omega\left(d^{3} / \varepsilon^{2}\right)Ω(d3/ε2) copies, matching the upper bound of [24]. We do so by a new proof technique which directly bounds the “tilt” of the posterior distribution after measurements, which yields a surprisingly short proof of our lower bound, and which we believe may be of independent interest. While this implies that adaptivity does not help for tomography with respect to trace distance, we show that it actually does help for tomography with respect to infidelity. We give an adaptive algorithm that outputs a state which is γ\gammaγ-close in infidelity to ρ\rhoρ using only O~(d3/γ)\widetilde{O}\left(d^{3} / \gamma\right)O(d3/γ) copies, which is optimal for incoherent measurements. In contrast, it is known [18] that any nonadaptive algorithm requires Ω(d3/γ2)\Omega\left(d^{3} / \gamma^{2}\right)Ω(d3/γ2) copies. While it is folklore that in 2 dimensions, one can achieve a scaling of O(1/γ)O(1 / \gamma)O(1/γ), to the best of our knowledge, our algorithm is the first to achieve the optimal rate in all dimensions.
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 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.
Learning properties of quantum states from measurement data is a fundamental challenge in quantum information. The sample complexity of such tasks depends crucially on the measurement primitive. While shadow tomography achieves sample-efficient learning by allowing entangling measurements across many copies, it requires prohibitively deep circuits. At the other extreme, two-copy measurements already yield exponential advantages over single-copy strategies in tasks such as Pauli tomography. In this work we show that such sharp separations extend far beyond the two-copy regime: for every prime c we construct explicit learning tasks of degree c, which are exponentially hard with (c - 1)-copy measurements but efficiently solvable with c-copy measurements. Our protocols are not only sample-efficient but also realizable with shallow circuits. Extending further, we show that such finite-degree tasks exist for all square-free integers c, pointing toward a general principle underlying their existence. Together, our results reveal an infinite hierarchy of multi-copy learning problems, uncovering new phase transitions in sample complexity and underscoring the role of reliable quantum memory as a key resource for exponential quantum advantage.