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

Finite-Size Limits of Adaptive Pauli Prediction

Luofei Wang, Boyu Liu, Zihe Wang, Zhangqi Yin

quant-phSubmitted Oct 9, 2026• Announced Oct 12, 2026• 0 citations• Revised Oct 29, 2026 (v2)
v1 · Oct 9, 2026v2 · Oct 29, 2026
arXivHTMLPDF

Abstract

The expectation values of a predetermined set of Pauli observables can be predicted using only a few copies of a quantum state. However, when later observables depend on earlier predictions, how the system size constrains the required number of copies remains unclear. We use classical interactive fingerprinting codes to establish this constraint. A compact Pauli-parity encoding embeds the fingerprinting interaction into the quantum prediction task, allowing any quantum prediction mechanism on the constructed diagonal states to be simulated by a classical response strategy subject to the same information constraints. We show that accurate prediction from too few copies would violate the guarantees of the fingerprinting code. For $n$ qubits and $M$ adaptively chosen Pauli observables, requiring all predictions to be simultaneously accurate to a fixed additive error with probability at least $2/3$ yields the worst-case lower bound $N^*(n,M)=Ω(\sqrt{\min\{n,M\}})$ on the required number of copies. For $M\le n$, this lower bound matches known upper bounds. In particular, $n$ adaptive predictions require $Θ(\sqrt{n})$ copies, whereas the same number of predetermined queries requires only $O(\log n)$ copies. This separation persists even for diagonal states and commuting observables.

Comments
19 pages, 2 figures. Clarified the discussion of post hoc generalization and updated acknowledgments

Related papers

Predicting Adaptively Chosen Observables in Quantum Systems

Jerry Huang, Laura Lewis, Hsin-Yuan Huang +1 more

Recent advances have demonstrated that O ( log  M ) measurements suffice to predict M properties of arbitrarily large quantum many-body systems. However, these remarkable findings assume that the properties to be predicted are chosen independently of the data. This assumption can be violated in practice, where scientists adaptively select properties after looking at previous predictions. This work investigates the adaptive setting for three classes of observables: local, Pauli, and bounded-Frobenius-norm observables. We prove that Ω ( M ) samples of an arbitrarily large unknown quantum state are necessary to predict expectation values of M adaptively chosen local and Pauli observables, where the system size scales exponentially and polynomially in M , respectively. We also present computationally efficient algorithms that achieve this information-theoretic lower bound. In contrast, for bounded-Frobenius-norm observables, we devise an algorithm requiring only O ( log  M ) samples, independent of system size. These results highlight the potential pitfalls of adaptivity in analyzing data from quantum experiments and provide algorithmic tools to safeguard against erroneous predictions in quantum experiments.

arXiv:2410.15501•PRX Quantum•Jan 28, 2026•0 citations

Pauli Measurements Are Not Optimal for Single-Copy Tomography

Jayadev Acharya, Abhilash Dharmavarapu, Yuhan Liu +1 more

Quantum state tomography is a fundamental problem in quantum computing. Given n copies of an unknown N -qubit state ρ∈ℂ d × d , d =2 N , the goal is to learn the state up to an accuracy ε in trace distance, say with at least constant probability 0.99. We are interested in the copy complexity, the minimum number of copies of ρ needed to fulfill the task. As current quantum devices are physically limited, Pauli measurements have attracted significant attention due to their ease of implementation. However, a large gap exists in the literature for tomography with Pauli measurements. The best-known upper bound is O ( N · 12 N /ε 2 ), and no non-trivial lower bound is known besides the general single-copy lower bound of Ω(8 N /ε 2 ), achieved by hard-to-implement structured POVMs such as MUB, SIC-POVM, and uniform POVM. We have made significant progress on this long-standing problem. We first prove a stronger upper bound of O (10 N /ε 2 ). To complement it, we also obtain a lower bound of Ω(9.118 N /ε 2 ), which holds even with adaptivity. To our knowledge, this demonstrates the first known separation between Pauli measurements and structured POVMs. The new lower bound is a consequence of a novel framework for adaptive quantum state tomography with measurement constraints. The main advantage is that we can use measurement-dependent hard instances to prove tight lower bounds for Pauli measurements, while prior lower-bound techniques for tomography only work with measurement-independent constructions. Moreover, we connect the copy complexity lower bound of tomography to the eigenvalues of the measurement information channel, which governs the measurement’s capacity to distinguish between states. To demonstrate the generality of the new framework, we obtain tight bounds for adaptive quantum state tomography with k -outcome measurements, where we recover existing results and establish new ones.

arXiv:2502.18170•ACM Symposium on Theory of Computing (STOC)•Jun 15, 2025•1 citation

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•0 citations

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•8 citations

Near-Optimal Mixedness Testing with Pauli Measurements

Jayadev Acharya, Abhilash Dharmavarapu, Yuhan Liu +1 more

