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

Senrui Chen; Weiyuan Gong; Sisi Zhou

quant-phFeb 4, 2026

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

Authors: Senrui Chen, Weiyuan Gong, Sisi Zhou

Organizations: IQIM, California Institute of Technology · SEAS, Harvard University · Perimeter Institute

Abstract

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.

Figures & tables

Panel of Figure 1 — Figure 1 : Relationship between six problems. $\Leftrightarrow$ means two problems are equivalent, and $\Leftarrow$ means one problem is no harder than (reduces to) the other. Note that within each problem, increasing $p$ (or decreasing $q$ ) will not increase the hardness of the problem.

Tasks	Oblivious estimation from $L^{q}$ -ellipsoid (Problems 1’ and 2’ , $p\in[1,\infty]$ )	Shadow estimation with $p$ -norm error (Problems 1 and 2 , $p\in[1,\infty]$ )
Lower bounds for many-versus-one distinguishing (applying to Problems 3’ )	$\Omega\big(\Gamma^{\mathrm{ob}}_{p}(\{O_{i}\}_{i=1}^{m})/\varepsilon^{2}\big)$ ( $\varepsilon\leq\eta^{\mathrm{ob}}$ , single-copy)	Same as the left column
	$\Omega\big(\Gamma^{\mathrm{ob}}_{p}(\{O_{i}\}_{i=1}^{m})/(c\varepsilon^{2})\big)$ ( $\varepsilon\leq\min\{\eta^{\mathrm{ob}},\eta^{\mathrm{ob}}_{c}\}$ , $c$ -copy)	Same as the left column
Lower bounds for unbiased, bounded estimation	$\Omega\big(\Gamma^{\mathrm{ob}}_{p}(\{O_{i}\}_{i=1}^{m})/(c\varepsilon^{2}\log(1/\epsilon))\big)$ ( $c$ -copy)	$\Omega\big(\Gamma_{p}(\{O_{i}\}_{i=1}^{m})/(c\varepsilon^{2}\log(m^{1/p}/\epsilon))\big)$ ( $c$ -copy, $p\in[2,\infty]$ )
Upper bounds using the two-step method	$O\big(\Gamma^{\mathrm{ob}}_{p}(\{O_{i}\}_{i=1}^{m})/\varepsilon^{2}\big)$ ( $\varepsilon\leq\overline{\eta}^{\mathrm{ob}}$ , single-copy)	$O\big(\log(m)\Gamma_{p}(\{O_{i}\}_{i=1}^{m})/\varepsilon^{2}\big)$ ( $\varepsilon\leq\overline{\eta}$ , single-copy)

Table 1: Summary of results. We use two different methods to derive lower bounds on the sample complexity using

c

-copy measurements. The first method is detailed in Section 7 where lower bounds and corresponding thresholds are derived for Problem 3’ using the learning tree method. The second method is detailed in Section 8 where lower bounds are derived directly for Problems 2 and 2’ using the Cramér–Rao method assuming unbiased and bounded estimators. Explicit algorithms are provided in Section 9 using the two-step method where state tomography is first used to find a nearby state and locally optimal estimation is then used to achieve the target precision.

Explore similar work

Sep 9, 2026quant-ph

Optimal Low-Rank Quantum State Tomography with Bounded-Sample Joint Measurements

We determine the optimal sample complexity of low-rank quantum state tomography when each measurement may act jointly on at most

t

samples. For sufficiently small

\varepsilon

, estimating an unknown state on

\mathbb{C}^d

of rank at most

r

to trace norm error

\varepsilon

with constant success probability requires, and is achievable with,

Θ\left( \frac{dr}{\varepsilon^2} \max\left\{1,\frac r{\sqrt t}\right\} \right)

samples. The lower bound allows the protocol to choose each joint measurement adaptively using all previous classical outcomes; the matching upper bound is nonadaptive. Thus joint measurements on at most

t

samples improve the complexity of algorithms making single-sample measurements by at most a factor

\sqrt t

. Further, measuring order

r^2

samples jointly is necessary and sufficient to attain the unrestricted collective rate. For the lower bound, we vary the support of a state with fixed uniform spectrum and bound the Fisher information trace of every joint measurement on

t

