Stabilizer bootstrapping: A recipe for efficient agnostic tomography and magic estimation

We study the task of agnostic tomography: given copies of an unknown n-qubit state which has fidelity with some state in a given class C, find a state which has fidelity - with. We give a new framework, stabilizer bootstrapping, for designing computationally efficient protocols for this task, and use this to get new agnostic tomography protocols for the following classes: Stabilizer states: We give a protocol that runs in time poly (n, 1/) (1/) ^O ( (1/) ), answering an open question posed by Grewal, Iyer, Kretschmer, Liang 40 and Anshu and Arunachalam 6. Previous protocols ran in time exp ( (n) ) or required >² (/8). States with stabilizer dimension n - t: We give a protocol that runs in time n³ (2ᵗ/) ^O ( (1/) ), extending recent work on learning quantum states prepared by circuits with few non-Clifford gates, which only applied in the realizable setting where = 1 30, 37, 46, 61. Discrete product states: If C = K^ n for some -separated discrete set K of single-qubit states, we give a protocol that runs in time (n/) ^O ( (1 + (1/) ) /) /². This strictly generalizes a prior guarantee which applied to stabilizer product states 39. For stabilizer product states, we give a further improved protocol that runs in time (n²/²) (1/) ^O ( (1/) ). As a corollary, we give the first protocol for estimating stabilizer fidelity, a standard measure of magic for quantum states, to error in n³ quasipoly (1/) time.