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 n^O (1 + (1/) ) / ². This runtime is quasipolynomial in all parameters, and polynomial if is a constant.