Agnostic Tomography of Stabilizer Product States
Sabee Grewal Vishnu Iyer William Kretschmer Daniel Liang
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(1 + \log(1/\tau))} / \varepsilon^2$. This runtime is quasipolynomial
in all parameters, and polynomial if $\tau$ is a constant.