We consider a fundamental problem of \emph{mixedness testing}: Given $n$ copies of an $N$-qubit state $ρ$, determine whether $ρ= \mathbb{I}_d/d$ or $\|ρ-\mathbb{I}_d/d\|_1 \geq \varepsilon$ with high probability, where $d = 2^N$. In particular, we focus on performing this task in the practical setting of single-qubit measurements, where measurements are prepared independently on each qubit. We provide a nearly complete picture of single-qubit mixedness tesing by showing $n = \tildeΘ\left(\sqrt{10}^N/\varepsilon^2\right)$. To establish our lower bound, we introduce a measurement-dependent lower bound framework for adaptive single-copy state certification. For the upper bound, we present a randomized Pauli basis measurement protocol, which relies on a new primitive for computationally efficient uniformity testing of correlation-concentrated distributions on the Boolean hypercube. In conjunction, we provide lower and upper bounds for mixedness testing with fixed Pauli measurement protocols.

quant-pharXiv:2608.18839•Aug 20, 2026•0 citations

Lower Bounds on Relative Error Quantum Compression and Classical Shadows

Sankar, Kaushik

We study the question of how much classical communication is needed when Alice is given a classical description of a quantum state $|ψ\rangle$ for Bob to recover any expectation value $\langle ψ| M |ψ\rangle$ given an observable $M$ with $M$ Hermitian and $||M||_{\text{op}} \leq 1$. This task, whose study was initiated by Raz (ACM 1999) and more recently investigated by Gosset and Smolin (TQC 2019), can be thought of as a fully classical version of the pure state case of the well-known classical shadows problem in quantum learning theory. We show how the hardness of these two seemingly distinct problems are connected. We first consider the relative error version of the communication question and prove a lower bound of $Ω(\sqrt{2^{n}}ε^{-2})$ on the one-way randomized classical communication, improving upon an additive error lower bound of $Ω(\sqrt{2^{n}})$ as shown by Gosset and Smolin. Notably, we show that this lower bound holds not only for the set of all observables but also when restricted to just the class of Pauli observables. This fact implies a $Ω(\sqrt{2^{n}})$ versus $O(\text{poly}(n))$ separation in the compression size between the relative and additive error settings for non-adaptive Pauli classical shadows with classical memory. Extending this framework, we prove randomized communication lower bounds for other relative error one-way classical communication tasks: an $Ω(2^{n}ε^{-2})$ lower bound when instead Alice is given an observable and Bob is given a quantum state and they are asked to estimate the expectation value, an $Ω(\sqrt{n}ε^{-2})$ lower bound when restricted to Paulis, and an $Ω(\sqrt{2^{n}}ε^{-2})$ lower bound when Alice and Bob are both given quantum states and asked to estimate the inner product.

