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.
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.
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.
In the change point problem, we determine when the observed distribution has changed to another one. We expand this problem to a quantum case where copies of an unknown pure state are being distributed. That is, we estimate when the distributed quantum pure state is changed. As the most fundamental case, we treat the problem of deciding the true change point
tc between the two given candidates
t1 and
t2. Our problem is mathematically equal to identifying a given state with one of the two unknown states when multiple copies of the states are provided. The minimum of the averaged error probability is given and the optimal positive operator-valued measure (POVM) is given to obtain it when the initial and final quantum pure states are subject to the invariant prior. We also compute the error probability for deciding the change point under the above POVM when the initial and final quantum pure states are fixed. These analytical results allow us to calculate the value in the asymptotic case.