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 and Anshu and Arunachalam. Previous protocols ran in time exp (Θ( n )) or required τ>cos 2 (π/8). States with stabilizer dimension n − t : We give a protocol that runs in time n 3 ·(2 t /τ) 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. 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/τ))/µ) /є 2 . This strictly generalizes a prior guarantee which applied to stabilizer product states. For stabilizer product states, we give a further improved protocol that runs in time ( n 2 /є 2 )· (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 3 quasipoly (1/є) time.

Authors

• Sitan Chen
• Weiyuan Gong
• Qi Ye 0005
• Zhihan Zhang 0006

Keywords

• Quantum learning
• agnostic tomography
• discrete product state
• magic estimation
• stabilizer dimension
• stabilizer product state
• stabilizer states