Costin Bādescu

We present improved sample complexity bounds for three fundamental quantum information tasks: state certification, separability testing, and shadow tomography. Given measurement access to n identical copies of an unknown quantum state ρ, we consider:

i. State certification: The task of verifying ρ is equal to a reference state σ or at least ϵ-far in trace distance. We present a testing algorithm for state certification that uses O(d/ϵ2) copies of ρ.

ii. Separability testing: For a bipartite state ρ on a d2-dimensional system, we prove a lower bound of Ω(d2/ϵ2) copies are necessary to distinguish separability from being ϵ-far in trace distance from the set of all separable states.

iii. Shadow tomography: The problem of estimating the expectation values tr(ρAi) for m observables A1, . . . ,Am to ±ϵ accuracy. We present an algorithm that accomplishes this with O(log2(m) log(d)/ϵ4) copies, which simultaneously achieves the best known dependence on each parameter m, d, and ϵ.