Agnostic Tomography of Stabilizer Product States

We define a quantum learning task called agnostic tomography, where given copies of an arbitrary state ρ and a class of quantum states C, the goal is to output a succinct description of a state that approximates ρ at least as well as any state in C (up to some small error ε). This task generalizes ordinary quantum tomography of states in C and is more challenging because the learning algorithm must be robust to perturbations of ρ. We give an efficient agnostic tomography algorithm for the class C of n-qubit stabilizer product states. Assuming ρ has fidelity at least τ with a stabilizer product state, the algorithm runs in time nO(1 + log(1/τ)) / ε². This runtime is quasipolynomial in all parameters, and polynomial if τ is a constant.