Thilo Scharnhorst, Jack Spilecki, John Wright (Oct 10 2025).
Abstract: We show that
n=Ω(rd/ε2) copies are necessary to learn a rank
r mixed state
ρ∈Cd×d up to error
ε in trace distance. This matches the upper bound of
n=O(rd/ε2) from prior work, and therefore settles the sample complexity of mixed state tomography. We prove this lower bound by studying a special case of full state tomography that we refer to as projector tomography, in which
ρ is promised to be of the form
ρ=P/r, where
P∈Cd×d is a rank
r projector. A key technical ingredient in our proof, which may be of independent interest, is a reduction which converts any algorithm for projector tomography which learns to error
ε in trace distance to an algorithm which learns to error
O(ε) in the more stringent Bures distance.