Agnostic Tomography of Stabilizer Product States

Abstract

We define a quantum learning task called agnostic tomography, where given copies of an arbitrary state $ρ$ and a class of quantum states $\mathcal{C}$, the goal is to output a succinct description of a state that approximates $ρ$ at least as well as any state in $\mathcal{C}$ (up to some small error $\varepsilon$). This task generalizes ordinary quantum tomography of states in $\mathcal{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 $\mathcal{C}$ of $n$-qubit stabilizer product states. Assuming $ρ$ has fidelity at least $τ$ with a stabilizer product state, the algorithm runs in time $n^{O(\log(2/τ))} / \varepsilon^2$, which is $\mathsf{poly}(n/\varepsilon)$ for any constant $τ$.