arXiv:2506.21345•Jun 26, 2025•0 citations
The expectation values of a predetermined set of Pauli observables can be predicted using only a few copies of a quantum state. However, when later observables depend on earlier predictions, how the system size constrains the required number of copies remains unclear. We use classical interactive fingerprinting codes to establish this constraint. A compact Pauli-parity encoding embeds the fingerprinting interaction into the quantum prediction task, allowing any quantum prediction mechanism on the constructed diagonal states to be simulated by a classical response strategy subject to the same information constraints. We show that accurate prediction from too few copies would violate the guarantees of the fingerprinting code. For nnn qubits and MMM adaptively chosen Pauli observables, requiring all predictions to be simultaneously accurate to a fixed additive error with probability at least 2/32/32/3 yields the worst-case lower bound N∗(n,M)=Ω(min⁡{n,M})N^*(n,M)=Ω(\sqrt{\min\{n,M\}})N∗(n,M)=Ω(min{n,M}​) on the required number of copies. For M≤nM\le nM≤n, this lower bound matches known upper bounds. In particular, nnn adaptive predictions require Θ(n)Θ(\sqrt{n})Θ(n​) copies, whereas the same number of predetermined queries requires only O(log⁡n)O(\log n)O(logn) copies. This separation persists even for diagonal states and commuting observables.
Recent advances have demonstrated that O ( log  M ) measurements suffice to predict M properties of arbitrarily large quantum many-body systems. However, these remarkable findings assume that the properties to be predicted are chosen independently of the data. This assumption can be violated in practice, where scientists adaptively select properties after looking at previous predictions. This work investigates the adaptive setting for three classes of observables: local, Pauli, and bounded-Frobenius-norm observables. We prove that Ω ( M ) samples of an arbitrarily large unknown quantum state are necessary to predict expectation values of M adaptively chosen local and Pauli observables, where the system size scales exponentially and polynomially in M , respectively. We also present computationally efficient algorithms that achieve this information-theoretic lower bound. In contrast, for bounded-Frobenius-norm observables, we devise an algorithm requiring only O ( log  M ) samples, independent of system size. These results highlight the potential pitfalls of adaptivity in analyzing data from quantum experiments and provide algorithmic tools to safeguard against erroneous predictions in quantum experiments.
Quantum state tomography is a fundamental problem in quantum computing. Given n copies of an unknown N -qubit state ρ∈ℂ d × d , d =2 N , the goal is to learn the state up to an accuracy ε in trace distance, say with at least constant probability 0.99. We are interested in the copy complexity, the minimum number of copies of ρ needed to fulfill the task. As current quantum devices are physically limited, Pauli measurements have attracted significant attention due to their ease of implementation. However, a large gap exists in the literature for tomography with Pauli measurements. The best-known upper bound is O ( N · 12 N /ε 2 ), and no non-trivial lower bound is known besides the general single-copy lower bound of Ω(8 N /ε 2 ), achieved by hard-to-implement structured POVMs such as MUB, SIC-POVM, and uniform POVM. We have made significant progress on this long-standing problem. We first prove a stronger upper bound of O (10 N /ε 2 ). To complement it, we also obtain a lower bound of Ω(9.118 N /ε 2 ), which holds even with adaptivity. To our knowledge, this demonstrates the first known separation between Pauli measurements and structured POVMs. The new lower bound is a consequence of a novel framework for adaptive quantum state tomography with measurement constraints. The main advantage is that we can use measurement-dependent hard instances to prove tight lower bounds for Pauli measurements, while prior lower-bound techniques for tomography only work with measurement-independent constructions. Moreover, we connect the copy complexity lower bound of tomography to the eigenvalues of the measurement information channel, which governs the measurement’s capacity to distinguish between states. To demonstrate the generality of the new framework, we obtain tight bounds for adaptive quantum state tomography with k -outcome measurements, where we recover existing results and establish new ones.
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 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.
We consider a fundamental problem of \emph{mixedness testing}: Given nnn copies of an NNN-qubit state ρρρ, determine whether ρ=Id/dρ= \mathbb{I}_d/dρ=Id​/d or ∥ρ−Id/d∥1≥ε\|ρ-\mathbb{I}_d/d\|_1 \geq \varepsilon∥ρ−Id​/d∥1​≥ε with high probability, where d=2Nd = 2^Nd=2N. In particular, we focus on performing this task in the practical setting of single-qubit measurements, where measurements are prepared independently on each qubit. We provide a nearly complete picture of single-qubit mixedness tesing by showing n=Θ~(10N/ε2)n = \tildeΘ\left(\sqrt{10}^N/\varepsilon^2\right)n=Θ~(10​N/ε2). To establish our lower bound, we introduce a measurement-dependent lower bound framework for adaptive single-copy state certification. For the upper bound, we present a randomized Pauli basis measurement protocol, which relies on a new primitive for computationally efficient uniformity testing of correlation-concentrated distributions on the Boolean hypercube. In conjunction, we provide lower and upper bounds for mixedness testing with fixed Pauli measurement protocols.
We study the question of how much classical communication is needed when Alice is given a classical description of a quantum state ∣ψ⟩|ψ\rangle∣ψ⟩ for Bob to recover any expectation value ⟨ψ∣M∣ψ⟩\langle ψ| M |ψ\rangle⟨ψ∣M∣ψ⟩ given an observable MMM with MMM Hermitian and ∣∣M∣∣op≤1||M||_{\text{op}} \leq 1∣∣M∣∣op​≤1. This task, whose study was initiated by Raz (ACM 1999) and more recently investigated by Gosset and Smolin (TQC 2019), can be thought of as a fully classical version of the pure state case of the well-known classical shadows problem in quantum learning theory. We show how the hardness of these two seemingly distinct problems are connected. We first consider the relative error version of the communication question and prove a lower bound of Ω(2nε−2)Ω(\sqrt{2^{n}}ε^{-2})Ω(2n​ε−2) on the one-way randomized classical communication, improving upon an additive error lower bound of Ω(2n)Ω(\sqrt{2^{n}})Ω(2n​) as shown by Gosset and Smolin. Notably, we show that this lower bound holds not only for the set of all observables but also when restricted to just the class of Pauli observables. This fact implies a Ω(2n)Ω(\sqrt{2^{n}})Ω(2n​) versus O(poly(n))O(\text{poly}(n))O(poly(n)) separation in the compression size between the relative and additive error settings for non-adaptive Pauli classical shadows with classical memory. Extending this framework, we prove randomized communication lower bounds for other relative error one-way classical communication tasks: an Ω(2nε−2)Ω(2^{n}ε^{-2})Ω(2nε−2) lower bound when instead Alice is given an observable and Bob is given a quantum state and they are asked to estimate the expectation value, an Ω(nε−2)Ω(\sqrt{n}ε^{-2})Ω(n​ε−2) lower bound when restricted to Paulis, and an Ω(2nε−2)Ω(\sqrt{2^{n}}ε^{-2})Ω(2n​ε−2) lower bound when Alice and Bob are both given quantum states and asked to estimate the inner product.