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 varepsilon). 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(log(2/τ)) / varepsilon2, which is mathsfpoly(n/varepsilon) for any constant τ.