Stabilizer Bootstrapping: A Recipe for Efficient Agnostic Tomography and Magic Estimation

We study the task of agnostic tomography: given copies of an unknown -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( , answering an open question posed by Grewal, Iyer, Kretschmer, Liang [43] and Anshu and Arunachalam [6]. Previous protocols ran in time exp(Θ( )) or required > cos 2 ( /8). • States with stabilizer dimension -: We give a protocol that runs in time 3 • (2 / ) (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 [33, 40, 49, 66] . • Discrete product states: If C = K ⊗ for some -separated discrete set K of single-qubit states, we give a protocol that runs in time ( / ) ( (1+log(1/ ) )/ ) / 2 . This strictly generalizes a prior guarantee which applied to stabilizer product states [42] . For stabilizer product states, we give a further improved protocol that runs in time ( 2 / 2 ) • (1/ ) (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 3 quasipoly(1/ ) time.