It is a fundamental problem to decide how many copies of an unknown mixed quantum state are necessary and sufficient to determine the state. Previously, it was known only that estimating states to error ε in trace distance required O(dr2/ε2) copies for a d-dimensional density matrix of rank r. Here, we give a theoretical measurement scheme (POVM) that requires O(dr/δ)ln (d/δ) copies to estimate ρ to error δ in infidelity, and a matching lower bound up to logarithmic factors. This implies O((dr/ε2)ln (d/ε)) copies suffice to achieve error ε in trace distance. We also prove that for independent (product) measurements, Ω(dr2/δ2)/ ln(1/δ) copies are necessary in order to achieve error δ in infidelity. For fixed d, our measurement can be implemented on a quantum computer in time polynomial in n.
Shadow tomography for quantum states provides a sample efficient approach for predicting the properties of quantum systems when the properties are restricted to expectation values of
2-outcome POVMs. However, these shadow tomography procedures yield poor bounds if there are more than 2 outcomes per measurement. In this paper, we consider a general problem of learning properties from unknown quantum states: given an unknown
d-dimensional quantum state
ρ and
M unknown quantum measurements
M1,...,MM with
K≥2 outcomes, estimating the probability distribution for applying
Mi on
ρ to within total variation distance
ε. Compared to the special case when
K=2, we need to learn unknown distributions instead of values. We develop an online shadow tomography procedure that solves this problem with high success probability requiring
O~(Klog2Mlogd/ε4) copies of
ρ. We further prove an information-theoretic lower bound that at least
Ω(min{d2,K+logM}/ε2) copies of
ρ are required to solve this problem with high success probability. Our shadow tomography procedure requires sample complexity with only logarithmic dependence on
M and
d and is sample-optimal for the dependence on
K.
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
{Oi}i=1m, the goal is to estimate expectation values
{tr(Oiρ)}i=1m to accuracy
ε in
Lp-norm, using possibly adaptive measurements that act on
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), where
Γp is a function of
{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∞-norm error. Concretely, we first analyze a simpler oblivious variant where the goal is to estimate an observable of the form
∑i=1mαiOi with
∥α∥q=1 (where
q is dual to
p) revealed after the measurement. For single-copy measurements, we obtain a sample complexity of
Θ(Γpob/ε2). We then show
Θ~(Γ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=Γ∞. 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.