arXiv:2404.03813v5 Announce Type: replace-cross
Abstract: We define a quantum learning task called agnostic tomography, where given copies of an arbitrary state $rho$ and a class of quantum states $mathcal{C}$, the goal is to output a succinct description of a state that approximates $rho$ 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 $rho$.
We give an efficient agnostic tomography algorithm for the class $mathcal{C}$ of $n$-qubit stabilizer product states. Assuming $rho$ has fidelity at least $tau$ with a stabilizer product state, the algorithm runs in time $n^{O(log(2/tau))} / varepsilon^2$, which is $mathsf{poly}(n/varepsilon)$ for any constant $tau$.