samples. The adaptive Fisher chain rule and the van Trees inequality then give the trace norm lower bound. For the upper bound, we construct and analyze a nonadaptive tomography protocol based on a Gaussian joint measurement. An explicit second moment identity and a conditional Gaussian law outside the state's support give a rank-dependent error analysis, yielding the matching rate.

Ashwin Nayak, Xingyu Zhou

Department of Combinatorics and Optimization, and Institute for Quantum Computing, University of Waterloo. · Department of Computer Science, University of British Columbia.

Qubit Optimal Sample Complexity Spectral Norm Joint Search Cone-Beam Computed Tomography

Ask PDF

Apr 24, 2026quant-ph

The Exact Replica Threshold for Nonlinear Moments of Quantum States

Joint measurements on multiple copies of a quantum state provide access to nonlinear observables such as

\operatorname{tr}(ρ^t)

, but whether replica number marks a sharp information-theoretic resource boundary has remained unclear. For every fixed order

t\ge 3

, existing protocols show that

\lceil t/2\rceil

replicas already suffice for polynomial-sample estimation of

\operatorname{tr}(ρ^t)

, yet it has remained open whether one fewer replica must necessarily incur a sample-complexity barrier growing with the dimension. We prove that this is indeed the case in the sample/copy-access model with replica-limited joint measurements: any protocol restricted to

\lceil t/2\rceil-1

replicas requires dimension-growing sample complexity, while

\lceil t/2\rceil

replicas suffice by prior work. Thus the exact replica threshold for fixed-order pure moments is

\lceil t/2\rceil

. Equivalently, for fixed-order pure moments, one additional coherent replica is not merely useful but marks the exact threshold between polynomial-sample estimation and a dimension-growing regime in the replica-limited model. We further show that the same threshold law extends to a broad family of observable-weighted moments

\operatorname{tr}(Oρ^t)

, including Pauli observables and other observables with bounded operator norm and macroscopic trace norm. Coherent replica number therefore acts as a genuinely discrete resource for nonlinear quantum-state estimation.

Shuai Zeng

School of Communication and Information Engineering, Chongqing University of Posts and Telecommunications, Chongqing 400065, P.R. China

Qubit Optimal Sample Complexity Nonlinearity

Ask PDF

Jul 13, 2026quant-ph

Fixed-Protocol Amortized MPS Tomography with Conformalized Predictive Uncertainty

Quantum state tomography is sample-starved, and the states one prepares live on a narrow, learnable manifold. A

k{=}0

prior-only control shows that on concentrated families a prior estimate is already near-optimal, so ``high fidelity at few measurements'' can be family memorization rather than tomography; genuine measurement-efficiency needs a model that conditions on the measurements and demonstrably uses them. On a shared matrix-product-state (MPS) core parameterization we study two routes. Approach~~A learns a generative prior over MPS cores with measurement-guided posterior inference (gold-standard-validated, but whose few-measurement accuracy the control shows is largely the prior). Approach~~B, our main proposal, is a \emph{fixed-protocol amortized} MPS estimator trained once with a gauge-invariant fidelity loss; we deliberately do not rest it on a permutation-invariant set encoder (a plain MLP matches it). The decisive lever is the measurement design: motivated by the fact that local reduced density matrices determine a

χ

-MPS, conditioning on an \emph{informative local} Pauli set rather than random strings turns a modest, memorization-prone estimator into a high-fidelity one (

\approx\!0.95

, up to

+0.59

over prior-only, decisively passing a shuffled-measurement control). A dropout ensemble, conformally recalibrated, gives

\approx\!90\%

-coverage intervals -- including for observables never measured, where a shot-based interval does not exist. Quality holds as the system grows (fidelity

0.90

n{=}10

, gain \emph{growing} in

n

;

0.88

at bond dimension

χ{=}4

), the parameterization is polynomial (native contraction to

20

qubits), and we close the loop on IBM hardware (

5

states at

0.97

from hardware-measured Paulis).

Jian Xu, Delu Zeng, John Paisley +1

1RIKEN iTHEMS · 2RIKEN AIP · 3South China University of Technology +1

Qubit Distributional Fidelity Posterior Cone-Beam Computed Tomography Online Conformal Prediction Uncertainty

Ask PDF