2025/10/09 by Thilo Scharnhorst, Jack Spilecki, Scharnhorst, Thilo +3 · 6 citations
Computer Science · #Quantum Computing Algorithms and Architecture #Complexity and Algorithms in Graphs #Quantum Information and Cryptography
paper · pdf · doi:10.48550/arxiv.2510.07699
We show that n = Ω(rd/ε2) copies are necessary to learn a rank r mixed state ρ∈ ℂd × 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 ∈ ℂd × 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.