Polynomial-Time Tolerant Testing Stabilizer States

We consider the following task: suppose an algorithm is given copies of an unknown n-qubit quantum state |ψ⟩ promised (i) |ψ⟩ is ε 1 -close to a stabilizer state in fidelity or (ii) |ψ⟩ is ε 2 -far from all stabilizer states, decide which is the case. We show that for every ε 1 > 0 and ε 2 ≤ ε C 1 , there is a poly(1/ε 1 )-sample and n • poly(1/ε 1 )-time algorithm that decides which is the case (where C > 1 is a universal constant). Our proof includes a new definition of Gowers norm for quantum states, an inverse theorem for the Gowers-3 norm of quantum states and new bounds on stabilizer covering for structured subsets of Paulis using results in additive combinatorics.