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(log(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 τ>cos²(π/8). States with stabilizer dimension $n - t$: We give a protocol that runs in time n³·(2ᵗ/τ)O(log(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 + log (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(log(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.