Tomography of quantum states with bounded extent

Abstract

We give a general framework for tomography of states that have bounded-extent with respect to a structured class of states. Let $\text{C}$ be a family of $n$-qubit states such that: $(i)$ $\text{C}$ is succinctly representable and $(ii)$ there is a weak agnostic learner of $\text{C}$. We give a tomography protocol for an unknown state $|\ddot{I}ˆ⟩$ that is promised to admit a decomposition of the form $|\ddot{I}ˆ⟩={\sum }_i{c}_i|\ddot{I}{•}_i⟩$, where $|\ddot{I}{•}_i⟩\in \text{C}$ with bounded ${\ell }_1$-norm of the coefficients (which we call extent). Our main contribution is to show that a weak agnostic learner for $\text{C}$ can be boosted into a tomography algorithm for states with bounded extent with respect to $\text{C}$. Our reduction is black-box and applies broadly across model classes. As an application, when $\text{C}$ is the class of stabilizer states, we obtain tomography algorithms for states with stabilizer extent $\hat{I}¾$ up to trace distance $\epsilon$, in time $\text{poly}(n,(\hat{I}¾/\epsilon {)}^{\log (\hat{I}¾/\epsilon )})$, which is improvable to $\text{poly}(n,\hat{I}¾,1/\epsilon )$ assuming the algorithmic polynomial Freiman-Ruzsa conjecture in the high-doubling regime. When the unknown state $|\ddot{I}ˆ⟩$ is arbitrary, we give an algorithmic decomposition result in the spirit of a weak regularity lemma for quantum states with respect to $\text{C}$ and show that the structure in $|\ddot{I}ˆ⟩$ that is explainable by $\text{C}$ can be efficiently learned. Our main conceptual message is that agnostic learning of a structured base class automatically yields learnability of its low-complexity linear span.

56 pages